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

%I #73 Jan 27 2023 21:49:17

%S 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,

%T 147,2,165,0,0,6,21,22,0,0,39,26,20237,2,231,0,325,18,39,0,4136875,0,

%U 18,6,423,0,135,10,1375,34,33,2,90,0,15,12,0,21,165,0,207,22,385,2

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

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

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

%C 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

%C a(96) = 1841996779; a(160) = 28521479; a(448) = 184390625; a(608) = 4633767. - _Michel Marcus_, Mar 08 2019

%C From _David A. Corneth_, Mar 08 2019: (Start)

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

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

%C 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.

%C 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)

%C a(384) = 1281916327741, a(768) <= 1367088016014857. - _Daniel Suteu_, Mar 18 2019; confirmed by _Michel Marcus_, Mar 18 2019

%C a(768) = 85001950390625. - _Ray Chandler_, Mar 26 2019

%e a(12) = 63 as 12 + 63 = 75, 2^2*3 + 3^2*7 = 5^2*3, all have the prime signature p^2*q.

%e a(1) = 0, because the only possible value for k is then 1, giving n+k=2, with a different signature.

%e a(2) = 3, because 2, 3 and 2+3=5 have the same prime signature.

%e 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

%t 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 *)

%o (PARI) sigt(n) = vecsort(factor(n)[,2]~);

%o a(n) = {

%o if ((n==1) || (isprimepower(n) && !isprime(n)), return(0));

%o if (isprimepower(n) && !isprime(n), return(0));

%o if ((n!=2) && isprime(n), if (isprime(n+2), return(2), return(0)));

%o if (n==36, return(0));

%o my(k=2, v = sigt(n));

%o while ((sigt(k) != v) || (sigt(n+k) != v), k++);

%o k;

%o } \\ _Michel Marcus_, Mar 07 2019; works for n <= 71

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

%K nonn

%O 1,2

%A _Amarnath Murthy_ and Meenakshi Srikanth (menakan_s(AT)yahoo.com), Jul 01 2003

%E a(20)-a(47) from _Max Alekseyev_, Aug 12 2013

%E a(48)-a(71) from _Amiram Eldar_, Mar 05 2019