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

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

Links

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

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

Example

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.

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

Prog

(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

Crossrefs

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

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

Sequence in context: A298423 A319810 A325250 * A322366 A363724 A345268

Adjacent sequences: A062827 A062828 A062829 * A062831 A062832 A062833

Keyword

easy,nonn

Author

Jason Earls, Jul 20 2001

Extensions

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

Status

approved