@JosephAdams Consider the wreath product structure of the Lamplighter group. All you need to do is to choose $i$ and $j$ in such a way that $a^ib^j$ lies in the base group.

@SidharthGhoshal If undocumented GAP code helps you, I can send it to you by email. Just let me know!

Just a minor issue: why $100^{1000}$, and not $1000^{100}$?

I sent a message to the CM team with respect to account merge.

This question has been answered by Denis Shatrov here.

@GerryMyerson I added a reference (quickly found by googling for the sequence of numbers which can be represented as a sum of a prime number and a nonnegative perfect power in exactly one way).

@GerryMyerson I just ran a little GAP program out of idle curiosity. Googling for 1771561 didn't immediately turn up anything useful, otherwise I would have included a link (e,g, the proofwiki one).

@GerryMyerson 0 and 1 are counted as perfect powers of nonnegative integers (it would seem artificial to exclude them, doesn't it?). So, $5 = 5+0^2$, $8 = 7+1^2$, $24 = 23+1^2$ and $1549 = 1549+0^2$.

@GerryMyerson May it be that you confused "perfect power of a nonnegative integer" and "prime power"? -- We have $905 = 5 + 30^2 = 229 + 26^2 = 421 + 22^2 = 709 + 14^2 = 761 + 12^2$. I am not aware of a reference at the moment.

On MathOverflow, when citing a paper of one's own, it is customary to explicitly disclose that it is a paper of one's own.

@DenisShatrov If the smallest solution would be large enough, that equation would make an excellent answer to the question.

Well — but doesn't the Pell equation in this always have the solution $(x,y) = (N^4,1)$, or did I misread something?