Considerando l'equazione 3 si nota che sicuramente 3tn − 2d1+...+dtn ≤ 0,
se n ≥ 0, inoltre se considero i casi intermedi delle formule precedenti (vale anche nel caso di n non ciclico) mi accorgo che se dopo l cicli, con l ≤ t, ottengo un certo numero k allora avrò 3ln − 2d1+...+dlk ≤ 0 Allora avrò:
Ora voglio ottenere una minorazione di log2(n) − log2(k) per fare considero
il caso di una sola iterazione e noto che log2(n) − log2 3n + 1 2d1 = log2 n · 2 d1 3n + 1
Ma posso notare che
log2
n 3n + 1
è una funzione monotona crescente per n ≥ 0 da cui mi accorgo che per i nostri ni posso considerare n ≥ 1 e n → ∞, così ottengo che
d1− 2 ≤ log2
n · 2d1
3n + 1
< − log2(3) + d1
Quindi posso chiamare P = 3n+1
2d1 e posso utilizzare di nuovo la disuguaglianza
per ottenere d2− 2 ≤ log2 P · 2d2 3P + 1 < − log2(3) + d2
Iterando questo meccanismo nché non arrivo a k = n o k = 1, ora sommando le disuguaglianze e supponendo che impieghi t iterazioni a per avere k = 1 o k = n, quindi ottengo
−2t + (d1+ d2+ . . . + dt) ≤ log2(n) − log2(k) < − log2(3)t + (d1+ d2+ . . . + dt)
Ma se suppongo che k = n, allora ottengo
−2t + (d1+ d2 + . . . + dt) ≤ 0 < − log2(3)t + (d1+ d2+ . . . + dt)
−2t ≤ −(d1+ d2+ . . . + dt) < − log2(3)t
2t ≥ d1 + d2+ . . . + dt > log2(3)t
Mentre nell'altro caso ottengo semplicemente
−2t + (d1+ d2+ . . . + dt) ≤ log2(n) < − log2(3)t + (d1+ d2+ . . . + dt)
−2t ≤ log2(n) − (d1+ d2+ . . . + dt) < − log2(3)t
Ora consideriamo all'interno di un ciclo il numero dispari più grande N e il numero dispari più piccolo n, nel primo caso ho (utilizzando le formule precedenti)
2 − d1 ≥ log2(k1) − log2(N ) > log2(3) − d1 (A.10)
dove k1è il numero dispari ottenuto dopo una iterazione dispari e d1 iterazioni
pari; a questo punto sappiamo che − log2(N ) + log2(k1) < 0 perché ho preso
N ≥ k1 allora ho che d1 ≥ log2(3), inoltre continuando questo ragionamento
per
2 · 2 − (d1+ d2) ≥ log2(k2) − log2(N ) > log2(3) · 2 − (d1+ d2)
E anche in questo caso sapendo che log2(k2) − log2(N ) < 0 ottengo che
d1 + d2 ≥ log2(3) · 2. Iterando questo ragionamento arrivo al passo (t − 1)-
esimo dove ottengo:
2(t−1)−(d1+. . .+dt−1) ≥ log2(kt−1)−log2(N ) ≥ log2(3)·(t−1)−(d1+. . .+dt−1)
E con il ragionamento precedente ottengo d1 + . . . + dt−1 ≥ log2(3)(t − 1).
Ma utilizzando lo stesso ragionamento solo sull'ultimo passo ho che: 2 − dt≥ log2(N ) − log2(kt−1) > log2(3) − dt
Dove per la ciclicità ho considerato kt = N allora ho che 2(t) ≥ d1+. . .+dt>
log2(3)t. Ma per quanto detto in precedenza log2(N ) − log2(kt−1) > 0 allora
ho che 1 ≤ dt≤ 2, ma banalmente si osserva che nel caso di dt= 2, a partire
da kt−1, trovo sempre un numero ch'è minore di kt−1 e quindi per ottenerne
uno maggiore devo avere dt = 1. La condizione dt= 2, vale solo nel caso in
cui N = 1 e io abbia un 1-ciclo. Mentre se considero n ho che: 2 − b1 ≥ log2(g1) − log2(n) > log2(3) − b1
quindi ho che log2(g1) − log2(n) > 0quindi ho che b1 ≤ 2ma siccome g1 > n
n = g1 ma così avrei un 1−ciclo e per dimostrazioni precedenti si ha solo nel
caso di n = 1. Mentre continuando questo ragionamento si ha che 2 · 2 − (b1+ b2) ≥ log2(g2) − log2(n) > log2(3) · 2 − (b1+ b2)
quindi per le ipotesi fatte ottengo che b1+ b2 ≤ 4. Iterando il ragionamento
ho che b1+ . . . + bt≤ 2(t). Ma sapendo che
2 − bt≥ log2(n) − log2(gt−1) > log2(3) − bt
si nota che bt ≥ 2. Quindi riepilogando quello che so, si può riassumere nei
seguenti fatti: N n d1 ≥ log2(3) b1 = 1 d1+ d2 ≥ log2(3) · 2 b1+ b2 ≤ 4 ... ... d1+ . . . + dt≥ log2(3)t b1+ . . . + bt ≤ 2t dt= 1 bt≥ 2
Si nota che posso togliere l'uguaglianza da ogni disuguaglianza se suppongo che n > 1, inoltre posso notare che se considero n, questo sarà sicuramente del tipo 4k+3, siccome dopo la prima iterazione devo avere una sola divisione per 2, mentre N sarà del tipo 4k + 1. Si può notare che nel caso in cui consideri n, posso sostituire il 2 nelle disuguaglianze, con log2 3·n+1n e nel caso N posso sostituire log2 3·N +1N
al posto di log2(3). Inoltre guardando l'ultima
disuguaglianza posso notare che per avere qualche possibilità di trovare un elemento ciclico, devo almeno avere un intervallo [log2(3)t, log2 3·n+1n t] in
cui ci sia un numero naturare, siccome i coe cienti d1, . . . , dt sono naturali
e la loro somma è pari alla somma di b1, . . . , bt; al variare di n ottengo i
n intervallo t 2 [4.754887502163469, 5.422064766172813] 3 6 [7.924812503605781, 8.314825063612147] 5 32 [26.94436251225966, 27.198518317181172] 17 147 [45.96391252091353, 46.05867622209695] 29 387 [64.9834625295674, 65.03438848766487] 41 1193 [148.9864750677887, 149.02436117890073] 94 3343 [232.98948760601, 233.01063284467455] 147 6725 [316.99250014423126, 317.0068015993742] 200 12825 [400.99551268245256, 401.00499928679466] 253 27114 [484.99852522067386, 485.00395245345516] 306 99781 [1538.9985882002427, 1539.003267964075] 971 330750 [2592.9986511798115, 2593.0010298624998] 1636 583288 [3646.9987141593806, 3647.000611244148] 2301 860564 [4700.99877713895, 4701.0004345917605] 2966 1166400 [5754.998840118518, 5755.000337153539] 3631 1505449 [6808.998903098088, 6809.000275405664] 4296 1883432 [7862.998966077656, 7863.000232774032] 4961 2307463 [8916.999029057226, 8917.000201571758] 5626 2786502 [9970.999092036795, 9971.000177746158] 6291 3331998 [11024.999155016363, 11025.000158957164] 6956 3958809 [12078.999217995932, 12079.000143760763] 7621 4686582 [13132.9992809755, 13133.000131216371] 8286 5541847 [14186.99934395507, 14187.000120685458] 8951 6561321 [15240.99940693464, 15241.000111719299] 9616 7797317 [16294.999469914208, 16295.000103993314] 10281 9327011 [17348.999532893777, 17349.00009726678] 10946 11269200 [18402.999595873345, 18403.000091357553] 11611 13816735 [19456.999658852914, 19457.000086125205] 12276 17304876 [20510.999721832482, 20511.000081459755] 12941 22372510 [21564.99978481205, 21565.000077273777] 13606 30406457 [22618.999847791623, 22619.00007349698] 14271 45088848 [23672.999910771192, 23673.00007007217] 14936 80497518 [24726.99997375076, 24727.00006695233] 15601 285817612 [75234.99998423185, 75235.00006409844] 47468
La ricerca è stata eettuata con un codice in python, e gli n sono scelti in modo tale da essere i più piccoli tali che ci sia una variazione di t, inoltre facendo questa ricerca con n = 1, 3 · 1018 ottengo che t ≥ 6586818670 e l'in-
tervallo è [10439860590.9999999999854, 10439860591.000000002422]. Questa ricerca è utile perché trova il più piccolo t associato a un certo n, inoltre anche il valore intero contenuto nell'intervallo equivale al numero di iterazioni 'pari' associate a questo numero ciclico n. La ricerca è stata eettuata partendo dalla conoscenza di n, in quanto l'algoritmo di Collatz è stato provato per numeri superiori a 5·260 ≈ 5 · 1018. Inoltre questo t vale no a n = 2, 15·1020,
già per n = 2, 2·1020devo ricalcolare t e l'intervallo, i quali saranno maggiori
di quelli precedenti. Il codice utilizzato è il seguente:
from mpmath import * #libreria python per l'utilizzo di una precisione # arbitraria nell'aritmetica floating-point
mp.dps=25 # imposta la precisione a 25 cifre def finaltest():
kk=0 b=0 ppp=0
jj =130*10**16 #pongo un certo numero n
ttt=log(fdiv(jj,(3*jj+1)),2) #operazioni della libreria mpmath kkk1=log(3,2)
for i in range(ppp,10**10+1): #calcolo il t a partire da 0 a un # massimo posto in questo caso a 10^{10}
p=fmul(kkk1,i) k=-fmul(ttt,i)
if (int(p)!=int(k)): #controlla che la parte intera sia diversa if i>kk:
print(jj,p,k,i) break
Bibliogra a
[1] [AL1] Applegate, D., e Lagarias, J.C., Density Bounds for the 3x + 1 P roblem I. T ree − Search M ethod, Math. Comp. 65 (1995), 411-426. [2] [AL2] Applegate, D., e Lagarias, J.C., Density Bounds for the 3x + 1
P roblem II Krasikov Inequalities, Math. Comp. 65 (1995), 427-438. [3] [AL3] Applegate, D., e Lagarias, J.C., On the Distribution of 3x + 1
T rees,Experimental Math. 4 (1995), 193-209.
[4] [Ba] Baker, A., Linear forms in the logarithms of algebric numbers IV, Mathematika 15 (1968), 204-216.
[5] [Ber] Berndt, B.C., Ramanujan0s N otebooks, P art II, Springer, New
York, 1989.
[6] [Br] Brox, T., Collatz cycles with few descents, Acta Arithmetica 92 (2000), 181-188.
[7] [BS] Böhm, C., e Sontacchi, G., On the existence of cycles of given length in integer sequences like xn+1 = xn/2 if xn even, and xn+1 =
3xn+ 1 otherwise, Atti Accad. Naz. Lincei, VIII Ser. Rend., Cl. Sci.
Fis. Mat. Nat. LXIV (1978), 260-264. 115
[8] [Col1] Collatz, L., V erzweigungsdiagramme und Hypergraphen, In- ternational Series for Numerical Mathematics, vol. 38, Birkhäuser, 1977.
[9] [Col2] Collatz, L., About the motivation of the (3n + 1) − problem, J. Qufu Norm. Univ., Nat. Sci. 3 (1986), 9 − 11 (cinese)
[10] [Con] Conway, J.H., Unpredictable Iterations, Proc. 1972 Number Theory Conf. University of Colorado, Boulder, Colorado (1972), 49-52. [11] [Cra] Crandall, R.E., On the03x+10P roblem,Math. Comp. 32 (October
1978), 1281-1292.
[12] [Eve] Everett, C.J., Iteration of the Number − T heoretic F unction f (2n) = n, f (2n + 1) = 3n + 2, Adv. Math. 25 (1977), 42-45.
[13] [FMMT] Feix, M.R., Muriel, A.,Merlini, D., e Tartini, R., T he (3x+1)/2 P roblem : A Statistical Approach, in: Stochastic Processes, Physics and Geometry II, Locarno 1991 (Eds. S. Albeverio, U. Cattaneo, D. Merlini) World Scienti c (1995) 289-300.
[14] [Krs] Krasikov, I., How many numbers satisfy the 3x + 1 conjecture?, Int. J. Math. Math. Sci. 12 (1989), 791-796.
[15] [Lag1] Lagarias, J.C, T he 3x+1 P roblem and its Generalizations, Am. Math. Mon. 92 (1985), 1-23.
[16] [Lag2] Lagarias, J.C., T he set of rational cycles for the 3x+1 problem, Acta Arith. LVI (1991), 33-53.
[17] [Lag3] Lagarias, J.C., 3x + 1 P roblem Annotated Bibliography, september 22, 1997.
[18] [LaW] Lagarias, J.C., e Weiss, A., T he 3x+1 P roblem : T wo Stochastic M odels, Ann. Appl. Probab. 2 (1992), 229-261.
[19] [LMN] Laurent, M., Mignotte, M., e Nesterenko, Y., F ormes linaires en deux logarithmes et dterminants d0interpolation, J. Number Th.55 (1995) 285-321.
[20] [Ma] Matveev, E.M., An explicit lower bound for a homogeneous rational linear f orm in logarithms of algebric numbers, Part I: Iz- vestia: Mathematics (1998), v.62, no. 4, pp.723-772; Part II: Izvestia: Mathematics (2000), v.64, no.6, pp.125-180.
[21] [Ne] Nesterenko, Y., Linear F orms in Logarithms of Rational N umbers, in: F. Amoroso e U. Zannier(eds.), Springer Lecture Notes in Mathematics Vol. 1819, 2003, pp.53-106.
[22] [OS] Oliveira, T., Silva, Computational verification of the 3x + 1 conjecture,.
[23] [Rh] Rhin, G., Approximants de P ad et measures effectives d0irrationalit, Progress in Mathematics 71 (1987), 155-164.
[24] [Si] Simons, J.L., On the nonexistence of 2 − cycles for the 3x + 1 problem, Mathematics of computation 74 (2005), 1565-1572.
[25] [Ste1] Steiner, R.P., A T heorem on the Syracuse P roblem, Proc. 7th Manitoba Conf. Numerical Mathematics and Computing 1977 Winnipeg (1978), 553-559.
[26] [Ste2] Steiner, R.P., On the 0Qx + 10 P roblem, Q odd, Fibonacci Q. 19
(1981), 285-288.
[27] [Ste3] Steiner, R.P., On the 0Qx + 10 P roblem, Q odd, II, Fibonacci Q.
19 (1981), 293-296.
[28] [Ter1] Terras, R., A stopping time problem on the positive integers, Acta Arith. XXX (1976), 241-252.
[29] [dW] de Weger, B.M.M, Algorithms for Diophantine Equations, CWI Tract 65, Centre for Mathematics and Computer Science, Amsterdam, (1989).
[30] [Wir] Wirsching, G.J., T he Dynamical System Generated by the 3n+1 F unction, Springer (1998)
[31] [SiWe] Simons, J.,e de Weger, B., T heoretical and computational bounds f or m − cycles of the 3n + 1 problem, version 1.43, July 31, (2007)
[32] Jerey C. Lagarias http://www.cecm.sfu.ca/organics/papers/ lagarias/paper/html/node4.html
[33] Terry Tao http://terrytao.wordpress.com/2011/08/25/