A085080 Smallest k such that n, k and n+k have the same prime signature (canonical form), or 0 if no such number exists.

0, 3, 2, 0, 2, 15, 0, 0, 0, 55, 2, 63, 0, 21, 6, 0, 2, 45, 0, 637, 14, 33, 0, 351, 0, 39, 0, 147, 2, 165, 0, 0, 6, 21, 22, 0, 0, 39, 26, 20237, 2, 231, 0, 325, 18, 39, 0, 4136875, 0, 18, 6, 423, 0, 135, 10, 1375, 34, 33, 2, 90, 0, 15, 12, 0, 21, 165, 0, 207, 22, 385, 2

Offset: 1

Author

Amarnath Murthy and Meenakshi Srikanth (menakan_s(AT)yahoo.com), Jul 01 2003

Keywords

• nonn

Comments

a(n) = 2 if n and n+2 form a twin prime pair.

a(n) = 0 if n is a perfect prime power or an odd prime such that n+2 is composite.

Here is a temporary list of integers <= 1000 for which a(n) is unknown (greater than a(48) or 0): 72, 200, 288, 432, 500, 648, 800, 864, 968, 972. - Michel Marcus, David A. Corneth, Mar 08 2019

a(96) = 1841996779; a(160) = 28521479; a(448) = 184390625; a(608) = 4633767. - Michel Marcus, Mar 08 2019

From David A. Corneth, Mar 08 2019: (Start)

By Fermat's Last Theorem, a(m^e) = 0 for e > 2 and positive integer m. For example, a(216) = a(6^3) = 0.

a(n) = 0 for squares < 1000, see worked example for n = 36 for the method.

a(192) = 30927921875, a(320) = 355182331, a(480) = 7771875, a(640) = 18243947439, a(832) = 194546043, a(896) = 2157109375, a(960) = 157546875. For the values to do, they are > 10^11 if a(n) > 0.

If n is even and a(n) > 0 and the exponent of 2 in the factorization of n is the largest in the prime signature then a(n) isn't necessarily odd. Ray Chandler found n = 392 as an example where a(n) = 108 is even. (End)

a(384) = 1281916327741, a(768) <= 1367088016014857. - Daniel Suteu, Mar 18 2019; confirmed by Michel Marcus, Mar 18 2019

a(768) = 85001950390625. - Ray Chandler, Mar 26 2019

Examples

			a(12) = 63 as 12 + 63 = 75, 2^2*3 + 3^2*7 = 5^2*3, all have the prime signature p^2*q.
a(1) = 0, because the only possible value for k is then 1, giving n+k=2, with a different signature.
a(2) = 3, because 2, 3 and 2+3=5 have the same prime signature.
a(36) = 0, because if a(n) exists then k exists such that k^2 + 36 = m^2 where k^2, 36 and m^2 have the same prime signature. Rewriting 36 = m^2 - k^2 = (m - k)*(m + k) and then inspection over divisors of 36 gives no terms. Alternatively checking Pythagorean triples gives the same result. - _David A. Corneth_, Mar 08 2019
		

Crossrefs

Cf. A085072 (only n and n+k have same prime signature), A215199.

Programs

Mathematica

a[n_?PrimeQ] := If[PrimeQ[n + 2], 2, 0]; a[2] = 3; a[36] = 0; ps[n_] := Sort[ FactorInteger[n][[;; , 2]] ]; a[n_] := Module[{k = 2, f = FactorInteger[n]}, ps0 = Sort[f[[;; , 2]]]; If[Length[f] == 1, 0, While[ps[k] != ps0 || ps[n + k] != ps0, k++]; k]]; Array[a, 71] (* Amiram Eldar, Mar 07 2019 works for n <= 71 *)

PARI

sigt(n) = vecsort(factor(n)[,2]~);
a(n) = {
  if ((n==1) || (isprimepower(n) && !isprime(n)), return(0));
  if (isprimepower(n) && !isprime(n), return(0));
  if ((n!=2) && isprime(n), if (isprime(n+2), return(2), return(0)));
  if (n==36, return(0));
  my(k=2, v = sigt(n));
  while ((sigt(k) != v) || (sigt(n+k) != v), k++);
  k;
} \\ Michel Marcus, Mar 07 2019; works for n <= 71

Extensions

a(20)-a(47) from Max Alekseyev, Aug 12 2013

a(48)-a(71) from Amiram Eldar, Mar 05 2019