Jak długo trwa rekurencja Collatz?

19

Mam następujący kod Python.

def collatz(n):
    if n <= 1:
        return True
    elif (n%2==0):
        return collatz(n/2)
    else:
        return collatz(3*n+1)

Jaki jest czas działania tego algorytmu?

Próbować:

Jeśli oznacza czas działania funkcji . Więc myślę, że mam { T ( n ) = 1  dla  n 1 T ( n ) = T ( n / 2 )  dla  n  parzystych T ( n ) = T ( 3 n + 1 )  dla  n  nieparzystychT(n)collatz(n)

{T(n)=1 for n1T(n)=T(n/2) for n evenT(n)=T(3n+1) for n odd

Myślę, że będzie lg n, jeśli n jest parzyste, ale jak ogólnie obliczyć nawrót?T(n)lgnn

9bi7
źródło
4
To powinno być i tak dalej. +1 jest ważne, w przeciwnym razie maszT(n)=1, dla wszystkichn,dla których sekwencja się kończy. T(n)=T(n2)+1T(n)=1n
user253751,
2
54 jest parzysty, T (54) = 112! =
Lg
Czy zakłada się, że użytkownik wprowadzi tylko liczbę całkowitą?
Dean MacGregor,
@DeanMacGregor Tak. W rzeczywistości przyjmuje się dodatnią liczbę całkowitą.
duskwuff
przydałoby się więcej szczegółów bkg. skąd masz kod, jak go wprowadzono? jest to półsławny otwarty problem teorii liczb nierozwiązany przez ~ pół wieku, na którym napisano całą książkę Lagariasa. z CS pov dowodzącego, że jest ona w dowolnej klasie złożoności w czasie lub przestrzeni jest równoważna z dowodem. wiele innych referencji tutaj . również świetny temat na czacie informatyki dla wszystkich zainteresowanych. istnieje także collatzznacznik na MathOverflow itp. Ostatnie badania pokazują, że problem ma wewnętrzne cechy fraktali, co utrudnia.
dniu

Odpowiedzi:

29


Zło
źródło
Dzięki. Ale moja rekurencja jest prawdziwa, prawda? Jeśli tak, to nadal nie możemy znaleźć rozwiązania dla tej rekurencji?
9bi7
T(n)
T(n)=2T(n/2)+O(n)
7
„ponieważ jest to nierozwiązane, nie ma górnej granicy” - tutaj musimy zachować ostrożność. Nie znamy rozwiązania tego nawrotu, końca historii.
Raphael
7
13

Funkcja złożoności czasowej to

{T(n)=O(1) for n1T(n)=T(n/2)+O(1) for n evenT(n)=T(3n+1)+O(1) for n odd

które można przepisać w następujący sposób, jeśli interesuje Cię asymptotyczna złożoność czasu.

{T(n)=1 for n1T(n)=T(n/2)+1 for n evenT(n)=T(3n+1)+1 for n odd

M,1nHaltnn

Hipoteza Collatza jest bardzo znaną hipotezą, którą Collatz zaproponował w 1937 r. Wielu wybitnych matematyków spędzało (czytało zmarnowane) niezliczone godziny na próbach rozwiązania tej hipotezy, ale bezskutecznie. Nawet Paul Erdős powiedział o przypuszczeniu Collatza: „Matematyka nie jest jeszcze gotowa na takie problemy”.

Shreesh
źródło
1
„zmarnowany” jest subiektywnym osądem. zobacz analizę ekspercką Lagarias, aby dowiedzieć się, dlaczego praca / częściowe wyniki przypuszczenia można uznać za „nie zmarnowane”. również cytat Erdosa ma prawdopodobnie kilka dziesięcioleci i od tego czasu matematyka znacznie się rozwinęła i nadal ... i prawdopodobnie nie podjęto prób wszystkich nowych technik matematycznych przeciwko temu problemowi.
vzn
To był język w komentarzu na policzku. (Aby być uczciwym, umieściłem to w nawiasach, prawda). Dopóki problem nie zostanie rozwiązany, wszystkie wysiłki wydają się marnotrawstwem, ale po jego rozwiązaniu widać, że nawet awarie doprowadziły do ​​rozwiązania. I nie zgadzam się z tobą, że matematyka znacznie się rozwinęła; technologia znacznie się rozwinęła, ale fizyka, matematyka, a nawet informatyka postępują powoli i tak właśnie powinno być (mogę to powiedzieć, ponieważ ja, który nauczyłem się swoich lin 30 lat temu, nadal nie czuję się przestarzały).
Shreesh
3x+1
Lagarias napisał / skompilował / zredagował całą książkę na ten temat i brzmi „przepraszająco” na temat studiowania problemu? lol! wręcz przeciwnie . jakkolwiek się zgodził / przyznał, że ma pozycję obronną, ponieważ wielu innych matematyków nie uważa problemu za znaczący lub wart poważnego ataku / wysiłku (i zauważ, że Gauss czuł się dokładnie tak samo w przypadku Fermats Last Thm!). ale istnieją masowe inne przypadki najlepszych matematyków, którzy traktują to całkowicie poważnie, np. Tao .
vzn
2

noddn3n+1

T(n)=2T(n/2)+nT(0)T(1)

3n+1

Sorrop
źródło
0

Masz T (n) = T (n / 2) + 1, jeśli n jest parzyste. Ale wtedy n / 2 prawdopodobnie nie jest nawet, więc utkniesz tam.

To, co się dzieje, polega na tym, że te małe, miłe zasady, których się nauczyłeś, stają przed prawdziwym problemem i nie działają. Uderzają w ścianę z cegły, twarzą w twarz, a to boli. Zrób sobie przysługę i ręcznie wykonaj rekurencję dla T (7), a następnie powiesz, czy nadal uważasz, że jest to związane lg n.

Jeśli uważasz, że nie ma to związku z pierwotnym pytaniem, ponieważ 7 nie jest parzyste: ilekroć n jest nieparzyste, T (n) = T (3n + 1), a 3n + 1 jest parzyste, więc jeśli T (n) było log n, jeśli n jest parzyste, będzie to log (3n + 1) + 1, gdy n> 1 jest nieparzysty.

gnasher729
źródło