A085072 Smallest k such that n and n+k have the same prime signature.

1, 2, 5, 2, 4, 4, 19, 16, 4, 2, 6, 4, 1, 6, 65, 2, 2, 4, 8, 1, 4, 6, 16, 24, 7, 98, 16, 2, 12, 6, 211, 1, 1, 3, 64, 4, 1, 7, 14, 2, 24, 4, 1, 5, 5, 6, 32, 72, 2, 4, 11, 6, 2, 2, 32, 1, 4, 2, 24, 6, 3, 5, 665, 4, 4, 4, 7, 5, 8, 2, 36, 6, 3, 1, 16, 5, 24, 4, 32, 544, 3, 6, 6, 1, 1, 4, 16, 8, 36, 2

Offset: 2

Author

Amarnath Murthy, Jul 01 2003

Keywords

• nonn

Examples

			a(28) = 17 as 28 = 2^2*7 and 28+17 = 45 = 3^2*5, both have the prime signature p^2*q where p and q are primes.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..20000

Crossrefs

Cf. A046523, A081761, A085073.

Programs

Maple

s:= n-> sort(map(i-> i[2], ifactors(n)[2])):
a:= proc(n) option remember; local k;
      for k while s(n)<>s(n+k) do od; k
    end:
seq(a(n), n=2..100);  # Alois P. Heinz, Feb 28 2018

Mathematica

s[n_] := Sort[FactorInteger[n][[All, 2]]];
a[n_] := Module[{sn = s[n], k}, For[k = 1, True, k++, If[sn == s[n+k], Return[k]]]];
a /@ Range[2, 100] (* Jean-François Alcover, Nov 02 2020 *)

PARI

a(n) = {my(k=1, s = vecsort(factor(n)[,2]~)); while (vecsort(factor(n+k)[,2]~) != s, k++); k;} \\ Michel Marcus, Nov 02 2020

Formula

a(prime(k)^r) = prime(k+1)^r- prime(k)^r.

a(2^m*prime(k)) = 2^m*(prime(k+1) - prime(k)).

a(n) = A081761(n) - n. - Michel Marcus, Nov 02 2020

Extensions

More terms from David Wasserman, Jan 12 2005