Conjectura de Collatz

Conjectura de Collatz

Grafo dirigit mostrant cóm funciona la Conjectura de Collatz, ometent els número par. En la conjectura es hipotetiza que tot número finalment termina en 1.

La conjectura de Collatz, coneguda també com a conjectura 3n+1 o conjectura d'Ulam (entre atres noms), va ser enunciada pel matemàtic Lothar Collatz en 1937, i encara no ha segut resolta.

Enunciat

Temps d'òrbita (número de passos o iteraciones) necessari per a alcançar l'unitat per a números compresos entre 1 i 13000.

Cota superior per a valors entre 1 i 1300. La llínea horisontal superior correspon a la cota 9232. Esta cota és un valor 'preferit' per a moltes seqüències, com les que comencen en 27, 31, 41, 47, 54, 55, 62, 63, etc.

Siga la següent operació, aplicable a qualsevol número entero positiu:

• Si el número és parell, es dividix entre 2.
• Si el número és impar, es multiplica per 3 i se suma 1.

Formalment, açò equival a una funció $f:\mathbb{N}\mapsto \mathbb{N}$:

Ara, es forma una successió per mig de l'aplicació d'esta operació repetidament, començant per qualsevol sancer positiu, i prenent el resultat de cada pas com l'entrada del següent.

En notació:

$a_i=\{\begin{array}{cc}n& \text{para }i=0\\ f(a_{i-1})& \text{para }i>0\end{array}$

(açò és: $a_i$ és el valor de $f$ aplicat a $n$ recursivamente $i$ voltes; $a_i=f^i(n)$).

La conjectura diu que sempre alcançarem l'1 independentment del número en el que comencem.

Eixemples

Donat un número qualsevol, podem considerar el seu òrbita, és dir, les imàgens successives al iterar la funció. Per eixemple, si n=13:

Si observem este eixemple, l'òrbita de 13 és periòdica, és dir, es repetix indefinidament a partir d'un moment donat, que correspon en el cicle 4, 2, 1:

13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

• Escomençant en n = 6, la successió té 8 passos, i aplega a la següent successió: 6, 3, 10, 5, 16, 8, 4, 2, 1. 3 dels passos són impars: 3, 5, 1.
• Escomençant en n = 11, la successió té 14 passos: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. 4 són impars (ademés de l'11): 17, 13, 11, 1.
• Escomençant en n = 27, la successió té 111 passos, aplegant fins a 9232 abans de descendir a 1: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1. Passos impars: 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1. Total: 41. Per això molts matemàtics elegixen treballar només en els número impar.
• Escomençant en n = 1002, la successió té 111 passos, aplegant fins a 9232 abans de descendir a 1. Este cas és peculiar, ya que presenta algunes semblances en el número 27; com lo és que els prenen 111 passos aplegar a 1, en el pas 77 apleguen al seu punt màxim, el qual és 9232 per a abdós successions.
• Escomençant en n = 75128138247, la successió té 1228 passos per a aplegar a 1. 461 dels passos són impars.
• Escomençant en n = 1424652103065, la successió té 1240 passos per a aplegar a 1.
• Escomençant en n = 40523437598309, la successió té 1250 passos per a aplegar a 1.
• Escomençant en n = 32018518596193, la successió té 1260 passos per a aplegar a 1.
• Escomençant en n = 151791495567137, la successió té 1270 passos per a aplegar a 1.
• Escomençant en n = 719604127133093, la successió té 1280 passos per a aplegar a 1.
• Escomençant en n = 1705728301352515, la successió té 1289 passos per a aplegar a 1.
• Escomençant en n = 16172831301712733, la successió té 1300 passos per a aplegar a 1.