A261283 -id:A261283 - cp's OEIS frontend

A253317 Indices in A261283 where records occur.

0, 1, 2, 3, 8, 9, 10, 11, 128, 129, 130, 131, 136, 137, 138, 139, 32768, 32769, 32770, 32771, 32776, 32777, 32778, 32779, 32896, 32897, 32898, 32899, 32904, 32905, 32906, 32907, 2147483648, 2147483649, 2147483650, 2147483651, 2147483656, 2147483657

Offset: 1

Philippe Beaudoin, Dec 30 2014

From Gus Wiseman, Dec 29 2023: (Start)
These are numbers whose binary indices are all powers of 2, where a binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. For example, the terms together with their binary expansions and binary indices begin:
       0 ~ {}
       1 ~ {1}
      10 ~ {2}
      11 ~ {1,2}
    1000 ~ {4}
    1001 ~ {1,4}
    1010 ~ {2,4}
    1011 ~ {1,2,4}
10000000 ~ {8}
10000001 ~ {1,8}
10000010 ~ {2,8}
10000011 ~ {1,2,8}
10001000 ~ {4,8}
10001001 ~ {1,4,8}
10001010 ~ {2,4,8}
10001011 ~ {1,2,4,8}
For powers of 3 we have A368531.
(End)

Michael De Vlieger, Table of n, a(n) for n = 1..4096
Lorenzo Sauras-Altuzarra, Some arithmetical problems that are obtained by analyzing proofs and infinite graphs, arXiv:2002.03075 [math.NT], 2020.

Cf. A053644 (most significant bit).
A048793 lists binary indices, length A000120, sum A029931.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A058891, A062050, A072639, A326031, A326675, A326702, A367771, A367912, A368183, A368109, A368531.

a := proc(n) local k, A:
A := [seq(0,i=1..n)]: A[1]:=0:
for k from 1 to n-1 do
   A[k+1] := A[k-2^ilog2(k)+1]+2^(2^ilog2(k)-1): od:
return A[n]: end proc: # Lorenzo Sauras Altuzarra, Dec 18 2019
# second Maple program:
a:= n-> (l-> add(l[i+1]*2^(2^i-1), i=0..nops(l)-1))(Bits[Split](n-1)):
seq(a(n), n=1..38);  # Alois P. Heinz, Dec 13 2023

Nest[Append[#1, #1[[-#2]] + 2^(#2 - 1)] & @@ {#, 2^(IntegerLength[Length[#], 2] - 1)} &, {0, 1}, 36] (* Michael De Vlieger, May 08 2020 *)

a(n)={if(n<=1, 0, my(t=1<Andrew Howroyd, Dec 20 2019

a(1) = 0 and a(n) = a(n-A053644(n-1)) + 2^(A053644(n-1)-1). - Lorenzo Sauras Altuzarra, Dec 18 2019
a(n) = A358126(n-1) / 2. - Tilman Piesk, Dec 18 2022
a(2^n+1) = 2^(2^n-1) = A058891(n+1). - Gus Wiseman, Dec 29 2023
a(2^n) = A072639(n). - Gus Wiseman, Dec 29 2023
G.f.: 1/(1-x) * Sum_{k>=0} (2^(-1+2^k))*x^2^k/(1+x^2^k). - John Tyler Rascoe, May 22 2024

Corrected reference in name from A253315 to A261283. - Tilman Piesk, Dec 18 2022

A341273 If A261283(n) = 0, then a(n) = n, otherwise a(n) is obtained by flipping the A261283(n)-th rightmost bit in the binary expansion of n.

Original entry on oeis.org

0, 0, 0, 7, 0, 7, 7, 7, 0, 25, 42, 75, 76, 45, 30, 7, 0, 25, 82, 51, 52, 85, 30, 7, 25, 25, 30, 25, 30, 25, 30, 30, 0, 97, 42, 51, 52, 45, 102, 7, 42, 45, 42, 42, 45, 45, 42, 45, 52, 51, 51, 51, 52, 52, 52, 51, 120, 25, 42, 51, 52, 45, 30, 127, 0, 97, 82, 75

Offset: 0

Rémy Sigrist, Feb 08 2021

All terms belong to A075926.

			For n = 7:
- A261283(7) = 0,
- so a(7) = 7.
For n = 43:
- A261283(43) = 1,
- so a(43) is obtained by flipping the rightmost binary digit in 43,
- a(43) = 42.

Rémy Sigrist, Table of n, a(n) for n = 0..32768

Cf. A075926, A261283.

a(n) = { my (m=n, x=0); while (m, my (v=valuation(m, 2)); x=bitxor(x, v+1); m-=2^v); if (x, bitxor(n, 2^(x-1)), n) }

A261283(a(n)) = 0.
a(a(n)) = a(n).
a(n) = n iff n belongs to A075926.
a(2^k) = 0 for any k >= 0.

A327041 a(n) is the number whose binary indices are the union of the set-system with BII-number n.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Aug 19 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. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

			22 is the BII-number of {{2},{1,2},{1,3}}, and 7 has binary indices {1,2,3}, so a(22) = 7.

Tilman Piesk, Illustration of the first 128 terms

Indices of records are A253317.

Cf. A000120, A001511, A029931, A035327, A048793, A070939, A072639, A326031, A326702, A326947, A261283 (XOR equivalent).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[Total[2^Union@@bpe/@bpe[n]]/2,{n,0,100}]

A253315 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n.

Original entry on oeis.org

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

Offset: 0

Philippe Beaudoin, Dec 30 2014

The least significant bit is numbered 0.
For any x < 2^m, for any y < m, there exist x' < 2^m s.t. x' differs from x by a single bit and a(x') = y.
Because of the above property, sequence a is a solution to the "coins on a chessboard" problem which states: given an 8x8 chessboard filled with coins randomly flipped "head" or "tail" and a cell number (from 0 to 63) find a way to communicate the cell number by flipping a single coin.
See A261283(n) = a(2n) for the version where the terms are not duplicated, which is equivalent to number the bits starting with 1 for the LSB. - M. F. Hasler, Aug 14 2015

			a(12) = a(0b1100) = XOR(2, 3) = XOR(0b10, 0b11) = 1, where the prefix "0b" means that the number is written in binary.

Philippe Beaudoin, Table of n, a(n) for n = 0..4095
Oliver Nash, Yet another prisoner puzzle, coins on a chessboard problem.

import Data.Bits (xor)
a253315 :: Integer -> Integer
a253315 = f 0 0 where
   f _ y 0 = y
   f z y x = f (z + 1) (y `xor` b * z) x' where (x', b) = divMod x 2
-- Reinhard Zumkeller, Jan 18 2015

# requires Maple 12 or later
b:= proc(n) local t, L,i;
  L:= convert(n,base,2);
  t:= 0;
  for i from 1 to nops(L) do if L[i]=1 then
    t:= Bits:-Xor(t,i-1)
  fi od;
  t;
end proc:
seq(b(n),n=0..100); # Robert Israel, Dec 30 2014

a[n_] := BitXor @@ Flatten[Position[IntegerDigits[n, 2] // Reverse, 1] - 1]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 07 2015 *)

A253315(n, b=bittest(n, 1))={for(i=2, #binary(n), bittest(n, i)&&b=bitxor(b, i)); b} \\ M. F. Hasler, Aug 14 2015

def a(n):
    r = 0
    b = 0
    while n > 0:
        if (n & 1):
            r = r ^ b
        b = b + 1
        n = n >> 1
    return r
print([a(n) for n in range(20)])

a(n) = f(0,0,n) where f(z,y,x) = if x = 0 then y else f (z+1) (y XOR (z * (x mod 2))) floor(x/2). - Reinhard Zumkeller, Jan 18 2015

A355340 a(0) = 0; for n >= 1, a(n) = a(n-1) XOR A001511(n), where XOR denotes bitwise exclusive-or (A003987) and A001511 is the binary ruler function.

Original entry on oeis.org

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

Offset: 0

Peter Munn, Jun 29 2022

Related to the Thue-Morse sequence, A010060, which gives the rightmost binary bit of each term. The next bit is given by the closely related A269723.
If we replace A001511(n) in the definition by A006519(n) = 2^(A001511(n)-1) we get Gray code (A003188).
Interesting symmetries of the sequence seem more apparent with the terms aligned in suitable periods, such as the arrangement in the example section.

			Initial terms arranged in periods of 16, with deliberate periodic spacing:
  0,1,3,2,  1,0,2,3,     7,6,4,5,  6,7,5,4,
  1,0,2,3,  0,1,3,2,     6,7,5,4,  7,6,4,5,
  3,2,0,1,  2,3,1,0,     4,5,7,6,  5,4,6,7,
  2,3,1,0,  3,2,0,1,     5,4,6,7,  4,5,7,6,
.
  1,0,2,3,  0,1,3,2,     6,7,5,4,  7,6,4,5,
  0,1,3,2,  1,0,2,3,     7,6,4,5,  6,7,5,4,
  2,3,1,0,  3,2,0,1,     5,4,6,7,  4,5,7,6,
  3,2,0,1,  2,3,1,0,     4,5,7,6,  5,4,6,7,
...
Note that when the arrangement is partitioned regularly into 2 X 2, 4 X 4 or 8 X 8 squares, the terms on any diagonal of a square share the same value. Note also the symmetry of the terms on the squares' circumferences.

Paolo Xausa, Table of n, a(n) for n = 0..16383
Rémy Sigrist, Colored representation of the first 2^15 terms as 128 rows of 256 terms (the color is function of a(x + 256*y), x = 0..255, y = 0..127)
Index entries for sequences related to binary expansion of n

Comparable sequences: A010060, A261283, A269723.
Cf. A001511, A003188, A003987, A006519.
Positions of: odd numbers: A000069, even numbers: A001969, previously unseen numbers: A253317 (apparently).

Block[{k = 0}, NestList[BitXor[#, IntegerExponent[k += 2, 2]] &, 0, 100]] (* Paolo Xausa, May 29 2024 *)

A010060(n) = a(n) mod 2.

A269723(n) = floor(a(n)/2) mod 2.

cp's OEIS Frontend

A253317 Indices in A261283 where records occur.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A341273 If A261283(n) = 0, then a(n) = n, otherwise a(n) is obtained by flipping the A261283(n)-th rightmost bit in the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A327041 a(n) is the number whose binary indices are the union of the set-system with BII-number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A253315 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A355340 a(0) = 0; for n >= 1, a(n) = a(n-1) XOR A001511(n), where XOR denotes bitwise exclusive-or (A003987) and A001511 is the binary ruler function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula