# Primality of $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , when $q$ is prime, $j\ge0$?

Let $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , $q$ prime and $j\ge0$.

$P_{2,j}$ is a Fermat number, $P_{q,0}$ is a Mersenne number. Apart from Fermat primes and Mersenne primes, and apart from
$P_{3,1}=73$,
$P_{3,2}=262657$
and $P_{7,1}=4432676798593$,
which other $P_{q,j}$ are known to be prime?

In the same spirit:

Let $Q_{p,j}=(2^{p.2^j}+1)/(2^{2^j}+1)$, $p$ prime and $j\ge0$.

$Q_{p,0}$ is a Wagstaff number. Apart from Wagstaff primes, and apart from
$Q_{3,1}=13$,
$Q_{3,2}=241$,
$Q_{3,5}=18446744069414584321$,
$Q_{5,2}=61681$,
$Q_{5,3}=4278255361$,
$Q_{7,2}=15790321$,
$Q_{13,3}=78919881726271091143763623681$,
$Q_{23,2}=291280009243618888211558641$,
and $Q_{37,2}=20988936657440586486151264256610222593863921$,
which other $Q_{p,j}$ are known to be prime? I believe that $Q_{p,1}$ is always composite for $p\gt3$, because of the Aurifeuillean factorization.

I have tried indexes as big as I can, but I can't find any new prime $P_{q,j}$ nor any new prime $Q_{p,j}$.
Is there any efficient primality test for these kind of numbers, like for the regular Mersenne numbers?

• Side note: for a fixed $q$ and $j$, the cyclotomic polynomial $\Phi_{q^{j+1}}(x) = (x^{q^{j+1}}-1)/(x^{q^j}-1)$ is irreducible and thus conjecturally takes a prime value for infinitely many positive integers $x$. – Greg Martin Mar 8 '14 at 20:31
• Thank you for the note. Would the same conjecture, if true, mean that there are infinitely many prime $P_{q,j}$ or $Q_{p,j}$? .. I don't see how. – René Gy Mar 10 '14 at 20:47
• Not the same conjecture, no, because it deals only with polynomial sequences, not exponential ones like this. I suspect the heuristics for whether there are infinitely many primes would be very similar to those for Mersenne primes (of which we suspect there are infinitely many) and Fermat primes (of which we suspect there are only finitely many). – Greg Martin Mar 10 '14 at 21:37