In this section

Rational Approximations to ln(2)

The exponential logarithm "ln(1+x)" can be approximated by the series

ln(1+x) = x - x2/2 + x3/3 - x4/4 ...

So to calculate ln(2) we can substitute x=1 and get the following series of approximations

Terms ln(2)
1 1/1 = 1.0
2 1/2 = 0.5
3 5/6 = ~ 0.833
4 7/12 = ~ 0.583
5 47/60 = ~ 0.783
6 37/60 = ~ 0.617
Terms ln(2)
7 319/420 = ~ 0.760
8 533/840 = ~ 0.635
9 1879/2520 = ~ 0.746
0 1627/2520 = ~ 0.646
11 20417/27720 = ~ 0.737
12 18107/27720 = ~ 0.653

ln(2) is approximately 0.69314718 so this calculation looks like it could take a long time to get there. Using this to calculate ln(3) is even worse, as the series diverges. The series converges much faster for smaller 'x' values, so to improve the convergence rate we need to find an expression involving values closer to 1. We we can make substitutions like

2 = (3/2) * (4/3)
⇒ ln(2) = ln(3/2) + ln(4/3)

How this converges can be seen in the next table.

Terms ln(3/2) ln(4/3) ln(3/2) + ln(4/3)
1 1/2 1/3 5/6 = ~ 0.833333333333
2 3/8 5/18 47/72 = ~ 0.652777777778
3 5/12 47/162 229/324 = ~ 0.706790123457
4 77/192 31/108 1189/1728 = ~ 0.688078703704
5 391/960 1399/4860 10811/15552 = ~ 0.695151748971
6 259/640 12581/43740 193805/279936 = ~ 0.692318958619
7 909/2240 88087/306180 679475/979776 = ~ 0.693500351101
8 29053/71680 528487/1837080L 65181881/94058496 = ~ 0.692993017877
9 261617/645120 14269429/49601160 1760476247/2539579392 = ~ 0.693215676795
10 130777/322560 2853869/9920232 4400559851/6348948480 = ~ 0.693116327036

This is significantly better as it has achieved 4 decimal places after 10 terms, the previous equation barely achieved 1. We can derive even faster converging equations, by making additional substitutions like

  ln(3/2) = ln(4/3) + ln(9/8)
⇒ ln(2)   = 2 * ln(4/3) + ln(9/8)

This converges a bit faster than the previous series, but not spectacularly so, at the expense of generating much larger integers in the rational representation.

Calculating ln(3)/ln(2)

To calculate ln(3) / ln(2) we notice that

ln(3) = ln(3/2) + ln(2)

which leads to

ln(3)/ln(2) = 1 + ln(3/2) / ln(2)

This isn't very good as we still have the slowly converging log(2) to calculate. But

ln(2) = ln(3/2) + ln(4/3)
⇒ ln(3)/ln(2) = 1 + ln(3/2) / (ln(3/2) + ln(4/3))

Calculating this gives

Terms log(3)/log(2) Estimate Approx Error
1 8/5 1.6 0.0150
2 74/47 1.5744681 -0.0105
3 364/229 1.5895197 0.0046
4 1882/1189 1.5828427 -0.0021
5 85726/54055 1.5859032 0.0009
6 1535458/969025 1.5845391 -0.0004
7 5385358/3397375 1.5851527 0.00019
8 516526138/325909405 1.5848764 -8.606 e-005
9 13951788646/8802381235 1.5850016 3.913 e-005
10 6974643542/4400559851 1.5849446 -1.791 e-005

This converges quite quickly with the error roughly halving for each extra term. The expected value is about 1.58496250072116. We can though make the additional substitution

ln(3/2) = ln(4/3) + ln(9/8)
⇒ ln(3)/ln(2) = 2 - ln(4/3)/(2 * ln(4/3) + ln(9/8))

Which will converge even faster as 1 < 9 / 8 < 4 / 3 but with the same drawbacks found when calculating ln(2).

Factorising 2

The above calculations depend on factorising 2 into ever smaller pieces. If this factorisation follows a predictable path we can generate a series that converges very quickly. The first 10 factorisations are shown in the following table. The "1 / (x-1)" gives an indication of the rate of convergence, so each term in the ln(2) = 41*ln(G) + 12*ln(J) summation would reduce the error by a factor of about 70 (based on G).

ID Fraction Alternative x-1 1/(x-1) Equation
A = 3/2 3/2 0.5 2  
B = 2/A = 4/3 (2^2) / 3 0.333... 3 2 = A * B
C = A/B = 9/8 (3^2)/(2^3) 0.125 8 2 = C * B^2
D = B/C 32/27 (2^5)/(3^3) 0.185... 5.4 2 = C^3 * D^2
E = D/C 256/243 (2^8)/(3^5) 1.053... 18.7 2 = C^5 * E^2
F = C/E 2187/2048 (3^7)/(2^11) 1.067... 14.7 2 = E^7 * F^5
G = F/E 531441/524288 (3^12)/(2^19) 1.013... 73.3 2 = E^12 * G^5
H = E/G   (2^27)/(3^17) 1.039... 25.4 2 = G^17 * H^12
I = H/G   (2^46)/(3^29) 1.025... 39.5 2 = G^29 * I^12
J = I/G   (2^65)/(3^41) 1.011... 86.7 2 = G^41 * J^12

The product is is always of the form

(2a/3b)c * (3e/2f)g = 2(a*c - f*g)/3(f*g - b*c) = 2
⇒ a*c = f*g + 1 and b*c = e*g

If we sum the first 5 terms of ln(2) = 41*log(G) + 12*ln(J) we get 0.693147180608, which compares quite well with the floating point version 0.6931471805599. Unfortunately, the 2 integers involved in forming this ratio are rather large: 2.953...*10127 and 4.261...*10127.

ln(3) / ln(2) revisited

The methods in the previous section can give us arbitrarily accurate rational approximations to ln(3) / ln(2), but only at the expense of dealing with unmanageably large integers. Curiously, though as the factors (2a / 3b) and (3e / 2f) get closer to one the ratios a / b and f / e get to closer ln(3) / ln(2), and obey the relation

a/b > ln(3)/ln(2) > f/e

We can calculate a, b, e and f using the following Python script. A javascript version can be found in the associated script "log3over2.js".

def findFactors(limit):

    a = 2
    b = 1
    e = b
    f = a-1

    for i in range (limit):
        m = a + f
        n = b + e
        m2 = 2**m
        n2 = 3**n

        if m2 > n2:
            a = m
            b = n
        else:
            e = n
            f = m

The next table shows the first 49 iterations of this script. The blue cells show which value has changed since the previous row.

Iteration (a,b) in 2a / 3b (e,f) in 3e / 2f a / b f / e
0 (2, 1) (1, 1) 2.0 1.0
1 (2, 1) (2, 3) 2.0 1.5
2 (5, 3) (2, 3) 1.66666666667 1.5
3 (8, 5) (2, 3) 1.6 1.5
4 (8, 5) (7, 11) 1.6 1.57142857143
5 (8, 5) (12, 19) 1.6 1.58333333333
6 (27, 17) (12, 19) 1.58823529412 1.58333333333
7 (46, 29) (12, 19) 1.58620689655 1.58333333333
8 (65, 41) (12, 19) 1.58536585366 1.58333333333
9 (65, 41) (53, 84) 1.58536585366 1.58490566038
10 (149, 94) (53, 84) 1.58510638298 1.58490566038
11 (233, 147) (53, 84) 1.58503401361 1.58490566038
12 (317, 200) (53, 84) 1.585 1.58490566038
13 (401, 253) (53, 84) 1.58498023715 1.58490566038
14 (485, 306) (53, 84) 1.58496732026 1.58490566038
15 (485, 306) (359, 569) 1.58496732026 1.58495821727
16 (485, 306) (665, 1054) 1.58496732026 1.58496240602
17 (1539, 971) (665, 1054) 1.58496395469 1.58496240602
18 (2593, 1636) (665, 1054) 1.58496332518 1.58496240602
19 (3647, 2301) (665, 1054) 1.58496305954 1.58496240602
20 (4701, 2966) (665, 1054) 1.58496291301 1.58496240602
21 (5755, 3631) (665, 1054) 1.58496282016 1.58496240602
22 (6809, 4296) (665, 1054) 1.58496275605 1.58496240602
23 (7863, 4961) (665, 1054) 1.58496270913 1.58496240602
24 (8917, 5626) (665, 1054) 1.5849626733 1.58496240602
25 (9971, 6291) (665, 1054) 1.58496264505 1.58496240602
26 (11025, 6956) (665, 1054) 1.5849626222 1.58496240602
27 (12079, 7621) (665, 1054) 1.58496260333 1.58496240602
28 (13133, 8286) (665, 1054) 1.5849625875 1.58496240602
29 (14187, 8951) (665, 1054) 1.58496257401 1.58496240602
30 (15241, 9616) (665, 1054) 1.5849625624 1.58496240602
31 (16295, 10281) (665, 1054) 1.58496255228 1.58496240602
32 (17349, 10946) (665, 1054) 1.58496254339 1.58496240602
33 (18403, 11611) (665, 1054) 1.58496253553 1.58496240602
34 (19457, 12276) (665, 1054) 1.58496252851 1.58496240602
35 (20511, 12941) (665, 1054) 1.58496252222 1.58496240602
36 (21565, 13606) (665, 1054) 1.58496251654 1.58496240602
37 (22619, 14271) (665, 1054) 1.58496251139 1.58496240602
38 (23673, 14936) (665, 1054) 1.5849625067 1.58496240602
39 (24727, 15601) (665, 1054) 1.5849625024 1.58496240602
40 (24727, 15601) (16266, 25781) 1.5849625024 1.58496249846
41 (24727, 15601) (31867, 50508) 1.5849625024 1.58496250039
42 (75235, 47468) (31867, 50508) 1.58496250105 1.58496250039
43 (125743, 79335) (31867, 50508) 1.58496250079 1.58496250039
44 (125743, 79335) (111202, 176251) 1.58496250079 1.58496250067
45 (301994, 190537) (111202, 176251) 1.58496250072 1.58496250067
46 (301994, 190537) (301739, 478245) 1.58496250072 1.5849625007
47 (301994, 190537) (492276, 780239) 1.58496250072 1.58496250071
48 (301994, 190537) (682813, 1082233) 1.58496250072 1.58496250071
49 (301994, 190537) (873350, 1384227) 1.58496250072 1.58496250072

ln(3) / ln(2) =~ 1.58496250072116, so after 49 iterations we have fractions that are indistinguishable from the floating point version. The a/b values converge on log(3) / log(2) from above and the f / e values from below. It is the a / b values that will be useful in deriving limits to where the loops might be in 3x+1.

When we get a particularly good value (like f / e = 1054 / 665) the other value (a/b) takes some time to catch up, see rows 17 to 39.

Although this appears to be an easy way to find integer approximations to ln(3) / ln(2) it suffers from two drawbacks:

  1. These might be good integer approximations but we don't know if they are the best (some may have been missed on the way). "a / b" can be considered the 'best' approximation so far if there is no fraction x/y (x < a) that is closer to the target value. We are searching for two series, one that approaches from below and one from above.
  2. To calculate the next pair of values we have to decide whether 2(a+f) is greater than 3(b+e); a+f is 1686221 and b+e 1063887 and 21686221 is of the order of 10507603.

You can use the following controls to explore alternative routes to log(3)/log(2). "Limit" controls the number of iterations. You could theoretically reproduce the table above but you may be waiting a long time. A: B: Limit:

 

Are these the best?

We seeded the Python script in the previous section with 22 / 31. In fact any seed of the form 2a / 3b in the range 1-2 would do. The next smallest unused value is 24/32 = 16 / 9 = 1.777... This is a bit high, but let's see what happens.

Iteration (a,b) in 2a / 3b (e,f) in 3e / 2f a / b f / e
0 (4, 2) (2, 3) 2.0 1.5
1 (7, 4) (2, 3) 1.75 1.5
2 (10, 6) (2, 3) 1.66666666667 1.5
3 (13, 8) (2, 3) 1.625 1.5
4 (16, 10) (2, 3) 1.6 1.5
5 (16, 10) (12, 19) 1.6 1.58333333333
6 (35, 22) (12, 19) 1.59090909091 1.58333333333
7 (54, 34) (12, 19) 1.58823529412 1.58333333333
8 (73, 46) (12, 19) 1.58695652174 1.58333333333
9 (92, 58) (12, 19) 1.58620689655 1.58333333333
10 (111, 70) (12, 19) 1.58571428571 1.58333333333
11 (130, 82) (12, 19) 1.58536585366 1.58333333333
12 (149, 94) (12, 19) 1.58510638298 1.58333333333
13 (149, 94) (106, 168) 1.58510638298 1.58490566038
14 (317, 200) (106, 168) 1.585 1.58490566038
15 (485, 306) (106, 168) 1.58496732026 1.58490566038
16 (485, 306) (412, 653) 1.58496732026 1.58495145631
17 (485, 306) (718, 1138) 1.58496732026 1.58495821727
18 (485, 306) (1024, 1623) 1.58496732026 1.5849609375
19 (485, 306) (1330, 2108) 1.58496732026 1.58496240602
20 (2593, 1636) (1330, 2108) 1.58496332518 1.58496240602
21 (4701, 2966) (1330, 2108) 1.58496291301 1.58496240602
22 (6809, 4296) (1330, 2108) 1.58496275605 1.58496240602
23 (8917, 5626) (1330, 2108) 1.5849626733 1.58496240602
24 (11025, 6956) (1330, 2108) 1.5849626222 1.58496240602
25 (13133, 8286) (1330, 2108) 1.5849625875 1.58496240602
26 (15241, 9616) (1330, 2108) 1.5849625624 1.58496240602
27 (17349, 10946) (1330, 2108) 1.58496254339 1.58496240602
28 (19457, 12276) (1330, 2108) 1.58496252851 1.58496240602
29 (21565, 13606) (1330, 2108) 1.58496251654 1.58496240602
30 (23673, 14936) (1330, 2108) 1.5849625067 1.58496240602
31 (23673, 14936) (16266, 25781) 1.5849625067 1.58496249846
32 (49454, 31202) (16266, 25781) 1.5849625024 1.58496249846
33 (75235, 47468) (16266, 25781) 1.58496250105 1.58496249846
34 (75235, 47468) (63734, 101016) 1.58496250105 1.58496250039
35 (75235, 47468) (111202, 176251) 1.58496250105 1.58496250067
36 (251486, 158670) (111202, 176251) 1.58496250079 1.58496250067
37 (427737, 269872) (111202, 176251) 1.58496250074 1.58496250067
38 (603988, 381074) (111202, 176251) 1.58496250072 1.58496250067
39 (603988, 381074) (492276, 780239) 1.58496250072 1.58496250071
40 (603988, 381074) (873350, 1384227) 1.58496250072 1.58496250072
41 (603988, 381074) (1254424, 1988215) 1.58496250072 1.58496250072
42 (603988, 381074) (1635498, 2592203) 1.58496250072 1.58496250072
43 (603988, 381074) (2016572, 3196191) 1.58496250072 1.58496250072
44 (603988, 381074) (2397646, 3800179) 1.58496250072 1.58496250072
45 (603988, 381074) (2778720, 4404167) 1.58496250072 1.58496250072
46 (603988, 381074) (3159794, 5008155) 1.58496250072 1.58496250072
47 (603988, 381074) (3540868, 5612143) 1.58496250072 1.58496250072
48 (603988, 381074) (3921942, 6216131) 1.58496250072 1.58496250072
49 (603988, 381074) (4303016, 6820119) 1.58496250072 1.58496250072

Here a+f = 7424107 and 27424107 will have something like 2234878 digits. My PC nearly ground to a halt calculating these.

None of the values generated by 16 / 9 are better than those for 4 / 3. 32 / 9, 128 / 81 and 4096 / 2187 didn't produce any better values either.

Other pages

 

(c) John Whitehouse 2011 - 2017