Konjekto de Collatz


La konjekto de Collatz (la konjekto de “\({\displaystyle 3n+1}\)” aŭ la sirakuza problemo) estas unu el ĝis nun ne solvitaj matematikaj problemoj. La simpleco de ĝia formulado faris ĝin vaste fama. La problemo estas nomata pro la nomo de la germana matematikisto Lothar Collatz, kiu formulis ĝin en 1937.

Enhavo

Formulado


Por iu ajn natura nombro \({\displaystyle n}\) oni konsideru la sinsekvon, konstruitan laŭ du jenaj reguloj:

Al la rezulto oni ree apliku la samajn regulojn k.t.p.

Uzante esprimojn de modula aritmetiko eblas difini tian funkcion:

\({\displaystyle f(n)={\begin{cases}n/2&{\text{se }}n\equiv 0{\pmod {2}}\\3n+1&{\text{se }}n\equiv 1{\pmod {2}}.\end{cases}}}\)

Do la sinsekvon ni difinu tiel: por iu ajn antaŭe elektita natura \({\displaystyle n}\) kaj ĉiu natura \({\displaystyle i\eqslantgtr 1}\)

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

En la konjekto de Collatz oni asertas, ke por iu ajn \({\displaystyle n}\) iu membro de la sinsekvo nepre estas 1 (unu). Do:

\({\displaystyle \forall n\in \mathbb {N} >0~\exists i\in \mathbb {N} :a_{i}=1}\).

Evidente, ke post 1 estas senfine ripetiĝanta ciklo el la nombroj 4, 2, 1.

Por certa komenca \({\displaystyle n}\) la plej malgrandan \({\displaystyle i}\), por kiu \({\displaystyle a_{i}=1}\), ni nomu la tempo de plena halto de \({\displaystyle n}\) (angle the total stopping time of \({\displaystyle n}\))[1], kaj la plej grandan \({\displaystyle a_{i}}\) dum la vojo al la nombro 1 ni nomu la maksimuma trajektoria punkto (angle the maximum trajectory point). Laŭ la konjekto de Collatz por ĉiu \({\displaystyle n}\) ekzistas certa finia tempo de plena halto.

Se la konjekto de Collatz estus erara, tio eblus, se por iu \({\displaystyle n}\) la sinsekvo formus alian ciklon, kiu ne enhavus la nombron 1; aŭ se por iu \({\displaystyle n}\) la sinsekvo kreskus senfine, ne farante iun ciklon.

Sinsekvojn, konstruitajn laŭ reguloj de Collatz, oni ofte nomas hajlera sinsekvo aŭ hajleraj nombroj, ĉar valoro de sinsekvo konstante altiĝas kaj malaltiĝas kvazaŭ hajleroj en nubo.[2]

Ekzemploj


Ekzemple, por \({\displaystyle n=3}\) estas:

\({\displaystyle 3}\) estas nepara, do \({\displaystyle 3\times 3+1=10}\);
\({\displaystyle 10}\) estas para, do \({\displaystyle 10/2=5}\);
\({\displaystyle 5}\) estas nepara, do \({\displaystyle 3\times 5+1=16}\);
\({\displaystyle 16}\) estas para, do \({\displaystyle 16/2=8}\);
\({\displaystyle 8}\) estas para, do \({\displaystyle 8/2=4}\);
\({\displaystyle 4}\) estas para, do \({\displaystyle 4/2=2}\);
\({\displaystyle 2}\) estas para, do \({\displaystyle 2/2=1}\);
\({\displaystyle 1}\) estas nepara, do \({\displaystyle 3\times 1+1=4}\).

Evidente, ke poste sekvas la menciita senfina ciklo (2, 1, 4 2, 1 …).

Por \({\displaystyle n=19}\) estas:

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, …

Por \({\displaystyle n=27}\) estas:

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, … (la sinsekvo A008884 en OEIS.)

En la lasta okazo la tempo de plena halto estas 111 kaj la maksimuma trajektoria punkto estas 9232.

La nombroj, kiu havas tempon de plena halto pli grandan ol tiu de ĉiu ajn pli malgranda nombro formas la sinsekvon, kiu komencas tiel:

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 en OEIS. Alivorte, estas sinsekvojn de nombroj \({\displaystyle n}\), kiuj havas rekordajn tempojn de halto.

La nombroj, kiu havas maksimuman trajektorian punkton pli grandan ol tiu de ĉiu ajn pli malgranda nombro formas la sinsekvon, kiu komencas tiel:

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 en OEIS Alivorte, estas sinsekvojn de nombroj \({\displaystyle n}\), kiuj havas rekordajn maksimumajn trajektoriajn punktojn.

Tempoj de plena halto ankaŭ formas la sinsekvon, kiu komencas tiel:

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 en OEIS

Cikloj


Ĉiu ebla kontraŭdira al la konjekto ekzemplo devas aŭ esti senfine kreskanta sinsekvo, aŭ enhavi ciklon malsaman al la triviala (4; 2; 1) ciklo. Do, se oni pruvus neeblecon de ekzistado de ambaŭ tiaj okazoj, do oni pruvus la konjekton de Collatz. Tion oni ne faris, sed kelkaj specoj de cikloj estis eliminitaj.

Tipon de ciklo eblas difini, uzante “simpligitan” difinon de sinsekvo de Collatz: \({\displaystyle f(n)={\frac {3n+1}{2}}}\) por nepara \({\displaystyle n}\) kaj \({\displaystyle f(n)={\frac {n}{2}}}\) por para \({\displaystyle n}\). Ciklo estas sinsekvo \({\displaystyle (a_{0};a_{1};\ldots ;a_{q})}\), dum \({\displaystyle f(a_{0})=a_{1}}\), \({\displaystyle f(a_{1})=a_{2}}\), k.t.p., kaj finfine \({\displaystyle f(a_{q})=a_{0}}\) por ringigi ciklon. Por tiu ĉi difino la triviala ciklo estas (1; 2). Kvankam 4 estas membro de la triviala ciklo laŭ la originala difino, ĝi ne estas la membro de la triviala ciklo laŭ la simpligita difino.

k-ciklo estas ciklo, kiu konsistas el \({\displaystyle 2k}\) da kontinuaj subsinsekvoj: \({\displaystyle k}\) da kreskantaj sinsekvoj de neparaj nombbroj kaj \({\displaystyle k}\) da malkreskantaj sinsekvoj de paraj nombbroj. Ekzemple, la triviala ciklo estas 1-ciklo.[3]

Steiner (1977) pruvis, ke ne ekzistas iu ajn 1-ciklo, krom la triviala (1; 2).[4] Simons (2004), uzis la metodo de Steiner por pruvi neekzistadon de iu ajn 2-ciklo.[5]

Simons kaj de Weger ĝeneraligis la metodon ĝis 68-cikloj: ne ekzistas iu k-ciklo, se \({\displaystyle k\leqslant 68}\). Por pli grandaj \({\displaystyle k}\) tiu ĉi metodo donas supran limon por la elementoj de ciklo. Ekzemple, se ekzistas 75-ciklo do almenaŭ unu ĝia elemento estas malpli granda ol 2385×250. [3] Do per komputila serĉado oni povos elimini ciklojn kun pli granda \({\displaystyle k}\).

Certigantaj argumentoj


Kvankam la konjekto ne estis pruvita, plimulto da matematikistoj, kiu esploris la problemon, rigardas la konjekton vera, ĉar eksperimentaj atestoj kaj nestrikta rezonado certigas ĝin.

Eksperimentaj atestoj

La konjekto estis kontrolita per komputiloj por ĉiuj \({\displaystyle n}\) ĝis 268 (2020).[6] Ĉiuj kontrolitaj sinsekvoj finfine atingas la ciklon (4; 2; 1).

Tiu ĉi komputila atesto ne povas esti pruvo de vereco de konjekto. Iufoje kontraŭdiraj ekzemploj aperas nur ĉe tre grandaj nombroj, kiel tio estas por konjekto de Pólya, konjekto de Mertens kaj Nombro de Skewes. Oni ne povas kontroli ĉiujn naturajn nombrojn.

Rezonado pri probableco

Se oni konsideras nur neparajn nombrojn en sinsekvoj de Collatz do oni ekscias ke ĉiu nepara nombro estas meznombre 3/4 de la antaŭa.[7] Tio povas sugesti, ke ĉiu sinsekvo de Colatz devas finfine malkreski. Tio ne estas pruvo, ĉar tio implicas aserton, ke la sinsekvoj estas konstruitaj el hazardaj, neinterligitaj nombroj.

La projekto “Collatz Conjecture”


En la aŭgusto de la 2009 aperis la projekto de la volontula disa komputado “Collatz Conjecture”, kies celo estas kontroli la konjekton de Collatz por grandaj nombroj, uzante komputilojn de volontuloj. [8] La projekto uzas la platformon Boinc.

Referencoj


  1. Lagarias, Jeffrey C. (1985). “The 3x + 1 problem and its generalizations”. The American Mathematical Monthly. 92 (1): 3–23. JSTOR 2322189
  2. “Hailstone Number” . MathWorld. Wolfram Research.
  3. 3,0 3,1 Simons, J.; de Weger, B. (2005). “Theoretical and computational bounds for m-cycles of the 3n + 1 problem” (PDF). Acta Arithmetica. 117 (1): 51–70. COI:10.4064/aa117-1-3 .
  4. Steiner, R. P. (1977). “A theorem on the syracuse problem”.Proceedings of the 7th Manitoba Conference on Numerical Mathematics. pp. 553–9.
  5. Simons, John L. (2004). “On the nonexistence of 2-cycles for the 3x+1 problem” . "Math. Comp." 74: 1565–72. COI:10.1090/s0025-5718-04-01728-4 ; Mathematical Reviews 2137019 .
  6. Roosendaal, Eric. [“On the 3x+1 Problem”. ]
  7. Lagarias (1985) (la referenco 1), section “A heuristic argument” .
  8. La oficiala paĝaro de Collatz Conjecture







Kategorioj: Konjektoj | Aritmetiko | Nombroteorio | Entjeraj vicoj




Informoj kiel: 29.09.2021 03:48:03 CEST

Fonto: Wikipedia (Aŭtoroj [Historio])    Permesilo: CC-BY-SA-3.0

Ŝanĝoj: Ĉiuj bildoj kaj plej multaj desegnaj elementoj rilataj al tiuj estas forigitaj. Iuj Ikonoj estis anstataŭigitaj per FontAwesome-Ikonoj. Iuj ŝablonoj estis forigitaj (kiel "artikolo bezonas vastiĝon) aŭ atribuitaj (kiel" hatnotoj). CSS-klasoj estis aŭ forigitaj aŭ harmoniigitaj.
Vikipedio-ligoj, kiuj ne kondukas al artikolo aŭ kategorio (kiel "Redlinks", "ligoj al la redaktopaĝo", "ligoj al portaloj") estis forigitaj. Ĉiu ekstera ligo havas plian FontAwesome-Ikonon. Krom kelkaj malgrandaj ŝanĝoj de dezajno, rimedo-ujo, mapoj, navigado-skatoloj, parolitaj versioj kaj Geo-mikroformatoj estis forigitaj.

Bonvolu rimarki: Ĉar la donita enhavo estas aŭtomate prenita el Vikipedio en la donita tempo, mana kontrolado estis kaj ne eblas. Tial LinkFang.org ne garantias la ekzaktecon kaj aktualecon de la akirita enhavo. Se estas informo malĝusta tiutempe aŭ malĝusta ekrano, bonvolu senti vin libera. kontaktu nin: retpoŝto.
Vidu ankaŭ: Presaĵo & Privateca politiko.