login
Numbers having no more than one 0 in their binary representation.
36

%I #88 May 25 2024 12:18:40

%S 0,1,2,3,5,6,7,11,13,14,15,23,27,29,30,31,47,55,59,61,62,63,95,111,

%T 119,123,125,126,127,191,223,239,247,251,253,254,255,383,447,479,495,

%U 503,507,509,510,511,767,895,959,991,1007,1015,1019,1021,1022,1023

%N Numbers having no more than one 0 in their binary representation.

%C Complement of A158582. - _Reinhard Zumkeller_, Apr 16 2009

%C Also union of A168604 and A030130. - _Douglas Latimer_, Jul 19 2012

%C Numbers of the form 2^t - 2^k - 1, 0 <= k < t.

%C n is in the sequence if and only if 2*n+1 is in the sequence. - _Robert Israel_, Dec 14 2018

%C Also the least binary rank of a strict integer partition of n, where the binary rank of a partition y is given by Sum_i 2^(y_i-1). - _Gus Wiseman_, May 24 2024

%H Reinhard Zumkeller, <a href="/A089633/b089633.txt">Table of n, a(n) for n = 0..10000</a>

%H Vladimir Shevelev, <a href="https://arxiv.org/abs/0801.0072">On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure</a>, arXiv:0801.0072 [math.CO], 2007-201. See Section 14.

%H Vladimir Shevelev, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Shevelev/shevelev14.html">Binomial Coefficient Predictors</a>, Journal of Integer Sequences, Vol. 14 (2011), Article 11.2.8.

%H Vladimir Shevelev, <a href="http://www.emis.de/journals/INTEGERS/papers/m1/m1.Abstract.html">The number of permutations with prescribed up-down structure as a function of two variables</a>, INTEGERS, 12 (2012), #A1.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.

%F A023416(a(n)) <= 1; A023416(a(n)) = A023532(n-2) for n>1;

%F A000120(a(u)) <= A000120(a(v)) for u<v; A000120(a(n)) = A003056(n).

%F a(0)=0, n>0: a(n+1) = Min{m>n: BinOnes(a(n))<=BinOnes(m)} with BinOnes=A000120.

%F If m = floor((sqrt(8*n+1) - 1) / 2), then a(n) = 2^(m+1) - 2^(m*(m+3)/2 - n) - 1. - _Carl R. White_, Feb 10 2009

%F A029931(a(n)) = n and A029931(m) != n for m < a(n). - _Reinhard Zumkeller_, Feb 28 2014

%F A265705(a(n),k) = A265705(a(n),a(n)-k), k = 0 .. a(n). - _Reinhard Zumkeller_, Dec 15 2015

%F a(A014132(n)-1) = 2*a(n-1)+1 for n >= 1. - _Robert Israel_, Dec 14 2018

%F Sum_{n>=1} 1/a(n) = A065442 + A160502 = 3.069285887459... . - _Amiram Eldar_, Jan 09 2024

%F A019565(a(n)) = A077011(n). - _Gus Wiseman_, May 24 2024

%e From _Tilman Piesk_, May 09 2012: (Start)

%e This may also be viewed as a triangle: In binary:

%e 0 0

%e 1 2 01 10

%e 3 5 6 011 101 110

%e 7 11 13 14 0111 1011 1101 1110

%e 15 23 27 29 30 01111 10111 11011 11101 11110

%e 31 47 55 59 61 62

%e 63 95 111 119 123 125 126

%e Left three diagonals are A000225, A055010, A086224. Right diagonal is A000918. Central column is A129868. Numbers in row n (counted from 0) have n binary 1s. (End)

%e From _Gus Wiseman_, May 24 2024: (Start)

%e The terms together with their binary expansions and binary indices begin:

%e 0: 0 ~ {}

%e 1: 1 ~ {1}

%e 2: 10 ~ {2}

%e 3: 11 ~ {1,2}

%e 5: 101 ~ {1,3}

%e 6: 110 ~ {2,3}

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

%e 11: 1011 ~ {1,2,4}

%e 13: 1101 ~ {1,3,4}

%e 14: 1110 ~ {2,3,4}

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

%e 23: 10111 ~ {1,2,3,5}

%e 27: 11011 ~ {1,2,4,5}

%e 29: 11101 ~ {1,3,4,5}

%e 30: 11110 ~ {2,3,4,5}

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

%e 47: 101111 ~ {1,2,3,4,6}

%e 55: 110111 ~ {1,2,3,5,6}

%e 59: 111011 ~ {1,2,4,5,6}

%e 61: 111101 ~ {1,3,4,5,6}

%e 62: 111110 ~ {2,3,4,5,6}

%e (End)

%p seq(seq(2^a-1-2^b,b=a-1..0,-1),a=1..11); # _Robert Israel_, Dec 14 2018

%t fQ[n_] := DigitCount[n, 2, 0] < 2; Select[ Range[0, 2^10], fQ] (* _Robert G. Wilson v_, Aug 02 2012 *)

%o (Haskell)

%o a089633 n = a089633_list !! (n-1)

%o a089633_list = [2 ^ t - 2 ^ k - 1 | t <- [1..], k <- [t-1,t-2..0]]

%o -- _Reinhard Zumkeller_, Feb 23 2012

%o (PARI) {insq(n) = local(dd, hf, v); v=binary(n);hf=length(v);dd=sum(i=1,hf,v[i]);if(dd<=hf-2,-1,1)}

%o {for(w=0,1536,if(insq(w)>=0,print1(w,", ")))}

%o \\ _Douglas Latimer_, May 07 2013

%o (PARI) isoka(n) = #select(x->(x==0), binary(n)) <= 1; \\ _Michel Marcus_, Dec 14 2018

%o (Python)

%o from itertools import count, islice

%o def A089633_gen(): # generator of terms

%o return ((1<<t)-(1<<k)-1 for t in count(1) for k in range(t-1,-1,-1))

%o A089633_list = list(islice(A089633_gen(),30)) # _Chai Wah Wu_, Feb 10 2023

%Y Cf. A000120, A007088, A011371, A014132, A023416, A023532, A029931.

%Y Cf. A181741 (primes), union of A081118 and A000918, apart from initial -1.

%Y Cf. A065442, A160502, A265705.

%Y For least binary index (instead of rank) we have A001511.

%Y Applying A019565 (Heinz number of binary indices) gives A077011.

%Y For greatest binary index we have A029837 or A070939, opposite A070940.

%Y Row minima of A118462 (binary ranks of strict partitions).

%Y For sum instead of minimum we have A372888, non-strict A372890.

%Y A000009 counts strict partitions, ranks A005117.

%Y A048675 gives binary rank of prime indices, distinct A087207.

%Y A048793 lists binary indices, product A096111, reverse A272020.

%Y A277905 groups all positive integers by binary rank of prime indices.

%Y Cf. A000041, A005940, A018819, A147655, A225620, A246868.

%K nonn,base

%O 0,3

%A _Reinhard Zumkeller_, Jan 01 2004