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