Tanya's sequence

[David Wilson]

Tanya's original question was, which numbers are not of the form prime + 
nonzero perfect power?

Tanya Khovanova effectively asked which numbers were not of the form prime + 
nonzero perfect power (A000040 + A001597). Let us call this Tanya's 
sequence.

Noting that the nonzero squares are a subset of the nonzero perfect powers, 
Tanya's sequence is a subsequence of the numbers that are not of the from 
prime + nonzero square, A064233.

We find that A064233 = (A020495 U A065377) U (squares of elements of 
A053726).

With high probability, the sequences A020495 and A065377 as given in the 
OEIS are finite and complete. If this is indeed the case, which is highly 
probable, the largest element of (A020495 U A065377) is 21679, and all 
larger numbers in A064233 would be squares of elements of A053726.

As Tanya's sequence is a subsequence of A064233, this would imply that all 
elements of Tanya's sequence that are > 21679 are squares of elements of 
A053726, e.g, the 1771561 = 1331^2.  This observation greatly reduces the 
computation required to check Tanya's sequence.