(12C Platinum) Sums of Powers of N numbers

(12C Platinum) Sums of Powers of N numbers - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (12C Platinum) Sums of Powers of N numbers (/thread-12248.html)

(12C Platinum) Sums of Powers of N numbers - Gamo - 01-22-2019 10:20 AM

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

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 01-22-2019 12:28 PM

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.

RE: (12C Platinum) Sums of Powers of N numbers - Gamo - 01-22-2019 01:19 PM

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

RE: (12C Platinum) Sums of Powers of N numbers - Thomas Klemm - 01-22-2019 11:57 PM

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

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 01-23-2019 05:40 PM

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

RE: (12C Platinum) Sums of Powers of N numbers - Thomas Klemm - 01-23-2019 07:21 PM

(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

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 01-23-2019 07:52 PM

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

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 01-23-2019 10:57 PM

(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

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 01-24-2019 08:28 PM

(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.

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 01-25-2019 03:02 PM

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

RE: (12C Platinum) Sums of Powers of N numbers - Thomas Klemm - 01-26-2019 09:02 PM

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

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 01-28-2019 03:08 PM

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.

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 07-29-2019 04:12 AM

Noticed a pattern with S_k(n) = Σi^k formula, when extend n to negative numbers:
(see http://www.mikeraugh.org/Talks/BernoulliSummation-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

RE: (12C Platinum) Sums of Powers of N numbers - Albert Chan - 07-29-2019 05:41 PM

(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