Conway's challenge sequence
2 отговора
114 прегледа
Conway's challenge sequence
Prez 1988 godina John Conway predlaga slednata redica (a(n)) kadeto n e estestweno chislo.
Dadeno e: a(1)=a(2)=1, a(n)=a(a(n-1))+a(n-a(n-1)) za n po-goliamo ili rawno na 3
Dokavete: 1. a(n)/n kloni kam 0.5
2. |(a(n)/n)-0.5|>1/20
3. |(a(n)/n) -0.5|>1/40
Niakoi move li da pomogne?
Dadeno e: a(1)=a(2)=1, a(n)=a(a(n-1))+a(n-a(n-1)) za n po-goliamo ili rawno na 3
Dokavete: 1. a(n)/n kloni kam 0.5
2. |(a(n)/n)-0.5|>1/20
3. |(a(n)/n) -0.5|>1/40
Niakoi move li da pomogne?
Re: Conway's challenge sequence
Доста сериозна ми се вижда задачата!
Поиграх си да построя зависимостта на a(n)/n от n за n до около 200000.
Зависимостта прилича смътно на траектория на подскачащо топче. a(n)/n достига минимална стойност 0.5 само при n=степен на 2 (2,4,8,16...). Така всеки "скок" е 2 пъти по-дълъг от предния. Максимумите наистина намаляват при всеки следващ скок:
a(1)/1=1.000000
a(3)/3=0.666667
a(6)/6=0.666667
a(11)/11=0.636364
a(23)/23=0.608696
a(44)/44=0.590909
a(92)/92=0.576087
a(178)/178=0.567416
a(370)/370=0.559459
a(719)/719=0.554937
a(1487)/1487=0.550101
a(2897)/2897=0.547463
a(5969)/5969=0.544145
a(11651)/11651=0.542443
a(22223)/22223=0.540071
a(45083)/45083=0.538784
a(89516)/89516=0.537044
...
Както се вижда обаче, ако a(n)/n е наистина сходяща, сходимостта е доста бавна.
Засега не мога да дам доказателство. Намаляването на максимумите прилича на някакъв дисипативен процес. Ако означим с f съотношението a(n)/n,
a(n)=n.f=a(a(n-1))+a(n-a(n-1))=f1.a(n-1)+f2.(n-a(n-1))
f=f2+a(n-1)/n*(f1-f2)=f2+(1-1/n)*f3*(f1-f2)
Тук f и f3 са съотношения от текущия “подскок”, а f1 и f2 – от предния. Може би оттук би могло някак да се докаже, че максимумът на текущия “подскок” ще е по-ниско от този на предния?
Поиграх си да построя зависимостта на a(n)/n от n за n до около 200000.
Зависимостта прилича смътно на траектория на подскачащо топче. a(n)/n достига минимална стойност 0.5 само при n=степен на 2 (2,4,8,16...). Така всеки "скок" е 2 пъти по-дълъг от предния. Максимумите наистина намаляват при всеки следващ скок:
a(1)/1=1.000000
a(3)/3=0.666667
a(6)/6=0.666667
a(11)/11=0.636364
a(23)/23=0.608696
a(44)/44=0.590909
a(92)/92=0.576087
a(178)/178=0.567416
a(370)/370=0.559459
a(719)/719=0.554937
a(1487)/1487=0.550101
a(2897)/2897=0.547463
a(5969)/5969=0.544145
a(11651)/11651=0.542443
a(22223)/22223=0.540071
a(45083)/45083=0.538784
a(89516)/89516=0.537044
...
Както се вижда обаче, ако a(n)/n е наистина сходяща, сходимостта е доста бавна.
Засега не мога да дам доказателство. Намаляването на максимумите прилича на някакъв дисипативен процес. Ако означим с f съотношението a(n)/n,
a(n)=n.f=a(a(n-1))+a(n-a(n-1))=f1.a(n-1)+f2.(n-a(n-1))
f=f2+a(n-1)/n*(f1-f2)=f2+(1-1/n)*f3*(f1-f2)
Тук f и f3 са съотношения от текущия “подскок”, а f1 и f2 – от предния. Може би оттук би могло някак да се докаже, че максимумът на текущия “подскок” ще е по-ниско от този на предния?