A009195 a(n) = gcd(n, phi(n)).
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
Offset: 1
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.
- Joshua Stucky, The distribution of gcd(n,phi(n)), arXiv:2402.13997 [math.NT], 2024.
Programs
-
Haskell
a009195 n = n `gcd` a000010 n -- Reinhard Zumkeller, Feb 27 2012
-
Magma
[Gcd(n, EulerPhi(n)): n in [1..100]]; // Vincenzo Librandi, Dec 17 2015
-
Maple
a009195 := n -> igcd(i,numtheory[phi](n));
-
Mathematica
Table[GCD[n,EulerPhi[n]],{n,100}] (* Harvey P. Dale, Aug 11 2011 *) -
PARI
a(n)=gcd(n,eulerphi(n)) \\ Charles R Greathouse IV, Nov 23 2011
-
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
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).
Comments