A065174 -id:A065174 - cp's OEIS frontend

A065176 Site swap sequence associated with the permutation A065174 of Z.

0, 2, 2, 4, 4, 2, 2, 8, 8, 2, 2, 4, 4, 2, 2, 16, 16, 2, 2, 4, 4, 2, 2, 8, 8, 2, 2, 4, 4, 2, 2, 32, 32, 2, 2, 4, 4, 2, 2, 8, 8, 2, 2, 4, 4, 2, 2, 16, 16, 2, 2, 4, 4, 2, 2, 8, 8, 2, 2, 4, 4, 2, 2, 64, 64, 2, 2, 4, 4, 2, 2, 8, 8, 2, 2, 4, 4, 2, 2, 16, 16, 2, 2, 4, 4, 2, 2, 8, 8, 2, 2, 4, 4, 2, 2, 32, 32, 2, 2

Offset: 1

Antti Karttunen, Oct 19 2001

Here the site swap pattern ...,2,16,2,4,2,8,2,4,2,0,2,4,2,8,2,4,2,16,2,... that spans over the Z (zero throw is at t=0) has been folded to N by picking values at t=0, t=1, t=-1, t=2, t=-2, etc. successively.

This pattern is shown in the figure 7 of Buhler and Graham paper and uses infinitely many balls, with each ball at step t thrown always to constant "height" 2^A001511[abs(t)] (no balls in hands at step t=0).

Georg Fischer, Table of n, a(n) for n = 1..16384
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, Vol. 101, No. 6 (1994), 507-519.

Bisection of this gives A171977 or 2*A006519 or 2^A001511.

Cf. A065174.

[seq(TZ2(abs(N2Z(n))), n=1..120)];  # using TZ2 from A065174
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);
# Alternative:
A065176 := n -> `if`(n = 1, 0, 2^padic:-ordp(n - 1 + irem(n-1, 2), 2)):
seq(A065176(n), n = 1..99);  # Peter Luschny, Nov 14 2021

a[n_] := 2^IntegerExponent[n - Mod[n, 2], 2]; a[1] = 0; Array[a, 100] (* Amiram Eldar, May 22 2025 *)

a(n) = if(n==1,0, 1<Kevin Ryde, Jul 09 2021

def A065176(n):
    s, h = 1, n // 2
    if 0 == h: return 0
    while 0 == h % 2:
        h //= 2
        s += s
    return s + s
print([A065176(n) for n in range(1, 100)])  # Peter Luschny, Nov 14 2021

G.f.: (1-x+x^2)/(1-x) + (1+x)*Sum(k>=1, 2^(k-1)*x^2^k/(1-x^2^k)). - Ralf Stephan, Apr 17 2003

a(n) = A171977(floor(n/2)) for n >= 2. - Georg Fischer, Nov 28 2022

A065175 Inverse permutation to A065174.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Oct 19 2001

nonn

Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers

[seq(Z2N(N2Z(n)-TZ2(abs(N2Z(n)))), n=1..120)];
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);

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

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

A065167 Table T(n,k) read by antidiagonals, where the k-th row gives the permutation t->t+k of Z, folded to N (k >= 0, n >= 1).

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 4, 1, 6, 6, 5, 6, 2, 8, 8, 6, 3, 8, 4, 10, 10, 7, 8, 1, 10, 6, 12, 12, 8, 5, 10, 2, 12, 8, 14, 14, 9, 10, 3, 12, 4, 14, 10, 16, 16, 10, 7, 12, 1, 14, 6, 16, 12, 18, 18, 11, 12, 5, 14, 2, 16, 8, 18, 14, 20, 20, 12, 9, 14, 3, 16, 4, 18, 10, 20, 16, 22, 22, 13, 14, 7, 16, 1

Offset: 0

Antti Karttunen, Oct 19 2001

Simple periodic site swap permutations of natural numbers.

Row n of the table (starting from n=0) gives a permutation of natural numbers corresponding to the simple, infinite, periodic site swap pattern ...nnnnn...

			Table begins:
1 2 3 4 5 6 7 ...
2 4 1 6 3 8 5 ...
4 6 2 8 1 10 3 ...
6 8 4 10 2 12 1 ...

Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Juggling Information Service, Site Swap FAQs

Successive rows and associated site swap sequences, starting from the zeroth row: (A000027, A000004), (A065164, A000012), (A065165, A007395), (A065166, A010701). Cf. also A065171, A065174, A065177. trinv given at A054425.

PerSS_table := (n) -> PerSS((((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1, (n-((trinv(n)*(trinv(n)-1))/2))); PerSS := (n,c) -> Z2N(N2Z(n)+c);
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);
[seq(PerSS_table(j),j=0..119)];

Let f: Z -> N be given by f(z) = 2z if z>0 else 2|z|+1, with inverse g(z) = z/2 if z even else (1-z)/2. Then the n-th term of the k-th row is f(g(n)+k).

A065171 Permutation of Z, folded to N, corresponding to the site swap pattern ...26120123456... which ascends infinitely after t=0.

Original entry on oeis.org

1, 4, 2, 8, 3, 12, 6, 16, 5, 20, 10, 24, 7, 28, 14, 32, 9, 36, 18, 40, 11, 44, 22, 48, 13, 52, 26, 56, 15, 60, 30, 64, 17, 68, 34, 72, 19, 76, 38, 80, 21, 84, 42, 88, 23, 92, 46, 96, 25, 100, 50, 104, 27, 108, 54, 112, 29, 116, 58, 120, 31, 124, 62, 128, 33, 132, 66, 136, 35

Offset: 1

Antti Karttunen, Oct 19 2001

This permutation consists of one fixed point (at 0, mapped here to 1) and an infinite number of infinite cycles.

			G.f. = x + 4*x^2 + 2*x^3 + 8*x^4 + 3*x^5 + 12*x^6 + 6*x^7 + 16*x^8 + ...

Colin Barker, Table of n, a(n) for n = 1..1000
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers
Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

Inverse permutation: A065172. A065173 gives the deltas p(t)-t, i.e., the associated site swap sequence. Cf. also A065167, A065174, A065260.

[seq(Z2N(InfRisingSS(N2Z(n))), n=1..120)]; InfRisingSS := z -> `if`((z < 0),`if`((0 = (z mod 2)),z/2,-z),2*z);
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);

Vec(x*(2*x^6+4*x^5+x^4+8*x^3+2*x^2+4*x+1)/((x-1)^2*(x+1)^2*(x^2+1)^2) + O(x^100)) \\ Colin Barker, Oct 29 2016

{a(n) = if( n%2, n\2+1, n*2)}; /* Michael Somos, Nov 06 2016 */

a(2*k+2) = 4*k+4, a(4*k+1) = 2*k+1, a(4*k+3) = 4*k+2. - Ralf Stephan, Jun 10 2005
G.f.: x*(2*x^6+4*x^5+x^4+8*x^3+2*x^2+4*x+1) / ((x-1)^2*(x+1)^2*(x^2+1)^2). - Colin Barker, Feb 18 2013
a(n) = 2*a(n-4)-a(n-8) for n>8. - Colin Barker, Oct 29 2016
a(n) = (11*n-1+(5*n+1)*(-1)^n+(n-3)*(1-(-1)^n)*(-1)^((2*n+3+(-1)^n)/4))/8. - Luce ETIENNE, Oct 20 2016

cp's OEIS Frontend

A065176 Site swap sequence associated with the permutation A065174 of Z.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A065175 Inverse permutation to A065174.

Views

Author

Keywords

Links

Programs

Maple

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

A065167 Table T(n,k) read by antidiagonals, where the k-th row gives the permutation t->t+k of Z, folded to N (k >= 0, n >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A065171 Permutation of Z, folded to N, corresponding to the site swap pattern ...26120123456... which ascends infinitely after t=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula