cp's OEIS Frontend

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

%I A350952 #15 Feb 22 2022 10:18:06
%S A350952 0,1,2,11,38,311,2254,36079,549790,17593311,549687102,35179974591,
%T A350952 2225029922430,284803830071167,36240869367020798,9277662557957324543,
%U A350952 2368116566113212692990,1212475681849964898811391,619877748107024946567312382,634754814061593545284927880191
%N A350952 The smallest number whose binary expansion has exactly n distinct runs.
%C A350952 Positions of first appearances in A297770 (with offset 0).
%C A350952 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 A350952 Michael S. Branicky, <a href="/A350952/b350952.txt">Table of n, a(n) for n = 0..114</a>
%H A350952 Mathematics Stack Exchange, <a href="https://math.stackexchange.com/q/87559">What is a sequence run? (answered 2011-12-01)</a>
%e A350952 The terms and their binary expansions begin:
%e A350952        0:                   ()
%e A350952        1:                    1
%e A350952        2:                   10
%e A350952       11:                 1011
%e A350952       38:               100110
%e A350952      311:            100110111
%e A350952     2254:         100011001110
%e A350952    36079:     1000110011101111
%e A350952   549790: 10000110001110011110
%e A350952 For example, 311 has binary expansion 100110111 with 5 distinct runs: 1, 00, 11, 0, 111.
%t A350952 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 A350952 (Python)
%o A350952 def a(n): # returns term by construction
%o A350952     if n == 0: return 0
%o A350952     q, r = divmod(n, 2)
%o A350952     if r == 0:
%o A350952         s = "".join("1"*i + "0"*(q-i+1) for i in range(1, q+1))
%o A350952         assert len(s) == n*(n//2+1)//2
%o A350952     else:
%o A350952         s = "1" + "".join("0"*(q-i+2) + "1"*i for i in range(2, q+2))
%o A350952         assert len(s) == ((n+1) + (n-1)*((n-1)//2+1))//2
%o A350952     return int(s, 2)
%o A350952 print([a(n) for n in range(20)]) # _Michael S. Branicky_, Feb 14 2022
%o A350952 (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 A350952 Runs in binary expansion are counted by A005811, distinct A297770.
%Y A350952 The version for run-lengths instead of runs is A165933, for A165413.
%Y A350952 Subset of A175413 (binary expansion has distinct runs), for lengths A044813.
%Y A350952 The version for standard compositions is A351015.
%Y A350952 A000120 counts binary weight.
%Y A350952 A011782 counts integer compositions.
%Y A350952 A242882 counts compositions with distinct multiplicities.
%Y A350952 A318928 gives runs-resistance of binary expansion.
%Y A350952 A334028 counts distinct parts in standard compositions.
%Y A350952 A351014 counts distinct runs in standard compositions.
%Y A350952 Counting words with all distinct runs:
%Y A350952 - A351013 = compositions, for run-lengths A329739, ranked by A351290.
%Y A350952 - A351016 = binary words, for run-lengths A351017.
%Y A350952 - A351018 = binary expansions, for run-lengths A032020.
%Y A350952 - A351200 = patterns, for run-lengths A351292.
%Y A350952 - A351202 = permutations of prime factors.
%Y A350952 Cf. A003242, A070939, A085207, A098859, A233564, A325545, A328592, A333489, A351203, A351291.
%K A350952 nonn
%O A350952 0,3
%A A350952 _Gus Wiseman_, Feb 14 2022
%E A350952 a(9)-a(19) from _Michael S. Branicky_, Feb 14 2022