A338430 Number of numbers less than sqrt(n) whose square does not divide n.

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

Offset

1,17

Links

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

Formula

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

Example

a(16) = 1: floor(sqrt(16))-1 = 3 and 3^2 does not divide 16, so a(16) = 1;
a(17) = 2: floor(sqrt(17))-1 = 3 and the squares of 2 and 3 do not divide 17, so a(17) = 2.

Mathematica

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

Prog

(PARI) a(n) = sum(k=1, floor(sqrt(n))-1, if (n % k^2, 1)); \\ Michel Marcus, Jan 31 2021

Crossrefs

Cf. A338228, A338231, A338233, A338234, A338236, A338434.

Sequence in context: A292375 A361702 A295218 * A223135 A084113 A323086

Adjacent sequences: A338427 A338428 A338429 * A338431 A338432 A338433

Keyword

nonn,easy

Author

Wesley Ivan Hurt, Jan 30 2021

Status

approved