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

%I #47 Sep 03 2024 00:42:49

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

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

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

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

%C Suggested by _Wouter Meeussen_.

%C a(n) = 0 iff n is a prime or 1 or 4. - _Robert G. Wilson v_, Nov 02 2005

%C From _Farideh Firoozbakht_, Dec 23 2014: (Start)

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

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

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

%H Michael De Vlieger, <a href="/A045763/b045763.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H Martin Beumer, <a href="http://www.jstor.org/stable/2310778">The Arithmetical Function tau_k(N)</a>, Amer. Math. Monthly, 69, Oct 1962, p. 780 (a(n)=ksi(N)).

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

%F Dirichlet generating function: zeta(s-1) + zeta(s) - zeta(s)^2 - zeta(s-1)/zeta(s). - _Robert Israel_, Dec 23 2014

%F a(n) = Sum_{k=1..n} (1 - floor(1/gcd(n,k))) * (ceiling(n/k) - floor(n/k)). - _Wesley Ivan Hurt_, Jan 06 2024

%p A045763 := proc(n)

%p n+1-numtheory[tau](n)-numtheory[phi](n) ;

%p end proc:

%p seq(A045763(n),n=1..100);# _Robert Israel_, Dec 23 2014

%t f[n_] := n + 1 - DivisorSigma[0, n] - EulerPhi[n]; Array[f, 84] (* _Robert G. Wilson v_ *)

%o (PARI) a(n)=n+1-numdiv(n)-eulerphi(n) \\ _Charles R Greathouse IV_, Jul 15 2011

%o (Python)

%o from sympy import divisor_count, totient

%o def A045763(n): return n+1-divisor_count(n)-totient(n) # _Chai Wah Wu_, Sep 02 2024

%Y Cf. A000005, A000010, A133995.

%K nonn,look

%O 1,10

%A _N. J. A. Sloane_

%E More terms from _Robert G. Wilson v_, Nov 02 2005