Hieronder enkele lussen voor een aantal van uw algemene Collatz rijen an+b,
met:
a = 3, 5 en 7
b = 1 t/m 15
n = 1 tot 500 (n = startgetal van de lus = kleinste getal in de betreffende lus)
a, b, n alle 3 oneven
met het maximale aantal iteraties (=stappen) van het algoritme <=1000
de gevonden lussen:
kolom 3: L = lengte van de lus
kolom 4: (het aantal oneven getallen in de lus) : (het aantal even getallen in de lus)
kolom 5: de lus, uitgedrukt in pariteiten (1=oneven getal, 0=even getal)
Voorbeeld:
a=3, b=5, n=19 geeft:
19, 62, 31, 98, 49, 152, 76, 38, 19, ...
vertaald in pariteiten:
19->1, 62->0, 31->1, 98->0, 49->1, 152->0, 76->0, 38->0, 19->1, ...
en dit geeft:
10101000
(de laatste 19->1 vervalt want dat is het begin van de volgende lus)
Het aantal enen hierin is 3, het aantal tweeen hierin is 5, wat de verhouding 3:5 geeft (en luslengte L=8).
Merk op:
(1) Elk oneven getal levert een factor a in de rij (de extra term b verwaarlozend), elk even getal een factor ½.
Voor verhouding oneven : even = k : m komen we dus terug uit op het startgetal van de lus als
\(a^k\approx 2^m\).
Met in acht neming van b zal
\(a^k\) dus net iets kleiner zijn dan
\(2^m\).
In bovenstaand voorbeeld:
\(3^3 = 27 \approx 32 = 2^5\)
en in geval a=7, b=5, n=27 is k : m = 11 : 31 en is
\(7^{11} = 1977326743 \approx 2147483648 = 2^{31}\)
(2) Er zijn een aantal voor de hand liggende lussen:
- als a=3 en n=b: b->(3b+b)=4b->2b->b (voorbeeld: n=b=1: 1->4->2->1; voorbeeld 2: n=b=5: 5->20->10->5)
- als a=5 en n=b: b->(5b+b)=6b->3b->(5*(3b)+b)=16b->8b->4b->2b->b
- als a=7 en n=b: b->(7b+b)=8b->4b->2b->b
(3) Als er voor gegeven getallen (a, b) een lus is voor n, dus n->->->....->n in
\(S\) stappen van het algoritme,
dan is er voor
oneven h voor alle (a, hb) ook een lus (hn)->->->....->(hn) in
\(S\) stappen van het algoritme:
Bewijs:
- Als
\(n_i\) even is, dan geldt
\(n_i \rightarrow \frac{n_i}{2}\), maar dan is ook
\(hn_i\) even en geldt
\(hn_i \rightarrow \frac{hn_i}{2}\)
- Als
\(n_i\) oneven is, dan geldt
\(\small n_i \rightarrow an_i+b\), maar dan is ook
\(\small hn_i\) oneven en geldt
\(\small hn_i \rightarrow ahn_i+nh = h(an_i+b)\), waarbij
\(h(an_i+b) \text{ is even} \Leftrightarrow (an_i+b) \text{ is even}\)
ofwel
\(h(an_i+b) \text{ is oneven} \Leftrightarrow (an_i+b) \text{ is oneven}\)
De stappen van het algoritme voor elke
\(n_i\) corresponderen dus één op één met die van
\(hn_i\)
Bijkomstig gevolg: in deze situaties zijn de pariteitssequenties gelijk.
Voorbeeld:
(a=5, b=3): n=43->218->109->548->274->137->688->344->172->86->43, pariteitrij: 1010010000
h=
3: (a=5, b=
3*3=9): n=
3*43=129->654->327->1644->822->411->2064->1032->516->258->129, pariteitrij: 1010010000
h=
5: (a=5, b=
5*3=15): n=
5*43=215->1090->545->2740->1370->685->3440->1720->860->430->215, pariteitrij: 1010010000
Code: Selecteer alles
==== a=3 b=1..15 n<=500 it<=1000 ====
b=1 n=1 L=3 1:2 100
b=3 n=3 L=3 1:2 100
b=5 n=1 L=4 1:3 1000
b=5 n=5 L=3 1:2 100
b=5 n=19 L=8 3:5 10101000
b=5 n=23 L=8 3:5 10100100
b=5 n=187 L=44 17:27 10101010101001010100101001000100101010100000
b=5 n=347 L=44 17:27 10101010100010101010100100100001010010100100
b=7 n=5 L=6 2:4 101000
b=7 n=7 L=3 1:2 100
b=9 n=9 L=3 1:2 100
b=11 n=1 L=8 2:6 10100000
b=11 n=11 L=3 1:2 100
b=11 n=13 L=22 8:14 1010100100101010001000
b=13 n=1 L=5 1:4 10000
b=13 n=13 L=3 1:2 100
b=13 n=131 L=39 15:24 101010100010101010101001010010100100000
b=13 n=211 L=13 5:8 1010101010000
b=13 n=227 L=13 5:8 1010101001000
b=13 n=251 L=13 5:8 1010100101000
b=13 n=259 L=13 5:8 1010101000100
b=13 n=283 L=13 5:8 1010100100100
b=13 n=287 L=13 5:8 1010010101000
b=13 n=319 L=13 5:8 1010010100100
b=15 n=3 L=4 1:3 1000
b=15 n=15 L=3 1:2 100
b=15 n=57 L=8 3:5 10101000
b=15 n=69 L=8 3:5 10100100
Code: Selecteer alles
==== a=5 b=1..15 n<=500 it<=1000 ====
b=1 n=1 L=7 2:5 1010000
b=1 n=13 L=10 3:7 1010100000
b=1 n=17 L=10 3:7 1010001000
b=3 n=1 L=4 1:3 1000
b=3 n=3 L=7 2:5 1010000
b=3 n=39 L=10 3:7 1010100000
b=3 n=43 L=10 3:7 1010010000
b=3 n=51 L=10 3:7 1010001000
b=3 n=53 L=10 3:7 1001010000
b=3 n=61 L=10 3:7 1001001000
b=5 n=5 L=7 2:5 1010000
b=5 n=65 L=10 3:7 1010100000
b=5 n=85 L=10 3:7 1010001000
b=7 n=1 L=49 14:35 1001010101001010000010010000100101000101000000000
b=7 n=7 L=7 2:5 1010000
b=7 n=9 L=7 2:5 1001000
b=7 n=57 L=60 18:42 100100100010101000101001001010010010001000001001000001010000
b=7 n=91 L=10 3:7 1010100000
b=7 n=119 L=10 3:7 1010001000
b=9 n=1 L=12 3:9 101001000000
b=9 n=3 L=4 1:3 1000
b=9 n=9 L=7 2:5 1010000
b=9 n=29 L=90 27:63 101010101001010001000000100101001010001010000010001010100100100000001010010100000010010000
b=9 n=89 L=30 9:21 101000100101010000100100010000
b=9 n=117 L=10 3:7 1010100000
b=9 n=129 L=10 3:7 1010010000
b=9 n=153 L=10 3:7 1010001000
b=9 n=159 L=10 3:7 1001010000
b=9 n=183 L=10 3:7 1001001000
b=11 n=1 L=5 1:4 10000
b=11 n=11 L=7 2:5 1010000
b=11 n=141 L=20 6:14 10010100100010010000
b=11 n=143 L=10 3:7 1010100000
b=11 n=187 L=10 3:7 1010001000
b=13 n=3 L=8 2:6 10010000
b=13 n=13 L=7 2:5 1010000
b=13 n=53 L=60 18:42 101001010101010000101001000100101010000001000000100010010000
b=13 n=169 L=10 3:7 1010100000
b=13 n=221 L=10 3:7 1010001000
b=15 n=5 L=4 1:3 1000
b=15 n=15 L=7 2:5 1010000
b=15 n=195 L=10 3:7 1010100000
b=15 n=215 L=10 3:7 1010010000
b=15 n=255 L=10 3:7 1010001000
b=15 n=265 L=10 3:7 1001010000
b=15 n=305 L=10 3:7 1001001000
Code: Selecteer alles
==== a=7 b=1..15 n<=500 it<=1000 ====
b=1 n=1 L=4 1:3 1000
b=3 n=3 L=4 1:3 1000
b=5 n=3 L=8 2:6 10100000
b=5 n=5 L=4 1:3 1000
b=5 n=27 L=42 11:31 101001010010000100000100010010000100010000
b=7 n=7 L=4 1:3 1000
b=9 n=1 L=5 1:4 10000
b=9 n=9 L=4 1:3 1000
b=11 n=11 L=4 1:3 1000
b=11 n=23 L=46 12:34 1001000100100100101010100010001000000000010000
b=13 n=13 L=4 1:3 1000
b=15 n=9 L=8 2:6 10100000
b=15 n=11 L=8 2:6 10010000
b=15 n=15 L=4 1:3 1000
b=15 n=81 L=42 11:31 101001010010000100000100010010000100010000
