A351058 Number of numbers <= n that are either nonprime divisors of n or primes not dividing n.

1, 1, 2, 3, 3, 3, 4, 6, 5, 4, 5, 7, 6, 6, 6, 9, 7, 9, 8, 10, 8, 8, 9, 13, 10, 9, 11, 11, 10, 12, 11, 15, 11, 11, 11, 16, 12, 12, 12, 16, 13, 15, 14, 16, 16, 14, 15, 21, 16, 17, 15, 17, 16, 20, 16, 20, 16, 16, 17, 23, 18, 18, 20, 23, 18, 20, 19, 21, 19, 21, 20, 28, 21, 21, 23

Offset

1,3

Comments

a(p) = pi(p) for p prime.

Links

Table of n, a(n) for n=1..75.

Formula

a(n) = n - Sum_{k=1..n} [u(n/k) = v(k)], where u(n) = 1 - ceiling(n) + floor(n), v is the prime characteristic (A010051), and [ ] is the Iverson bracket.

Example

a(8) = 6; 1 is nonprime and divides 8, 3 does not divide 8 and is prime, 4 is not prime and divides 8, 5 is prime and does not divide 8, 7 is prime and does not divide 8, and 8 (nonprime) divides itself. So a(8) = 6.

Prog

(PARI) a(n) = sum(k=1, n, bitxor(isprime(k)&&(n%k), !isprime(k)&&!(n%k))); \\ Michel Marcus, Jan 31 2022

Crossrefs

Cf. A010051.

Sequence in context: A108932 A029067 A048460 * A036017 A029066 A174522

Adjacent sequences: A351055 A351056 A351057 * A351059 A351060 A351061

Keyword

nonn

Author

Wesley Ivan Hurt, Jan 30 2022

Status

approved