Expression 2^j + q^j below q = prime <= prime provided always prime at j=0; or for j=1 if q is a lesser-twin-prime; or more rarely 3 or 4 primes [four ones at q=3,5,17,37,59,137,179,223,461]; never found 5 or more relevant primes and the corresponding exponents proved to be powers of 2. Formal proofs of observations wanted.
See comment by Michael Somos, Aug 27 2004 for proof that j must be zero or a power of 2. - Robert Price, Apr 30 2013
Since the number j must be zero or a power of 2, checked j being powers of two through 2^19. Thus a(5) > 10^2400000. Primes of this magnitude are rare (about 1 in 5.6 million), so chance of finding one is remote with today's computer algorithms and speeds. - Robert Price, Apr 30 2013