Mathematrec

I’m still thinking about \((n-1)^{th}\) degree polynomials that generate the first \(n\) powers of 2 at the start. Which is rather a mouthful so I'm just going to call them p2 polynomials from here on. For instance, \(p2(5) = \frac{1}{24}(n^4-2n^3+11m^2+14m+24)\) generates the sequence 1, 2, 4, 8, 16, 31, 57, 99...

(By the way, this series of posts originally was prompted in part by this recent video by 3Blue1Brown which mentions the circle division problem I started off with — Moser's circle problem, it's called. This morning they posted another video which apparently goes into detail about the problem. I haven't watched it yet, but I'm sure it's worth watching.)

As I said before, it's easy to prove by induction that these polynomials, after giving you \(2^0\) through \(2^{n-1}\), go on to give you \(2^n-1\). Hence the 31 in \(p2(5)\).

But look at what comes after that: 31, 57, 99, 163, 256... hang on. 256 is \(2^8\). Are there any more powers of 2 after that? No, none that I've found anyway. So is that 256 just happenstance?

It appears it's not. It's the \((2n-1)^{st}\) entry in the sequence (if you count from 0). But if you look at other p2 polynomials, it always seems to be true that the \((2n-1)^{st}\) entry is \(2^{2n-2}\):

n	0	1	2	3	4	5	6	7	8	9	10	11
1	1	1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10	11	12
3	1	2	4	7	11	16	22	29	37	46	56	67
4	1	2	4	8	15	26	42	64	93	130	176	232
5	1	2	4	8	16	31	57	99	163	256	386	562
6	1	2	4	8	16	32	63	120	219	382	638	1024

I say “seems to be” because I've checked a lot of values of \(n\) and I always see this, but I have no idea yet how to prove it. It's not simple induction, since the entry in question is 2 entries further to the right in each row, with an ever increasing gap between the \(n+1\) values you can easily understand and the entry you're trying to understand, and bridging that gap would require understanding the numbers past the first \(n+1\) a lot better than I do.

Do any other powers of 2 appear? For \(n=2\) the answer's obviously yes, since it's just stepping through all the integers. For \(n=3\) the 90th entry is 4096, and for \(n=4\) the 23rd entry is 2048. Those doesn't seem to be part of any pattern, though. Maybe those two are indeed just happenstance. Other than that there aren't any others out as far as I’ve checked, to entry 800 for \(n\) up to 800.

At this point the numbers are getting way too big to print out and try to understand. So let's instead look at a plot. We'll draw an array of blocks. Each row of blocks is a p2 polynomial, columns are entries in each row, and a black block is drawn whenever the value is a power of 2. And just to make it more interesting, a red block is drawn whenever the value is 1 less than a power of 2. To make it more interesting still, anything else is colored blue if it’s even and yellow if it’s odd.

We expect the blocks below the main diagonal to be black — the \(n\) powers of 2 leading off — and then the blocks immediately right of the main diagonal should be red. We should see pairs of red and black blocks in the \(n=2\) row, and single isolated black blocks in the \(n=3\) and \(n=4\) rows. And a line of black blocks with slope \(-\frac{1}{2}\) at entry number \(2n-1\). And we do, and those are all the black or red blocks we find.

As for blue and yellow, they’re interesting…

Here’s the first 100 rows and columns:

Sierpinski triangles! Didn’t expect that. But no black or red blocks other than the ones enumerated above. Nor are there any more in the first 800 rows and columns:

So are there are any more powers of 2, beyond the big black triangle, the black line, and the ones we’ve seen for \(n<5\)? My guess is there are, but very rarely, because the size of the powers of 2 makes it very unlikely you’d hit one “randomly”.