[VA] SRC #012c - Then and Now: Sum

[Albert Chan]

(12-05-2022 05:05 PM)Werner Wrote:  - started the summation from C=2, as in Albert's code. Made it ever so slightly shorter - but I added the 1/4 at the end, not at the beginning, gaining 1 digit of accuracy ;-)

Nice work! Numbers dead-on target!

Since we know S is around 2, we might as well go for S-2
For returning S-2, patch with 3 steps on the right.

20 4 @ wrap-up
21 1/X
22 RCL+ "S"
23 1
24 2
25 LN
26 -
27 ÷                --> 27 -
28 1                --> 28 LASTX
29 +                --> 29 ÷
30 RTN

Quote:Free42, C=105 and S=2.086377665005988716089755856734133

We now have:      S-2=0.08637766500598871608975585673413264      // error 13 ULP (should be 77)

[Werner]

to get the ..77 as well, in my code:
- sum from C=105 to 2 (small to large)
- change switch criterion for H(n) to 0.01 + n = 0.01 (we need two more digits)
- then, with S = sum(C=105 to 2 step -1, (H(n)-ln(2))/f(n)), calculate (LN(2)-0.75 + S)/(1-LN(2))
(no need, I think, to paste that code anew - it is slightly off-topic)

Cheers, Werner

[Albert Chan]

I was curious what it take if we do brute force, no tricks, S = sum(1/F)

G(b)/F(b) = sum(1/F(k), k = 2^(b-1) .. 2^b - 1)

S ≈ 2.086, for 12-digits accuracy we solve G(b)/F(b) = 1E-11 (1 ULP), for b

G(b)/F(b) ≈ ln(2)/(b*log2(b)) ≈ 1E-11 --> b ≈ 2.2E9      (*)

It take more terms for convergence, even though all other terms below 1 ULP.

sum(1/F) terms needed > 2^b ≈ googol ^ 6622660

(*)
We assume F grow about same rate as primes, to be conservative.
We know F grow faster, because sum of reciprocal primes diverges.

---

Update: using actual recursive definition of f(b)

ln(2)/f(b) ≈ 1E-11 --> b ≈ 85573726

sum(1/F) terms needed > 2^b ≈ googol ^ 257603

Edit: google should be googol (10^100), corrected.

[PeterP]

you probably mean a googol, not a google, right?
https://en.wikipedia.org/wiki/Googol

[Werner]

(12-08-2022 06:55 PM)Albert Chan Wrote:  I was curious what it take if we do brute force, no tricks, S = sum(1/F)

G(b)/F(b) = sum(1/F(k), k = 2^(b-1) .. 2^b - 1)

S ≈ 2.086, for 12-digits accuracy we solve G(b)/F(b) = 1E-11 (1 ULP), for b

G(b)/F(b) ≈ ln(2)/(b*log2(b)) ≈ 1E-11 --> b ≈ 2.2E9      (*)

It take more terms for convergence, even though all other terms below 1 ULP.

sum(1/F) terms needed > 2^b ≈ googol ^ 6622660

(*)
We assume F grow about same rate as primes, to be conservative.
We know F grow faster, because sum of reciprocal primes diverges.

---

Update: using actual recursive definition of f(b)

ln(2)/f(b) ≈ 1E-11 --> b ≈ 85573726

sum(1/F) terms needed > 2^b ≈ googol ^ 257603

Edit: google should be googol (10^100), corrected.

It is far worse than that, I believe. Unless I made a gross error - which is increasingly likely:
Let's try and compute Sk = 1/fk + 1/fk+1 + ... for large k

take k=2^(128-1) so b=128 and k=1.7e38

Sk = ln2*(1/fb + .. 1/fk-1 + 1/fk + 1/fk+1 + ..)
Sk*(1-ln2) = ln2*(1/fb + .. + 1/fk-1)

b=128 = 2^(8-1) so c=8
Sk*(1-ln2) = ln2*ln2*(1/fc + 1/fb-1)

and finally

Sk*(1-ln2) = ln2*ln2*(g4/f4 + g5/f5 + g6/f6 + g7/f7)

for k=2^(128-1), Sk =2.1e-03
for l=2^k-1, Sl = ln2*Sk = 1.5e-03
etc.
so even if the googol^large power term is just below 1e-11, the remainder still adds up to a sizeable fraction..

Cheers, Werner

[Albert Chan]

Knowing s ≈ 2.086377665, lets try something easily calculated

sum(1/f, k=16 .. inf) = s - sum(1/f, k=1 .. 15) ≈ 0.262900
sum(1/f, k=2^16 .. inf) ≈ sum(g/f, k=16 .. inf) ≈ 0.262900 * ln2      (*)

Continued doing this, how many (* ln2) we need to make RHS ≈ 1E-11 (1 ULP) ?

number of ln2's = ln(1E-11/0.262900) / ln(ln2) ≈ 65.46

We will need tetration notation to handle term size this enormous!

16 = 2^2^2 = ³2
2^16 = 2^2^2^2 = ⁴2

sum(1/f) terms need for 12-digits accuracy (error < 1ULP) ≈ ⁶⁹2      
I have no words to describe how big this is ...

(*) the estimate had an off-by-1 error. To make it all into equality:

sum(1/f, k=2^16 .. inf) = sum(g/f, k=17 .. inf) = (sum(1/f, k=16 .. inf) - 1/f(16)) * K
where ln2 < K < g(17) ≈ ln2 + 1/2^18

We over-estimated the sum, but under-estimated K.
Overall, we probably over-estimated terms needed.

(0.262900 * ln2) ≈ 0.182228
(0.262900 - 1/480) * (ln2 + 1/2^19) ≈ 0.180785

Udpate: off-by-1 error effect after "first ln2" can be ignored.

number of ln2's = ln(1E-11/0.180785) / ln(ln2) + 1 ≈ 65.44

In terms of tetration exponent, off-by-1 error can be ignored.

[Valentin Albillo]

      
Hi, all,

As I see there's still some activity in this thread, I'm providing an Epilogue of sorts, including additional comments about my Problem 3 and the featured series. Let's start ...

Epilogue

Most of my many Problems and Challenges large and small usually feature some mathematical aspects that can be intriguing, curious and even weird at times, and this Problem 3 is no exception.

The surprising factor here is that the series whose sum I asked people to compute looks quite simple, defined in a single line of text, yet it converges excruciatingly slowly to say the least, requiring a hyperexponential number of terms to get even one correct digit (let alone 10-12 digits,) so most people's natural instinct to sum a (somewhat large) number of terms to get some value leads absolutely nowhere and thus other more refined techniques are sorely needed, as seen for instance in my solution above.

Now, slowly convergent and divergent series are not unusual and sometimes they resemble each other so much that it's not hard but certainly not trivial to ascertain whether a given series converges or diverges. For instance, all the following series are divergent ...
      

... while all the following very similar ones are convergent for any ε > 0 ...
      

... and as you can see the divergent ones correspond to the particular case ε = 0.

And what about our series ? Well, as it happens its terms tend to zero more slowly than the terms of any of the convergent series above but faster than the terms of any of the divergent series, almost a "middle" case so to say. But as there's no series that lies exactly on the (also nonexistent) "dividing line" between convergence and divergence), which is it ? Does this series converge or does it diverge ?

Fortunately for the soundness of my Problem 3, it does converge and matter of fact its sum is just a trifle over 2, namely 2.08637766500599+ but, as stated above, it would require summing a hyperexponential number of terms to get 12 correct digits, never mind 15 or more.

However, if multiprecision is available, using the formula Sum 3 obtained in my solution above (and using a multiprecision version of H(n)) we can get greater accuracy by just increasing the number of terms summed up. For instance, using 50 terms it will deliver the 15 correct digits shown earlier, and so on and so forth.

On a final note, the fact that I stated in the series' definition that "d(n) = number of binary digits of n" is crucial for the convergence of the series. Had I stated "ternary" (base 3) digits instead of "binary" (base 2), the resulting series would've been divergent.

Note: if d(n) is stated in terms of the logarithm base a, the series does converge for a < e and diverges otherwise. Thus, for binary digits the base is 2 < e and the series does converge, while for ternary digits the base is 3 > e and the resulting series would diverge.

See you in Problem 4 next January.  
V.