A338233 Number of numbers less than n whose square does not divide n.

0, 0, 1, 1, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12, 13, 12, 15, 15, 17, 17, 19, 20, 21, 21, 22, 24, 24, 25, 27, 28, 29, 28, 31, 32, 33, 31, 35, 36, 37, 37, 39, 40, 41, 41, 42, 44, 45, 44, 46, 47, 49, 49, 51, 51, 53, 53, 55, 56, 57, 57, 59, 60, 60, 59, 63, 64, 65, 65, 67, 68, 69, 67

Offset

1,5

Links

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

Formula

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

For n > 1, a(n) = n - 1 - tau(sqrt(n/A007913(n)) = n - A000005(sqrt(n/A007913(n)). - Chai Wah Wu, Feb 01 2021

Example

a(7) = 5; 1^2|7, but the squares of 2,3,4,5 and 6 do not. So a(7) = 5.
a(8) = 5; 1^2|8 and 2^2|8, but the squares of 3,4,5,6,and 7 do not. So a(8) = 5.

Mathematica

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

Prog

(PARI) a(n) = sum(k=1, n-1, if (n % k^2, 1)); \\ Michel Marcus, Jan 31 2021
(Python)
def A338233(n):
    return 0 if n <= 1 else n-1-divisor_count(integer_nthroot(n//core(n, 2), 2)[0]) # Chai Wah Wu, Feb 01 2021

Crossrefs

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

Sequence in context: A200066 A227789 A116183 * A177744 A330195 A330101

Adjacent sequences: A338230 A338231 A338232 * A338234 A338235 A338236

Keyword

nonn,easy

Author

Wesley Ivan Hurt, Jan 30 2021

Status

approved