login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A243285
Number of integers 1 <= k <= n which are not divisible by the square of their largest noncomposite divisor.
8
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
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
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jun 02 2014
STATUS
approved