| Displaying 1-4 of 4 results found.
page
1
The siteswap sequence (the deltas p[i]-i, i in ]-inf,+inf[, folded from Z to N, mapping 0->1, 1->2, -1->3, 2->4, -2->5, etc.) for A065284.
+20
3
0, 2, 2, 4, 4, 4, 2, 8, 8, 8, 10, 8, 4, 8, 4, 16, 16, 16, 18, 16, 20, 16, 22, 16, 8, 16, 8, 16, 8, 16, 8, 32, 32, 32, 34, 32, 36, 32, 38, 32, 40, 32, 42, 32, 44, 32, 46, 32, 16, 32, 16, 32, 16, 32, 16, 32, 16, 32, 16, 32, 16, 32, 16, 64, 64, 64, 66, 64, 68, 64, 70, 64, 72, 64, 74
CROSSREFS
The bisection of even terms (the positive half of Z) is given by A062383 and the bisection of odd terms (the nonpositive half of Z) is given by A065286.
1, 3, 7, 5, 13, 2, 15, 9, 25, 11, 27, 4, 29, 6, 31, 17, 49, 19, 51, 21, 53, 23, 55, 8, 57, 10, 59, 12, 61, 14, 63, 33, 97, 35, 99, 37, 101, 39, 103, 41, 105, 43, 107, 45, 109, 47, 111, 16, 113, 18, 115, 20, 117, 22, 119, 24, 121, 26, 123, 28, 125, 30, 127, 65, 193, 67, 195
Reverse the order of all but the most significant bit in binary expansion of n: if n = 1ab..yz then a(n) = 1zy..ba.
+10
114
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
COMMENTS
A self-inverse permutation of the natural numbers.
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 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: 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 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)
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
EXAMPLE
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 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, ...
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:
MATHEMATICA
ro[n_]:=Module[{idn=IntegerDigits[n, 2]}, FromDigits[Join[{First[idn]}, Reverse[ Rest[idn]]], 2]]; Array[ro, 80] (* Harvey P. Dale, Oct 24 2012 *)
PROG
(PARI) { for (n=1, 1023, a=1; b=n; while (b>1, a=2*a + 2*frac(b/2); b=floor(b/2); ); write("b059893.txt", n, " ", a); ) } \\ Harry J. Smith, Jun 30 2009 (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 (Haskell)
a059893 = foldl (\v b -> v * 2 + b) 1 . init . a030308_row
(Scheme, with memoization-macro definec)
(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
(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
(Python)
def a(n): return int('1' + bin(n)[3:][::-1], 2)
Infinite binary tree inspired permutation of N: 1 -> 1, 11ab..yz -> 11ab..yz1, 10ab..y1 -> 10ab..y, 10ab..y0 -> 11ab..y0.
+10
6
1, 3, 7, 6, 2, 13, 15, 12, 4, 14, 5, 25, 27, 29, 31, 24, 8, 26, 9, 28, 10, 30, 11, 49, 51, 53, 55, 57, 59, 61, 63, 48, 16, 50, 17, 52, 18, 54, 19, 56, 20, 58, 21, 60, 22, 62, 23, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 96, 32, 98, 33
COMMENTS
On the right side every node replaces its right child, on the left side the right children replace their parents and the left children are transferred to the same offset at the right side (staying left children). See comment at A065263.
MAPLE
LeftChildTransferred := proc(n) local k; if(1 = n) then RETURN(1); fi; k := floor_log_2(n)-1; if(3 = floor(n/(2^k))) then RETURN((2*n)+1); fi; if(1 = (n mod 2)) then RETURN((n-1)/2); fi; RETURN(n + (2^k)); end;
Search completed in 0.009 seconds
| 