[Algorytmy] Średnia długość ciągu Collatza

[matemix]

Niedawno uzyskałem pewien wzór na średnią (arytmetyczną) długość ciągu Collatza na przedziale od liczby 1 do \(\displaystyle{ n}\). Wydaje się, że rzeczywista średnia długość ciągu Collatza (na przedziale od 1 do \(\displaystyle{ n}\)) jest zbieżna do tego wzoru. Pracuję nad dowodem. Tymczasem czy ktoś mógłby sprawdzić czy ta zbieżność występuje również dla dużych \(\displaystyle{ n}\) metodami obliczeniowymi?

Nie za bardzo potrafię napisać program który coś takiego by sprawdził i dlatego sam przetestowałem tylko liczby do 1000, a chciałbym do 10 000, 100 000, 1 000 000 a nawet 1 000 000 000.

Definicja ciągu (bierzemy skróconą formułę!):

\(\displaystyle{ c_{n+1} = \begin{cases} 1,5 \cdot c_{n} +0,5 \ \ gdy \ c_{n} \ nieparzyste \\ \frac{c_{n}}{2} \ \ gdy \ c_{n} \ parzyste \end{cases}}\)

Przyjmujemy, że algorytm zatrzymuje się, gdy osiągnie wartość 1.

Przykłady:

Liczba - 1, długość ciągu 0

Liczba - 2, długość ciągu 1:

2, 1

Liczba - 3, długość ciągu 5:

3, 5, 8, 4, 2, 1

Liczba - 4, długość ciągu 2:

4, 2, 1

Średnia długość ciągu od liczby 1 do 4:

\(\displaystyle{ R(4)= \frac{0+1+5+2}{4}=2}\)

Mój wzór na średnią długość ciągu liczb od 1 do \(\displaystyle{ n}\) jest następujący:

\(\displaystyle{ D(n) = \frac {2}{ln(0,75)} \cdot \frac {n \cdot (ln(\frac {1}{n})+1)-1}{n}}\)

Dla małych \(\displaystyle{ n}\) uzyskujemy słabe dokładności, ale w miarę przyrostu n dokładność wzoru rośnie, dla \(\displaystyle{ n=1000}\), mamy:

- rzeczywista średnia: \(\displaystyle{ R(1000) = 39,89}\)
- szacowana ze wzoru: \(\displaystyle{ D(1000) = 41,08}\)



A zatem czy ktoś może sprawdzić czy ta zbieżność występuje również dla większych \(\displaystyle{ n}\)? Pożądany wykres jednych i drugich wartości Bardziej formalnie sugeruję następującą równość asymptotyczną:

\(\displaystyle{ \lim_{n\to\infty} \frac {R(n)}{D(n)} = 1}\)

Można także udowdnić równość:

\(\displaystyle{ \lim_{n\to\infty} \frac {D(n)}{\frac {2}{ln(0,75)} \cdot (1+ln(\frac {1}{n}))} = 1}\)

Wtedy możemy badać zbieżność tej średniej do nieco prostszego wzoru:

\(\displaystyle{ D_{1}(n) = \frac {2}{ln(0,75)} \cdot (1+ln(\frac {1}{n}))}\)

[PMichalak]

Obliczyłem Ci dla kilku wartości, myślę, że jeszcze kolejną dałoby się obliczyć w sensownym czasie.

Kod: Zaznacz cały

10 5
100 21.37
1000 39.889
10000 56.7644
100000 71.889
1000000 87.816
10000000 103.592
100000000 118.555
1000000000 133.881
10000000000 136.25
100000000000 135.222

[matemix]

Cóż, wyniki jednak różnią się nieco od moich, szczególnie dla potęg większych niż 7. Co jeszcze nie oznacza, że zbieżności do wzoru który zaproponowałem nie ma...

Przewidywania obliczone z mojego wzoru są następujące:

9,751
25,133
41,078
57,080
73,087
89,095
105,103
121,111
137,118
153,126
169,134

Co daje rosnące dokładności do potęgi 7:

0,51
0,85
0,97
0,99
0,98
0,99
0,99
0,98
0,98
0,89
0,80

Widać, że dla liczb większych od \(\displaystyle{ 10^{7}}\) zaczynamy mieć jakieś fluktuacje i to całkiem spore biorąc pod uwagę rzędy liczb. Być może w następnej kolejności dla potęg większych niż 11 zawrócą one znów i zbliżą się do mojego oszacowania, jakkolwiek myślałem, że na tym poziomie nie będzie już niejednorodności w długości średniej ciągu tego rzędu. Jednak może to być kwestia akurat pechowego dobrania przedziałów (jako potęgi 10) i być może akurat w tych przedziałach (\(\displaystyle{ 10^{10}}\) i \(\displaystyle{ 10^{11}}\)) napotykamy na swojego rodzaju "dziury" które być może zostaną nadrobione już w minimalnej ilości kolejnych liczb.

To dziwne, że średnia długość ciągu tak gwałtownie maleje i w końcu dla potęgi 11 jest mniejsza niż dla potęgi 10. Jesteś pewny, że to nie wynik np. zaokrągleń lub jakichś innych błędów?

Takim błędem może być właśnie taka "dziura" pechowo powtarzająca się w okolicach potęg 10, dlatego mam pytanie czy mógłbyś zrobić to samo oszacowanie dla przedziałów nieco przesuniętych od potęg 10 lub dla jakiś innych potęg np. liczby 9?

[PMichalak]

Tamte wyniki były chyba niepoprawne, te są ok:

Kod: Zaznacz cały

128 24.3281
256 30.2031
512 35.2402
1024 40.1094
2048 45.1279
4096 50.2371
8192 55.1813
16384 59.8675
32768 64.3882
65536 68.9971
131072 73.7365
262144 78.5309
524288 83.3451
1048576 88.1341
2097152 92.918
4194304 97.7098
8388608 102.502
16777216 107.304
33554432 112.113
67108864 116.924
134217728 121.741
268435456 126.559
536870912 131.377
1073741824 136.195
2147483648 141.013
4294967296 145.831

[matemix]

Te faktycznie wydają się już być poprawne. I potwierdzają mój wzór.