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

Author

Antti Karttunen, Jun 02 2014

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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

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

Scheme

(define (A243285 n) (- n (A243283 n)))

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.