The Nagell-Ljunggren Equation

1 + 3 + 9 + 27 + 81 = 121

This raised many questions. How did I not know this already?! Were there other examples? Was there some pattern that I was completely unaware of? I ran a quick search for examples with right-hand side less than a million, and found two more.

1 + 18 + 324 = 343
1 + 7 + 49 + 343 = 400

Using that information, I searched on OEIS for “121,343,400” and found the sequence A208242. From the remarks there, I learned that the equations above represent the only known solutions of the Nagell-Ljunggren equation (xⁿ−1)/(x−1) = y^q (with n ≥ 3 and x, y, q ≥ 2), and that the number of other solutions is probably finite, possibly zero.

Just for fun I also searched on Google for “Nagell-Ljunggren” and found a paper that mentioned a fourth solution with x = −19.

1 − 19 + 361 = 343

This all seemed tantalizingly familiar. The solution with powers of 7 summing to 400 clearly had something to do with my favorite number 2401 (see for example Powers of N and near the end of Multiplication in Base 10), and the solutions with powers of 18 and 19 summing to 7³ … surely it couldn't be a coincidence that 7 is a double exception in bases 18 and 19? I felt like I was on the verge of discovering some amazing unifying principle.

In fact, I was on the verge of being disappointed on several levels. I'd forgotten that most of the special qualities of 2401 derive from the fact that 5 is an exception in base 7. So, there was no unifying principle, just a connection between Nagell-Ljunggren solutions and exceptions. The connection was weak, too. It only worked in one direction—solutions lead to exceptions, but not vice versa—and it wasn't even guaranteed to work. Worst of all, I'd forgotten that I'd seen one of the solutions before and put it in an essay. It's right there near the end of Multiplication in Base 10.

The situation isn't a complete loss, though. The Nagell-Ljunggren solutions are nice, especially the one with powers of 3 summing to 11². It's nice to have a reason that some numbers are exceptions, even if all it really does is replace “it happens to be an exception” with “it's an exception because it happens to be a solution of the Nagell-Ljunggren equation”. It also turns out that there's a pattern I'd never noticed. If you look back at the solutions with x = 18 and −19, you can see that they're related. The relationship can be expressed in terms of sharps and flats.

324 + 18 = 18^♯ = 19^♭ = 361 − 19.

With that clue, it's easy to prove that there's a pattern: if x is a solution with n = 3, then so is −(x+1). Of course, there are no other solutions with n = 3, so it's a pattern with only one instance. But, we'll see that there's a similar pattern for exceptions, and that it has at least three instances. That's the pattern I'd never noticed.

By the way, there really are no other solutions with n = 3. According to that paper, if there are any other solutions of the Nagell-Ljunggren equation, then among other things, n is not divisible by 2 or 3.

That's pretty much the whole story. Later I ran another search and found a few other nice identities.

Other Identities

I also wrote down a bunch of other stuff. It doesn't add much to what I've already said, I just wanted to have it on the record because when I revisited Repeat Length Again I was annoyed that I'd glossed over so many details.

Mathematical Results
Exception Patterns
Tables of Exceptions