cp's OEIS Frontend

A009195 a(n) = gcd(n, phi(n)).

%I A009195 #51 Feb 22 2024 09:09:14
%S A009195 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 A009195 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 A009195 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 A009195 a(n) = gcd(n, phi(n)).
%C A009195 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 A009195 Erdős shows that for almost all n, a(n) ~ log log log log n. - _Charles R Greathouse IV_, Nov 23 2011
%H A009195 T. D. Noe, <a href="/A009195/b009195.txt">Table of n, a(n) for n = 1..10000</a>
%H A009195 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 A009195 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 A009195 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 A009195 a(n) = gcd(n, A051953(n)). - _Labos Elemer_
%F A009195 a(n) = n / A109395(n). - _Antti Karttunen_, May 04 2017 (corrected also typo in above formula).
%p A009195 a009195 := n -> igcd(i,numtheory[phi](n));
%t A009195 Table[GCD[n,EulerPhi[n]],{n,100}] (* _Harvey P. Dale_, Aug 11 2011 *)
%o A009195 (PARI) a(n)=gcd(n,eulerphi(n)) \\ _Charles R Greathouse IV_, Nov 23 2011
%o A009195 (Haskell)
%o A009195 a009195 n = n `gcd` a000010 n  -- _Reinhard Zumkeller_, Feb 27 2012
%o A009195 (Python)
%o A009195 def a009195(n):
%o A009195     from math import gcd
%o A009195     phi = lambda x: len([i for i in range(x) if gcd(x,i) == 1])
%o A009195     return gcd(n, phi(n))
%o A009195 # _Edward Minnix III_, Dec 05 2015
%o A009195 (Magma) [Gcd(n, EulerPhi(n)): n in [1..100]]; // _Vincenzo Librandi_, Dec 17 2015
%Y A009195 Cf. A000010, A003277, A050399, A051953, A061303, A109395, A285711.
%K A009195 nonn,easy,nice
%O A009195 1,4
%A A009195 _David W. Wilson_