Good work guys!! Its nice to see some cool RPL code. Here is my solution.
I started looking at summations of integers raised to real-value powers. I did a basic study using Excel and
linearized regression. I noticed that the log-log of S(n,p) vs n fits gave good straight lines. That is,
ln[S(n,p)] = a + b ln(n) had a high value for the coefficient of determination. This model worked for integer
and real values of p. I realized that there I can apply some approximations to the various series.
Armed with the results of the power fit, I focused on the approximation approach. Using the analytical equations
for the series S(n,p) it is easy to see that the term with the highest power of n is the most relevant. It is
these terms that appeared in the power curve fir that I performed. My first step is to deduce the first approximation
for S(n,p), which is:
S(n,p) = n^(p+1) / (p+1)
This approximation works well as the values for n and p increase.
To improve the above approximation, I decided to look at including the second most relevant term.
For a simple series, where p = 1, S(n,1) is:
n^2 / + n / 2
The second term is n / 2.
For the case of p = 2, S(n, 2) is:
n^3/3 + n^2/2 + n/6
The second term is n^2 / 2.
For the case of p = 3, S(n, 3) is:
n^4/4 + n^3/2 + n^2/4
The second term is n^3 / 2.
For the case of p = 4, S(n, 4) is:
n^5/5 + n^4/2 + n^3/3 n/30
The second term is n^4 / 2.
For the case of p = 5, S(n, 5) is:
n^6/6 + n^5/2 + 5n^4/12 n^2/12
T second term is n^5 / 2.
For the case of p = 6, S(n, 6) is:
n^7/7 + n^6/2 + n^5/2 n^3/6 + n/42
The second term is n^6 / 2.
By induction, I write the general formula for the second most relevant term for S(n.p) as:
n^p / 2
Thus, a refined approximation for S(n,p) is:
S(n,p) = n^p/(p+1) + n^p / 2
Which I rewrite as:
S(n,p) = n^p (n/(p+1) + 1/2)
The summation approximation formula works for p = 1,2,3,4, and on. For p = 1, the above equation gives an exact
result since it matches the Gauss formula. The approximation also does well for positive real values of the power p.
The summation approximation formula gives good approximations at a fraction of the time needed in using loops
(especially for positive non-integer values of p). Moreover the calculation time is independent of the value of n.
The duration of loops used to calculate the summations is directly proportional to the value of n.
And finally, here is a sample results that compare the exact summations withe the approximated values. The error is taken
per billion instead of a percent.
N S(n,1.5) Approx S(n,1.5) Error (ppb)
---------------------------------------------------
100 40501.22452 40500 -30234.0
250 397263.082 397261.1311 -4910.9
500 2241660.917 2241658.147 -1235.5
1000 12664925.96 12664922.03 -310.1
5000 707283566.7 707283557.9 -12.5
10000 4000500012 4000500000 -3.1
N S(n,2) Approx S(n,2) Error (ppb)
---------------------------------------------------
100 338350 338333.3333 -49258.7
250 5239625 5239583.333 -7952.2
500 41791750 41791666.67 -1994.0
1000 333833500 333833333.3 -499.3
5000 41679167500 41679166667 -20.0
10000 3.33383E+11 3.33383E+11 -5.0
N S(n,2.5) Approx S(n,2.5) Error (ppb)
---------------------------------------------------
100 2907351.199 2907142.857 -71660.3
250 71081484.32 71080660.8 -11585.6
500 801393120.5 801390791.2 -2906.5
1000 9050897005 9050890417 -727.9
5000 2.52627E+12 2.52627E+12 -29.2
10000 2.85764E+13 2.85764E+13 -7.3
N S(n,3) Approx S(n,3) Error (ppb)
---------------------------------------------------
100 25502500 25500000 -98029.6
250 984390625 984375000 -15872.8
500 15687562500 15687500000 -3984.0
1000 2.505E+11 2.505E+11 -998.0
5000 1.56313E+14 1.56313E+14 -40.0
10000 2.5005E+15 2.5005E+15 -10.0
N S(n,3.5) Approx S(n,3.5) Error (ppb)
---------------------------------------------------
100 227251388.7 227222222.2 -128344.6
250 13848978155 13848689927 -20812.2
500 3.11964E+11 3.11963E+11 -5226.5
1000 7.0431E+12 7.0431E+12 -1309.6
5000 9.82535E+15 9.82535E+15 -52.5
10000 2.22272E+17 2.22272E+17 -13.1
N S(n,6) Approx S(n,6) Error (ppb)
---------------------------------------------------
100 1.47907E+13 1.47857E+13 -338038.7
250 8.84187E+15 8.84138E+15 -55223.5
500 1.1239E+18 1.12388E+18 -13902.5
1000 1.43358E+20 1.43357E+20 -3487.8
5000 1.11685E+25 1.11685E+25 -139.9
10000 1.42907E+27 1.42907E+27 -35.0
Go back to the main exhibit hall