Post Reply 
(12C Platinum) Sums of Powers of N numbers
01-22-2019, 10:20 AM (This post was last modified: 01-22-2019 10:23 AM by Gamo.)
Post: #1
(12C Platinum) Sums of Powers of N numbers
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
Find all posts by this user
Quote this message in a reply
01-22-2019, 12:28 PM (This post was last modified: 01-22-2019 12:53 PM by Albert Chan.)
Post: #2
RE: (12C Platinum) Sums of Powers of N numbers
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.
Find all posts by this user
Quote this message in a reply
01-22-2019, 01:19 PM (This post was last modified: 01-22-2019 01:22 PM by Gamo.)
Post: #3
RE: (12C Platinum) Sums of Powers of N numbers
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
Find all posts by this user
Quote this message in a reply
01-22-2019, 11:57 PM
Post: #4
RE: (12C Platinum) Sums of Powers of N numbers
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
CF0
2 1/x
CFi
CFi


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
CF0
6 1/x
CFi
2 1/x
CFi
3 1/x
CFi


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
CF0
CFi
4 1/x
CFi
2 1/x
CFi
x<>y
CFi


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
Find all posts by this user
Quote this message in a reply
01-23-2019, 05:40 PM (This post was last modified: 01-24-2019 04:50 PM by Albert Chan.)
Post: #5
RE: (12C Platinum) Sums of Powers of N numbers
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
Find all posts by this user
Quote this message in a reply
01-23-2019, 07:21 PM
Post: #6
RE: (12C Platinum) Sums of Powers of N numbers
(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
Find all posts by this user
Quote this message in a reply
01-23-2019, 07:52 PM (This post was last modified: 01-23-2019 08:04 PM by Albert Chan.)
Post: #7
RE: (12C Platinum) Sums of Powers of N numbers
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
Find all posts by this user
Quote this message in a reply
01-23-2019, 10:57 PM (This post was last modified: 01-24-2019 12:38 PM by Albert Chan.)
Post: #8
RE: (12C Platinum) Sums of Powers of N numbers
(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
Find all posts by this user
Quote this message in a reply
01-24-2019, 08:28 PM
Post: #9
RE: (12C Platinum) Sums of Powers of N numbers
(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.
Find all posts by this user
Quote this message in a reply
01-25-2019, 03:02 PM (This post was last modified: 01-27-2019 05:22 PM by Albert Chan.)
Post: #10
RE: (12C Platinum) Sums of Powers of N numbers
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

see Comparison of Algorithms for polynomial interpolation
Find all posts by this user
Quote this message in a reply
01-26-2019, 09:02 PM
Post: #11
RE: (12C Platinum) Sums of Powers of N numbers
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
Find all posts by this user
Quote this message in a reply
01-28-2019, 03:08 PM (This post was last modified: 01-30-2019 01:47 AM by Albert Chan.)
Post: #12
RE: (12C Platinum) Sums of Powers of N numbers
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.
Find all posts by this user
Quote this message in a reply
07-29-2019, 04:12 AM (This post was last modified: 08-25-2019 02:46 PM by Albert Chan.)
Post: #13
RE: (12C Platinum) Sums of Powers of N numbers
Noticed a pattern with Sk(n) = Σi^k formula, when extend n to negative numbers:
(see http://www.mikeraugh.org/Talks/Bernoulli...n-LACC.pdf, slide 26)

Sk(-n) = (-1)^(k+1) * Sk(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

S4(-3) = -S4(2) = -(1 + 16) = -17

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

S5(-3) = +S5(2) = 1 + 32 = 33

S5(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
Find all posts by this user
Quote this message in a reply
07-29-2019, 05:41 PM (This post was last modified: 08-01-2019 05:25 PM by Albert Chan.)
Post: #14
RE: (12C Platinum) Sums of Powers of N numbers
(07-29-2019 04:12 AM)Albert Chan Wrote:  Noticed a pattern with Sk(n) = Σi^k formula, when extend n to negative numbers:

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

Trivia, based on above formula, Sk(-1) = Sk(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
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)