A004754 -id:A004754 - cp's OEIS frontend

A004761 Numbers n whose binary expansion does not begin with 11.

0, 1, 2, 4, 5, 8, 9, 10, 11, 16, 17, 18, 19, 20, 21, 22, 23, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 64, 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, 95, 128, 129

Offset: 1

N. J. A. Sloane

Robert Israel, Table of n, a(n) for n = 1..10000

Apart from initial terms, same as A004754.

f:= proc(n) option remember; if n::odd then procname(n-1)+1 else 2*procname(n/2+1) fi
end proc:
f(1):= 0: f(2):= 1:
map(f, [$1..100]); # Robert Israel, Mar 31 2017

Select[Range[0, 140], # <= 2 || Take[IntegerDigits[#, 2], 2] != {1, 1} &] (* Michael De Vlieger, Aug 03 2016 *)

is(n)=n^2==n || !binary(n)[2] \\ Charles R Greathouse IV, Mar 07 2013

a(n) = if(n<=2,n-1, n-=2; n + 1<Kevin Ryde, Apr 14 2021

def A004761(n): return m+(1<Chai Wah Wu, Jul 26 2023

maxrow <- 8 # by choice
b01 <- 1
for(m in 0:maxrow){
  b01 <- c(b01,rep(1,2^(m+1))); b01[2^(m+1):(2^(m+1)+2^m-1)] <- 0
}
(a <- c(0,1,which(b01 == 0)))
# Yosu Yurramendi, Mar 30 2017

a(1)=0, a(2)=1 and for k>1: a(2*k-1) = a(2*k-2)+1, a(2*k) = 2*a(k+1). - Reinhard Zumkeller, Jan 09 2002, corrected by Robert Israel, Mar 31 2017
For n > 0, a(n) = 1/2 * (4n - 3 - A006257(n-1)). - Ralf Stephan, Sep 16 2003
a(1) = 0, a(2) = 1, a(2^m+k+2) = 2^(m+1)+k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Jul 30 2016
a(2^m+k) = A004760(2^m+k) - 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 08 2016
G.f. g(x) satisfies g(x) = 2*(1+x)*g(x^2)/x^2 - x^2*(1-x^2-x^3)/(1-x^2). - Robert Israel, Mar 31 2017

A004756 Binary expansion starts 100.

Original entry on oeis.org

4, 8, 9, 16, 17, 18, 19, 32, 33, 34, 35, 36, 37, 38, 39, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153

Offset: 1

N. J. A. Sloane

			18 in binary is 10010, so 18 is in sequence.

T. D. Noe, Table of n, a(n) for n = 1..1023
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A004754 (10), A004755 (11), A004757 (101), A004758 (110), A004759 (111).

Cf. A004760, A053644, A062050, A076877.

import Data.List (transpose)
a004756 n = a004756_list !! (n-1)
a004756_list = 4 : concat (transpose [zs, map (+ 1) zs])
                   where zs = map (* 2) a004756_list
-- Reinhard Zumkeller, Dec 04 2015

Select[Range[4, 153], Take[IntegerDigits[#, 2], 3] == {1, 0, 0} &] (* Michael De Vlieger, Aug 07 2016 *)

PARI
```
a(n)=n+3*2^floor(log(n)/log(2))
```

def A004756(n): return n+(3<Chai Wah Wu, Jul 13 2022

a(2n) = 2a(n), a(2n+1) = 2a(n) + 1 + 3*[n==0].
a(n) = n + 3 * 2^floor(log_2(n)) = A004755(n) + A053644(n).
a(2^m+k) = 2^(m+2) + k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 07 2016

Edited by Ralf Stephan, Oct 12 2003

A171757 Even numbers whose binary expansion begins 10.

Original entry on oeis.org

2, 4, 8, 10, 16, 18, 20, 22, 32, 34, 36, 38, 40, 42, 44, 46, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178

Offset: 1

N. J. A. Sloane, Oct 12 2010

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1024 from R. J. Mathar)

Cf. A004761, A171758, A171763, A171764.

A subsequence of A004754.

n := 1 ;
for k from 2 to 4000 by 2 do
    dgs := convert(k,base,2) ;
    if op(-1,dgs) = 1 and op(-2,dgs) = 0 then
        printf("%d %d\n",n,k) ;
        n := n+1 ;
    end if;
end do: # R. J. Mathar, Jan 31 2015

Select[Range[2, 200, 2], IntegerDigits[#, 2][[1 ;; 2]] == {1, 0} &] (* Amiram Eldar, Sep 01 2020 *)

isok(m) = if (!(m%2), my(b=binary(m)); (b[1]==1) && (b[2]==0)); \\ Michel Marcus, Jun 24 2021

from itertools import count, product, takewhile
def agen(): # generator for sequence
    yield 2
    for digits in count(0):
        for mid in product("01", repeat=digits):
            yield int("10" + "".join(mid) + "0", 2)
def aupto(lim): return list(takewhile(lambda x: x <= lim, agen()))
print(aupto(180)) # Michael S. Branicky, Jun 24 2021

a(n) = 2*A004761(n+1). - Jon Maiga / Georg Fischer, Jun 24 2021

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 67, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Sep 02 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The terms, binary expansions, and standard compositions:
   1:       1  (1)
   3:      11  (1,1)
   5:     101  (2,1)
   6:     110  (1,2)
   7:     111  (1,1,1)
   9:    1001  (3,1)
  11:    1011  (2,1,1)
  12:    1100  (1,3)
  13:    1101  (1,2,1)
  14:    1110  (1,1,2)
  15:    1111  (1,1,1,1)
  17:   10001  (4,1)
  19:   10011  (3,1,1)
  21:   10101  (2,2,1)
  22:   10110  (2,1,2)
  23:   10111  (2,1,1,1)
  24:   11000  (1,4)
  25:   11001  (1,3,1)
  26:   11010  (1,2,2)
  27:   11011  (1,2,1,1)
  28:   11100  (1,1,3)
  29:   11101  (1,1,2,1)
  30:   11110  (1,1,1,2)
  31:   11111  (1,1,1,1,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
The case beginning with 1 is A004760, complement A004754.
The complement is A022340.
These compositions are counted by A099036, complement A212804.
The case covering an initial interval is A333217.
The gapless but non-initial version is A356843, unordered A356845.
Cf. A004780, A005408, A055932, A073492, A073493, A132747.

Select[Range[0,100],OddQ[#]||MatchQ[IntegerDigits[#,2],{_,1,1,_}]&]

Union of A005408 and A004780.

A004759 Binary expansion starts 111.

Original entry on oeis.org

7, 14, 15, 28, 29, 30, 31, 56, 57, 58, 59, 60, 61, 62, 63, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244

Offset: 1

N. J. A. Sloane

This is the minimal recursive sequence such that a(1)=7, A007814(a(n))= A007814(n) and A010060(a(n))=A010060(n). - Vladimir Shevelev, Apr 23 2009

			30 in binary is 11110, so 30 is in sequence.

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

Cf. A004754 (10), A004755 (11), A004756 (100), A004757 (101), A004758 (110).
Cf. A004760, A053644, A062050, A076877.
Cf. A007814, A010060, A103204, A159559, A159560, A159615, A159619, A159629, A159698. -Vladimir Shevelev, Apr 23 2009

import Data.List (transpose)
a004759 n = a004759_list !! (n-1)
a004759_list = 7 : concat (transpose [zs, map (+ 1) zs])
                   where zs = map (* 2) a004759_list
-- Reinhard Zumkeller, Dec 03 2015

w = {1, 1, 1}; Select[Range[5, 244], If[# < 2^(Length@ w - 1), True, Take[IntegerDigits[#, 2], Length@ w] == w] &] (* Michael De Vlieger, Aug 10 2016 *)
Sort[FromDigits[#,2]&/@(Flatten[Table[Join[{1,1,1},#]&/@Tuples[{1,0},n],{n,0,5}],1])] (* Harvey P. Dale, Sep 01 2016 *)

PARI
```
a(n)=n+6*2^floor(log(n)/log(2))
```

def A004759(n): return n+(3<Chai Wah Wu, Jul 13 2022

a(2n) = 2a(n), a(2n+1) = 2a(n) + 1 + 6[n==0].
a(n) = n + 6 * 2^floor(log_2(n)) = A004758(n) + A053644(n).
a(n+1) = min{m > a(n): A007814(m) = A007814(n+1) and A010060(m) = A010060(n+1)}. a(2^k) - a(2^k-1) = A103204(k+2), k >= 1. - Vladimir Shevelev, Apr 23 2009
a(2^m+k) = 7*2^m + k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 08 2016

Edited by Ralf Stephan, Oct 12 2003

A364295 Numbers k such that A292943(k) = A292944(k).

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 45, 48, 64, 72, 90, 96, 128, 144, 165, 180, 189, 192, 256, 288, 330, 360, 378, 384, 512, 576, 660, 720, 756, 768, 1024, 1152, 1320, 1440, 1512, 1536, 2048, 2304, 2640, 2880, 3024, 3072, 4096, 4608, 5280, 5760, 6048, 6144, 8192, 9216, 10560, 11520, 12096, 12288, 16384

Offset: 1

Antti Karttunen, Jul 26 2023

nonn

If n is present, then 2*n is also present, and vice versa.

A007283 is included as a subsequence, because it gives the known fixed points of map n -> A163511(n).

Cf. A163511, A243071, A292943, A292944.
Subsequences: A000079, A007283, A029744, A364296 (odd terms).
Cf. also A364494, A364496.

A004754(n) = (n+(1<<(#binary(n)-1)));
A053644(n) = { my(k=1); while(k<=n, k<<=1); (k>>1); };
A292272(n) = (n - bitand(n,n\2));
A292944(n) = (A292272(A004754(n)) - 2*A053644(n));
A054429(n) = ((3<<#binary(n\2))-n-1);
A156552(n) = { my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A243071(n) = if(n<=2, n-1, A054429(A156552(n)));
A292943(n) = A292944(A243071(n));
isA364295(n) = (A292943(n)==A292944(n));

A010078 Shortest representation of -n in 2's-complement format.

Original entry on oeis.org

1, 2, 5, 4, 11, 10, 9, 8, 23, 22, 21, 20, 19, 18, 17, 16, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 191, 190, 189

Offset: 1

Leonid Broukhis

			In binary:
  a(   1_2) =    1_2,
  a(  10_2) =   10_2,
  a( 011_2) =  101_2,
  a( 100_2) =  100_2,
  a(0101_2) = 1011_2,
  a(0110_2) = 1010_2,
  a(0111_2) = 1001_2,
  a(1000_2) = 1000_2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..8192
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Cf. A004754 (terms sorted), A008687 (binary weight).

a010078 = x . subtract 1 where
   x m = if m == 0 then 1 else 2 * x m' + 1 - b
            where (m',b) = divMod m 2
-- Reinhard Zumkeller, Feb 21 2014

Array[2^(Ceiling[Log2[#] + 1]) - # &, 67] (* Michael De Vlieger, Oct 15 2018 *)

a(n) = if(n--, bitneg(n,2+logint(n,2)), 1); \\ Kevin Ryde, Apr 14 2021

a(n) = 2^(ceiling(log_2(n)+1)) - n.
a(n) = b(n-1), where b(n) = 1 if n = 0, otherwise 2*b(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Feb 19 2003
G.f.: (x/(1-x)) * (1/x + Sum_{k>=0} 2^k*(x^2^k + 2x^2^(k+1))/(1+x^2^k)). - Ralf Stephan, Jun 15 2003
a(1) = 1; for n > 1, a(2n-1) = 2*a(n) + 1; for n >= 1, a(2n) = 2*a(n). - Philippe Deléham, Feb 29 2004

A092754 a(1)=1, a(2n)=2a(n)+1, a(2n+1)=2a(n)+2.

Original entry on oeis.org

1, 3, 4, 7, 8, 9, 10, 15, 16, 17, 18, 19, 20, 21, 22, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 63, 64, 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, 127, 128, 129, 130, 131, 132

Offset: 1

Benoit Cloitre, Apr 13 2004

More generally the sequence b(1)=1, b(2n)=2b(n)+x, b(2n+1)=2b(n)+y is given by the formula b(n)=A053644(n)+x*(n-A053644(n))+y*(A053644(n)-1).

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

Cf. A053644 (x=y=0), A054429(x=-1, y=+1), A062050(x=+1, y=-1).
Cf. A206332 (complement).
Cf. A004754.

a092754 n = if n < 2 then n else 2 * a092754 n' + m + 1
            where (n',m) = divMod n 2
a092754_list = map a092754 [1..]
-- Reinhard Zumkeller, May 07 2012

a(n)=if(n<2,1,if(n%2,a(n-1)+1,a(n/2)*2+1))

PARI
```
a(n) = n + 1<Kevin Ryde, Jun 19 2021
```

a(n) = 2^floor(log(n)/log(2)) + n - 1.

a(n) = A004754(n) - 1. - Rémy Sigrist, May 05 2019

A171763 Odd numbers whose binary expansion begins 10.

Original entry on oeis.org

5, 9, 11, 17, 19, 21, 23, 33, 35, 37, 39, 41, 43, 45, 47, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179

Offset: 1

N. J. A. Sloane, Oct 12 2010

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

Cf. A171757, A171758, A171764.

A subsequence of A004754.

Select[Range[3,181,2],Take[IntegerDigits[#,2],2]=={1,0}&] (* Harvey P. Dale, Jun 09 2016 *)

A218614 a(n) = binary code (shown here in decimal) of the position of natural number n in the beanstalk-tree A218778.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 13, 21, 29, 37, 53, 69, 101, 85, 117, 181, 245, 309, 437, 565, 821, 693, 949, 1205, 1717, 1461, 1973, 2741, 3765, 2485, 3509, 5557, 7605, 9653, 13749, 17845, 26037, 21941, 30133, 38325, 54709, 46517, 62901, 87477, 120245, 79285, 112053, 144821

Offset: 1

Antti Karttunen, Nov 16 2012

The binary code is the same as used by function general-car-cdr of MIT/GNU Scheme: a zero bit represents a cdr operation (taking the right hand side branch in the binary tree), and a one bit represents a car (taking the left hand side branch in the binary tree). The bits are interpreted from LSB to MSB, and the most significant one bit, rather than being interpreted as an operation, signals the end of the binary code.

			As we must traverse to 4 in A218778-tree (see the example there) by first taking the left branch (car) from the root, resulting bit 1 as the least significant bit of the code, then by taking the right branch (cdr) from 3 to get to 4, resulting bit 0 as the second rightmost bit of the code, which when capped with an extra termination-one, results binary code 101, 5 in decimal, thus a(4)=5.

A. Karttunen, Table of n, a(n) for n = 1..1024
MIT/GNU Scheme 9.1. documentation, Function general-car-cdr

a(n) = A054429(A218615(n)). Superset of A218790. Used to construct A218778, A218779. Cf. also A218787, A218788

a(1)=1; for even n, a(n) = A004754(a(A011371(n))); for odd n, a(n) = A004755(a(A011371(n))).

cp's OEIS Frontend

A004761 Numbers n whose binary expansion does not begin with 11.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

R

Formula

A004756 Binary expansion starts 100.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A171757 Even numbers whose binary expansion begins 10.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A004759 Binary expansion starts 111.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A364295 Numbers k such that A292943(k) = A292944(k).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A010078 Shortest representation of -n in 2's-complement format.

Views

Author

Keywords

Examples