A338236 Number of numbers less than or equal to sqrt(n) whose square does not divide n.

0, 0, 0, 0, 1, 1, 1, 0, 1, 2, 2, 1, 2, 2, 2, 1, 3, 2, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 4, 4, 4, 2, 4, 4, 4, 2, 5, 5, 5, 4, 5, 5, 5, 4, 4, 5, 5, 3, 5, 5, 6, 5, 6, 5, 6, 5, 6, 6, 6, 5, 6, 6, 5, 4, 7, 7, 7, 6, 7, 7, 7, 4, 7, 7, 6, 6, 7, 7, 7, 5, 6, 8, 8, 7, 8, 8, 8, 7, 8, 7, 8

Offset

1,10

Comments

Number of squares less than n that do not divide n. - Wesley Ivan Hurt, Jan 06 2024

Links

Felix Fröhlich, Table of n, a(n) for n = 1..10000

Formula

a(n) = floor(sqrt(n)) - Sum_{k=1..sqrt(n)} (1 - ceiling(n/k^2) + floor(n/k^2)).

a(n) = floor(sqrt(n)) - tau(sqrt(n/A007913(n))) = A000196(n) - A000005(sqrt(n/A007913(n))). - Chai Wah Wu, Jan 31 2021

a(n) = Sum_{k=1..n} c(k) * (ceiling(n/k) - floor(n/k)), where c = A010052. - Wesley Ivan Hurt, Jan 06 2024

a(n) = A000196(n) - A046951(n). - Ridouane Oudra, Sep 04 2024

Example

a(9) = 1; floor(sqrt(9)) = 3 and the square of 2 does not divide 9,
a(10) = 2; floor(sqrt(10)) = 3 and the squares of 2 and 3 do not divide 10.

Mathematica

Table[Sum[Ceiling[n/k^2] - Floor[n/k^2], {k, Sqrt[n]}], {n, 100}]

Prog

(PARI) a(n) = sum(k=1, floor(sqrt(n)), if (n % k^2, 1)); \\ Michel Marcus, Jan 31 2021
(Python)
from sympy import divisor_count, integer_nthroot
from sympy.ntheory.factor_ import core
def A338236(n):
    return integer_nthroot(n, 2)[0]-divisor_count(integer_nthroot(n//core(n, 2), 2)[0]) # Chai Wah Wu, Jan 31 2021

Crossrefs

Cf. A000005, A000196, A007913, A046951.

Cf. A338228, A338231, A338233, A338234, A368820.

Sequence in context: A347562 A359790 A107260 * A279346 A168258 A116204

Adjacent sequences: A338233 A338234 A338235 * A338237 A338238 A338239

Keyword

nonn,easy,changed

Author

Wesley Ivan Hurt, Jan 30 2021

Status

approved