(12C Platinum) Sums of Powers of N numbers

01222019, 10:20 AM
(This post was last modified: 01222019 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:
2. Sums of consecutive Squares Code:
3. Sums of consecutive Cubes Code:
Gamo 

01222019, 12:28 PM
(This post was last modified: 01222019 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. 

01222019, 01:19 PM
(This post was last modified: 01222019 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 

01222019, 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 1. Arithmetic Series \(\frac{x(x+1)}{2}=\frac{x^2}{2}+\frac{x}{2}\) 0 CF_{0} 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_{0} 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_{0} 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 HP12C Platinum. But this works with the regular HP12C. Kind regards Thomas PS: Cf. HP12C’s Serendipitous Solver 

01232019, 05:40 PM
(This post was last modified: 01242019 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 All the intepolations above are simple linear interpolation. Example, 1030 is from interpolation of 2 points (3, 484), (0, 250), for N=10 

01232019, 07:21 PM
Post: #6




RE: (12C Platinum) Sums of Powers of N numbers  
01232019, 07:52 PM
(This post was last modified: 01232019 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 

01232019, 10:57 PM
(This post was last modified: 01242019 12:38 PM by Albert Chan.)
Post: #8




RE: (12C Platinum) Sums of Powers of N numbers
(01232019 05:40 PM)Albert Chan Wrote: 1 8 27 64 Above formula can be efficiently calculated with Horner's like method: sum of cubes = (((6 * (n3)/4 + 12) * (n2)/3 + 7) * (n1)/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 * (n3) + 48) * (n2) + 84) * (n1) + 24) / 24 * n 

01242019, 08:28 PM
Post: #9




RE: (12C Platinum) Sums of Powers of N numbers
(01232019 05:40 PM)Albert Chan Wrote: 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. 

01252019, 03:02 PM
(This post was last modified: 01272019 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) To get the actual interpolated values, undo Offset(s): Sum of N cubes = (((0.25 * (N1) + 3) * (N2) + 18.5) * (N3) + 64) * (N4) + 100 If above points order were reversed, we get different, but equivalent formula: Sum of N cubes = (((0.25 * (N3) + 2) * (N2) + 3.5) * (N1) + 1) * N see Comparison of Algorithms for polynomial interpolation 

01262019, 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 HP12C 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 

01282019, 03:08 PM
(This post was last modified: 01302019 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 5digits 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 Each interpolated diagonals gained 1 digits accuracy, so only 4 points needed. Recover interpolated slope to value: LN(12.3) = 0.0823 * (12.312) + 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. 

07292019, 04:12 AM
(This post was last modified: 08252019 02:46 PM by Albert Chan.)
Post: #13




RE: (12C Platinum) Sums of Powers of N numbers
Noticed a pattern with S_{k}(n) = Σi^k formula, when extend n to negative numbers:
(see http://www.mikeraugh.org/Talks/Bernoulli...nLACC.pdf, slide 26) S_{k}(n) = (1)^(k+1) * S_{k}(n1) 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 = i1 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_{4}(3) = S_{4}(2) = (1 + 16) = 17 S_{4}(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_{5}(3) = +S_{5}(2) = 1 + 32 = 33 S_{5}(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 

07292019, 05:41 PM
(This post was last modified: 08012019 05:25 PM by Albert Chan.)
Post: #14




RE: (12C Platinum) Sums of Powers of N numbers
(07292019 04:12 AM)Albert Chan Wrote: Noticed a pattern with S_{k}(n) = Σi^k formula, when extend n to negative numbers: 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+1i)/(k+1i), {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 

« Next Oldest  Next Newest »

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