A243285 Number of integers 1 <= k <= n which are not divisible by the square of their largest noncomposite divisor.

0, 1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 10, 11, 11, 12, 12, 13, 14, 15, 16, 17, 18, 18, 19, 19, 20, 21, 22, 23, 23, 24, 25, 26, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 38, 38, 39, 40, 41, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 50, 51, 52, 53, 54, 55, 56, 57

Offset

1,3

Comments

a(n) tells how many natural numbers <= n there are which are not divisible by the square of their largest noncomposite divisor.

The largest noncomposite divisor of 1 is 1 itself, and 1 is divisible by 1^2, thus 1 is not included in the count, and a(1)=0.

The "largest noncomposite divisor" for any integer > 1 means the same thing as the largest prime divisor, and thus we are counting the terms of A102750 (Numbers n such that square of largest prime dividing n does not divide n).

Thus this is the partial sums of the characteric function for A102750.

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000

Formula

a(n) = n - A243283(n).

For all n, a(A102750(n)) = n, thus this sequence works also as an inverse function for the injection A102750.

Example

For n = 9, there are numbers 2, 3, 5, 6 and 7 which are not divisible by the square of their largest prime factor, while 1 is excluded (no prime factors) and 4 and 8 are divisible both by 2^2 and 9 is divisible by 3^2. Thus a(9) = 5.

Mathematica

ndsQ[n_]:=Mod[n, Max[Select[Divisors[n], !CompositeQ[#]&]]^2]!=0; Accumulate[Table[If[ ndsQ[n], 1, 0], {n, 80}]] (* Harvey P. Dale, Oct 14 2023 *)

Prog

(Scheme) (define (A243285 n) (- n (A243283 n)))
(Python)
from sympy import primefactors
def a243285(n): return 0 if n==1 else sum([1 for k in range(2, n + 1) if k%(primefactors(k)[-1]**2)!=0]) # Indranil Ghosh, Jun 15 2017

Crossrefs

Cf. A243282, A243283, A102750, A070003, A013928, A057627.

Sequence in context: A072490 A242493 A261345 * A085972 A136378 A344374

Adjacent sequences: A243282 A243283 A243284 * A243286 A243287 A243288

Keyword

nonn

Author

Antti Karttunen, Jun 02 2014

Status

approved