Other Identities

P(x,n) = xn
S(x,n) = xn	+ xn−1 + xn−2 + … + x + 1
A(x,n) = xn	− xn−1 + xn−2 − … + (−1)n−1x + (−1)n

The left-hand side of the Nagell-Ljunggren equation is S(x,n−1), but for this one essay let's shift the allowed values of n by 1, then we can write the equation as simply S(x,n) = P(y,q) with all parameters at least 2.

What about solutions with negative x? Wouldn't we like to find those too? Yes, but it turns out that's the wrong way to think about it. If x is negative, then the sign of S(x,n) depends on the value of n, and we effectively lose half of the possible values (since P(y,q) is always positive). In fact, we have the following identities (now with positive x).

P(−x,n) = (−1)n	P(x,n)
S(−x,n) = (−1)n	A(x,n)
A(−x,n) = (−1)n	S(x,n)

However, those identities also show us how to fix the problem. Instead of looking for solutions with negative x, we should look for solutions to a different equation, A(x,n) = P(y,q).

Then, as long as we're doing that, we might as well take all the values of the functions P, S, and A with all parameters at least 2, throw them into a single big pile, and look through it for duplicates of any kind whatsoever. So, that's what I did. With a nice algorithm (priority queue of possible next values), even my poor old computer was able to check for duplicates up to 10²⁰ in just a few hours. Here are the identities it found.

0. A Boring Pattern

If n is a composite number, then the following identity holds for every nontrivial divisor d.

P(x,n) = P(x^d,n/d)

Here's an example.

P(3,6) = P(9,3) = P(27,2)

729	= 36
	= 93
	= 272

1. A Pattern We Already Knew About

Here's a simple identity that I think about in terms of sharps and flats.

x² + x = x^♯ = (x+1)^♭ = (x+1)² − (x+1)

If we add 1 to both sides, we obtain this relation between S and A.

S(x,2) = A(x+1,2)

Here's one example. There will also be several more examples below.

S(10,2) = A(11,2)

111	= 100 + 10 + 1
	= 121 − 11 + 1

2. A New Pattern

I was quite surprised when I saw this identity in the search results.

S(4,n) = A(2,2n+1)

However, it's pretty easy to understand if we use negative digits and binary. In base 10, 11 = 9, but in base 2, 11 = 1. So, for example,

A(2,5) = 111111 = 10101 = 100² + 100 + 1 = S(4,2).

Note that if you try to do the same thing with an even exponent, it doesn't lead anywhere.

A(2,6) = 1111111 = 101011

S(4,2) is also the only value that appears in two different patterns. Here are both patterns together written out in decimal.

A(2,5) = S(4,2) = A(5,2)

21	= 32 − 16 + 8 − 4 + 2 − 1
	= 16 + 4 + 1
	= 25 − 5 + 1

3. Nagell-Ljunggren Solutions

Of course I didn't find any new solutions to the Nagell-Ljunggren equation.

P(11,2) = S(3,4)

121	= 112
	= 81 + 27 + 9 + 3 + 1

P(7,3) = S(18,2) = A(19,2)

343	= 73
	= 324 + 18 + 1
	= 361 − 19 + 1

P(20,2) = S(7,3)

400	= 202
	= 343 + 49 + 7 + 1

I also didn't find any new solutions to A(x,n) = P(y,q). I think in theory it should be possible to have solutions that aren't related to Nagell-Ljunggren solutions, but in practice there just aren't any.

4. Four Other Identities

There are four other identities that don't fit into any pattern.

S(2,4) = S(5,2) = A(6,2)

31	= 16 + 8 + 4 + 2 + 1
	= 25 + 5 + 1
	= 36 − 6 + 1

A(2,6) = S(6,2) = A(7,2)

43	= 64 − 32 + 16 − 8 + 4 − 2 + 1
	= 36 + 6 + 1
	= 49 − 7 + 1

S(10,3) = A(6,4)

1111	= 1000 + 100 + 10 + 1
	= 1296 − 216 + 36 − 6 + 1

S(2,12) = S(90,2) = A(91,2)

8191	= 4096 + 2048 + 1024 + 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1
	= 8100 + 90 + 1
	= 8281 − 91 + 1

My favorite is the third one! Note that S(x,n) is always a repunit in base x.

Three of the identities are confusingly similar. I made a table with the idea that it might help, but it didn't do much for me.

21	= A(2,5)	= S(4,2)	= A(5,2)
31	= S(2,4)	= S(5,2)	= A(6,2)
43	= A(2,6)	= S(6,2)	= A(7,2)

Anyway, that's all the identities I found, and probably also all the identities there are. I don't have any proof, of course, but I do have some circumstantial evidence.

• As I said earlier, people seem to think it's possible that we've already found all the solutions to the Nagell-Ljunggren equation.
• Catalan's conjecture, now a theorem, is that there's only one solution to the equation P(x,n) = P(y,q) + 1.
• The Wikipedia article about Catalan's conjecture has a nice section about the generalized equation P(x,n) = P(y,q) + C. That too seems to have a finite number of solutions for each value of C.
• The sets of values we're discussing (values of P, S, and A, values of P shifted by a constant) are equally sparse, with one value near each power xⁿ.
• So, it makes sense that the number of solutions to any such equation ought to be finite (unless there's a pattern).