A372541 - OEIS

%I #24 May 11 2024 13:00:09

%S 1,3,6,11,20,60,78,157,314,624,1245,3736,4982,9962,19920,39844,79688,

%T 239046,318725,956194,1912371,2549834,5099650,15298984,20398664,

%U 40797327,81594626,163189197,326378284,979135127,1305513583,2611027094,5222054081,10444108051

%N Least k such that the k-th squarefree number has exactly n ones in its binary expansion.

%H Chai Wah Wu, <a href="/A372541/b372541.txt">Table of n, a(n) for n = 0..56</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamming_weight">Hamming weight</a>.

%e The squarefree numbers A005117(a(n)) together with their binary expansions and binary indices begin:

%e        1:                   1 ~ {1}

%e        3:                  11 ~ {1,2}

%e        7:                 111 ~ {1,2,3}

%e       15:                1111 ~ {1,2,3,4}

%e       31:               11111 ~ {1,2,3,4,5}

%e       95:             1011111 ~ {1,2,3,4,5,7}

%e      127:             1111111 ~ {1,2,3,4,5,6,7}

%e      255:            11111111 ~ {1,2,3,4,5,6,7,8}

%e      511:           111111111 ~ {1,2,3,4,5,6,7,8,9}

%e     1023:          1111111111 ~ {1,2,3,4,5,6,7,8,9,10}

%e     2047:         11111111111 ~ {1,2,3,4,5,6,7,8,9,10,11}

%e     6143:       1011111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,13}

%e     8191:       1111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13}

%e    16383:      11111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13,14}

%e    32767:     111111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

%e    65535:    1111111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

%e   131071:   11111111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

%t nn=10000;

%t spnm[y_]:=Max@@NestWhile[Most,y,Union[#]!=Range[0,Max@@#]&];

%t dcs=DigitCount[Select[Range[nn],SquareFreeQ],2,1];

%t Table[Position[dcs,i][[1,1]],{i,spnm[dcs-1]}]

%o (Python)

%o from math import isqrt

%o from itertools import count

%o from sympy import factorint, mobius

%o from sympy.utilities.iterables import multiset_permutations

%o def A372541(n):

%o     if n==0: return 1

%o     for l in count(n):

%o         m = 1<<l

%o         for d in multiset_permutations('0'*(l-n)+'1'*n):

%o             k = m+int('0'+''.join(d),2)

%o             if max(factorint(k).values(),default=0)==1:

%o                 return sum(mobius(a)*(k//a**2) for a in range(1, isqrt(k)+1)) # _Chai Wah Wu_, May 10 2024

%Y Positions of firsts appearances in A372433.

%Y Counting zeros instead of ones gives A372473, firsts in A372472.

%Y For prime instead of squarefree we have A372517, firsts of A014499.

%Y Counting bits (length) gives A372540, firsts of A372475, runs A077643.

%Y A000120 counts ones in binary expansion (binary weight), zeros A080791.

%Y A005117 lists squarefree numbers.

%Y A030190 gives binary expansion, reversed A030308.

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

%Y A145037, A097110 count ones minus zeros, for primes A372516, A177796.

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

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

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

%Y Cf. A023416, A049093, A049094, A069010, A070939, A071403, A211997, A280296, A372474.

%K nonn,base

%O 0,2

%A _Gus Wiseman_, May 09 2024

%E a(23)-a(33) from _Chai Wah Wu_, May 10 2024