The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A009195 a(n) = gcd(n, phi(n)). 53
 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, 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, 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS The inequality gcd(n, phi(n)) <= 2n exp(-sqrt(log 2 log n)) holds for all squarefree n >= 1 (Erdős, Luca, and Pomerance). Erdős shows that for almost all n, a(n) ~ log log log log n. - Charles R Greathouse IV, Nov 23 2011 LINKS T. D. Noe, Table of n, a(n) for n = 1..10000 Paul Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), pp. 75-78. Paul Erdős, Florian Luca, Carl Pomerance, On the proportion of numbers coprime to a given integer, in Anatomy of Integers, pp. 47-64, J.-M. De Koninck, A. Granville, F. Luca (editors), AMS, 2008. FORMULA a(n) = gcd(n, A051953(n)). - Labos Elemer a(n) = n / A109395(n). - Antti Karttunen, May 04 2017 (corrected also typo in above formula). MAPLE a009195 := n -> igcd(i, numtheory[phi](n)); MATHEMATICA Table[GCD[n, EulerPhi[n]], {n, 100}] (* Harvey P. Dale, Aug 11 2011 *) PROG (PARI) a(n)=gcd(n, eulerphi(n)) \\ Charles R Greathouse IV, Nov 23 2011 (Haskell) a009195 n = n `gcd` a000010 n  -- Reinhard Zumkeller, Feb 27 2012 (Python) def a009195(n):     from math import gcd     phi = lambda x: len([i for i in range(x) if gcd(x, i) == 1])     return gcd(n, phi(n)) # Edward Minnix III, Dec 05 2015 (MAGMA) [Gcd(n, EulerPhi(n)): n in [1..100]]; // Vincenzo Librandi, Dec 17 2015 CROSSREFS Cf. A000010, A003277, A050399, A051953, A061303, A109395, A285711. Sequence in context: A200219 A270120 A325567 * A072994 A332741 A052126 Adjacent sequences:  A009192 A009193 A009194 * A009196 A009197 A009198 KEYWORD nonn,easy,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 17 04:22 EST 2021. Contains 340214 sequences. (Running on oeis4.)