A016035 a(n) = Sum_{j|n, 1 < j < n} phi(j). Also a(n) = n - phi(n) - 1 for n > 1.

0, 0, 0, 1, 0, 3, 0, 3, 2, 5, 0, 7, 0, 7, 6, 7, 0, 11, 0, 11, 8, 11, 0, 15, 4, 13, 8, 15, 0, 21, 0, 15, 12, 17, 10, 23, 0, 19, 14, 23, 0, 29, 0, 23, 20, 23, 0, 31, 6, 29, 18, 27, 0, 35, 14, 31, 20, 29, 0, 43, 0, 31, 26, 31, 16, 45, 0, 35, 24, 45, 0, 47, 0, 37, 34, 39, 16, 53

Offset: 1

Author

Robert G. Wilson v

Keywords

• nonn
• easy

Comments

Number of integers less than n with at least one common factor with n. - Olivier Gérard, Feb 08 2011

A number N is a Fermat base 2 pseudoprime, that is, 2^(N-1) == 1 mod N, iff 2^a(N) == 1 mod N. - T. D. Noe, Jul 10 2003

Number of zero divisors in ring Z_n, where Z_n is the ring of integers modulo n. - Armin Vollmer (armin_vollmer(AT)web.de), Jul 23 2004

From Jianing Song, Apr 20 2019: (Start)

a(p) = 0 if and only if p is a prime, which is equivalent to the fact that Z_p is a field if and only if p is a prime.

a(n) = n/2 is and only if n = 2p, p prime. (End)

Examples

			For n = 6, the a(6) = 3 integers less than 6 with at least one common factor with 6 are {2,3,4}.
		

References

• Al Hibbard and Ken Levasseur, "Exploring Abstract Algebra with Mathematica", Springer Verlag.

Links

• Olivier Gérard, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001567 (base 2 pseudoprimes).

Cf. A000010, A027750.

Essentially one less than cototient, A051953.

Programs

Haskell

a016035 1 = 0
a016035 n = sum $ map a000010 $ init $ tail $ a027750_row n
-- Reinhard Zumkeller, Mar 02 2012

Mathematica

Needs["AbstractAlgebra`Master`"] Length[ZeroDivisors[Z[ # ]]] & /@ Range[2, 25] (* Armin Vollmer, Jul 23 2004 *)
a[n_] := n - EulerPhi[n] - 1; a[1] = 0; Table[a[n], {n, 1, 78}] (* Jean-François Alcover, Jan 04 2013 *)

PARI

for(n=1,100,p=0;for(i=1,n-1,if(gcd(i,n)>1,p++));print1(p",")) /* V. Raman, Nov 22 2012 */

PARI

for(n=1,100,if(n==1,print1(0","),print1(n-1-eulerphi(n)","))) /* V. Raman, Nov 22 2012 */

Formula

For n > 1, a(n) = A051953(n) - 1. - Antti Karttunen, Mar 12 2018

Extensions

Typo in definition fixed by Reinhard Zumkeller, Mar 02 2012