If the limiting ratio be called r:
Eventually, somewhere it the middle, it'll get close enough to
... , x, rx, (r^2)x, ...
so:
(r^2)x = Arx + Bx
r^2 - Ar - B = 0
r = (A +/- sqrt(A^2 + 4B)) / 2
To be non-negative,
r = (A + sqrt(A^2 + 4B)) / 2
unless B itself is negative, then we could use both choices, but we'll stick with positive B's.
If we want r = N,
N = (A + sqrt(A^2 + 4B)) / 2
2N = A + sqrt(A^2 + 4B)
2N - A = sqrt(A^2 + 4B)
(2N - A)^2 = A^2 + 4B
4B = (2N - A)^2 - A^2
B = ((2N - A)^2 - A^2) / 4
Choose A as you like and then calculate the appropriate B from this formula.
What should B be for various N, if A = 1?:
N B
1 0
2 2
3 6
4 12
5 20
6 30
7 42
8 56
9 72
10 90
It seems to be (N-1)*N.
So, A=1, B=(N-1)*N will work.
Verify for N=2; A=1; B=2:
member ratio
1
1 1
3 3
5 1.66666666666667
11 2.2
21 1.90909090909091
43 2.04761904761905
85 1.97674418604651
171 2.01176470588235
341 1.99415204678363
683 2.00293255131965
1365 1.99853587115666
2731 2.0007326007326
5461 1.99963383376053
10923 2.0001831166453
21845 1.99990845005951
43691 2.00004577706569
87381 1.99997711199103
174763 2.00001144413545
349525 1.99999427796502
699051 2.00000286102568
1398101 1.99999856948921
2796203 2.00000071525591
5592405 1.99999964237217
11184811 2.00000017881395
22369621 1.99999991059304
44739243 2.00000004470348
89478485 1.99999997764826
178956971 2.00000001117587
357913941 1.99999999441206
715827883 2.00000000279397
1431655765 1.99999999860302
2863311531 2.00000000069849
5726623061 1.99999999965075
11453246123 2.00000000017462
22906492245 1.99999999991269
45812984491 2.00000000004366
91625968981 1.99999999997817
183251937963 2.00000000001091
366503875925 1.99999999999454
733007751851 2.00000000000273
1466015503701 1.99999999999864
2932031007403 2.00000000000068
5864062014805 1.99999999999966
11728124029611 2.00000000000017
23456248059221 1.99999999999991
46912496118443 2.00000000000004
93824992236885 1.99999999999998
187649984473771 2.00000000000001
375299968947541 1.99999999999999
750599937895083 2
1.50119987579017E+15 2
For N=3; A=1; B=6:
member ratio
1
1 1
7 7
13 1.85714285714286
55 4.23076923076923
133 2.41818181818182
463 3.4812030075188
1261 2.72354211663067
4039 3.203013481364
11605 2.87323594949245
35839 3.08823782852219
105469 2.9428555484249
320503 3.03883605609231
953317 2.97444017684702
2876335 3.01718630843675
8596237 2.98860772476085
25854247 3.00762380097245
77431669 2.99493034935421
232557151 3.00338548817797
697147165 2.99774555201702
2092490071 3.00150409562377
6275373061 2.99899777206637
18830313487 3.00066837524387
56482551853 2.9995545157543
169464432775 3.00029703360506
508359743893 2.99980199720112
1525146340543 3.00013201057874
4575304803901 2.99991199681996
13726182847159 3.00005867050776
41178011670565 2.99996088709308
123535108753519 3.00002607561124
370603178776909 2.99998261641027
1.11181383129802E+15 3.00001158912697
3.33543290395948E+15 2.9999922739452
1.00063158917476E+16 3.00000515071647
3.00189133155045E+16 2.99999656619492
9.00568086659902E+16 3.00000228920601
2.70170288559017E+17 2.99999847386383
8.10511140554958E+17 3.00000101742463
2.43153287190906E+18 2.99999932171714
7.29459971523881E+18 3.00000045218867
2.18837969466932E+19 2.99999969854093
6.5651395238126E+19 3.00000020097273
1.96954176918285E+20 2.99999986601819
5.90862548347041E+20 3.00000008932121
1.77258760985675E+21 2.99999994045253
5.317762899939E+21 3.00000003969832
1.59532885590795E+22 2.99999997353446
4.78598659587135E+22 3.0000000176437
1.43579597313191E+23 2.99999998823754
4.30738793065472E+23 3.00000000784164
1.29221637694461E+24 2.99999999477224
I haven't tried fiddling with A to get faster convergence for the ratio or slower increases in value. Presumably to get the latter, values of A smaller than 1 would be necessary.
Wait, change that: smaller A's would require larger B's; but, say for N=3 as above, A=2, B=3 would work:
1
1 1
5 5
13 2.6
41 3.15384615384615
121 2.95121951219512
365 3.01652892561983
1093 2.99452054794521
3281 3.00182982616651
9841 2.99939042974703
29525 3.00020323137892
88573 2.99993226079594
265721 3.00002258024454
797161 2.99999247330847
2391485 3.00000250890347
7174453 2.99999916369954
21523361 3.0000002787669
64570081 2.99999990707771
193710245 3.0000000309741
581130733 2.9999999896753
1743392201 3.00000000344157
5230176601 2.99999999885281
15690529805 3.0000000003824
47071589413 2.99999999987253
141214768241 3.00000000004249
423644304721 2.99999999998584
1270932914165 3.00000000000472
3812798742493 2.99999999999843
11438396227481 3.00000000000052
34315188682441 2.99999999999983
102945566047325 3.00000000000006
308836698141973 2.99999999999998
926510094425921 3.00000000000001
2.77953028327776E+15 3
8.33859084983329E+15 3
2.50157725494999E+16 3
7.50473176484996E+16 3
2.25141952945499E+17 3
6.75425858836496E+17 3
2.02627757650949E+18 3
6.07883272952846E+18 3
1.82364981885854E+19 3
5.47094945657562E+19 3
1.64128483697269E+20 3
4.92385451091806E+20 3
1.47715635327542E+21 3
4.43146905982625E+21 3
1.32944071794788E+22 3
3.98832215384363E+22 3
1.19649664615309E+23 3
3.58948993845926E+23 3
1.07684698153778E+24 3
Well, it seems to get large just as rapidly, but it does converge more rapidly.
In fact, if we take A=N-1, then from B = ((2N - A)^2 - A^2) / 4, we get B = ((N+1)^2 - (N-1)^2) / 4 = N.
Maybe that's always the best answer: A=N-1; B=N.
Of course the quickest way to convergence is A=N, B=0, but that's cheating. :-)
|
|
Posted by Charlie
on 2015-12-07 18:01:58 |
solution
