A045763 Number of numbers "unrelated to n": m < n such that m is neither a divisor of n nor relatively prime to n.

0, 0, 0, 0, 0, 1, 0, 1, 1, 3, 0, 3, 0, 5, 4, 4, 0, 7, 0, 7, 6, 9, 0, 9, 3, 11, 6, 11, 0, 15, 0, 11, 10, 15, 8, 16, 0, 17, 12, 17, 0, 23, 0, 19, 16, 21, 0, 23, 5, 25, 16, 23, 0, 29, 12, 25, 18, 27, 0, 33, 0, 29, 22, 26, 14, 39, 0, 31, 22, 39, 0, 37, 0, 35, 30, 35, 14, 47, 0, 39, 23, 39, 0, 49

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• look

Comments

Suggested by Wouter Meeussen.

a(n) = 0 iff n is a prime or 1 or 4. - Robert G. Wilson v, Nov 02 2005

From Farideh Firoozbakht, Dec 23 2014: (Start)

1. a(p^k) = p^(k-1) - k where p is a prime and k is a positive integer. Hence if p is prime then a(p) = 0 which is a result of the previous comment.

2. If n = 2*p or n = 4*p and p is an odd prime then a(n) = phi(n) - 1.

3. If n = 3*p where p is a prime not equal to 3 then a(n) = (1/2)*phi(n). (End)

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
• Martin Beumer, The Arithmetical Function tau_k(N), Amer. Math. Monthly, 69, Oct 1962, p. 780 (a(n)=ksi(N)).

Crossrefs

Cf. A000005, A000010, A133995.

Programs

Maple

A045763 := proc(n)
    n+1-numtheory[tau](n)-numtheory[phi](n) ;
end proc:
seq(A045763(n),n=1..100);# Robert Israel, Dec 23 2014

Mathematica

f[n_] := n + 1 - DivisorSigma[0, n] - EulerPhi[n]; Array[f, 84] (* Robert G. Wilson v *)

PARI

a(n)=n+1-numdiv(n)-eulerphi(n) \\ Charles R Greathouse IV, Jul 15 2011

Python

from sympy import divisor_count, totient
def A045763(n): return n+1-divisor_count(n)-totient(n) # Chai Wah Wu, Sep 02 2024

Formula

a(n) = n + 1 - d(n) - phi(n), where d(n) is the number of divisors of n and phi is Euler's totient function.

Dirichlet generating function: zeta(s-1) + zeta(s) - zeta(s)^2 - zeta(s-1)/zeta(s). - Robert Israel, Dec 23 2014

a(n) = Sum_{k=1..n} (1 - floor(1/gcd(n,k))) * (ceiling(n/k) - floor(n/k)). - Wesley Ivan Hurt, Jan 06 2024

Extensions

More terms from Robert G. Wilson v, Nov 02 2005