## 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)

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