A062830 a(n) = #{ 0 <= k <= n : K(n, k) = 0 } where K(n, k) is the Kronecker symbol. This is the number of integers 0 <= k <= n that are not coprime to n.

1, 0, 2, 2, 3, 2, 5, 2, 5, 4, 7, 2, 9, 2, 9, 8, 9, 2, 13, 2, 13, 10, 13, 2, 17, 6, 15, 10, 17, 2, 23, 2, 17, 14, 19, 12, 25, 2, 21, 16, 25, 2, 31, 2, 25, 22, 25, 2, 33, 8, 31, 20, 29, 2, 37, 16, 33, 22, 31, 2, 45, 2, 33, 28, 33, 18, 47, 2, 37, 26, 47, 2

Offset: 0

Author

Jason Earls, Jul 20 2001

Keywords

• easy
• nonn

Comments

For n >= 2 this is the cototient(A051953) + 1. If n = p*q for different primes p and q, a(n) = p + q. - Wesley Ivan Hurt, Aug 27 2013

If n is the product of twin primes, (a(n) +- 2)/2 gives the two primes. - Wesley Ivan Hurt, Sep 06 2013

Examples

			a(10) = 7, since 10 - phi(10) + 1 = 10 - 4 + 1 = 7.  Also, since 10 is a squarefree semiprime, 7 represents the sum of the distinct prime factors of 10.
		

Links

• Peter Luschny, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A000010, A006881, A008472, A051953, A067392.

Cf. A096396 (#K(n,i)=1), A096397 (#K(n,i)=-1), this sequence (#K(n,i)=0).

Programs

Maple

with(numtheory); 1, 0, seq(k - phi(k) + 1, k = 2..70);
# Wesley Ivan Hurt, Aug 27 2013
K := (n, k) -> NumberTheory:-KroneckerSymbol(n, k):
seq(nops(select(k -> K(n, k) = 0, [seq(0..n)])), n = 0..70);
# Alternative:
T := (n, k) -> ifelse(NumberTheory:-AreCoprime(n, k), 1, 0):
seq(nops(select(k -> T(n, k) = 0, [seq(0..n)])), n = 0..70);
# Peter Luschny, May 15 2024

Mathematica

Table[n - EulerPhi[n] + 1 - Boole[n == 1], {n, 0, 70}]
(* Wesley Ivan Hurt, Aug 27 2013 *)
Table[Count[Table[KroneckerSymbol[n, k], {k, 0, n}], 0], {n, 0, 70}]
(* Peter Luschny, May 15 2024 *)

PARI

j=[1,0]; for(n=2, 200, j=concat(j, n+1-eulerphi(n))); j

SageMath

print([sum(kronecker(n, k) == 0 for k in range(n + 1)) for n in range(70)])
# Peter Luschny, May 16 2024

Formula

a(n) = n - phi(n) + 1 for n >= 2. (previous name)

From Wesley Ivan Hurt, Aug 27 2013: (Start)

a(n) = A051953(n) + 1 for n >= 2.

a(n) = n - A000010(n) + 1 for n >= 2.

a(A006881(n)) = A008472(A006881(n)). (End)

a(n) = 2*A067392(n)/n for n > 1. - Robert G. Wilson v, Jul 16 2019

Extensions

Offset set to 0, a(0) = 1 added, a(1) adapted and new name by Peter Luschny, May 15 2024