A372475 Length of binary expansion (or number of bits) of the n-th squarefree number.

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

Offset

1,2

Links

Table of n, a(n) for n=1..87.

Formula

a(n) = A070939(A005117(n)).

a(n) = A372472(n) + A372433(n).

Example

The 10th squarefree number is 14, with binary expansion (1,1,1,0), so a(10) = 4.

Mathematica

IntegerLength[Select[Range[1000], SquareFreeQ], 2]

Prog

(Python)
from math import isqrt
from sympy import mobius
def A372475(n):
    def f(x): return n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return int(m).bit_length() # Chai Wah Wu, Aug 02 2024

Crossrefs

For prime instead of squarefree we have A035100, 1's A014499, 0's A035103.

Restriction of A070939 to A005117.

Run-lengths are A077643.

For weight instead of length we have A372433 (restrict A000120 to A005117).

For zeros instead of length we have A372472, firsts A372473.

Positions of first appearances are A372540.

A030190 gives binary expansion, reversed A030308.

A048793 lists positions of ones in reversed binary expansion, sum A029931.

A371571 lists positions of zeros in binary expansion, sum A359359.

A371572 lists positions of ones in binary expansion, sum A230877.

A372515 lists positions of zeros in reversed binary expansion, sum A359400.

Cf. A003714, A023416, A049093, A049094, A059015, A069010, A073642, A145037, A211997, A368494, A372474, A372516.

Sequence in context: A137300 A201052 A278044 * A255121 A095791 A238965

Adjacent sequences: A372472 A372473 A372474 * A372476 A372477 A372478

Keyword

nonn,base

Author

Gus Wiseman, May 09 2024

Status

approved