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

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

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

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

Prog

(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

Crossrefs

Cf. A000005, A000010, A133995.

Sequence in context: A323135 A356205 A100258 * A132748 A022901 A348215

Adjacent sequences: A045760 A045761 A045762 * A045764 A045765 A045766

Keyword

nonn,look

Author

N. J. A. Sloane

Extensions

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

Status

approved