A puzzle I saw via @HAClaphamSixth, but whose originator they don’t know:

What integer pairs $(n,k)$ satisfy $n! + 8 = 2^k$? How do you know you have them all?

This is not a problem I know the answer to! I shall attempt problem-solving out loud, with spoilers below the line!

—

Two thoughts jumped to mind:

  • 24 + 8 = 32, so $(4,5)$ works. (Brute force some solutions)
  • 8 is also a power of 2.

The first observation is a nice answer, but nothing like a solution. The second feels more likely to be productive.

So, we can rewrite our criterion as $n! = 2^k - 2^3$, or even $n! = 2^3\left(2^{k-3}-1\right)$.

That makes it clear that $n=4$ is the smallest that can possibly work – 24 is the first factorial that’s a multiple of 8.

At this point, I’m drawn to the fact that all of the factorials larger than 4! end in 0. Explore your hunches.

So, we’re only going to have other solutions when $2^{k-3}-1$ is a multiple of 5 – which only happens when $2^{k-3}$ ends in a 6.

In fact, I’m going to change my notation and go back to $2^k - 8$ as my expression of interest. It’s a bit easier to work with – and now I need $2^k$ to end in 8.

That happens for $k = 3, 7, 11, \dots, 4a-1, \dots$ . Clearly it doesn’t work for $k=3$ because 0 is not a factorial number, but how about 7? 128 - 8 = 120, which is 5! and we have a second solution of $(5,7)$.

Let’s look at $k=11$, which gives us 2040, which isn’t a factorial. $k=15$ gives 32,760, which is again not a factorial, and $k=19$ gives 524,280. Nope.

$k=23$ is also a fail, but an interesting one: it’s 8,388,600 – this is the first one (discounting, in some sense, 0) that ends in two zeros, as all of the factorials beyond this point will. From here, we’d need to look up in 20s rather than in fours.

$k=43$ gives 8,796,093,022,200, which is between 15! and 16! – and these end with three zeros rather than just 2.

$k=103$ is the first power of two that ends 008, but the factorials at this point end in five zeros! I wonder if there’s an idea here.

I’m looking for $k$ such that $2^k \pmod {10^p} \equiv 8$, with $k> 3$. That’s a bit tedious.

Aha! A judicious application of the think carefully before you do hard work principle pays dividends! It’s not 10s I should be looking at, it’s 2s. Or rather, 16s.

Every factorial from 6! and up is a multiple of 16. But $2^k - 8$ is not a multiple of 16 unless $k=3$ – for $k>3$, it’s always 8 away from a multiple of 16.

Therefore, any solutions to $n! +8 =2^k$ must have $n < 6$ – and we’ve examined all of those cases already!

So the only solutions are $(4,5)$ and $(5,7)$. Neat!

—

Did you approach it differently? Do tell me all about it!