|
|
EXAMPLE
|
k = 9: 2^9 - 1 = 7*73 (not a prime), and we have 2*(2^9-1) + 7 = 7^3 is 7-smooth and 2*(2^9-1) + 73 = 3*5*73 is 73-smooth, so 9 is a term.
k = 67: 2^67 - 1 = 193707721*761838257287 (not a prime), and we have 2*(2^67-1) + 193707721 = 3*5^2*16033*1267117*193707721 is 193707721-smooth and 2*(2^67-1) + 761838257287 = 3*5011*25771*761838257287 is 761838257287-smooth, so 67 is a term.
k = 137: 2^137 - 1 = 32032215596496435569*5439042183600204290159 (not a prime), and we have 2*(2^137-1) + 32032215596496435569 = 379*28702069570449626861*32032215596496435569 is 32032215596496435569-smooth and 2*(2^137-1) + 5439042183600204290159 = 9007*7112738002996877*5439042183600204290159 is 5439042183600204290159-smooth, so 137 is a term.
|
|
|
PROG
|
(PARI) gpf(n) = vecmax(factor(n)[, 1]);
ispsmooth(n, p, {lim=1<<256}) = if(n<=lim, n==1 || gpf(n)<=p, my(N=n/p^valuation(n, p)); forprime(q=2, p, N=N/q^valuation(N, q); if((N<=lim && isprime(N)) || N==1, return(N<=p))); 0); \\ check if n is p-smooth, using brute force if n is too large
isA354532(n, {lim=256}, {p_lim=1<<32}) = {
my(N=2^n-1);
if(isprime(N), return(0));
if(n>lim, forprime(p=3, p_lim, if(N%p==0 && !ispsmooth(2*N+p, p), return(0)))); \\ first check if there is a prime factor p <= p_lim of 2^n-1 such that 2*(2^n-1)+p is not p-smooth (for large n)
my(d=divisors(n));
for(i=1, #d, my(f=factor(2^d[i]-1)[, 1]); for(j=1, #f, if(!ispsmooth(2*N+f[j], f[j], 1<<lim), return(0)))); 1 \\ then check if 2*(2^n-1)+p is p-smooth for p|2^d-1, d|N
}
|
