login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: gray code
Displaying 1-10 of 222 results found. page 1 2 3 4 5 6 7 8 9 10 ... 23
     Sort: relevance | references | number | modified | created      Format: long | short | data
A003188 Decimal equivalent of Gray code for n.
(Formerly M2250)
+40
215
0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24, 25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16, 48, 49, 51, 50, 54, 55, 53, 52, 60, 61, 63, 62, 58, 59, 57, 56, 40, 41, 43, 42, 46, 47, 45, 44, 36, 37, 39, 38, 34, 35, 33, 32, 96, 97, 99, 98, 102, 103, 101 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Inverse of sequence A006068 considered as a permutation of the nonnegative integers, i.e., A006068(A003188(n)) = n = A003188(A006068(n)). - Howard A. Landman, Sep 25 2001
Restricts to a permutation of each {2^(i - 1) .. 2^i - 1}. - Jason Kimberley, Apr 02 2012
a(n) mod 2 = floor(((n + 1) mod 4) / 2), see also A021913. - Reinhard Zumkeller, Apr 28 2012
Invented by Emile Baudot (1845-1903), originally called a "cyclic-permuted" code. Gray codes are named after Frank Gray, who patented their use for shaft encoders in 1953. [F. Gray, "Pulse Code Communication", U.S. Patent 2,632,058, March 17, 1953.] - Robert G. Wilson v, Jun 22 2014
For n >= 2, let G_n be the graph whose vertices are labeled as 0,1,...,2^n-1, and two vertices are adjacent if and only if their binary expansions differ in exactly one bit, then a(0),a(1),...,a(2^n-1),a(0) is a Hamilton cycle in G_n. - Jianing Song, Jun 01 2022
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
Indranil Ghosh, Table of n, a(n) for n = 0..32767 (first 1001 terms from N. J. A. Sloane)
M. W. Bunder, K. P. Tognetti, and G. E. Wheeler, On binary reflected Gray codes and functions, Discr. Math., 308 (2008), 1690-1700.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 39.
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
J. A. Oteo and J. Ros, A Fractal Set from the Binary Reflected Gray Code, J. Phys. A: Math Gen. 38 (2005) 8935-8949.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]
Pierluigi Vellucci and Alberto Maria Bersani, Ordering of nested square roots of 2 according to Gray code, arXiv:1604.00222 [math.NT], 2016.
FORMULA
a(n) = 2*a(floor(n/2)) + A021913(n - 1). - Henry Bottomley, Apr 05 2001
a(n) = n XOR floor(n/2), where XOR is the binary exclusive OR operator. - Paul D. Hanna, Jun 04 2002
G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*x^2^k/(1 + x^2^(k+1)). - Ralf Stephan, May 06 2003
a(0) = 0, a(2n) = 2a(n) + [n odd], a(2n + 1) = 2a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(0) = 0, a(n) = 2 a(floor(n/2)) + mod(floor((n + 1)/2), 2).
a(n) = Sum_{k=1..n} 2^A007814(k) * (-1)^((k/2^A007814(k) - 1)/2). - Ralf Stephan, Oct 29 2003
a(0) = 0, a(n + 1) = a(n) XOR 2^A007814(n) - Jaume Simon Gispert (jaume(AT)nuem.com), Sep 11 2004
Inverse of sequence A006068. - Philippe Deléham, Apr 29 2005
a(n) = a(n-1) XOR A006519(n). - Franklin T. Adams-Watters, Jul 18 2011
From Mikhail Kurkov, Sep 27 2023: (Start)
a(2^m + k) = a(2^m - k - 1) + 2^m for 0 <= k < 2^m, m >= 0.
a(n) = a(A053645(A054429(n))) + A053644(n) for n > 0.
a(n) = A063946(a(A053645(n)) + A053644(n)) for n > 0. (End)
EXAMPLE
For n = 13, the binary reflected Gray code representation of n is '1011' and 1011_2 = 11_10. So, a(13) = 11. - Indranil Ghosh, Jan 23 2017
MAPLE
with(combinat); graycode(6); # to produce first 64 terms
printf(cat(` %.6d`$64), op(map(convert, graycode(6), binary))); lprint(); # to produce binary strings
# alternative:
read("transforms"):
A003188 := proc(n)
XORnos(n, floor(n/2)) ;
end proc: # R. J. Mathar, Mar 09 2015
# another Maple program:
a:= n-> Bits[Xor](n, iquo(n, 2)):
seq(a(n), n=0..70); # Alois P. Heinz, Aug 16 2020
MATHEMATICA
f[n_] := BitXor[n, Floor[n/2]]; Array[f, 70, 0] (* Robert G. Wilson v, Jun 09 2010 *)
PROG
(PARI) a(n)=bitxor(n, n>>1);
(PARI) a(n)=sum(k=1, n, (-1)^((k/2^valuation(k, 2)-1)/2)*2^valuation(k, 2))
(C) int a(int n) { return n ^ (n>>1); }
(Magma) // A recursive algorithm
N := 10; s := [[]];
for n in [1..N] do
for j in [#s..1 by -1] do
Append(~s, Append(s[j], 1));
Append(~s[j], 0);
end for;
end for;
[SequenceToInteger(b, 2):b in s]; // Jason Kimberley, Apr 02 2012
(Magma) // A direct algorithm
I2B := func< i | [b eq 1: b in IntegerToSequence(i, 2)]>;
B2I := func< s | SequenceToInteger([b select 1 else 0:b in s], 2)>;
[B2I(Xor(I2B(i), I2B(i div 2)cat[false])):i in [1..127]]; //Jason Kimberley, Apr 02 2012
(Haskell)
import Data.Bits (xor, shiftR)
a003188 n = n `xor` (shiftR n 1) :: Integer
-- Reinhard Zumkeller, May 26 2013, Apr 28 2012
(Python)
def A003188(n):
return int(bin(n^(n/2))[2:], 2) # Indranil Ghosh, Jan 23 2017
(Python)
def A003188(n): return n^ n>>1 # Chai Wah Wu, Jun 29 2022
(R)
maxn <- 63 # by choice
a <- 1
for(n in 1:maxn){ a[2*n ] <- 2*a[n] + (n%%2 != 0)
a[2*n+1] <- 2*a[n] + (n%%2 == 0)}
(a <- c(0, a))
# Yosu Yurramendi, Apr 10 2020
(C#)
static uint a(this uint n) => (n >> 1) ^ n; // Frank Hollstein, Mar 12 2021
CROSSREFS
a(2*A003714(n)) = 3*A003714(n) for all n. - Antti Karttunen, Apr 26 1999
Cf. A014550 (in binary), A055975 (first differences), A048724 (even bisection), A065621 (odd bisection).
KEYWORD
nonn,nice,easy,look
AUTHOR
STATUS
approved
A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.
(Formerly M0110)
+40
212
0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 4, 5, 6, 5, 4, 5 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Starting with a(1) = 0 mirror all initial 2^k segments and increase by one.
a(n) gives the net rotation (measured in right angles) after taking n steps along a dragon curve. - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
This sequence generates A082410: (0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, ...) and A014577; identical to the latter except starting 1, 1, 0, ...; by writing a "1" if a(n+1) > a(n); if not, write "0". E.g., A014577(2) = 0, since a(3) < a(2), or 1 < 2. - Gary W. Adamson, Sep 20 2003
Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - Gary W. Adamson, Jul 23 2008
The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
Can be used as a binomial transform operator: Let a(n) = the n-th term in any S(n); then extract 2^k strings, adding the terms. This results in the binomial transform of S(n). Say S(n) = 1, 3, 5, ...; then we obtain the strings: (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), ...; = the binomial transform of (1, 3, 5, ...) = (1, 4, 12, 32, 80, ...). Example: the 8-bit string has a sum of 32 with a distribution of (1, 3, 3, 1) or one 1, three 3's, three 5's, and one 7; as expected. - Gary W. Adamson, Jun 21 2012
Considers all positive odd numbers as nodes of a graph. Two nodes are connected if and only if the sum of the two corresponding odd numbers is a power of 2. Then a(n) is the distance between 2n + 1 and 1. - Jianing Song, Apr 20 2019
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
J.-P. Allouche, G.-N. Han and J. Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Danielle Cox and K. McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149.  Reprinted with addendum in Donald E. Knuth, Selected Papers on Fun and Games, 2010, pages 571-614. Equation 3.2 g(n) = a(n-1).
P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
P. Flajolet and Lyle Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980), 142-158.
S. Kropf and S. Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
Sara Kropf and S. Wagner, On q-Quasiadditive and q-Quasimultiplicative Functions, arXiv preprint arXiv:1608.03700 [math.CO], 2016.
Helmut Prodinger and Friedrich J. Urbanek, Infinite 0-1-Sequences Without Long Adjacent Identical Blocks, Discrete Mathematics, volume 28, issue 3, 1979, pages 277-289.  Also first author's copy. Their "variation" v(k) at definition 3.4 is a(k).
Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.
FORMULA
a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller, Aug 14 2001
a(2n+1) = 2a(n) - a(2n) + 1, a(4n) = a(2n), a(4n+2) = 1 + a(2n+1).
a(j+1) = a(j) + (-1)^A014707(j). - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
G.f.: (1/(1-x)) * Sum_{k>=0} x^2^k/(1+x^2^(k+1)). - Ralf Stephan, May 02 2003
Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - Gary W. Adamson, Oct 19 2003
a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(n) = Sum_{k=1..n} (-1)^((k/2^A007814(k)-1)/2) = Sum_{k=1..n} (-1)^A025480(k-1). - Ralf Stephan, Oct 29 2003
a(n) = A069010(n) + A033264(n). - Ralf Stephan, Oct 29 2003
a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - Benoit Cloitre, Jan 20 2014
a(n) = A037834(n) + 1.
EXAMPLE
Considered as a triangle with 2^k terms per row, the first few rows are:
1
2, 1
2, 3, 2, 1
2, 3, 4, 3, 2, 3, 2, 1
...
The n-th row becomes right half of next row; left half is mirrored terms of n-th row increased by one. - Gary W. Adamson, Jun 20 2012
MAPLE
A005811 := proc(n)
local i, b, ans;
if n = 0 then
return 0 ;
end if;
ans := 1;
b := convert(n, base, 2);
for i from nops(b)-1 to 1 by -1 do
if b[ i+1 ]<>b[ i ] then
ans := ans+1
fi
od;
return ans ;
end proc:
seq(A005811(i), i=1..50) ;
# second Maple program:
a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(a(n), n=0..100); # Alois P. Heinz, Feb 01 2023
MATHEMATICA
Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
PROG
(PARI) a(n)=sum(k=1, n, (-1)^((k/2^valuation(k, 2)-1)/2))
(PARI) a(n)=if(n<1, 0, a(n\2)+(a(n\2)+n)%2) \\ Benoit Cloitre, Jan 20 2014
(PARI) a(n) = hammingweight(bitxor(n, n>>1)); \\ Gheorghe Coserea, Sep 03 2015
(Haskell)
import Data.List (group)
a005811 0 = 0
a005811 n = length $ group $ a030308_row n
a005811_list = 0 : f [1] where
f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
-- Reinhard Zumkeller, Feb 16 2013, Mar 07 2011
(Python)
def a(n): return bin(n^(n>>1))[2:].count("1") # Indranil Ghosh, Apr 29 2017
CROSSREFS
Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs).
Partial sums of A112347.
Cf. A003188.
KEYWORD
easy,nonn,core,nice,hear
AUTHOR
EXTENSIONS
Additional description from Wouter Meeussen
STATUS
approved
A006068 a(n) is Gray-coded into n.
(Formerly M2253)
+40
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'.
Inverse of sequence A003188 considered as a permutation of the nonnegative integers, i.e., a(A003188(n)) = n = A003188(a(n)). - Howard A. Landman, Sep 25 2001
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
Joerg Arndt, Matters Computational (The Fxtbook), section 1.16 Gray code, C code inverse_gray_code() with "version 3" giving the PARI code here.
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, Dec 08, 2020
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) XOR [a(n)/2] = n. - Paul D. Hanna, Jan 18 2012
A066194(n) = a(n-1) + 1, n>=1. - Philippe Deléham, Apr 29 2005
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
a(n) = a(A053645(A063946(n))) + A053644(n) for n > 0 with a(0) = 0. - Mikhail Kurkov, Sep 09 2023
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:
seq(a(n), n=0..100); # Alois P. Heinz, Apr 17 2018
MATHEMATICA
a[n_] := BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]; a[0]=0; Table[a[n], {n, 0, 69}] (* Jean-François Alcover, Jul 19 2012, after Paul D. Hanna *)
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 );
} /* Joerg Arndt, Jul 19 2012 */
(Haskell)
a006068 n = foldl xor 0 $
map (div n) $ takeWhile (<= n) a000079_list :: Integer
-- Reinhard Zumkeller, Apr 28 2012
(Python)
def a(n):
s=1
while True:
ns=n>>s
if ns==0: break
n=n^ns
s<<=1
return n
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 07 2017, after PARI code by Joerg Arndt
(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))
# Yosu Yurramendi, Oct 12 2021, after PARI code by Joerg Arndt
CROSSREFS
Cf. A054429, A180200. - Reinhard Zumkeller, Aug 15 2010
Cf. A000079, A055975 (first differences), A209281 (binary weight).
A003987, A010060 are used to express relationship between terms of this sequence.
KEYWORD
nonn,easy,nice,look,hear
AUTHOR
EXTENSIONS
More terms from Henry Bottomley, Jan 10 2001
STATUS
approved
A014550 Binary reflected Gray code. +40
31
0, 1, 11, 10, 110, 111, 101, 100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000, 11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100, 10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000, 110000, 110001, 110011, 110010, 110110 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
REFERENCES
Gardner, M. "The Binary Gray Code." Ch. 2 in Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, 1986.
C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 392.
LINKS
Eric Weisstein's World of Mathematics, Gray Code
Wikipedia, Gray code
MAPLE
a:= proc(n) option remember; `if`(n<2, n,
(b-> 10^b +a(2^(b+1)-1-n))(ilog2(n)))
end:
seq(a(n), n=0..50); # Alois P. Heinz, Nov 01 2008
MATHEMATICA
a[n_] := a[n] = (b = Floor[Log[2, n]]; If[n <= 1, n, 10^b + a[2^(b + 1) - 1 - n]]); Table[a[n], {n, 0, 36}] (* Jean-François Alcover, Oct 11 2012, after Alois P. Heinz *)
PROG
(PARI) a(n)=fromdigits(binary(bitxor(n, n>>1))) \\ Charles R Greathouse IV, Feb 06 2017
CROSSREFS
Same sequence in decimal: A003188.
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Larry Reeves (Larryr(AT)acm.org), Sep 05 2000
STATUS
approved
A268717 Permutation of natural numbers: a(0) = 0, a(n) = A003188(1+A006068(n-1)), where A003188 is binary Gray code and A006068 is its inverse. +40
19
0, 1, 3, 6, 2, 12, 4, 7, 5, 24, 8, 11, 9, 13, 15, 10, 14, 48, 16, 19, 17, 21, 23, 18, 22, 25, 27, 30, 26, 20, 28, 31, 29, 96, 32, 35, 33, 37, 39, 34, 38, 41, 43, 46, 42, 36, 44, 47, 45, 49, 51, 54, 50, 60, 52, 55, 53, 40, 56, 59, 57, 61, 63, 58, 62, 192, 64, 67, 65, 69, 71, 66, 70, 73, 75, 78, 74, 68, 76, 79, 77, 81 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
LINKS
FORMULA
a(n) = A003188(A066194(n)) = A003188(1+A006068(n-1)).
Other identities. For all n >= 0:
A101080(n,a(n+1)) = 1. [The Hamming distance between n and a(n+1) is always one.]
A268726(n) = A000523(A003987(n, a(n+1))). [A268726 gives the index of the toggled bit.]
MATHEMATICA
A003188[n_] := BitXor[n, Floor[n/2]]; A006068[n_] := If[n == 0, 0, BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]]; a[n_] := If[n == 0, 0, A003188[1 + A006068[n-1]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 23 2016 *)
PROG
(Scheme) (define (A268717 n) (if (zero? n) n (A003188 (A066194 n))))
(PARI) A003188(n) = bitxor(n, floor(n/2));
A006068(n) = if(n<2, n, {my(m = A006068(floor(n/2))); 2*m + (n%2 + m%2)%2});
for(n=0, 100, print1(if(n<1, 0, A003188(1 + A006068(n - 1)))", ")) \\ Indranil Ghosh, Mar 31 2017
(Python)
def A003188(n): return n^(n//2)
def A006068(n):
if n<2: return n
m = A006068(n//2)
return 2*m + (n%2 + m%2)%2
def a(n): return 0 if n<1 else A003188(1 + A006068(n - 1))
print([a(n) for n in range(0, 101)]) # Indranil Ghosh, Mar 31 2017
(Python)
def A268717(n):
k, m = n-1, n-1>>1
while m > 0:
k ^= m
m >>= 1
return k+1^ k+1>>1 # Chai Wah Wu, Jun 29 2022
CROSSREFS
Inverse: A268718.
Row 1 and column 1 of array A268715 (without the initial zero).
Row 1 of array A268820.
Cf. A092246 (fixed points).
Cf. A268817 ("square" of this permutation).
Cf. A268821 ("shifted square"), A268823 ("shifted cube") and also A268825, A268827 and A268831 ("shifted higher powers").
KEYWORD
nonn
AUTHOR
Antti Karttunen, Feb 12 2016
STATUS
approved
A302846 Interleave the Gray-coded X and Y-coordinates of 2-dimensional Hilbert's curve in alternate bit-positions: a(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))). +40
15
0, 1, 3, 2, 10, 8, 9, 11, 15, 13, 12, 14, 6, 7, 5, 4, 20, 22, 23, 21, 17, 16, 18, 19, 27, 26, 24, 25, 29, 31, 30, 28, 60, 62, 63, 61, 57, 56, 58, 59, 51, 50, 48, 49, 53, 55, 54, 52, 36, 37, 39, 38, 46, 44, 45, 47, 43, 41, 40, 42, 34, 35, 33, 32, 160, 162, 163, 161, 165, 164, 166, 167, 175, 174, 172, 173, 169, 171, 170, 168, 136 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Like in binary Gray code A003188, also in this permutation the binary expansions of a(n) and a(n+1) differ always by just a single bit-position, that is, A000120(A003987(a(n),a(n+1))) = 1 for all n >= 0. Here A003987 computes bitwise-XOR of its two arguments.
When composed with A052330 this gives A302781.
LINKS
FORMULA
a(n) = A064706(A163356(n)) = A003188(A302844(n)).
PROG
(PARI)
A064706(n) = bitxor(n, n>>2);
A057300(n) = { my(t=1, s=0); while(n>0, if(1==(n%4), n++, if(2==(n%4), n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
A163356(n) = if(!n, n, my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d, f-1-A163356(r), A057300(A163356(r))));
CROSSREFS
Cf. A302845 (inverse permutation).
Cf. also A003188, A163252, A300838 for other permutations satisfying the same condition.
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, Apr 14 2018
STATUS
approved
A344341 Gray-code Niven numbers: numbers divisible by the number of 1's in their binary reflected Gray code (A005811). +40
15
1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 15, 16, 20, 24, 27, 28, 30, 31, 32, 33, 36, 39, 40, 42, 44, 45, 48, 51, 52, 56, 57, 60, 62, 63, 64, 68, 72, 75, 76, 80, 84, 88, 90, 92, 96, 99, 100, 104, 105, 108, 111, 112, 116, 120, 123, 124, 126, 127, 128, 129, 132, 135, 136 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
LINKS
Eric Weisstein's World of Mathematics, Gray Code.
Wikipedia, Gray code.
EXAMPLE
2 is a term since its Gray code is 11 and 1+1 = 2 is a divisor of 2.
6 is a term since its Gray code is 101 and 1+0+1 = 2 is a divisor of 6.
MATHEMATICA
gcNivenQ[n_] := Divisible[n, DigitCount[BitXor[n, Floor[n/2]], 2, 1]]; Select[Range[150], gcNivenQ]
CROSSREFS
Subsequences: A344342, A344343, A344344.
Similar sequences: A005349 (decimal), A049445 (binary), A064150 (ternary), A064438 (quaternary), A064481 (base 5), A118363 (factorial), A328208 (Zeckendorf), A328212 (lazy Fibonacci), A331085 (negaFibonacci), A333426 (primorial), A334308 (base phi), A331728 (negabinary), A342426 (base 3/2), A342726 (base i-1).
KEYWORD
nonn,base
AUTHOR
Amiram Eldar, May 15 2021
STATUS
approved
A344342 Numbers k such that k and k + 1 are both Gray-code Niven numbers (A344341). +40
15
1, 2, 3, 6, 7, 8, 14, 15, 27, 30, 31, 32, 39, 44, 51, 56, 62, 63, 75, 99, 104, 111, 123, 126, 127, 128, 135, 144, 155, 159, 174, 175, 184, 185, 195, 204, 207, 215, 224, 231, 234, 235, 243, 244, 248, 254, 255, 264, 275, 284, 294, 300, 304, 305, 315, 335, 354, 375 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
LINKS
EXAMPLE
1 is a term since 1 and 2 are both Gray-code Niven numbers.
MATHEMATICA
gcNivenQ[n_] := Divisible[n, DigitCount[BitXor[n, Floor[n/2]], 2, 1]]; Select[Range[400], And @@ gcNivenQ[# + {0, 1}] &]
CROSSREFS
Subsequence of: A344341.
Subsequences: A344343 and A344344.
Similar sequences: A330927 (decimal), A328205 (factorial), A328209 (Zeckendorf), A328213 (lazy Fibonacci), A330931 (binary), A331086 (negaFibonacci), A333427 (primorial), A334309 (base phi), A331820 (negabinary), A342427 (base 3/2).
KEYWORD
nonn,base
AUTHOR
Amiram Eldar, May 15 2021
STATUS
approved
A344343 Starts of runs of 3 consecutive Gray-code Niven numbers (A344341). +40
15
1, 2, 6, 7, 14, 30, 31, 62, 126, 127, 174, 184, 234, 243, 254, 304, 474, 483, 510, 511, 534, 543, 544, 783, 784, 903, 904, 954, 963, 1022, 1134, 1144, 1253, 1264, 1448, 1475, 1504, 1895, 1914, 1923, 1974, 2046, 2047, 2093, 2094, 2104, 2814, 2888, 2944, 3054, 3064 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
LINKS
EXAMPLE
1 is a term since 1, 2 and 3 are all Gray-code Niven numbers.
MATHEMATICA
gcNivenQ[n_] := Divisible[n, DigitCount[BitXor[n, Floor[n/2]], 2, 1]]; Select[Range[3000], AllTrue[# + {0, 1, 2}, gcNivenQ] &]
CROSSREFS
Subsequence of A344341 and A344342.
Subsequences: A344344.
Similar sequences: A154701 (decimal), A328206 (factorial), A328210 (Zeckendorf), A328214 (lazy Fibonacci), A330932 (binary), A331087 (negaFibonacci), A333428 (primorial), A334310 (base phi), A331822 (negabinary), A342428 (base 3/2).
KEYWORD
nonn,base
AUTHOR
Amiram Eldar, May 15 2021
STATUS
approved
A268718 Permutation of natural numbers: a(0) = 0, a(n) = 1 + A003188(A006068(n)-1), where A003188 is binary Gray code and A006068 is its inverse. +40
14
0, 1, 4, 2, 6, 8, 3, 7, 10, 12, 15, 11, 5, 13, 16, 14, 18, 20, 23, 19, 29, 21, 24, 22, 9, 25, 28, 26, 30, 32, 27, 31, 34, 36, 39, 35, 45, 37, 40, 38, 57, 41, 44, 42, 46, 48, 43, 47, 17, 49, 52, 50, 54, 56, 51, 55, 58, 60, 63, 59, 53, 61, 64, 62, 66, 68, 71, 67, 77, 69, 72, 70, 89, 73, 76, 74, 78, 80, 75, 79, 113, 81 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
LINKS
FORMULA
a(0) = 0, and for n >= 1, a(n) = A105081(A006068(n)) = 1 + A003188(A006068(n)-1).
Other identities. For all n >= 1:
a(A128309(n)) = A128309(n)+2. [Maps any even odious number to that number + 2.]
MATHEMATICA
{0}~Join~Table[1 + BitXor[#, Floor[#/2]] &[BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}] - 1], {n, 81}] (* Michael De Vlieger, Feb 29 2016, after Jean-François Alcover at A006068 and Robert G. Wilson v at A003188 *)
PROG
(Scheme) (define (A268718 n) (if (zero? n) n (A105081 (A006068 n))))
(PARI)
a003188(n)=bitxor(n, n>>1);
a006068(n)= {
my( s=1, ns );
while ( 1,
ns = n >> s;
if ( 0==ns, break() );
n = bitxor(n, ns);
s <<= 1;
);
return (n);
} \\ by Joerg Arndt
a(n)=if(n==0, 0, 1 + a003188(a006068(n) - 1)); \\ Indranil Ghosh, Jun 07 2017
(Python)
def a003188(n): return n^(n>>1)
def a006068(n):
s=1
while True:
ns=n>>s
if ns==0: break
n=n^ns
s<<=1
return n
def a(n): return 0 if n==0 else 1 + a003188(a006068(n) - 1) # Indranil Ghosh, Jun 07 2017
CROSSREFS
Inverse: A268717.
Row 1 of array A268830.
Cf. A092246 (fixed points).
Cf. A268818 ("square" of this permutation).
Cf. A268822 ("shifted square"), A268824 ("shifted cube") and also A268826, A268828 and A268832 (higher "shifted powers").
KEYWORD
nonn
AUTHOR
Antti Karttunen, Feb 12 2016
STATUS
approved
page 1 2 3 4 5 6 7 8 9 10 ... 23

Search completed in 0.255 seconds

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 07:33 EDT 2024. Contains 371235 sequences. (Running on oeis4.)