Generalize finding perfect squares by adding odd numbers

Question

I was doing a iterator-based Sieve of Eratosthenes (in Swift). I was using the variant where the detector for prime X wouldn't be inserted until I counted up to X^2. Instead of multiplying each cycle to get the square, I had a register starting with 1 and updated it by adding increasing odd numbers.

My mind wandered to reading something years ago that there a similar rule for cubes. I couldn't figure it out back then, but realized something when I tried it out this week. Unlike squares, where the difference between them increases by two, the difference between cubes increases by values that themselves increase by six each time.

Now I wondered if this can be generalized. I stumbled onto Perfect Power and saw the seed for fourth-powers was 24 = 4!. I didn't realize that the seed for cubes being 6 = 3! was important.

I'm thinking of number registers. For each power, there is a result register initialized with 1. (1 to any power is 1.) For power 0, there are no other registers; all later integers also have 1 as their 0th power. For power 1, I add delta register initialized to 1. Each update adds that value to the result register; so I get each increasing integer.

I add a second delta register when computing squares, initialized to two. That value gets added to the first delta register, which gets added to result register. For cubes, I add a third delta register that's initialized to six.

Now I'm stuck, if I got the pattern right, I need a fourth delta register for fourth-powers, and initialize it to 24. But how can I get the first-order delta register to be 15 (to go from 1 to 16) just by adding? I'm missing something here.

(The math gets hairy, finding the difference between (n + 1)^K and n^K, finding the difference for that difference, finding the register seeds, etc. No one ever tried this before?)

Update 1

Instead of going crazy figuring it out algebraically, I tried some samples with pencil & paper.

For power 0, we have 0 registers besides the result:

1 |

So the list of answers, the whole numbers to the zero-power, is 1 forever.

For power 1, we have 1 delta register:

1 | 1

So the list of answers increases by 1 (= 1!) every turn, giving the list of whole numbers (1, 2, 3...).

For power 2, we have 2 delta registers:

1 | 1 2

Every turn, the 2 (= 2!) is added to the first-order delta register, then that register is added to the result register. This leads to the square numbers (1, 4, 9, ...).

For power 3, I thought about it like this: we have the first-order delta register set to 7, and use only it during the first turn. In the second turn, we use the second-order register, initialized to 12, to increase first-order delta register, which is then used to increase the result register. In the third and later turns, we use the third-order register, initialized to a constant 6 (= 3!), to increase the second-order, first-order, and result registers in a cascade in that order.

(I came up with that idea while looking at the difference chart I made for the fourth power. This means I need to revise my square register set to "1 | 3 2," not using its second-order register until the second turn.)

The charts I made are adjacent differences. For the first power:

[1, 2, 3, ...] -> [1! forever]

Second:

[1, 4, 9, 16, ...] -> [3, 5, 7, ...] -> [2! forever]

Third:

[1, 8, 27, 64, 125, ...] -> [7, 19, 37, 61, ...] -> [12, 18, 24, ...] -> [3! forever]

Fourth:

[1, 16, 81, 256, 625, 1296, ...] -> [15, 65, 175, 369, 671, ...] -> [50, 110, 194, 302, ...] -> [60, 84, 108, ...] -> [4! forever]

Fifth:

[1, 32, 243, 1024, 3125, 7776, 16807, ...] -> [31, 211, 781, 2101, 4651, 9031, ...] -> [180, 570, 1320, 2550, 4380, ...] -> [390, 750, 1230, 1830, ...] -> [360, 480, 600, ...] -> [5! forever]

The pattern is that, for power K:

• I need to make delta register array of K elements
• Element 1 is $2^K - 1$, Element K is $K!$, but the ones in-between aren't obvious. I can compute $1^K$ through $(K + 1)^K$ manually through repeated multiplication, then build the K rounds of adjacent differences to get the seed values for the delta registers. (The seed values are the first element of each differences array. For example, the fourth-power seeds are [15, 50, 60, 24].) Since the whole point of this iteration technique is to do repeated adding to avoid multiplying, needing front-load the adding with a multiplication-heavy preparation phase seems disappointing. The core question of this post: is there a way to build the list of seeds without calculating the first $K+1$ Kth powers first? (If I use multiplication, I won't need answers via iteration until the $(K + 2)$-th turn.)
• When iterating, I don't involve the Nth-order register until turn N. (That means once we get to turn K, all the delta registers are used from then on.)

My trial work that lead to this update made things easier for me to understand. Hopefully it'll help all of you too. (Maybe it'll remind someone of something easy in a really advanced math book.)

Answer 1

Pascal's Triangle and the link from Math Forum helped me piece it together. I figured out how to un-hairy finding all the differences.

The point of this exercise is to go from $n^K$ to $(n + 1)^K$ just by adding. The expansion of the latter is $\sum_{i = 0}^{K} \binom{K}{i} n^i$. We're taking the difference, which is just the highest-order term cut off (i.e. $\sum_{i = 0}^{K - 1} \binom{K}{i} n^i$ instead).

The iteration starts from 1, so we substitute that into the polynomial when we need actual numbers. The answer is just all the coefficients added together.

I also defined a computer algorithm to get a polynomial (defined as an ordered list) in $n$ to $n + 1$. The updated polynomial keeps the same degree and highest-order coefficient as the original. Use the expansion of lower powers of $n + 1$ with a cached storage of Pascal's Triangle for the update. It'll involve $K^{th}$ triangle number ($= \binom{K + 1}{2}$) of multiplies and $(K - 1)^{th}$ triangle number of adds.

So now I got the first-order difference and the next step from it. Subtracting these gives us the second-order difference! (Note that the degree always goes down by 1.) That subtracting involves $K$ regular subtractions (or $K - 1$ if you elide that highest-order coefficient).

Like the first-order difference, substituting 1 into $n$ in the new polynomial (i.e. adding the coefficients) gives the second-order seed. The procedure can be applied again to get the third-order seed, and so on to the constant $K^{th}$-order seed.

The whole seed list would need the $K^{th}$ tetrahedral number ($= \binom{K + 2}{3}$) multiplications, $(K - 1)^{th}$ tetrahedral number additions, and $K^{th}$ triangle number subtractions.

Before figuring this out, I tried the brute-force way with finding the $1^K$ through $(K + 1)^K$ powers, then building the pyramid of adjacent differences. With naive exponentiation, I would need $K(K + 1)$ multiplications and $K^{th}$ triangle number subtractions.

The brute-force method also generates a lot of deltas, where the new method only generates two per level (just enough to get the first next-order delta). But the new method trades a huge multiplication block for a distributed block to build Pascal's Triangle, which just uses additions. Maybe someone here could figure out which method is best (including if there's a trade-off point between the two at a given $K$).

Example

For cubes, we're going from $n^3$ to $(n + 1)^3$. The latter is $n^3 + 3 n^2 + 3 n + 1$, giving a difference of $3 n^2 + 3 n + 1$. Filling in 1 for $n$ gives the first-order delta of 7.

Substituting $n + 1$ for $n$ in the $3 n^2 + 3 n + 1$ gives us the second first-difference, $3 n^2 + 9 n + 7$. The difference between those elements is form of the first second-difference: $6 n + 6$. Substituting 1 for $n$ gives the second-order delta of 12.

Doing the $n \rightarrow n + 1$ progression again gives the second second-difference, $6 n + 12$. Subtract to get the first third-difference of 6. Since this is a constant (and therefore the value of all subsequent third-differences), we also have the third-order delta and stop.