A343150 -id:A343150 - cp's OEIS frontend

A059893 Reverse the order of all but the most significant bit in binary expansion of n: if n = 1ab..yz then a(n) = 1zy..ba.

1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 15, 16, 24, 20, 28, 18, 26, 22, 30, 17, 25, 21, 29, 19, 27, 23, 31, 32, 48, 40, 56, 36, 52, 44, 60, 34, 50, 42, 58, 38, 54, 46, 62, 33, 49, 41, 57, 37, 53, 45, 61, 35, 51, 43, 59, 39, 55, 47, 63, 64, 96, 80, 112, 72, 104, 88, 120

Offset: 1

Marc LeBrun, Feb 06 2001

A self-inverse permutation of the natural numbers.
a(n)=n if and only if A081242(n) is a palindrome. - Clark Kimberling, Mar 12 2003
a(n) is the position in B of the reversal of the n-th term of B, where B is the left-to-right binary enumeration sequence (A081242 with the empty word attached as first term). - Clark Kimberling, Mar 12 2003
From Antti Karttunen, Oct 28 2001: (Start)
When certain Stern-Brocot tree-related permutations are conjugated with this permutation, they induce a permutation on Z (folded to N), which is an infinite siteswap permutation (see, e.g., figure 7 in the Buhler and Graham paper, which is permutation A065174). We get:
   A065260(n) = a(A057115(a(n))),
   A065266(n) = a(A065264(a(n))),
   A065272(n) = a(A065270(a(n))),
   A065278(n) = a(A065276(a(n))),
   A065284(n) = a(A065282(a(n))),
   A065290(n) = a(A065288(a(n))). (End)
Every nonnegative integer has a unique representation c(1) + c(2)*2 + c(3)*2^2 + c(4)*2^3 + ..., where every c(i) is 0 or 1. Taking tuples of coefficients in lexical order (i.e., 0, 1; 01,11; 001,011,101,111; ...) yields A059893. - Clark Kimberling, Mar 15 2015
From Ed Pegg Jr, Sep 09 2015: (Start)
The reduced rationals can be ordered either as the Calkin-Wilf tree A002487(n)/A002487(n+1) or the Stern-Brocot tree A007305(n+2)/A047679(n). The present sequence gives the order of matching rationals in the other sequence.
For reference, the Calkin-Wilf tree is 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5, ..., which is A002487(n)/A002487(n+1).
The Stern-Brocot tree is 1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, 5/4, 7/5, 8/5, 7/4, 7/3, 8/3, 7/2, ..., which is A007305(n+2)/A047679(n).
There is a great little OEIS-is-useful story here. I had code for the position of fractions in the Calkin-Wilf tree. The best I had for positions of fractions in the Stern-Brocot tree was the paper "Locating terms in the Stern-Brocot tree" by Bruce Bates, Martin Bunder, Keith Tognetti. The method was opaque to me, so I used my Calkin-Wilf code on the Stern-Brocot fractions, and got A059893. And thus the problem was solved. (End)

			a(11) = a(1011) = 1110 = 14.
With empty word e prefixed, A081242 becomes (e,1,2,11,21,12,22,111,211,121,221,112,...); (reversal of term #9) = (term #12); i.e., a(9)=12 and a(12)=9. - _Clark Kimberling_, Mar 12 2003
From _Philippe Deléham_, Jun 02 2015: (Start)
This sequence regarded as a triangle with rows of lengths 1, 2, 4, 8, 16, ...:
   1;
   2,  3;
   4,  6,  5,  7;
   8, 12, 10, 14,  9,  13,  11,  15;
  16, 24, 20, 28, 18,  26,  22,  30,  17,  25,  21,  29,  19,  27,  23,  31;
  32, 48, 40, 56, 36,  52,  44, ...
Row sums = A010036. (End)

Alois P. Heinz, Table of n, a(n) for n = 1..8191 (first 1023 terms from T. D. Noe)
Bruce Bates, Martin Bunder, and Keith Tognetti, Locating terms in the Stern-Brocot tree, European Journal of Combinatorics 31.3 (2010): 1020-1033.
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507-519.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, 2020-2021.
Wikipedia, Calkin-Wilf Tree.
Wikipedia, Stern-Brocot tree.
Index entries for sequences related to Stern's sequences
Index entries for sequences that are permutations of the natural numbers

{A000027, A054429, A059893, A059894} form a 4-group.
The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.
Cf. A000079, A000523, A007931, A030308.
In other bases: A351702 (balanced ternary), A343150 (Zeckendorf), A343152 (lazy Fibonacci).

a059893 = foldl (\v b -> v * 2 + b) 1 . init . a030308_row
-- Reinhard Zumkeller, May 01 2013
(Scheme, with memoization-macro definec)
(definec (A059893 n) (if (<= n 1) n (let* ((k (- (A000523 n) 1)) (r (A059893 (- n (A000079 k))))) (if (= 2 (floor->exact (/ n (A000079 k)))) (* 2 r) (+ 1 r)))))
;; Antti Karttunen, May 16 2015

# Implements Bottomley's formula
A059893 := proc(n) option remember; local k; if(1 = n) then RETURN(1); fi; k := floor_log_2(n)-1; if(2 = floor(n/(2^k))) then RETURN(2*A059893(n-(2^k))); else RETURN(1+A059893(n-(2^k))); fi; end;
floor_log_2 := proc(n) local nn,i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;
# second Maple program:
a:= proc(n) local i, m, r; m, r:= n, 0;
      for i from 0 while m>1 do r:= 2*r +irem(m,2,'m') od;
      r +2^i
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 28 2015

A059893 = Reap[ For[n=1, n <= 100, n++, a=1; b=n; While[b > 1, a = 2*a + 2*FractionalPart[b/2]; b=Floor[b/2]]; Sow[a]]][[2, 1]] (* Jean-François Alcover, Jul 16 2012, after Harry J. Smith *)
ro[n_]:=Module[{idn=IntegerDigits[n,2]},FromDigits[Join[{First[idn]}, Reverse[ Rest[idn]]],2]]; Array[ro,80] (* Harvey P. Dale, Oct 24 2012 *)

a(n) = my(b=binary(n)); fromdigits(concat(b[1], Vecrev(vector(#b-1, k, b[k+1]))), 2); \\ Michel Marcus, Sep 29 2021

def a(n): return int('1' + bin(n)[3:][::-1], 2)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Mar 21 2017

maxrow <- 6 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)) {
  a[2^(m+1)+    k] <- 2*a[2^m+k]
  a[2^(m+1)+2^m+k] <- 2*a[2^m+k] + 1
}
a
# Yosu Yurramendi, Mar 20 2017

maxblock <- 7 # by choice
a <- 1
for(n in 2:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  anbit <- nbit
  anbit[1:(length(anbit) - 1)] <- anbit[rev(1:(length(anbit)-1))]
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
# Yosu Yurramendi, Apr 25 2021

a(n) = A030109(n) + A053644(n). If 2*2^k <= n < 3*2^k then a(n) = 2*a(n-2^k); if 3*2^k <= n < 4*2^k then a(n) = 1 + a(n-2^k) starting with a(1)=1. - Henry Bottomley, Sep 13 2001

A345201 Bit-reverse the odd part of the Zeckendorf representation of n: a(n) = A022290(A057889(A003714(n))).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19, 18, 17, 20, 21, 22, 23, 24, 30, 26, 27, 31, 29, 25, 28, 32, 33, 34, 35, 36, 37, 48, 39, 43, 49, 42, 40, 44, 50, 53, 47, 38, 41, 45, 51, 52, 46, 54, 55, 56, 57, 58, 77, 60, 69, 78, 63, 64, 70, 79, 85

Offset: 0

Rémy Sigrist, Jun 10 2021

This sequence is a self-inverse permutation of the nonnegative integers.

This sequence is similar to A343150 and to A344682.

Rémy Sigrist, Table of n, a(n) for n = 0..10946
Rémy Sigrist, PARI program for A345201
Rémy Sigrist, Alternate PARI program for A345201
Index entries for sequences that are permutations of the natural numbers

Cf. A000045, A003714, A022290, A057889, A343150, A344682.

PARI
```
See Links section.
```

a(n) < A000045(k) for any n < A000045(k).

A343152 Reverse the order of all but the most significant bits in the maximal Fibonacci expansion of n.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 11, 10, 9, 12, 16, 14, 19, 13, 18, 17, 15, 20, 21, 29, 27, 24, 32, 26, 23, 31, 22, 30, 28, 25, 33, 42, 37, 50, 35, 48, 45, 40, 53, 34, 47, 44, 39, 52, 43, 38, 51, 36, 49, 46, 41, 54, 55, 76, 71, 63, 84, 69, 61, 82, 58, 79, 74, 66, 87

Offset: 1

J. Parker Shectman, Apr 07 2021

A self-inverse permutation of the natural numbers.
Analogous to A059893 with binary expansion replaced by maximal Fibonacci expansion.
Analogous to A343150 with minimal Fibonacci expansion replaced by maximal Fibonacci expansion.
For n=1, the expansion equals 1. For n>=2, the expansion equals A104326(n-1) with a 1 appended. The 1 corresponds to a digit (always equal to 1) for F(1)=1, in addition to the digit for F(2)=1. (This expansion is NOT a representation, see reference in link, pp. 106 and 137.)
Write the sequence as a (right-justified) "tetrangle" or "irregular triangle" tableau with F(t) (Fibonacci number) entries on each row, for t=1,2,3,.... Then, columns of the tableau equal rows of the array A083047 (see reference in link, p. 131):
                               1
                               2
                           3,  4
                       6,  5,  7
               8, 11, 10,  9, 12
  16, 14, 19, 13, 18, 17, 15, 20
  ...

			For an example of calculation by reversing Fibonacci binary digits, see reference in link, p. 144:
On the basis (1,1,2,3,5,8) n=13 is written as 110101, Reversing all but the most AND least significant digits gives 101011, which evaluates to 16, so a(13)=16.
On the basis (1,1,2,3,5,8) n=14 is written as 101101, Reversing all but the most AND least significant digits gives 101101, which evaluates to 14, so a(14)=14.

Cf. A059893, A083047, A104326, A247647, A343150.

(*Produce indices of maximal Fibonacci expansion (recursively)*)
MaxFibInd[n_] := Module[{t = Floor[Log[GoldenRatio, Sqrt[5]*n + 1]] - 1}, Piecewise[{{{1}, n == 1}, {Append[MaxFibInd[n - Fibonacci[t]], t], n > 1}},]];
(*Define a(n)*)
a[n_] := Module[{MFI = MaxFibInd[n]}, Apply[Plus, Fibonacci[Last[MFI] - MFI + 1]]];
(*Generate DATA*)
Array[a, 67]

A344682 a(0) = 0, and for any n > 0, a(n) = A022290(A059893(A003754(n+1))).

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 6, 7, 10, 9, 8, 11, 15, 13, 18, 12, 17, 16, 14, 19, 20, 28, 26, 23, 31, 25, 22, 30, 21, 29, 27, 24, 32, 41, 36, 49, 34, 47, 44, 39, 52, 33, 46, 43, 38, 51, 42, 37, 50, 35, 48, 45, 40, 53, 54, 75, 70, 62, 83, 68, 60, 81, 57, 78, 73, 65, 86, 67

Offset: 0

Rémy Sigrist, Jun 08 2021

This sequence is a self-inverse permutation of the nonnegative integers.

The construction of this sequence is similar to that of A343150; we start with a representation of a number n as a sum of distinct positive Fibonacci numbers, through some binary encoding, and we reverse some of the bits in a bijective way to obtain a(n).

Rémy Sigrist, Table of n, a(n) for n = 0..10944
Rémy Sigrist, PARI program for A344682
Index entries for sequences that are permutations of the natural numbers

Cf. A003754, A059893, A022290, A343150.

# after renaming a(n) to A059893(n) in A059893...
A344682 := proc(n)
    if n = 0 then
        0;
    else
        A022290(A059893(A003754(n+1))) ;
    end if;
end proc:
seq(A344682(n),n=0..70) ; # R. J. Mathar, Jul 29 2021

PARI
```
See Links section.
```

A349238 Reverse the digits in the Zeckendorf representation of n (A189920).

Original entry on oeis.org

0, 1, 1, 1, 4, 1, 6, 4, 1, 9, 6, 4, 12, 1, 14, 9, 6, 19, 4, 17, 12, 1, 22, 14, 9, 30, 6, 27, 19, 4, 25, 17, 12, 33, 1, 35, 22, 14, 48, 9, 43, 30, 6, 40, 27, 19, 53, 4, 38, 25, 17, 51, 12, 46, 33, 1, 56, 35, 22, 77, 14, 69, 48, 9, 64, 43, 30, 85, 6, 61, 40, 27

Offset: 0

Kevin Ryde, Nov 11 2021

Fixed points a(n) = n are the Zeckendorf palindromes n = A094202.
Apart from a(0)=0, all terms end with a 1 digit so are "odd" A003622.
a(n) = 1 iff n is a Fibonacci number >= 1 (A000045) since they are Zeckendorf 100..00 which reverses to 00..001.
A given k first occurs as a(n) = k at its reversal n = a(k), and thereafter at this n with any number of least significant 0's appended.
The equivalent reversal in binary is A030101 so that a conversion to Fibbinary (A003714) and back gives a(n) = A022290(A030101(A003714(n))).
A reverse and reverse again loses any least significant 0 digits as in A348853 so that a(a(n)) = A348853(n).

			n    = 1445 = Zeckendorf 101000101001000
a(n) =  313 = Zeckendorf 000100101000101 reversal

Kevin Ryde, Table of n, a(n) for n = 0..10000
Kevin Ryde, PARI/GP Code.

Cf. A189920 (Zeckendorf digits), A094202 (fixed points), A003622 (range), A348853 (delete trailing 0's).
Cf. A003714 (Fibbinary), A022290 (its inverse).
Cf. A343150 (reverse below MSB).
Other base reversals: A030101 (binary), A004086 (decimal).

PARI
```
\\ See links.
```

def NumToFib(n): # n > 0
    f0, f1, k = 1, 1, 0
    while f0 <= n:
        f0, f1, k = f0+f1, f0, k+1
    s = ""
    while k > 0:
        f0, f1, k = f1, f0-f1, k-1
        if f0 <= n:
            s, n = s+"1", n-f0
        else:
            s = s+"0"
    return s
def RevFibToNum(s):
    f0, f1 = 1, 1
    n, k = 0, 0
    while k < len(s):
        if s[k] == "1":
            n = n+f0
        f0, f1, k = f0+f1, f0, k+1
    return n
n, a = 0, 0
print(a, end = ", ")
while n < 71:
    n += 1
    print(RevFibToNum(NumToFib(n)), end = ", ") # A.H.M. Smeets, Nov 14 2021

There is a linear representation of rank 6 for this sequence. - Jeffrey Shallit, May 13 2023

A351702 In the balanced ternary representation of n, reverse the order of digits other than the most significant.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 11, 6, 9, 12, 7, 10, 13, 14, 23, 32, 17, 26, 35, 20, 29, 38, 15, 24, 33, 18, 27, 36, 21, 30, 39, 16, 25, 34, 19, 28, 37, 22, 31, 40, 41, 68, 95, 50, 77, 104, 59, 86, 113, 44, 71, 98, 53, 80, 107, 62, 89, 116, 47, 74, 101, 56, 83, 110, 65, 92

Offset: 0

Kevin Ryde, Feb 19 2022

Self-inverse permutation with swaps confined to terms of a given digit length (A134021) so within blocks n = (3^k+1)/2 .. (3^(k+1)-1)/2.
Can extend to negative n by a(-n) = -a(n).
A072998 is balanced ternary coded in decimal digits so that reversal except first digit of A072998(n) is at A072998(a(n)).  Similarly its ternary equivalent A157671, and also A132141 ternary starting with 1.
These sequences all have a fixed initial digit followed by all ternary strings which is the reversed part.  A007932 is such strings as decimal digits 1,2,3 but it omits the empty string so the whole reversal of A007932(n) is at A007932(a(n+1)-1).
Fixed points a(n) = n are where n in balanced ternary is a palindrome apart from its initial 1.  These are the full balanced ternary palindromes with their least significant 1 removed, so all n = (A134027(m)-1)/3 for m>=2.

			n    = 224 = balanced ternary 1,  0, -1, 1,  0, -1
                      reverse     ^^^^^^^^^^^^^^^^
a(n) = 168 = balanced ternary 1, -1,  0, 1, -1,  0

Cf. A059095 (balanced ternary), A134028 (full reverse), A134027 (palindromes).
Cf. A072998, A157671, A132141, A007932.
In other bases: A059893 (binary), A343150 (Zeckendorf), A343152 (lazy Fibonacci).

a(n) = if(n==0,0, my(k=if(n,logint(n<<1,3)), s=(3^k+1)>>1); s + fromdigits(Vec(Vecrev(digits(n-s,3)),k),3));

A356331 Bit-reverse the odd part of the negaFibonacci representation of n: a(n) = A356327(A057889(A215024(n))).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 17, 10, 11, 12, 13, 14, 15, 19, 9, 18, 16, 20, 21, 51, 44, 24, 38, 26, 32, 28, 45, 46, 31, 27, 33, 34, 35, 36, 48, 25, 39, 40, 49, 53, 43, 23, 29, 30, 47, 37, 41, 50, 22, 52, 42, 54, 55, 140, 133, 58, 106, 115, 79, 62, 113, 127, 99

Offset: 0

Rémy Sigrist, Aug 04 2022

This sequence is a self-inverse permutation of the nonnegative integers similar to A343150, A344682, A345201 and A356332.

			The first terms, alongside the corresponding negaFibonacci representations, are:
  n   a(n)  nega(n)  nega(a(n))
  --  ----  -------  ----------
   0     0        0           0
   1     1        1           1
   2     2      100         100
   3     3      101         101
   4     4    10010       10010
   5     5    10000       10000
   6     6    10001       10001
   7     7    10100       10100
   8     8    10101       10101
   9    17  1001010     1010010
  10    10  1001000     1001000
  11    11  1001001     1001001
  12    12  1000010     1000010
  13    13  1000000     1000000
  14    14  1000001     1000001
  15    15  1000100     1000100
  16    19  1000101     1010001
  17     9  1010010     1001010
  18    18  1010000     1010000
  19    16  1010001     1000101
  20    20  1010100     1010100
  21    21  1010101     1010101

Rémy Sigrist, Table of n, a(n) for n = 0..6765
Rémy Sigrist, PARI program
Index entries for sequences related to Zeckendorf expansion of n
Index entries for sequences that are permutations of the natural numbers

Cf. A000045, A057889, A215025, A343150, A344682, A345201, A356327, A356332.

PARI
```
See Links section.
```

a(a(n)) = n.

a(n) <= A000045(2*k) iff n <= A000045(2*k).

A356332 Bit-reverse the odd part of the negaFibonacci representation of -n (and negate): a(n) = -A356327(A057889(A215025(n))).

Original entry on oeis.org

0, 1, 2, 3, 4, 10, 6, 7, 8, 9, 5, 11, 12, 31, 27, 23, 16, 17, 28, 19, 20, 21, 22, 15, 24, 30, 26, 14, 18, 29, 25, 13, 32, 33, 86, 82, 65, 71, 38, 78, 61, 57, 42, 51, 44, 45, 72, 83, 74, 62, 50, 43, 75, 53, 54, 55, 56, 41, 58, 77, 70, 40, 49, 63, 64, 36, 79, 85

Offset: 0

Rémy Sigrist, Aug 04 2022

This sequence is a self-inverse permutation of the nonnegative integers similar to A343150, A344682, A345201 and A356331.

			The first terms, alongside the corresponding negaFibonacci representations, are:
  n   a(n)  nega(-n)  nega(-a(n))
  --  ----  --------  -----------
   0     0         0            0
   1     1        10           10
   2     2      1001         1001
   3     3      1000         1000
   4     4      1010         1010
   5    10    100101       101001
   6     6    100100       100100
   7     7    100001       100001
   8     8    100000       100000
   9     9    100010       100010
  10     5    101001       100101
  11    11    101000       101000
  12    12    101010       101010
  13    31  10010101     10101001

Rémy Sigrist, Table of n, a(n) for n = 0..10945
Rémy Sigrist, PARI program
Index entries for sequences related to Zeckendorf expansion of n
Index entries for sequences that are permutations of the natural numbers

Cf. A000045, A057889, A215025, A343150, A344682, A345201, A356327, A356331.

PARI
```
See Links section.
```

a(a(n)) = n.

a(n) < A000045(2*k+1) iff n < A000045(2*k+1).

cp's OEIS Frontend

A059893 Reverse the order of all but the most significant bit in binary expansion of n: if n = 1ab..yz then a(n) = 1zy..ba.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

R

R

Formula

A345201 Bit-reverse the odd part of the Zeckendorf representation of n: a(n) = A022290(A057889(A003714(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A343152 Reverse the order of all but the most significant bits in the maximal Fibonacci expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A344682 a(0) = 0, and for any n > 0, a(n) = A022290(A059893(A003754(n+1))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

A349238 Reverse the digits in the Zeckendorf representation of n (A189920).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A351702 In the balanced ternary representation of n, reverse the order of digits other than the most significant.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A356331 Bit-reverse the odd part of the negaFibonacci representation of n: a(n) = A356327(A057889(A215024(n))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI