A300903 a(n) is the smallest k such that k^2 - n^2 is a prime power (A000961), or 0 if no such k exists.

1, 2, 3, 4, 5, 6, 7, 9, 9, 10, 15, 12, 13, 14, 15, 16, 48, 0, 19, 0, 21, 22, 0, 24, 25, 0, 27, 54, 36, 30, 31, 33, 96, 34, 0, 36, 37, 0, 0, 40, 41, 42, 0, 0, 45, 0, 0, 0, 49, 0, 51, 52, 0, 54, 55, 66, 57, 0, 0, 0, 61, 0, 63, 64, 192, 66, 0, 0, 69, 70, 0, 0, 0, 0, 75, 76, 0, 0, 79, 0, 0, 82, 0, 84, 85, 0, 87, 0, 0, 90, 91, 0, 0, 0, 0, 96, 97

Offset: 0

Author

Altug Alkan, Mar 14 2018

Keywords

• nonn
• easy

Comments

If such k exists (for n > 0), then the maximum ratio of k / n is (p + 1)/(p - 1) with p = 2 where p is prime root of corresponding prime power. So a(n) <= 3*n.

If 2*n+1 is in A000961 (in particular if n is in A005097), then a(n) = n + 1.

Numbers n such that a(n) = 0 are 17, 19, 22, 25, 34, 37, 38, 42, 43, 45, 46, ...

Initial corresponding prime powers are 1, 3, 5, 7, 9, 11, 13, 32, 17, 19, 125, 23, 25, 27, 29, 31, 2048.

Examples

			a(17) = 0 because there is no k such that k^2 - 17^2 = (k + 17)*(k - 17) is a prime power.
a(21) = 22 because 22^2 - 21^2 = 43 and 22 is the least number with this property.
a(27) = 54 because 54^2 - 27^2 = 3^7 and 54 is the only number with this property.
		

Crossrefs

Cf. A000961, A005097, A024352.

Programs

Maple

f:= proc(n) local p,k,a,b,r;
  if nops(numtheory:-factorset(2*n+1))<=1 then return n+1 fi;
  k:= infinity;
  for p in numtheory:-factorset(2*n) do
    b:= padic:-ordp(2*n,p);
    r:= 2*n + p^b;
    a:= padic:-ordp(r,p);
    if r = p^a then
      k:= min(k, (p^a+p^b)/2)
    fi
  od;
  if k = infinity then 0 else k fi
end proc:
map(f, [$0..1000]); # Robert Israel, Mar 15 2018

Mathematica

Table[Boole[n == 0] + Block[{k = n + 1, m = 3 n}, While[Nor[PrimePowerQ[k^2 - n^2], k > m], k++]; If[k > m, 0, k]], {n, 0, 96}] (* Michael De Vlieger, Mar 16 2018 *)

PARI

a(n) = if(n==0, 1, for(k=n+1, 3*n, if(isprimepower(k^2-n^2), return(k)));0)