login
Numbers n such that n^2 + 1 = p*q, p < q primes and q-p is a power of 2.
1

%I #19 Oct 19 2014 05:44:22

%S 8,100,3524,5084,36680,77980,21474824,134201344,148647496,300741464,

%T 73851531256,153122539756,778318386944,6669171349484,16526971109344,

%U 596403262068016,9376599920124524,26698166963373164,140144514160214876,1613032378604451500

%N Numbers n such that n^2 + 1 = p*q, p < q primes and q-p is a power of 2.

%C Note that if n^2+1 = p*q, then p+q cannot be a power of 2. Proof by contradiction: There are two cases: p an odd prime and p=2. Case 1: suppose p and q are odd primes and q = 2^m-p. Then p(2^m-p) = n^2+1 for some even n. Rearranging terms, we obtain p*2^m-1 = p^2+n^2. Looking at this equation modulo 4, we obtain -1 = 1, a contradiction. Case 2: Let p=2. Then we obtain 2^(m+1)-n^2 = 5, which has no solutions in integers.

%H Giovanni Resta, <a href="/A238947/a238947.txt">Some terms greater than a(20)</a>

%e 8^2+1 = 65 = 5*13 and 13-5 = 2^3;

%e 100^2+1 = 10001 = 73*137 and 137-73 = 2^6;

%e 3524^2+1 = 12418577 = 3049*4073 and 4073-3049 = 2^10.

%p with(numtheory):for a from 1 to 200000 do:p:=ithprime(a):for i from 1 to 50 do:q:=p+2^i:if type(q,prime)=true then x:=sqrt(p*q-1):if x=floor(x) then print(x):else fi:fi:od:od:

%t Select[Range[10^6],!PrimeQ[#^2+1]&&Plus@@Last/@FactorInteger[#^2+1]==2&&PrimeNu[#^2+1]==2&&IntegerQ[Log[2,FactorInteger[#^2+1][[2]][[1]]-FactorInteger[#^2+1][[1]][[1]]]]&

%o (PARI) isok(n) = (bigomega(n^2+1) == 2) && (f = factor(n^2+1)) && ((f[2, 1] - f[1, 1])== 2^(valuation(f[2, 1] - f[1, 1], 2))); \\ _Michel Marcus_, Mar 07 2014

%Y Cf. A134406, A134407, A002522.

%Y Subsequence of A085722.

%K nonn,hard

%O 1,1

%A _Michel Lagneau_, Mar 07 2014

%E a(7)-a(20) from _Giovanni Resta_, Mar 07 2014