Close Print

Collatz Conjecture

Comments: Komentarze są wyłączone
BOINC fraktal CollatzConjecture

Projekt można liczyć na kartach graficznych nVidii i ATI oraz CPU.

Problem Collatza

Problem Collatza (znany też jako problem 3x+1, problem Ulama) to nie rozstrzygnięty dotychczas (i nie wiadomo, czy w ogóle rozstrzygalny) problem o wyjątkowo prostym – jak wiele innych problemów teorii liczb – sformułowaniu. Nazwa pochodzi od nazwiska niemieckiego matematyka Lothara Collatza (1937). Zagadnienie to było również rozpatrywane przez polskiego matematyka Stanisława Ulama.

Weźmy dowolną liczbę naturalną c0 (większą od 0). Jeśli jest ona parzysta, to za c1 przyjmijmy c0/2, w przeciwnym wypadku niech c1=3c0 + 1. Następnie, z liczbą c1 postępujemy podobnie jak z c0 i kontynuujemy ten proces. Otrzymamy w ten sposób ciąg liczb naturalnych określony rekurencyjnie przez formułę

BOINC wzór CC

lub

BOINC CC wzór

Hipoteza Collatza stwierdza, że niezależnie od jakiej liczby c0 wystartujemy, w końcu dojdziemy do liczby 1.

Zaczynając od n = 11 mamy,
11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Zaczynając od n = 27 mamy,
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

dla n = 27 cały proces zajmuje aż 111 kroków z maksymalną wartością 9232.
Wykazano prawdziwość hipotezy Collatza dla liczb c0 aż do 3×253 (prawie 2.70216 × 1016). Granicę tę w lutym 2004r. przesunięto do 258 (ponad 2.8823 × 1017), jednak dla ogólnego przypadku problem nadal pozostaje nierozstrzygnięty.

Są dwie możliwości zaprzeczenia hipotezie:

dla jakiejś liczby początkowej otrzymany ciąg wpada w cykl inny niż (…, 8, 4, 2, 1, …);
dla jakiejś liczby początkowej otrzymany ciąg jest rozbieżny do nieskończoności,
przy czym możliwości te nie wykluczają się.

Paul Erdős wypowiedział o problemie Collatza słynne zdanie: „mathematics is not yet ready for such problems” – „matematyka nie jest jeszcze gotowa na takie problemy”. Niewątpliwie świadczy to o złożoności ewentualnego rozwiązania, z drugiej strony kontrast pomiędzy ową złożonością a prostotą sformułowania jest intrygujący.

Źródło

Strona projektu Strona drużyny w projekcie


Welcome , today is niedziela, 17 grudnia 2017