login
Least k such that the k-th squarefree number has exactly n zeros in its binary expansion.
16

%I #20 May 11 2024 12:59:55

%S 1,2,7,12,21,40,79,158,315,1247,1246,2492,4983,9963,19921,39845,79689,

%T 159361,318726,637462,1274919,2549835,5099651,10199302,20398665,

%U 40797328,81594627,163189198,326378285,652756723,1305513584,2611027095,5222054082,10444108052

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

%C Note that the data is not strictly increasing.

%H Chai Wah Wu, <a href="/A372473/b372473.txt">Table of n, a(n) for n = 0..57</a>

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

%e 1: 1 ~ {1}

%e 2: 10 ~ {2}

%e 10: 1010 ~ {2,4}

%e 17: 10001 ~ {1,5}

%e 33: 100001 ~ {1,6}

%e 65: 1000001 ~ {1,7}

%e 129: 10000001 ~ {1,8}

%e 257: 100000001 ~ {1,9}

%e 514: 1000000010 ~ {2,10}

%e 2051: 100000000011 ~ {1,2,12}

%e 2049: 100000000001 ~ {1,12}

%e 4097: 1000000000001 ~ {1,13}

%e 8193: 10000000000001 ~ {1,14}

%t nn=10000;

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

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

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

%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 A372473(n):

%o if n==0: return 1

%o for l in count(n):

%o m = 1<<l

%o for d in multiset_permutations('0'*n+'1'*(l-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 first appearances in A372472.

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

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

%Y Counting 1's (weight) instead of 0's gives A372541, firsts of A372433.

%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 A070939 gives length of binary expansion (number of bits).

%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. A035100, A039004, A049093, A049094, A059015, A069010, A145037, A211997.

%K nonn,base

%O 0,2

%A _Gus Wiseman_, May 09 2024

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