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,6

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)

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

Formula

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

Example

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

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 *)

Prog

(Haskell)
a016035 1 = 0
a016035 n = sum $ map a000010 $ init $ tail $ a027750_row n
-- Reinhard Zumkeller, Mar 02 2012
(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 */

Crossrefs

Cf. A001567 (base 2 pseudoprimes).

Cf. A000010, A027750.

Essentially one less than cototient, A051953.

Sequence in context: A324180 A271860 A219428 * A340090 A297168 A112470

Adjacent sequences: A016032 A016033 A016034 * A016036 A016037 A016038

Keyword

nonn,easy

Author

Robert G. Wilson v

Extensions

Typo in definition fixed by Reinhard Zumkeller, Mar 02 2012

Status

approved