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?)
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:
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]
[1, 4, 9, 16, ...] -> [3, 5, 7, ...] -> [2! forever]
[1, 8, 27, 64, 125, ...] -> [7, 19, 37, 61, ...] -> [12, 18, 24, ...] -> [3! forever]
[1, 16, 81, 256, 625, 1296, ...] -> [15, 65, 175, 369, 671, ...] -> [50, 110, 194, 302, ...] -> [60, 84, 108, ...] -> [4! forever]
[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.)