|
|
A006068
|
|
a(n) is Gray-coded into n.
(Formerly M2253)
|
|
153
|
|
|
0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 13, 8, 9, 11, 10, 31, 30, 28, 29, 24, 25, 27, 26, 16, 17, 19, 18, 23, 22, 20, 21, 63, 62, 60, 61, 56, 57, 59, 58, 48, 49, 51, 50, 55, 54, 52, 53, 32, 33, 35, 34, 39, 38, 36, 37, 47, 46, 44, 45, 40, 41, 43, 42, 127, 126, 124, 125, 120, 121
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Equivalently, if binary expansion of n has m bits (say), compute derivative of n (A038554), getting sequence n' of length m-1; sort on n'.
The sequence exhibits glide reflections that grow fractally. These show up well on the scatterplot, also audibly using the "listen" link. - Peter Munn, Aug 18 2019
|
|
REFERENCES
|
M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.
M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Eric Rowland and Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 22.
|
|
FORMULA
|
a(n) = 2*a(ceiling((n+1)/2)) + A010060(n-1). If 3*2^(k-1) < n <= 2^(k+1), a(n) = 2^(k+1) - 1 - a(n-2^k); if 2^(k+1) < n <= 3*2^k, a(n) = a(n-2^k) + 2^k. - Henry Bottomley, Jan 10 2001
a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ... XOR [n/2^m] where m = [log(n)/log(2)] (for n>0) and [x] is integer floor of x. - Paul D. Hanna, Jun 04 2002
a(n) = if n<2 then n else 2*m + (n mod 2 + m mod 2) mod 2, with m=a(floor(n/2)). - Reinhard Zumkeller, Aug 10 2010
a(n XOR m) = a(n) XOR a(m), where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Dec 14 2019
a(0) = 0. For all n >= 0 if a(n) is even a(2*n) = 2*a(n), a(2*n+1) = 2*a(n)+1, else a(2*n) = 2*a(n)+1, a(2*n+1) = 2*a(n). - Yosu Yurramendi, Oct 12 2021
|
|
EXAMPLE
|
The first few values of n' are -,-,1,0,10,11,01,00,100,101,111,110,010,011,001,000,... (for n=0..15) and to put these in lexicographic order we must take n in the order 0,1,3,2,7,6,4,5,15,14,12,13,8,9,11,10,...
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<2, n,
Bits[Xor](n, a(iquo(n, 2))))
end:
|
|
MATHEMATICA
|
Table[Fold[BitXor, n, Quotient[n, 2^Range[BitLength[n] - 1]]], {n, 0, 70}] (* Jan Mangaldan, Mar 20 2013 *)
|
|
PROG
|
(PARI) {a(n)=local(B=n); for(k=1, floor(log(n+1)/log(2)), B=bitxor(B, n\2^k)); B} /* Paul D. Hanna, Jan 18 2012 */
(PARI) /* the following routine needs only O(log_2(n)) operations */
a(n)= {
my( s=1, ns );
while ( 1,
ns = n >> s;
if ( 0==ns, break() );
n = bitxor(n, ns);
s <<= 1;
);
return ( n );
(Haskell)
a006068 n = foldl xor 0 $
map (div n) $ takeWhile (<= n) a000079_list :: Integer
(Python)
def a(n):
s=1
while True:
ns=n>>s
if ns==0: break
n=n^ns
s<<=1
return n
(R) nmax <- 63 # by choice
a <- vector()
for(n in 1:nmax){
ones <- which(as.integer(intToBits(n)) == 1)
nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
level <- 0; anbit <- nbit; anbit.s <- nbit
while(sum(anbit.s) > 0){
s <- 2^level; if(s > length(anbit.s)) break
anbit.s <- c(anbit[-(1:s)], rep(0, s))
anbit <- bitwXor(anbit, anbit.s)
level <- level + 1
}
a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
(a <- c(0, a))
|
|
CROSSREFS
|
A003987, A010060 are used to express relationship between terms of this sequence.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|