art with code

2009-06-13

Sum representation of integer powers

The power xn where x,n ∈ N can be represented as an nth-order sum where the innermost factor is n!.

First, consider x1: the difference between x1 and (x+1)1 is 1. So we have a first-order sum where the innermost factor is 1! (= 1.)

x^1 = sum(i = 0..x, 1)

Now let's look at x2. Let's write the sequence of x2 from -3 to +3 and mark under each two elements the difference between them:

9 4 1 0 1 4 9
-5 -3 -1 1 3 5
2 2 2 2 2

From this we see that we have a second-order sum where the innermost factor is 2! (=2) and the outer factor is -1 (going diagonally left from zero.)

x^2 = -1*sum(i = 0..x, 2*i*sum(j = 0..i, 1))

We can now give a recursive function for the sums that takes a list of factors as its argument (this one only works for positive integers though):

sumMap lst f = sum (map f lst)

sums [] i = 0
sums [x] i = x * i
sums (x:xs) i = x*i + sumMap [0..i] (sums xs)

Then, let's look at the left side of x6:

46656 15625 4096 729 64 1 0 1
-31031 -11529 -3367 -665 -63 -1 1
19502 8162 2702 602 62 2
-11340 -5460 -2100 -540 -60
5880 3360 1560 480
-2520 -1800 -1080
720 720

From which we get the factors [-1, 62, -540, 1560, -1800, 720] and

x^6 = -1*sum(a=0..x, 62*sum(b=0..a, -540*sum(c=0..b, 1560*sum(d=0..c, -1800*sum(e=0..d, 720*sum(f=0..e, 1))))))
or
pow6 = sums [-1, 62, -540, 1560, -1800, 720]

In the general case, the first factor is -1(n-1), the second factor is -2n + 2 * -1n, the second to last factor is -(n-1)n! * 2-1 and the last factor is n!. I don't know about the rest of the factors.

Fun with cubes


Here's the difference grid for the third power:

-27 -8 -1 0 1 8 27
19 7 1 1 7 19
-12 -6 0 6 12
6 6 6 6

Which gives the factors [1, -6, 6].

One result of the sum representation is that each x cubed minus x is divisible by 6: 6 | x3 - x. Or put another way, x3 = x + 6k, k ∈ Z. And the sum between two cubes minus the sum of the bases is also divisible by six: 6 | x3 + y3 - (x + y).

We also see that the difference between any two integer cubes grows as a second order function: n3 - (n-1)3 = 6(n/2)(n+1)+1 = 3n2+3n+1.

cubeDiff n = 3*(n^2 + n) + 1
pow3 n = sumMap [0..n-1] cubeDiff

-- pow3 5
-- 125

There's another amusing difference grid in (x3 - x) / 6:

0 1 4 10 20 35 56 84
1 3 6 10 15 21 28
2 3 4 5 6 7
1 1 1 1 1
Post a Comment

About Me

My photo

Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes, much bad code, much bad art.

Have freelanced for Verizon, Google, Mozilla, Warner Bros, Sony Pictures, Yahoo!, Microsoft, Valve Software, TDK Electronics.

Ex-Chrome Developer Relations.