A082061 Greatest common prime divisor of n and phi(n)=A000010(n); a(n)=1 if no common prime divisor exists.

1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 2, 5, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 7, 5, 1, 2, 1, 3, 5, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 5, 2, 1, 3, 1, 2, 3, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 2, 1, 7, 3, 5, 1, 2, 1, 2, 3

Offset: 1

Author

Labos Elemer, Apr 07 2003

Keywords

• nonn

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384

Crossrefs

Cf. A000010, A003277, A006530, A009195, A070003.

Cf. also A082062, A082063, A082064, A082065, A082066, A082067.

Programs

Maple

gcpd := proc(a,b) local g ,d ; g := 1 ; for d in numtheory[divisors](a) intersect numtheory[divisors](b) do if isprime(d) then g := max(g,d) ; end if; end do: g ; end proc:
A082061 := proc(n) gcpd( numtheory[phi](n), n) ; end proc: # R. J. Mathar, Jul 09 2011

Mathematica

(* factors/exponent SET *) ffi[x_] := Flatten[FactorInteger[x]]; lf[x_] := Length[FactorInteger[x]]; ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}]; f1[x_] := x; f2[x_] := EulerPhi[x]; Table[Max[Intersection[ba[f1[w]], ba[f2[w]]]], {w, 1, 128}]
(* Second program: *)
Array[If[CoprimeQ[#1, #2], 1, Max@ Apply[Intersection, Map[FactorInteger[#][[All, 1]] &, {#1, #2}]]] & @@ {#, EulerPhi@ #} &, 105] (* Michael De Vlieger, Nov 03 2017 *)

PARI

gpf(n)=if(n>1,my(f=factor(n)[,1]);f[#f],1)
a(n)=gpf(gcd(eulerphi(n),n)) \\ Charles R Greathouse IV, Feb 19 2013

Formula

a(n) = A006530(A009195(n)). - Antti Karttunen, Nov 03 2017

From Amiram Eldar, Dec 06 2024: (Start)

a(n) <= A006530(n), with equality if and only if n is in A070003.

a(n) = 1 if and only if n is a cyclic number (A003277). (End)

Extensions

Changed "was found" to "exists" in definition. - N. J. A. Sloane, Jan 29 2022