(12C Platinum) Sums of Powers of N numbers

[Gamo]

ALG program solution of "Sums of Powers of the Natural Numbers"

1. Arithmetic Series ( Gauss Sum )

n(n+1) / 2

2. Sum of the consecutive Squares.

n(n+1)(2n+1) / 6

3. Sum of the consecutive Cubes.

n^2(n+1)^2 / 4

----------------------------------------------
Procedure:

Nth [R/S] display Sums of Powers

----------------------------------------------

1. Gauss Sum

Code:


1 [+] [X<>Y] [x] [LSTx] [÷] 2 [=]

2. Sums of consecutive Squares

Code:


1 [+] [X<>Y] [x] [LSTx] [x] ( [LSTx] [x] 2 [+] 1 ) [÷] 6 [=]

3. Sums of consecutive Cubes

Code:


1 [+] [X<>Y] [=] [X^2] [x] [LSTx] [X^2] [÷] 4 [=]

Gamo

[Albert Chan]

Is the code for ALG mode ?
If true, all "1 +" should be "+ 1"

Also, for sum of cubes, LSTx = n ?

I would guess the code should be just Gauss Sum code, then square it.

[Gamo]

Albert Chan thanks for the review.

Yes program above is in ALG mode.

I was reading over at the 12C Platinum
Manual that mention about [LSTx] and
[X<>Y] functions that work differently
Compared to RPN .

For ALG programming in order to recall
LSTx it need to be in previous display so
At the start of each program above I use
1 + X<>Y so that the n can be recall by using the LSTx
So above program doesn't use Store Registers.

Example:
1 + X<>Y x .......
If n is 10 when run that will become 1 + 10 x ......
10 is last seen in display after execution forward.
Then LSTx will recall 10 for next step.

Gamo

[Thomas Klemm]

We can use the Net Present Value (NPV) to evaluate a polynomial:

\(NPV = CF_0 + \frac{CF_1}{1+r} + \frac{CF_2}{(1+r)^2} + \frac{CF_3}{(1+r)^3} + \cdots + \frac{CF_n}{(1+r)^n}\)

Use the ∆% function to transform \(x=\frac{1}{1+r}\) to \(i=100r\).

This leads to the following generic program to evaluate a polynomial:

Code:

01-       1    1
02-      24    ∆%
03-   44 12    STO i
04-   42 13    NPV

1. Arithmetic Series

\(\frac{x(x+1)}{2}=\frac{x^2}{2}+\frac{x}{2}\)

0
CF₀
2 1/x
CF_i
CF_i


Examples:

1 R/S
1.0000

2 R/S
3.0000

3 R/S
6.0000

10 R/S
55.0000


2. Sum of the consecutive Squares

\(\frac{x(x+1)(2x+1)}{6}=\frac{x^3}{3}+\frac{x^2}{2}+\frac{x}{6}\)

0
CF₀
6 1/x
CF_i
2 1/x
CF_i
3 1/x
CF_i


Examples:

1 R/S
1.0000

2 R/S
5.0000

3 R/S
14.0000

10 R/S
385.0000


3. Sum of the consecutive Cubes

\(\frac{x^2(x+1)^2}{4}=\frac{x^4}{4}+\frac{x^3}{2}+\frac{x^2}{4}\)

0
CF₀
CF_i
4 1/x
CF_i
2 1/x
CF_i
x<>y
CF_i


Examples:

1 R/S
1.0000

2 R/S
9.0000

3 R/S
36.0000

10 R/S
3025.0000


Disclaimer: I don't have an HP-12C Platinum.
But this works with the regular HP-12C.

Kind regards
Thomas

PS: Cf. HP-12C’s Serendipitous Solver

[Albert Chan]

From another thread about forward difference table, we can treat sum of powers on N numbers as polynomial interpolation.

For sum of kth powers, we expect a polynomial with degree k+1

Example, for sum of cubes, just use forward differences of cubes of 4 numbers

1 8 27 64
7 19 37
12 18
6

Thus sum of cubes formula = \(1\binom{n}{1}+7\binom{n}{2}+12\binom{n}{3}+6\binom{n}{4} = [n(n+1)/2]^2
\)

We can also do interpolation with 5 points. (5 points "fixed" a quartic polynomial)
Example, for sum of cubes of 10 numbers, interpolate for N=10:

Code:

N Sum Intepolation for N=10
4 100
3 36  484
2 9   373  1261
1 1   298  1135  2269
0 0   250  1030  2185  3025

All the intepolations above are simple linear interpolation.
Example, 1030 is from interpolation of 2 points (3, 484), (0, 250), for N=10

[Thomas Klemm]

(01-23-2019 05:40 PM)Albert Chan Wrote:  

Code:

N Sum Interpolation for N=10
4 100
3 36  484
2 9   373  1261
1 1   298  1135  2269
0 0   250  1030  2185  3025

Could you elaborate on how to calculate these numbers?

Thanks in advance
Thomas

[Albert Chan]

Hi, Thomas Klemm

The trick is from Acton Forman's book Numerical Method that Work, p94
It was a modified Aitken's method.

First, arrange the points in sorted order, closest to interpolated N on top.
Back in the old days, people don't have computers readily available.
The sorting ensured for each columns, interpolated values "tighter".
Manual calculation mistakes are thus easier to spot.

For each column, top point is "locked", and do interpolation with other points.

First column:
(4,100) and (3,36) => (10,484)
(4,100) and (2,9) => (10,373) ...
Second column:
(3,484) and (2,373) => (10,1261)
(3,484) and (1,298) => (10,1135) ...
...
Last column: (1,2269) and (0,2185) => (10,3025)

Without sorting, we still get the same interpolated value, but mistakes harder to spot.

Code:

N Sum Interpolation for N=10
0 0   
1 1   10
2 9   45  325
3 36  120 505 1765
4 100 250 730 1945 3025

[Albert Chan]

(01-23-2019 05:40 PM)Albert Chan Wrote:  1 8 27 64
7 19 37
12 18
6

Thus sum of cubes formula = \(1\binom{n}{1}+7\binom{n}{2}+12\binom{n}{3}+6\binom{n}{4}\)

Above formula can be efficiently calculated with Horner's like method:

sum of cubes = (((6 * (n-3)/4 + 12) * (n-2)/3 + 7) * (n-1)/2 + 1) * n

Or, to avoid rounding error, scale away the division:

{1,7,12,6} * 4! / {1!,2!,3!,4!} = {24,84,48,6}

sum of cubes = (((6 * (n-3) + 48) * (n-2) + 84) * (n-1) + 24) / 24 * n

[Albert Chan]

(01-23-2019 05:40 PM)Albert Chan Wrote:  

Code:

N Sum Interpolation for N=10
4 100
3 36  484
2 9   373  1261
1 1   298  1135  2269
0 0   250  1030  2185  3025

Just discovered every interpolation numbers have meanings.

Example, 4th line:
(10, 298) = linear fit of 2 points: (4,100), (1,1)
(10, 1135) = quadratic fit of 3 points: (4,100), (3,36), (1,1)
(10, 2269) = cubic fit of 4 points: (4,100), (3,36), (2,9), (1,1)

Since data points is sorted (closest to N=10 on top), diagonal numbers were "best" estimates.

Another trick: with quadratic regression, above only need 4 interpolations.

[Albert Chan]

Another trick about polynomial interpolation is do slopes.

Code:

N Sum Offset=(4,100)        Offset=(3,64)          Offset=(2,18.5)         Offset=(1,3)
4 100
3 36  (100-36)/(4-3) = 64
2 9   (100-9)/(4-2) = 45.5  (64-45.5)/(3-2) = 18.5 
1 1   (100-1)/(4-1) = 33    (64-33)/(3-1) = 15.5   (18.5-15.5)/(2-1) = 3
0 0   (100-0)/(4-0) = 25    (64-25)/(3-0) = 13     (18.5-13)/(2-0) = 2.75  (3-2.75)/(1-0) = 0.25

To get the actual interpolated values, undo Offset(s):

Sum of N cubes = (((0.25 * (N-1) + 3) * (N-2) + 18.5) * (N-3) + 64) * (N-4) + 100

If above points order were reversed, we get different, but equivalent formula:

Sum of N cubes = (((0.25 * (N-3) + 2) * (N-2) + 3.5) * (N-1) + 1) * N

[Thomas Klemm]

We can also use Neville's algorithm to interpolate the polynomial at \(n=10\):

\(\begin{matrix}
0 & 0 & & & & \\
& & 10 & & & \\
1 & 1 & & 325 & & \\
& & 73 & & 1765 & \\
2 & 9 & & 757 & & 3025\\
& & 225 & & 2269 & \\
3 & 36 & & 1261 & & \\
& & 484 & & & \\
4 & 100 & & & &
\end{matrix}\)

For this we can use the HP-12C since only linear forecasts are used:

CLEAR ∑
0 ENTER 0 ∑+
1 ENTER 1 ∑+
10 ŷ,r
10.0000

CLEAR ∑
1 ENTER 1 ∑+
9 ENTER 2 ∑+
10 ŷ,r
73.0000

CLEAR ∑
9 ENTER 2 ∑+
36 ENTER 3 ∑+
10 ŷ,r
225.0000

CLEAR ∑
36 ENTER 3 ∑+
100 ENTER 4 ∑+
10 ŷ,r
484.0000

---

CLEAR ∑
10 ENTER 0 ∑+
73 ENTER 2 ∑+
10 ŷ,r
325.0000

CLEAR ∑
73 ENTER 1 ∑+
225 ENTER 3 ∑+
10 ŷ,r
757.0000

CLEAR ∑
225 ENTER 2 ∑+
484 ENTER 4 ∑+
10 ŷ,r
1261.0000

---

CLEAR ∑
325 ENTER 0 ∑+
757 ENTER 3 ∑+
10 ŷ,r
1765.0000

CLEAR ∑
757 ENTER 1 ∑+
1261 ENTER 4 ∑+
10 ŷ,r
2269.0000

---

CLEAR ∑
1765 ENTER 0 ∑+
2269 ENTER 4 ∑+
10 ŷ,r
3025.0000


Cheers
Thomas

[Albert Chan]

Modified Aitken's method can interpolate slope too, then recover interpolated value.
Example, with 5-digits precision, calculate LN(12.3), with tables of LN (integer domain):

LN(12.3) is between LN(12)=2.4849, and LN(13)=2.5649
So, LN(12.3) = 2.5 (2 digits accurate), only 3 digits slope required

Code:

X   LN(X)   Slopes, interpolate for X=12.3
12  2.4849
13  2.5649  0.0800
11  2.3979  0.0870  825
14  2.6391  0.0771  820  823

Each interpolated diagonals gained 1 digits accuracy, so only 4 points needed.
Recover interpolated slope to value:

LN(12.3) = 0.0823 * (12.3-12) + 2.4849 = 2.5096 (5 digits)

Interpolations needed are reduced (only 3 interpolations for cubic fit, down 50%)
Also, with slopes interpolated to full precision, recovered result may be more accurate.

[Albert Chan]

Noticed a pattern with S_k(n) = Σi^k formula, when extend n to negative numbers:
(see http://www.mikeraugh.org/Talks/Bernoulli...n-LACC.pdf, slide 26)

S_k(-n) = (-1)^(k+1) * S_k(n-1)

This allow the use of symmetries, to keep forward difference table numbers small.
To force 0 in the center, start i = -floor(k/2), offset = i-1

Even k example: Σi^4 formula, forward difference table, start at offset of -3 (3 numbers before 1):

16 1 0 1 16            // i^4, i = -2 to 2
-15 -1 1 15
14 2 14
-12 12
24

S₄(-3) = -S₄(2) = -(1 + 16) = -17

S₄(n) = -17 + \(16\binom{n+3}{1}-15\binom{n+3}{2}+14 \binom{n+3}{3}-12\binom{n+3}{4}+24\binom{n+3}{5}\)

Odd k example: Σi^5 formula, forward difference table, start at offset of -3 (3 numbers before 1):

-32 -1 0 1 32 243   // i^5, i = -2 to 3
31 1 1 31 211
-30 0 30 180
30 30 150
0 120
120

S₅(-3) = +S₅(2) = 1 + 32 = 33

S₅(n) = 33 - \(32\binom{n+3}{1}+31\binom{n+3}{2}-30\binom{n+3}{3}+30\binom{n+3}{4}+120\binom{n+3}{6}\)

Update: if needed, above expression can be transformed without offset.
Example: \(\binom{n+3}{6} = \binom{n}{6} + 3\binom{n}{5} + 3\binom{n}{4} +\binom{n}{3}\)         // See Vandermonde Convolution Formula

[Albert Chan]

(07-29-2019 04:12 AM)Albert Chan Wrote:  Noticed a pattern with S_k(n) = Σi^k formula, when extend n to negative numbers:

S_k(-n) = (-1)^(k+1) * S_k(n-1)

Trivia, based on above formula, S_k(-1) = S_k(0) = 0

→ All Σi^k formulas (k positive integer), has the factor n * (n + 1)
→ All Σ(polynomial, degree > 0), has the factor n * (n + 1)

Update: just learned Σi^k formula and Bernoulli numbers are related:

For Mathematica, below formula = Sum[i^k, {k,n}], where k > 0

S[k_] := n^(k+1)/(k+1) + n^k/2 + Sum[BernoulliB[i] * Binomial[k,i] * n^(k+1-i)/(k+1-i), {i,2,k,2}]

Example: Σi^5 = n^6/6 + n^5/2 + (1/6)(10)*n^4/4 + (-1/30)(5)*n^2/2 = n^6/6 + n^5/2 + (5/12)*n^4 - n^2/12