login
a(n) = gcd(n, phi(n)).
60

%I #51 Feb 22 2024 09:09:14

%S 1,1,1,2,1,2,1,4,3,2,1,4,1,2,1,8,1,6,1,4,3,2,1,8,5,2,9,4,1,2,1,16,1,2,

%T 1,12,1,2,3,8,1,6,1,4,3,2,1,16,7,10,1,4,1,18,5,8,3,2,1,4,1,2,9,32,1,2,

%U 1,4,1,2,1,24,1,2,5,4,1,6,1,16,27,2,1,12,1,2,1,8,1,6,1,4,3,2,1,32,1,14,3,20

%N a(n) = gcd(n, phi(n)).

%C The inequality gcd(n, phi(n)) <= 2n exp(-sqrt(log 2 log n)) holds for all squarefree n >= 1 (Erdős, Luca, and Pomerance).

%C Erdős shows that for almost all n, a(n) ~ log log log log n. - _Charles R Greathouse IV_, Nov 23 2011

%H T. D. Noe, <a href="/A009195/b009195.txt">Table of n, a(n) for n = 1..10000</a>

%H Paul Erdős, <a href="http://www.renyi.hu/~p_erdos/1948-11.pdf">Some asymptotic formulas in number theory</a>, J. Indian Math. Soc. (N.S.) 12 (1948), pp. 75-78.

%H Paul Erdős, Florian Luca, Carl Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/PDF/gcdnphin14.pdf">On the proportion of numbers coprime to a given integer</a>, in Anatomy of Integers, pp. 47-64, J.-M. De Koninck, A. Granville, F. Luca (editors), AMS, 2008.

%H Joshua Stucky, <a href="https://arxiv.org/abs/2402.13997">The distribution of gcd(n,phi(n))</a>, arXiv:2402.13997 [math.NT], 2024.

%F a(n) = gcd(n, A051953(n)). - _Labos Elemer_

%F a(n) = n / A109395(n). - _Antti Karttunen_, May 04 2017 (corrected also typo in above formula).

%p a009195 := n -> igcd(i,numtheory[phi](n));

%t Table[GCD[n,EulerPhi[n]],{n,100}] (* _Harvey P. Dale_, Aug 11 2011 *)

%o (PARI) a(n)=gcd(n,eulerphi(n)) \\ _Charles R Greathouse IV_, Nov 23 2011

%o (Haskell)

%o a009195 n = n `gcd` a000010 n -- _Reinhard Zumkeller_, Feb 27 2012

%o (Python)

%o def a009195(n):

%o from math import gcd

%o phi = lambda x: len([i for i in range(x) if gcd(x,i) == 1])

%o return gcd(n, phi(n))

%o # _Edward Minnix III_, Dec 05 2015

%o (Magma) [Gcd(n, EulerPhi(n)): n in [1..100]]; // _Vincenzo Librandi_, Dec 17 2015

%Y Cf. A000010, A003277, A050399, A051953, A061303, A109395, A285711.

%K nonn,easy,nice

%O 1,4

%A _David W. Wilson_