A158582 -id:A158582 - cp's OEIS frontend

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

0, 1, 2, 3, 5, 6, 7, 11, 13, 14, 15, 23, 27, 29, 30, 31, 47, 55, 59, 61, 62, 63, 95, 111, 119, 123, 125, 126, 127, 191, 223, 239, 247, 251, 253, 254, 255, 383, 447, 479, 495, 503, 507, 509, 510, 511, 767, 895, 959, 991, 1007, 1015, 1019, 1021, 1022, 1023

Offset: 0

Reinhard Zumkeller, Jan 01 2004

Complement of A158582. - Reinhard Zumkeller, Apr 16 2009
Also union of A168604 and A030130. - Douglas Latimer, Jul 19 2012
Numbers of the form 2^t - 2^k - 1, 0 <= k < t.
n is in the sequence if and only if 2*n+1 is in the sequence. - Robert Israel, Dec 14 2018
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

			From _Tilman Piesk_, May 09 2012: (Start)
This may also be viewed as a triangle:             In binary:
                  0                                         0
               1     2                                 01       10
             3    5    6                          011      101      110
           7   11   13   14                  0111     1011     1101     1110
        15   23   27   29   30          01111    10111    11011    11101    11110
      31  47   55   59   61   62
   63   95  111  119  123  125  126
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)
From _Gus Wiseman_, May 24 2024: (Start)
The terms together with their binary expansions and binary indices begin:
   0:      0 ~ {}
   1:      1 ~ {1}
   2:     10 ~ {2}
   3:     11 ~ {1,2}
   5:    101 ~ {1,3}
   6:    110 ~ {2,3}
   7:    111 ~ {1,2,3}
  11:   1011 ~ {1,2,4}
  13:   1101 ~ {1,3,4}
  14:   1110 ~ {2,3,4}
  15:   1111 ~ {1,2,3,4}
  23:  10111 ~ {1,2,3,5}
  27:  11011 ~ {1,2,4,5}
  29:  11101 ~ {1,3,4,5}
  30:  11110 ~ {2,3,4,5}
  31:  11111 ~ {1,2,3,4,5}
  47: 101111 ~ {1,2,3,4,6}
  55: 110111 ~ {1,2,3,5,6}
  59: 111011 ~ {1,2,4,5,6}
  61: 111101 ~ {1,3,4,5,6}
  62: 111110 ~ {2,3,4,5,6}
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure, arXiv:0801.0072 [math.CO], 2007-201. See Section 14.
Vladimir Shevelev, Binomial Coefficient Predictors, Journal of Integer Sequences, Vol. 14 (2011), Article 11.2.8.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1.
Index entries for sequences related to binary expansion of n.

Cf. A000120, A007088, A011371, A014132, A023416, A023532, A029931.
Cf. A181741 (primes), union of A081118 and A000918, apart from initial -1.
Cf. A065442, A160502, A265705.
For least binary index (instead of rank) we have A001511.
Applying A019565 (Heinz number of binary indices) gives A077011.
For greatest binary index we have A029837 or A070939, opposite A070940.
Row minima of A118462 (binary ranks of strict partitions).
For sum instead of minimum we have A372888, non-strict A372890.
A000009 counts strict partitions, ranks A005117.
A048675 gives binary rank of prime indices, distinct A087207.
A048793 lists binary indices, product A096111, reverse A272020.
A277905 groups all positive integers by binary rank of prime indices.
Cf. A000041, A005940, A018819, A147655, A225620, A246868.

a089633 n = a089633_list !! (n-1)
a089633_list = [2 ^ t - 2 ^ k - 1 | t <- [1..], k <- [t-1,t-2..0]]
-- Reinhard Zumkeller, Feb 23 2012

seq(seq(2^a-1-2^b,b=a-1..0,-1),a=1..11); # Robert Israel, Dec 14 2018

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

{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)}
{for(w=0,1536,if(insq(w)>=0,print1(w,", ")))}
\\ Douglas Latimer, May 07 2013

isoka(n) = #select(x->(x==0), binary(n)) <= 1; \\ Michel Marcus, Dec 14 2018

from itertools import count, islice
def A089633_gen(): # generator of terms
    return ((1<A089633_list = list(islice(A089633_gen(),30)) # Chai Wah Wu, Feb 10 2023

from math import isqrt, comb
def A089633(n): return (1<<(a:=(isqrt((n<<3)+1)-1>>1)+1))-(1<Chai Wah Wu, Dec 19 2024

A023416(a(n)) <= 1; A023416(a(n)) = A023532(n-2) for n>1;
A000120(a(u)) <= A000120(a(v)) for uA000120(a(n)) = A003056(n).
a(0)=0, n>0: a(n+1) = Min{m>n: BinOnes(a(n))<=BinOnes(m)} with BinOnes=A000120.
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
A029931(a(n)) = n and A029931(m) != n for m < a(n). - Reinhard Zumkeller, Feb 28 2014
A265705(a(n),k) = A265705(a(n),a(n)-k), k = 0 .. a(n). - Reinhard Zumkeller, Dec 15 2015
a(A014132(n)-1) = 2*a(n-1)+1 for n >= 1. - Robert Israel, Dec 14 2018
Sum_{n>=1} 1/a(n) = A065442 + A160502 = 3.069285887459... . - Amiram Eldar, Jan 09 2024
A019565(a(n)) = A077011(n). - Gus Wiseman, May 24 2024

A265705 Triangle read by rows: T(n,k) = k IMPL n, 0 <= k <= n, bitwise logical IMPL.

Original entry on oeis.org

0, 1, 1, 3, 2, 3, 3, 3, 3, 3, 7, 6, 5, 4, 7, 7, 7, 5, 5, 7, 7, 7, 6, 7, 6, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 15, 14, 13, 12, 11, 10, 9, 8, 15, 15, 15, 13, 13, 11, 11, 9, 9, 15, 15, 15, 14, 15, 14, 11, 10, 11, 10, 15, 14, 15, 15, 15, 15, 15, 11, 11, 11, 11, 15

Offset: 0

Reinhard Zumkeller, Dec 15 2015

			.          10 | 1010                            12 | 1100
.           4 |  100                             6 |  110
.   ----------+-----                     ----------+-----
.   4 IMPL 10 | 1011 -> T(10,4)=11       6 IMPL 12 | 1101 -> T(12,6)=13
.
First 16 rows of the triangle, where non-symmetrical rows are marked, see comment concerning A158582 and A089633:
.   0:                                 0
.   1:                               1   1
.   2:                             3   2   3
.   3:                           3   3   3   3
.   4:                         7   6   5   4   7    X
.   5:                       7   7   5   5   7   7
.   6:                     7   6   7   6   7   6   7
.   7:                   7   7   7   7   7   7   7   7
.   8:                15  14  13  12  11  10   9   8  15    X
.   9:              15  15  13  13  11  11   9   9  15  15    X
.  10:            15  14  15  14  11  10  11  10  15  14  15    X
.  11:          15  15  15  15  11  11  11  11  15  15  15  15
.  12:        15  14  13  12  15  14  13  12  15  14  13  12  15    X
.  13:      15  15  13  13  15  15  13  13  15  15  13  13  15  15
.  14:    15  14  15  14  15  14  15  14  15  14  15  14  15  14  15
.  15:  15  15  15  15  15  15  15  15  15  15  15  15  15  15  15  15 .

Reinhard Zumkeller, Rows n = 0..255 of triangle, flattened
Eric Weisstein's World of Mathematics, Implies

Cf. A003817, A007088, A029578, A089633, A158582, A247648, A265716 (central terms), A265736 (row sums).
Cf. A053644, A265885, A327490.
Other triangles: A080099 (AND), A080098 (OR), A051933 (XOR), A102037 (CNIMPL).

a265705_tabl = map a265705_row [0..]
a265705_row n = map (a265705 n) [0..n]
a265705 n k = k `bimpl` n where
   bimpl 0 0 = 0
   bimpl p q = 2 * bimpl p' q' + if u <= v then 1 else 0
               where (p', u) = divMod p 2; (q', v) = divMod q 2

using IntegerSequences
for n in 0:15 println(n == 0 ? [0] : [Bits("IMP", k, n) for k in 0:n]) end  # Peter Luschny, Sep 25 2021

A265705 := (n, k) -> Bits:-Implies(k, n):
seq(seq(A265705(n, k), k=0..n), n=0..11); # Peter Luschny, Sep 23 2019

T[n_, k_] := If[n == 0, 0, BitOr[2^Length[IntegerDigits[n, 2]]-1-k, n]];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 25 2021, after David A. Corneth's PARI code *)

T(n, k) = if(n==0,return(0)); bitor((2<David A. Corneth, Sep 24 2021

T(n,0) = T(n,n) = A003817(n).
T(2*n,n) = A265716(n).
Let m = A089633(n): T(m,k) = T(m,m-k), k = 0..m.
Let m = A158582(n): T(m,k) != T(m,m-k) for at least one k <= n.
Let m = A247648(n): T(2*m,m) = 2*m.
For n > 0: A029578(n+2) = number of odd terms in row n; no even terms in odd-indexed rows.
A265885(n) = T(prime(n),n).
A053644(n) = smallest k such that row k contains n.

A362248 a(n) is the number of locations 1..n-1 which can reach i=n-1, where jumps from location i to i +- a(i) are permitted (within 1..n-1); a(1)=1. See example.

Original entry on oeis.org

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

Offset: 1

Neal Gersh Tolunsky, May 12 2023

nonn

Note that location n-1 itself is counted as a term which can reach i=n-1.
Conjecture: a(n) is also the largest number such that starting point i=n can reach every previous location (with a(1)=1 and the same rule for jumps as in the current name).
A047619 appears to be the indices of 1's in this sequence.
A023758 appears to be the indices of terms for which a(n)=n-1.
A089633 appears to be the distinct values of the sequence (and its complement A158582 the missing values).
The sequence appears to consist of monotonically increasing runs of length 4.
It appears that a(A004767(n))=A100892(n) and a(A016825(n))=A100892(n)-1.

			a(6)=5 because there are 5 starting terms from which i=5 can be reached:
  1, 1, 2, 3, 1
  1->1->2---->1
We can see that i=1,2,3 and trivially 5 can reach i=5. i=4 can also reach i=5:
  1, 1, 2, 3, 1
  1<-------3
  1->1->2---->1
This is a total of 5 locations, so a(6)=5.

Kevin Ryde, Table of n, a(n) for n = 1..10000
Kevin Ryde, C Code

Cf. A360746, A360745, A047619, A023758, A089633, A100892.

C
```
/* See links */
```

a(24) onwards from Kevin Ryde, May 17 2023

A158581 Numbers having in binary representation at least two ones and two zeros.

Original entry on oeis.org

9, 10, 12, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 60, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 96, 97

Offset: 1

Reinhard Zumkeller, Apr 16 2009

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Intersection of A158582 and A057716.

Cf. A007088, A000120, A023416

Select[Range[100],Min[DigitCount[#,2]]>1&] (* Harvey P. Dale, Mar 09 2013 *)

def ok(n): b = bin(n)[2:]; return b.count('0') >= 2 and b.count('1') >= 2
print(list(filter(ok, range(98)))) # Michael S. Branicky, Sep 10 2021

def A158581(n):
    def f(x):
        c = n+((l:=(x+1).bit_length())*(l+1)>>1)-3
        m = bin(x+1)[2:].find('0')
        c += m if m>-1 else l
        return c
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Dec 24 2024

A023416(a(n)) > 1; A000120(a(n)) > 1.

A089591 "Lazy binary" representation of n. Also called redundant binary representation of n.

Original entry on oeis.org

0, 1, 10, 11, 20, 101, 110, 111, 120, 201, 210, 1011, 1020, 1101, 1110, 1111, 1120, 1201, 1210, 2011, 2020, 2101, 2110, 10111, 10120, 10201, 10210, 11011, 11020, 11101, 11110, 11111, 11120, 11201, 11210, 12011, 12020, 12101, 12110, 20111

Offset: 0

Jeff Erickson, Dec 29 2003

Let a(0) = 0 and construct a(n) from a(n-1) by (i) incrementing the rightmost digit and (ii) if any digit is 2, replace the rightmost 2 with a 0 and increment the digit immediately to its left. (Note that changing "if" to "while" in this recipe gives the standard binary representation of n, A007088(n)).
Equivalently, a(2n+1) = a(n):1 and a(2n+2) = b(n):0, where b(n) is obtained from a(n) by incrementing the least significant digit and : denotes string concatenation.
If the digits of a(n) are d_k, d_{k-1}, ..., d_2, d_1, d_0, then n = Sum_{i=0..k} d_i*2^i, just as in standard binary notation.  The difference is that here we are a bit lazy, and allow a few digits to be 2's. The number of 2's in a(n) appears to be A037800(n+1). - N. J. A. Sloane, Jun 03 2023
Every pair of 2's is separated by a 0 and every pair of significant 0's is separated by a 2.
a(n) has exactly floor(log_2((n+2)/3))+1 digits [cf. A033484] and their sum is exactly floor(log_2(n+1)) [A000523].
The i-th digit of a(n) is ceiling( floor( ((n+1-2^i) mod 2^(i+1))/2^(i-1) ) / 2).
A137951 gives values of terms interpreted as ternary numbers, a(n)=A007089(A137951(n)). - Reinhard Zumkeller, Feb 25 2008

			a(8) = 120 -> 121 -> 201 = a(9); a(9) = 201 -> 202 -> 210 = a(10).

Gerth S. Brodal, Worst-case efficient priority queues, SODA 1996.
Michael J. Clancy and D. E. Knuth, A programming and problem-solving seminar, Technical Report STAN-CS-77-606, Department of Computer Science, Stanford University, Palo Alto, 1977.
Haim Kaplan and Robert E. Tarjan, Purely functional representations of catenable sorted lists, STOC 1996.
Chris Okasaki, Purely Functional Data Structures, Cambridge, 1998.

R. Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A000523, A033484, A072998, A024629, A089600, A089601, A089604, A037800.

A158582: lazy binary different from regular binary, A089633: lazy binary and regular binary agree.

A089591 := proc(n) option remember ; local nhalf ; if n <= 1 then RETURN(n) ; else nhalf := floor(n/2) ; if n mod 2 = 1 then RETURN(10*A089591(nhalf) +1) ; else RETURN(10*(A089591(nhalf-1)+1)) ; fi ; fi ; end: for n from 0 to 200 do printf("%d, ",A089591(n)) ; od ; # R. J. Mathar, Mar 11 2007

a[n_] := a[n] = Module[{nhalf}, If[n <= 1, Return[n], nhalf = Floor[n/2]; If[Mod[n, 2]==1, Return[10*a[nhalf]+1], Return[10*(a[nhalf-1]+1)]]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 19 2016, after R. J. Mathar *)

More terms from R. J. Mathar, Mar 11 2007
Edited by Charles R Greathouse IV, Apr 30 2010
Edited by N. J. A. Sloane, Jun 03 2023

A377563 Numbers that have fewer infinitary divisors than noninfinitary divisors.

Original entry on oeis.org

16, 36, 48, 80, 81, 100, 112, 144, 162, 176, 180, 196, 208, 225, 240, 252, 256, 272, 288, 300, 304, 324, 336, 368, 396, 400, 405, 432, 441, 450, 464, 468, 484, 496, 512, 528, 560, 567, 576, 588, 592, 612, 624, 625, 648, 656, 676, 684, 688, 700, 720, 752, 768, 784, 800

Offset: 1

Amiram Eldar, Nov 01 2024

Numbers whose prime factorization has at least one exponent that has at least two zeros in its binary representation (A158582), or at least two exponents that are not of the form 2^k-1, with k >= 1 (A062289).

The asymptotic density of this sequence is 1 - d * (1 + Sum_{p prime} (Sum_{k>=0} 1/p^(3*2^k-1))/(1 + Sum_{k>=1} 1/p^(2^k-1))) = 0.07306380398261191432..., where d = A327839.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000005, A037445, A062289, A077609, A083329, A158582, A327839, A335832, A348341, A377562.

f[p_, e_] := 2^DigitCount[e, 2, 1]/(e + 1); q[1] = False; q[n_] := Times @@ f @@@ FactorInteger[n] < 1/2; Select[Range[800], q]

is(n) = {my(f = factor(n)); vecprod(apply(x -> (1 << hammingweight(x)) / (x+1), f[, 2])) < 1/2;}

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A265705 Triangle read by rows: T(n,k) = k IMPL n, 0 <= k <= n, bitwise logical IMPL.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Julia

Maple

Mathematica

PARI

Formula

A362248 a(n) is the number of locations 1..n-1 which can reach i=n-1, where jumps from location i to i +- a(i) are permitted (within 1..n-1); a(1)=1. See example.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Extensions

A158581 Numbers having in binary representation at least two ones and two zeros.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Python

Formula

A089591 "Lazy binary" representation of n. Also called redundant binary representation of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A377563 Numbers that have fewer infinitary divisors than noninfinitary divisors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI