cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A065290 A065288 conjugated with A059893, inverse of A065289.

Original entry on oeis.org

2, 4, 1, 8, 6, 10, 3, 16, 12, 18, 14, 20, 5, 22, 7, 32, 24, 34, 26, 36, 28, 38, 30, 40, 9, 42, 11, 44, 13, 46, 15, 64, 48, 66, 50, 68, 52, 70, 54, 72, 56, 74, 58, 76, 60, 78, 62, 80, 17, 82, 19, 84, 21, 86, 23, 88, 25, 90, 27, 92, 29, 94, 31, 128, 96, 130, 98, 132, 100, 134
Offset: 1

Views

Author

Antti Karttunen, Oct 28 2001

Keywords

Comments

This permutation of N induces also such permutation of Z, that p(i)-i >= 0 for all i.

Links

Crossrefs

The associated siteswap sequence is A065291.

Formula

a(n) = A059893(A065288(A059893(n)))

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.

Original entry on oeis.org

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

Views

Author

Marc LeBrun, Feb 06 2001

Keywords

Comments

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)

Examples

			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)

Links

Crossrefs

{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).

Programs

  • Haskell
    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
  • Maple
    # 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
  • Mathematica
    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 *)
  • PARI
    a(n) = my(b=binary(n)); fromdigits(concat(b[1], Vecrev(vector(#b-1, k, b[k+1]))), 2); \\ Michel Marcus, Sep 29 2021
  • Python
    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
  • R
    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
  • R
    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

Formula

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

A065287 Infinite binary tree inspired permutation of N: 1 -> 3, 11ab..yz -> 11ab..yz1, 10ab..y0 -> 10ab..y, 10ab..y1 -> 11ab..y0.

Original entry on oeis.org

3, 1, 7, 2, 6, 13, 15, 4, 12, 5, 14, 25, 27, 29, 31, 8, 24, 9, 26, 10, 28, 11, 30, 49, 51, 53, 55, 57, 59, 61, 63, 16, 48, 17, 50, 18, 52, 19, 54, 20, 56, 21, 58, 22, 60, 23, 62, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 32, 96, 33, 98
Offset: 1

Views

Author

Antti Karttunen, Oct 28 2001

Keywords

Comments

On the right side every node replaces its right child, on the left side the left children replace their parents and the right children are transferred to the same offset - 1 at the right side (becoming left children). See comment at A065263.

Links

Crossrefs

A057114, A065263, A065269, A065275, A065281. Inverse: A065288, conjugated with A059893: A065289 and the inverse of that: A065290.

Programs

  • Maple
    RightChildTransferred_1 := proc(n) local k; if(1 = n) then RETURN(3); fi; k := floor_log_2(n)-1; if(3 = floor(n/(2^k))) then RETURN((2*n)+1); fi; if(0 = (n mod 2)) then RETURN(n/2); fi; RETURN(n + (2^k) - 1); end;
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.