login
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.
9

%I #43 May 17 2024 04:20:54

%S 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,

%T 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,

%U 16,33,22,31,2,45,2,33,28,33,18,47,2,37,26,47,2

%N 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.

%C 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

%C If n is the product of twin primes, (a(n) +- 2)/2 gives the two primes. - _Wesley Ivan Hurt_, Sep 06 2013

%H Peter Luschny, <a href="/A062830/b062830.txt">Table of n, a(n) for n = 0..10000</a>

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

%F From _Wesley Ivan Hurt_, Aug 27 2013: (Start)

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

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

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

%F a(n) = 2*A067392(n)/n for n > 1. - _Robert G. Wilson v_, Jul 16 2019

%e 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.

%p with(numtheory); 1, 0, seq(k - phi(k) + 1, k = 2..70);

%p # _Wesley Ivan Hurt_, Aug 27 2013

%p K := (n, k) -> NumberTheory:-KroneckerSymbol(n, k):

%p seq(nops(select(k -> K(n, k) = 0, [seq(0..n)])), n = 0..70);

%p # Alternative:

%p T := (n, k) -> ifelse(NumberTheory:-AreCoprime(n, k), 1, 0):

%p seq(nops(select(k -> T(n, k) = 0, [seq(0..n)])), n = 0..70);

%p # _Peter Luschny_, May 15 2024

%t Table[n - EulerPhi[n] + 1 - Boole[n == 1], {n, 0, 70}]

%t (* _Wesley Ivan Hurt_, Aug 27 2013 *)

%t Table[Count[Table[KroneckerSymbol[n, k], {k, 0, n}], 0], {n, 0, 70}]

%t (* _Peter Luschny_, May 15 2024 *)

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

%o (SageMath)

%o print([sum(kronecker(n, k) == 0 for k in range(n + 1)) for n in range(70)])

%o # _Peter Luschny_, May 16 2024

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

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

%K easy,nonn

%O 0,3

%A _Jason Earls_, Jul 20 2001

%E Offset set to 0, a(0) = 1 added, a(1) adapted and new name by _Peter Luschny_, May 15 2024