login
The smallest number whose binary expansion has exactly n distinct runs.
14

%I #15 Feb 22 2022 10:18:06

%S 0,1,2,11,38,311,2254,36079,549790,17593311,549687102,35179974591,

%T 2225029922430,284803830071167,36240869367020798,9277662557957324543,

%U 2368116566113212692990,1212475681849964898811391,619877748107024946567312382,634754814061593545284927880191

%N The smallest number whose binary expansion has exactly n distinct runs.

%C Positions of first appearances in A297770 (with offset 0).

%C The binary expansion of terms for n > 0 starts with 1, then floor(n/2) 0's, then alternates runs of increasing numbers of 1's, and decreasing numbers of 0's; see Python code. Thus, for n even, terms have n*(n/2+1)/2 binary digits, and for n odd, ((n+1) + (n-1)*((n-1)/2+1))/2 binary digits. - _Michael S. Branicky_, Feb 14 2022

%H Michael S. Branicky, <a href="/A350952/b350952.txt">Table of n, a(n) for n = 0..114</a>

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/q/87559">What is a sequence run? (answered 2011-12-01)</a>

%e The terms and their binary expansions begin:

%e 0: ()

%e 1: 1

%e 2: 10

%e 11: 1011

%e 38: 100110

%e 311: 100110111

%e 2254: 100011001110

%e 36079: 1000110011101111

%e 549790: 10000110001110011110

%e For example, 311 has binary expansion 100110111 with 5 distinct runs: 1, 00, 11, 0, 111.

%t q=Table[Length[Union[Split[If[n==0,{},IntegerDigits[n,2]]]]],{n,0,1000}];Table[Position[q,i][[1,1]]-1,{i,Union[q]}]

%o (Python)

%o def a(n): # returns term by construction

%o if n == 0: return 0

%o q, r = divmod(n, 2)

%o if r == 0:

%o s = "".join("1"*i + "0"*(q-i+1) for i in range(1, q+1))

%o assert len(s) == n*(n//2+1)//2

%o else:

%o s = "1" + "".join("0"*(q-i+2) + "1"*i for i in range(2, q+2))

%o assert len(s) == ((n+1) + (n-1)*((n-1)//2+1))//2

%o return int(s, 2)

%o print([a(n) for n in range(20)]) # _Michael S. Branicky_, Feb 14 2022

%o (PARI) a(n)={my(t=0); for(k=1, (n+1)\2, t=((t<<k)+(2^k-1))<<(n\2+1-k)); t} \\ _Andrew Howroyd_, Feb 15 2022

%Y Runs in binary expansion are counted by A005811, distinct A297770.

%Y The version for run-lengths instead of runs is A165933, for A165413.

%Y Subset of A175413 (binary expansion has distinct runs), for lengths A044813.

%Y The version for standard compositions is A351015.

%Y A000120 counts binary weight.

%Y A011782 counts integer compositions.

%Y A242882 counts compositions with distinct multiplicities.

%Y A318928 gives runs-resistance of binary expansion.

%Y A334028 counts distinct parts in standard compositions.

%Y A351014 counts distinct runs in standard compositions.

%Y Counting words with all distinct runs:

%Y - A351013 = compositions, for run-lengths A329739, ranked by A351290.

%Y - A351016 = binary words, for run-lengths A351017.

%Y - A351018 = binary expansions, for run-lengths A032020.

%Y - A351200 = patterns, for run-lengths A351292.

%Y - A351202 = permutations of prime factors.

%Y Cf. A003242, A070939, A085207, A098859, A233564, A325545, A328592, A333489, A351203, A351291.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 14 2022

%E a(9)-a(19) from _Michael S. Branicky_, Feb 14 2022