Collatzen aierua

Zenbait zenbakik osatzen duten segida sorta, zuhaitz motako grafikoan adierazia (ez dira pauso guztiak ageri).

Collatzen aierua matematikako aieru bat da, honela definitutako sekuentziei dagokiena: hasi edozein zenbaki oso positiborekin n. Beraz, termino bakoitza honela ateratzen da aurreko terminotik: aurreko terminoa bikoitia bada, hurrengo terminoa aurreko terminoaren erdia da. Aurreko terminoa bakoitia bada, hurrengo terminoa aurreko terminoa bider 3 gehi 1 da. Ustea zera da, n-ren balioa zeinahi dela ere, sekuentzia beti iritsiko da 1 zenbakira.

Lothar Collatz matematikariarengandik hartu du izena aieruak, 1937an sartu baitzuen ideia, doktoretza jaso eta bi urtera. Izen hauek ere hartzen ditu aieruak: 3n + 1 arazoa, 3n + 1 aierua, Ulamen aierua (Stanisاaw Ulamen arabera), Kakutaniren arazoa (Shizuo Kakutaniren arabera), Thwaitesen aierua (Sir Bryan Thwaitesen arabera), Hasseren algoritmoa (Helmut Hasseren arabera), edo Sirakusako arazoa. Parte hartzen duten zenbakien sekuentziari, batzuetan, kazkabar-sekuentzia edo txingor-zenbakiak esaten zaio (izan ere, balioek, oro har, jaitsiera eta igoera ugari izaten dituzte, hala nola hodei bateko txingorra), edo zenbaki zoragarriak.

Problemaren definizioa

Zenbaki oso positibo batentzat honako eragiketa definitzen da, lehenik:

• Zenbakia bikoitia bada, zati bi egin behar da.
• Zenbakia bakoitia bada, bider hiru egin eta bat gehitu behar da.

Zenbakiari n deituz gero, eta eragiketa f(n) funtzio gisa definituz:

$f(n)={\begin{cases}{\frac {n}{2}}&{\text{baldin }}n\equiv 0{\pmod {2}}\\[4px]3n+1&{\text{baldin }}n\equiv 1{\pmod {2}}.\end{cases}}$

Azkenik, eragiketa hori behin eta berriz aplikatzen den segida definitzen da. Honela, a_i zenbaki sorta lortzen da, aldiro a_i-1 balioari eragiketa aplikatuz lortzen diren zenbakiz osatua.

$a_{i}={\begin{cases}n&{\text{non }}i=0\\f(a_{i-1})&{\text{non }}i>0\end{cases}}$

Collatz aieruak dioenez, azkenean segidak a_i = 1 balioa hartuko luke beti, hasierako zenbakia (n) edozein izanik ere. Ohar bedi n = 1 hasierako baliorako sekuentzia itxia dela, hots 1, 4, 2, 1 zikloa betetzen duela etengabe. Zenbaki batetik abiatuz 1 zenbakira heltzeko segidari zikloa edo orbita deitzen zaio.

Collatz aierua zuzena ez balitz, bi aukera leudeke: edo hasierako balioak 1 balioa sekula hartzen ez duen segida itxia sortzea, edo segida etengabe haztea. Oraingoz, ez da horrelakorik aurkitu, ez denik frogatu ez bada ere.

Azkenik, n bakoitia denean 3n+1 beti bikoitia denez, honela ere defini daiteke funtzioa:

$$f(n)={\begin{cases}{\frac {n}{2}}&{\text{baldin }}n\equiv 0{\pmod {2}},\\[4px]{\frac {3n+1}{2}}&{\text{baldin }}n\equiv 1{\pmod {2}}.\end{cases}}$$

• 
  1000rainoko zenbakien Collatz segidak
• 
  20 pauso baino gutxiago dituzten Collatz segiden irudikapena

Gelditze-unea

1etitk 9999rako zenbakien guztizko gelditze denborak.

Hasierako n balioarentzat, a_i < a₀ gertatzen i pausoari n-ren gelditze-unea deritzo. Era berean, a_k = 1 gertatzen den pausoari n-ren erabateko gelditze-unea deritzo. Collatzen aieruaren interpretazio bat zera da, edozein zenbakiren erabateko gelditze-unea finitua dela.

Zenbakien gelditze denbora aurrikustea zaila da, ez baita batere erregularra. Oraingoz, 5,7x10¹⁸ baliorainoko zenbaki guztiak frogatu dira, eta guztiek dituzte erabateko gelditze-une finituak.

Aldaerak

3n + 1 formularen ordez besteren batzuk ere erabil daitezke, 3q + 1 itxura errespetatuz, antzeko segidak sortzen dituztenak. Adibidez, 5n + 1 formulak antzeko zikloak sortzen ditu, baina frogatua da kasu horretan 1 zenbakian bukatzen ez diren beste ziklo itxiak badaudela. Segida infinituak ere sor ditzakeela uste da, baina hori ez da frogatua.

Aldaera horiek beste aieru baten sorburu dira, 3q + 1 segidek q > 3 balio bakoitientzat 1 zenbakia barne hartzen ez duten zikloak dituztela dioena. Jakina, aieru hori ere ez da frogatua izan.

Datu enpirikoak

Adibidez, n = 12rekin hasita eta f funtzioa "lasterbiderik" gabe aplikatuta, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1 sekuentzia lortzen da.

n = 19 zenbakiak denbora gehiago behar du 1 lortzeko:19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

n = 27rako sekuentziak, jarraian zerrendatua eta grafikatua, 111 urrats hartzen ditu (41 urrats zenbaki bakoitietan zehar, letra lodiz), eta 9232ra igotzen da 1era jaitsi aurretik.

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 (A008884 sekuentzia OEIS-ean).

Guztizko geldialdi-denbora edozein hasierako balio txikiagokoa baino handiagoa duten zenbakiek sekuentzia bat osatzen dute, eta honela hasten da:

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... (A006877 sekuentzia OEIS-ean).

Hasierako edozein balio txikiago baino ibilbide-puntu handiagoa duten hasierako balioak honako hauek dira:

1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... (A006884 sekuentzia OEIS-ean).

Zenbat urrats egin behar dira 1era iristeko?

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... (A006577 sekuentzia OEIS-ean).

Gelditze-denbora osoaren hasierako balioa,

Zenbakiak 250, 1000, 4000, 20000, 100000, 500000 arte gelditzeko denbora guztira

10 baino gutxiago 9 da, 19 urrats dituena,

100 baino gutxiago 97 da, 118 urrats dituena,

1000 baino gutxiago 871 da, 178 urrats dituena,

104 baino gutxiago 6171 da, 261 urrats ditu,

105etik behera 77031 da, 350 urrats dituena,

106 baino gutxiago 837799 da, 524 urrats dituena,

107 baino gutxiago 8400511 da, 685 urrats dituena,

108tik beherakoa 63728127 da, 949 urrats dituena,

109 baino gutxiago 670617279 da, 986 urrats dituena,

1010 baino gutxiago 9780657630 da, 1132 pasabide dituena,

1011 baino gutxiago 75128138247 da, 1228 urrats dituena,

1012 baino gutxiago 989345275647 da, 1348 urrats dituena,

Adierazitako pasabideen zenbaketa duten zenbaki baxuenak dira, baina ez derrigorrez emandako mugaren azpitik dauden bakarrak. Adibidez, 9780657631k 1132 urrats ditu, 9780657630ek bezala.

Guztizko gelditze-denbora txikiena duten hasierako balioak, digitu kopuruari dagokionez (2. oinarrian), biren potentziak dira; izan ere, 2ⁿ erdira n aldiz murrizten da 1era iristeko, eta inoiz ez da handitzen.

Kanpo estekak

• Datuak: Q837314
• Multimedia: Collatz conjecture / Q837314