A010848 Number of numbers k <= n such that at least one prime factor of n is not a prime factor of k.

0, 1, 2, 2, 4, 5, 6, 4, 6, 9, 10, 10, 12, 13, 14, 8, 16, 15, 18, 18, 20, 21, 22, 20, 20, 25, 18, 26, 28, 29, 30, 16, 32, 33, 34, 30, 36, 37, 38, 36, 40, 41, 42, 42, 42, 45, 46, 40, 42, 45, 50, 50, 52, 45, 54, 52, 56, 57, 58, 58, 60, 61, 60, 32, 64, 65, 66, 66, 68, 69, 70, 60

Offset

1,3

Comments

The number of integers k from 1 to n such that gcd(n, k) is a non-coreful divisor of n (see A308135 for a definition of a non-coreful divisor). - Amiram Eldar, Nov 22 2025

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

a(n) = n - A003557(n). - Vladeta Jovovic, Sep 15 2006

Dirichlet g.f.: zeta(s-1) - Product_{p prime} (1 + 1/(p^s - p)). - Amiram Eldar, Nov 22 2025

Maple

f:= n -> n - n/convert(numtheory:-factorset(n), `*`):
map(f, [$1..100]); # Robert Israel, Apr 10 2018

Mathematica

a[n_] := n * (1 - 1/Times @@ FactorInteger[n][[;; , 1]]); Array[a, 100] (* Amiram Eldar, Nov 22 2025 *)

Prog

(PARI) a(n) = n - n/vecprod(factor(n)[, 1]); \\ Amiram Eldar, Nov 22 2025

Crossrefs

Cf. A003557, A008479, A010846, A010847, A308135.

Sequence in context: A364049 A368866 A137413 * A133937 A181523 A353855

Adjacent sequences: A010845 A010846 A010847 * A010849 A010850 A010851

Keyword

nonn,easy

Author

Olivier Gérard

Extensions

Definition corrected by Vladeta Jovovic, Sep 15 2006

Status

approved