A003714 -id:A003714 - cp's OEIS frontend

A257250 Numbers n for which A256999(n) = n; numbers that cannot be made any larger by rotating (by one or more steps) the non-msb bits of their binary representation (with A080541 or A080542).

0, 1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 16, 24, 26, 28, 30, 31, 32, 48, 52, 56, 58, 60, 62, 63, 64, 96, 100, 104, 106, 112, 114, 116, 118, 120, 122, 124, 126, 127, 128, 192, 200, 208, 212, 224, 226, 228, 232, 234, 236, 240, 242, 244, 246, 248, 250, 252, 254, 255, 256, 384, 392, 400, 416, 420, 424, 426, 448, 450

Offset: 0

Antti Karttunen, May 16 2015

These correspond to the maximal (lexicographically largest) representatives selected from each equivalence class of binary necklaces. See the last example.
Indexing starts from zero, because a(0) = 0 is a special case.
If k is a member then so also is 2*k, i.e., k with 0 appended to the end of its binary representation.
If k is a member then so also is A004755(k), i.e., k with 1 prepended to the front of its binary representation.
One obtains A065609 if one erases the most significant bit of each term [as A053645(a(n))] and then discards any zero-terms produced from the terms that originally were powers of two (A000079).
First differs from A328607 in lacking 108, with binary expansion 1101100. If we define a dual-necklace to be a finite sequence that is lexicographically maximal (not minimal) among all of its cyclic rotations, these are numbers whose binary expansion, without the most significant digit, is a dual-necklace. - Gus Wiseman, Nov 04 2019

			For n = 5, with binary representation "101", if we rotate other bits than the most significant bit (that is, only the two rightmost digits "01") one step to either direction, we get "110" = 6 > 5, so 5 can be made larger by such rotations, and thus is NOT included in this sequence.
For n = 6, with binary representation "110", no such rotation will yield a larger number, and thus 6 is included in this sequence.
For n = 28, with binary representation "11100", if we rotate non-msb bits towards right, we get additional numbers 22, 19 and 25 (with binary representations "10110", "10011", "11001") before coming to 28 again, and 28 is the largest of these numbers, thus 28 is included in this sequence.
  Also, if we discard the most significant bit of each and consider them just as binary strings, then A053645(28) = 12 is the lexicographically largest representative of {"1100", "0110", "0011", "1001"}, which is the complete set of representatives for a particular equivalence class of binary necklaces, obtained by rotating all bits of binary string "1100" successively towards right or left.

Antti Karttunen, Table of n, a(n) for n = 0..16637
Wikipedia, Necklace (combinatorics)
Index entries for sequences related to necklaces

Complement: A257739.
Odd terms: A000225.
Subsequence of A065609.
Cf. A004755, A053645, A080541, A080542, A256999.
Subsequence: A258003.
The non-dual version is A328668.
The version involving all digits is A065609.
The non-dual reversed version is A328607.
Numbers whose reversed binary expansion is a necklace are A328595.
Binary necklaces are A000031.
Necklace compositions are A008965.
Cf. A000120, A001037, A003714, A014081, A069010, A275692, A328594, A328596.

reckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
Select[Range[0,110],#<=1||reckQ[Rest[IntegerDigits[#,2]]]&] (* Gus Wiseman, Nov 04 2019 *)

;; With Antti Karttunen's IntSeq-library.
(define A257250 (MATCHING-POS 0 0 (lambda (n) (= n (A256999 n)))))

A269161 Formula for Wolfram's Rule 86 cellular automaton: a(n) = 4n XOR (2n OR n).

Original entry on oeis.org

0, 7, 14, 11, 28, 27, 22, 19, 56, 63, 54, 51, 44, 43, 38, 35, 112, 119, 126, 123, 108, 107, 102, 99, 88, 95, 86, 83, 76, 75, 70, 67, 224, 231, 238, 235, 252, 251, 246, 243, 216, 223, 214, 211, 204, 203, 198, 195, 176, 183, 190, 187, 172, 171, 166, 163, 152, 159, 150, 147, 140, 139, 134, 131, 448, 455, 462, 459

Offset: 0

Antti Karttunen, Feb 20 2016

nonn

The sequence is injective: no value occurs more than once.

Fibbinary numbers (A003714) give all integers n>=0 for which a(n) = A048727(n) and for which a(n) = A269160(n).

Antti Karttunen, Table of n, a(n) for n = 0..16383
Eric Weisstein's World of Mathematics, Rule 30
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A003714, A003986, A003987, A057889, A163617.
Cf. A265281 (iterates starting from 1).
Cf. also A048727, A269160.

a[n_] := BitXor[4n, BitOr[2n, n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 23 2016 *)

def A269161(n): return n<<2 ^ (n<<1 |n) # Chai Wah Wu, Jun 29 2022

(define (A269161 n) (A003987bi (* 4 n) (A003986bi (* 2 n) n))) ;; Where A003986bi and A003987bi are implementation of dyadic functions giving bitwise-OR (A003986) and bitwise-XOR (A003987) of their arguments.

a(n) = 4n XOR (2n OR n) = A003987(4*n, A003986(2*n, n)).
a(n) = 4*n XOR A163617(n).
Other identities. For all n >= 0:
a(2*n) = 2*a(n).
a(n) = A057889(A269160(A057889(n))). [Rule 86 is the mirror image of rule 30.]

A244161 Greedy Catalan Base (A014418) interpreted as base-4 numbers, then shown in decimal.

Original entry on oeis.org

0, 1, 4, 5, 8, 16, 17, 20, 21, 24, 32, 33, 36, 37, 64, 65, 68, 69, 72, 80, 81, 84, 85, 88, 96, 97, 100, 101, 128, 129, 132, 133, 136, 144, 145, 148, 149, 152, 160, 161, 164, 165, 256, 257, 260, 261, 264, 272, 273, 276, 277, 280, 288, 289, 292, 293, 320, 321, 324, 325

Offset: 0

Antti Karttunen, Jun 23 2014

This representation does not lose any information, because C(n+1)/C(n) [where C(n) is the n-th Catalan number, A000108(n)] approaches 4 from below, but never attains it.

Analogously to "Fibbinary numbers", A003714, this sequence could be called "Catquaternary numbers".

Indranil Ghosh, Table of n, a(n) for n = 0..1000

Cf. A000108, A014418, A003714, A085183, A085184, A244160.

from sympy import catalan
def a244160(n):
    if n==0: return 0
    i=1
    while True:
        if catalan(i)>n: break
        else: i+=1
    return i - 1
def a(n):
    if n==0: return 0
    x=a244160(n)
    return 4**(x - 1) + a(n - catalan(x))
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 08 2017

;; With memoizing definec-macro from Antti Karttunen's IntSeq-library.
;; Version based on direct recurrence:
(definec (A244161 n) (if (zero? n) n (+ (expt 4 (- (A244160 n) 1)) (A244161 (- n (A000108 (A244160 n)))))))

a(0) = 0, a(n) = 4^(A244160(n)-1) + a(n-A000108(A244160(n))). [Where A244160 gives the index of the largest Catalan number that still fits into the sum].

A000035(a(n)) = A000035(A014418(n)). [This sequence and the base-10 version are equal when reduced modulo 2].

A246200 Self-inverse permutation of natural numbers: a(n) = A057889(3*n) / 3.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 19, 14, 15, 16, 17, 18, 13, 20, 21, 22, 27, 24, 35, 38, 23, 28, 39, 30, 31, 32, 33, 34, 25, 36, 41, 26, 29, 40, 37, 42, 43, 44, 75, 54, 59, 48, 67, 70, 51, 76, 83, 46, 55, 56, 71, 78, 47, 60, 79, 62, 63, 64, 65, 66, 49, 68, 81, 50, 57, 72, 73, 82, 45, 52, 77, 58, 61, 80, 69

Offset: 0

Antti Karttunen, Aug 27 2014

In binary system, 3 ("11" in binary), has a similar shortcut rule for divisibility as eleven has in decimal system. This rule doesn't depend on which end of the number representation it is applied from, thus, if we reverse the number 3*n with "balanced bit-reverse" (A057889), the result should still be divisible by 3. Moreover, because the reversing operation is itself a self-inverse involution, and the prime factorization of any natural number is unique, we get a self-inverse permutation of nonnegative integers when we divide the bit-reversed result with 3.

Antti Karttunen, Table of n, a(n) for n = 0..10921
Index entries for sequences that are permutations of the natural numbers

Cf. A036215, A057889, A003714, A048724, A083822, A083824.

def a057889(n):
    x=bin(n)[2:]
    y=x[::-1]
    return int(str(int(y))+(len(x) - len(str(int(y))))*'0', 2)
def a(n): return a057889(3*n)//3
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 11 2017

(define (A246200 n) (/ (A057889 (* 3 n)) 3))

a(n) = A057889(3*n) / 3.

A328593 Numbers whose binary indices have no consecutive divisible parts.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 14, 16, 18, 20, 22, 24, 28, 30, 32, 40, 44, 46, 48, 50, 52, 54, 56, 60, 62, 64, 66, 68, 70, 72, 76, 78, 80, 82, 84, 86, 88, 92, 94, 96, 104, 108, 110, 112, 114, 116, 118, 120, 124, 126, 128, 132, 134, 144, 146, 148, 150, 152, 156, 158, 160

Offset: 1

Gus Wiseman, Oct 21 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The sequence of terms together with their binary expansions and binary indices begins:
   0:      0 ~ {}
   1:      1 ~ {1}
   2:     10 ~ {2}
   4:    100 ~ {3}
   6:    110 ~ {2,3}
   8:   1000 ~ {4}
  12:   1100 ~ {3,4}
  14:   1110 ~ {2,3,4}
  16:  10000 ~ {5}
  18:  10010 ~ {2,5}
  20:  10100 ~ {3,5}
  22:  10110 ~ {2,3,5}
  24:  11000 ~ {4,5}
  28:  11100 ~ {3,4,5}
  30:  11110 ~ {2,3,4,5}
  32: 100000 ~ {6}
  40: 101000 ~ {4,6}
  44: 101100 ~ {3,4,6}
  46: 101110 ~ {2,3,4,6}
  48: 110000 ~ {5,6}
  50: 110010 ~ {2,5,6}

The version for prime indices is A328603.
Numbers with no successive binary indices are A003714.
Partitions with no consecutive divisible parts are A328171.
Compositions without consecutive divisible parts are A328460.
Cf. A000120, A014081, A328187, A328508, A328594, A328595, A328598, A328600, A328608.

Select[Range[0,100],!MatchQ[Join@@Position[Reverse[IntegerDigits[#,2]],1],{_,x_,y_,_}/;Divisible[y,x]]&]

A356771 a(n) is the sum of the Fibonacci numbers in common in the Zeckendorf and dual Zeckendorf representations of n.

Original entry on oeis.org

0, 1, 2, 0, 4, 0, 1, 7, 0, 1, 2, 3, 12, 0, 1, 2, 0, 4, 5, 6, 20, 0, 1, 2, 3, 4, 0, 1, 7, 8, 9, 10, 11, 33, 0, 1, 2, 0, 4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 13, 17, 18, 19, 54, 0, 1, 2, 3, 4, 0, 1, 7, 8, 9, 10, 11, 12, 0, 1, 2, 0, 4, 5, 6, 20, 21, 22, 23, 24

Offset: 0

Rémy Sigrist, Aug 27 2022

The Zeckendorf and dual Zeckendorf representations both express a number n as a sum of distinct positive Fibonacci numbers; these distinct Fibonacci numbers can be encoded in binary (see A022290 for the decoding function):
- in the Zeckendorf representation (or greedy Fibonacci representation):
  - Fibonacci numbers are as big as possible (see A035517),
  - and the corresponding binary encoding, A003714(n),
    cannot have two consecutive 1's;
- in the dual Zeckendorf representation (or lazy Fibonacci representation):
  - Fibonacci numbers are as small as possible (see A112309),
  - and the corresponding binary encoding, A003754(n+1),
    cannot have two consecutive nonleading 0's.
See A356326 for a similar sequence.

			For n = 28:
- using F(k) = A000045(k),
- the Zeckendorf representation of 28 is F(8) + F(5) + F(3),
- the dual Zeckendorf representation of 28 is F(7) + F(6) + F(5) + F(3),
- F(5) and F(3) appear in both representations,
- so a(28) = F(5) + F(3) = 7.

Rémy Sigrist, Table of n, a(n) for n = 0..10946
Rémy Sigrist, PARI program
Index entries for sequences related to Zeckendorf expansion of n

Cf. A000071, A003714, A003754, A022290, A035517, A112309, A331467, A356326.

PARI
```
\\ See Links section.
```

a(n) = A022290(A003714(n) AND A003754(n+1)) (where AND denotes the bitwise AND operator).
a(n) = 0 iff n belongs to A331467.
a(n) = n iff n belongs to A000071.

A372516 Number of ones minus number of zeros in the binary expansion of the n-th prime number.

Original entry on oeis.org

0, 2, 1, 3, 2, 2, -1, 1, 3, 3, 5, 0, 0, 2, 4, 2, 4, 4, -1, 1, -1, 3, 1, 1, -1, 1, 3, 3, 3, 1, 7, -2, -2, 0, 0, 2, 2, 0, 2, 2, 2, 2, 6, -2, 0, 2, 2, 6, 2, 2, 2, 6, 2, 6, -5, -1, -1, 1, -1, -1, 1, -1, 1, 3, 1, 3, 1, -1, 3, 3, -1, 3, 5, 3, 5, 7, -1, 1, -1, 1, 1

Offset: 1

Gus Wiseman, May 13 2024

sign

Absolute value is A177718.

			The binary expansion of 83 is (1,0,1,0,0,1,1), and 83 is the 23rd prime, so a(23) = 4 - 3 = 1.

The sum instead of difference is A035100, firsts A372684 (primes A104080).
The negative version is A037861(A000040(n)).
Restriction of A145037 to the primes.
The unsigned version is A177718.
- Positions of zeros are A177796, indices of the primes A066196.
- Positions of positive terms are indices of the primes A095070.
- Positions of negative terms are indices of the primes A095071.
- Positions of negative ones are A372539, indices of the primes A095072.
- Positions of ones are A372538, indices of the primes A095073.
- Positions of nonnegative terms are indices of the primes A095074.
- Positions of nonpositive terms are indices of the primes A095075.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A030190 gives binary expansion, reversed A030308.
A035103 counts zeros in binary expansion of primes, firsts A372474.
A048793 lists binary indices, reverse A272020, sum A029931.
A070939 gives length of binary expansion.
A101211 lists run-lengths in binary expansion, row-lengths A069010.
A372471 lists the binary indices of each prime.
Cf. A000043, A003714, A005940, A059305, A061712, A066195, A071814, A211997, A372429, A372517, A372686.

Table[DigitCount[Prime[n],2,1]-DigitCount[Prime[n],2,0],{n,100}]
DigitCount[#,2,1]-DigitCount[#,2,0]&/@Prime[Range[100]] (* Harvey P. Dale, May 09 2025 *)

a(n) = A000120(A000040(n)) - A080791(A000040(n)).
a(n) = A014499(n) - A035103(n).
a(n) = A145037(A000040(n))

A116361 Smallest k such that n XOR n2^k = n(2^k + 1).

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 4, 2, 4, 3, 4, 1, 1, 1, 2, 1, 1, 4, 5, 2, 2, 4, 5, 3, 5, 4, 5, 1, 1, 1, 2, 1, 1, 2, 6, 1, 1, 1, 6, 4, 4, 5, 6, 2, 2, 2, 2, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 4, 2, 5, 6, 7, 1, 1, 1, 7, 1, 1, 6, 7, 4, 5, 4, 7, 5, 5, 6, 7, 2, 2, 2, 2, 2, 7, 2, 7, 4

Offset: 0

Reinhard Zumkeller, Feb 04 2006

a(A003714(n)) <= 1;
a(A048716(n)) <= 2;
a(A115845(n)) <= 3;
a(A115847(n)) <= 4;
a(A114086(n)) <= 5;
a(A116362(n)) = n and a(m) < n for m < A116362(n).

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

a[n_] := Module[{k}, For[k = 0, True, k++,
     If[BitXor[n, n*2^k] == n*(2^k+1), Return[k]]]];
Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Nov 19 2021 *)

a(n)=my(k);while(bitxor(n,n<Charles R Greathouse IV, Mar 07 2013

from itertools import count
def A116361(n): return next(k for k in count(0) if n^(m:=n<Chai Wah Wu, Jul 19 2024

Offset corrected by Charles R Greathouse IV, Mar 07 2013

A263132 Positive values of m such that binomial(4*m - 1, m) is odd.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 11, 12, 16, 22, 24, 32, 43, 44, 48, 64, 86, 88, 96, 128, 171, 172, 176, 192, 256, 342, 344, 352, 384, 512, 683, 684, 688, 704, 768, 1024, 1366, 1368, 1376, 1408, 1536, 2048, 2731, 2732, 2736, 2752, 2816, 3072, 4096, 5462, 5464, 5472, 5504

Offset: 1

Peter Bala, Oct 10 2015

This sequence, when viewed as a set, equals the set of numbers of the form 4^n * ceiling(2^k/3) for n >= 0, k >= 1, i.e., the product subset in Z of A000302 and A005578 regarded as sets. See the example below.
Equivalently, this sequence, when viewed as a set, equals the set of numbers of the form 2^n * (2^(2*k + 1) + 1)/3 for n,k >= 0, i.e., the product subset in Z of A000079 and A007583 regarded as sets. See the example below.
2*a(n) gives the values of m such that binomial(4*m - 2,m) is odd. 4*a(n) gives the values of m such that binomial(4*m - 3,m) is odd (other than m = 1) and also the values of m such that binomial(4*m - 4,m) is odd.

			1) Notice how this sequence can be read from Table 1 below by moving through the table in a sequence of 'knight moves' (1 down and 2 to the left) starting from the first row. For example, starting at 11 on the top row we move in a series of knights moves 11 -> 12 -> 16, then return to the top row at 22 and move 22 -> 24 -> 32, return to the top row at 43 and move 43 -> 44 -> 48 -> 64, then return to top row at 86 and so on.
........................................................
.   Table 1: 4^n * ceiling(2^k/3) for n >= 0, k >= 1   .
........................................................
n\k|   1    2    3    4     5     6    7    8     9
---+----------------------------------------------------
0  |   1    2    3    6    11    22   43   86   171 ...
1  |   4    8   12   24    44    88  172  ...
2  |  16   32   48   96   176    ...
3  |  64  128  192  ...
4  | 256  ...
...
2) Notice how this sequence can be read from Table 2 below in a sequence of 'knight moves' (2 down and 1 to the left) starting from the first two rows. For example, starting at 43 in the first row we jump 43 -> 44 -> 48 -> 64, then return to the second row at 86 and jump 86 -> 88 -> 96 -> 128, followed by 171 -> 172 -> 176 -> 192 -> 256, and so on.
....................................................
.   Table 2: 2^n * (2^(2*k + 1) + 1)/3, n,k >= 0   .
....................................................
n\k|   0    1     2     3      4      5
---+----------------------------------------------
0  |   1    3    11    43    171    683  ...
1  |   2    6    22    86    342   1366  ...
2  |   4   12    44   172    684   2732  ...
3  |   8   24    88   344   1368   5464  ...
4  |  16   48   176   688   2736  10928  ...
5  |  32   96   352  1376   5472  21856  ...
6  |  64  192   704  2752  10944  43712  ...
7  | 128  384  1408  5504  21888  87424  ...
8  | 256 ...

Cf. A000079, A000267, A000302, A005578, A007583, A048716, A384688.

Other odd binomials: A002450 (4*m+1,m), A020988 (4*m+2,m), A263133 (4*m+3,m), A080674 (4*m+4,m), A118113 (3*m-2,m), A003714 (3*m,m).

[n: n in [1..6000] | Binomial(4*n-1, n) mod 2 eq 1]; // Vincenzo Librandi, Oct 12 2015

for n from 1 to 5000 do if mod(binomial(4*n-1, n), 2) = 1 then print(n) end if end do;

Select[Range[6000],OddQ[Binomial[4#-1,#]]&] (* Harvey P. Dale, Dec 26 2015 *)

for(n=1, 1e4, if (binomial(4*n-1, n) % 2 == 1, print1(n", "))) \\ Altug Alkan, Oct 11 2015

a(n) = my(r,s=sqrtint(4*n-3,&r)); (1<Kevin Ryde, Jun 14 2025

Python

A263132_list = [m for m in range(1,10**6) if not ~(4*m-1) & m] # Chai Wah Wu, Feb 07 2016

Formula

a(n) = A263133(n) + 1.

m is a term if and only if m AND NOT (4*m-1) = 0 where AND and NOT are bitwise operators. - Chai Wah Wu, Feb 07 2016

a(n) = (2^A000267(n-1) + 2^A384688(n-1)) / 3. - Kevin Ryde, Jun 14 2025

Extensions

More terms from Vincenzo Librandi, Oct 12 2015

cp's OEIS Frontend

A257250 Numbers n for which A256999(n) = n; numbers that cannot be made any larger by rotating (by one or more steps) the non-msb bits of their binary representation (with A080541 or A080542).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

A269161 Formula for Wolfram's Rule 86 cellular automaton: a(n) = 4n XOR (2n OR n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A244161 Greedy Catalan Base (A014418) interpreted as base-4 numbers, then shown in decimal.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Scheme

Formula

A246200 Self-inverse permutation of natural numbers: a(n) = A057889(3*n) / 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Scheme

Formula

A328593 Numbers whose binary indices have no consecutive divisible parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A356771 a(n) is the sum of the Fibonacci numbers in common in the Zeckendorf and dual Zeckendorf representations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A372516 Number of ones minus number of zeros in the binary expansion of the n-th prime number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A116361 Smallest k such that n XOR n*2^k = n*(2^k + 1).

Views

Author

Keywords

A116361 Smallest k such that n XOR n2^k = n(2^k + 1).