A003100 -id:A003100 - cp's OEIS frontend

A006068 a(n) is Gray-coded into n.

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

Offset: 0

N. J. A. Sloane

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
Each bit at bit-index k (counted from the right hand end, with the least significant bit having bit-index 0) in the binary representation of a(n) is the parity of the number of 1's among the bits of the binary representation of n that have a bit-index of k or higher. - Frederik P.J. Vandecasteele, May 26 2025

			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,...

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

T. D. Noe, Table of n, a(n) for n = 0..1023
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.
Paul Tarau, Isomorphic Data Encodings and their Generalization to Hylomorphisms on Hereditarily Finite Data Types; see also alternate link.
Index entries for sequences that are permutations of the natural numbers

Cf. A038554, A005811, A003188, A014550, A003100, A265263, A377404.
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.

a006068 n = foldl xor 0 $
                  map (div n) $ takeWhile (<= n) a000079_list :: Integer
-- Reinhard Zumkeller, Apr 28 2012

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

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 *)

{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 */

/* 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 */

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

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

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
Conjecture: a(n) = a(A053645(A063946(n))) + A053644(n) for n > 0 with a(0) = 0. - Mikhail Kurkov, Sep 09 2023
a(n) = 2*A265263(n) - 2*A377404(n) - A010060(n). - Alan Michael Gómez Calderón, Jun 26 2025

More terms from Henry Bottomley, Jan 10 2001

A106649 Replace each digit d (except the leading one) of n with 9-d.

Original entry on oeis.org

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

Offset: 0

Zak Seidov, May 12 2005

By definition, one-digit numbers do not change.

Differs from A003100 starting with a(21)=29: A003100(21)=20.

Index entries for sequences that are permutations of the natural numbers

Cf. A003100.

Cf. A054429, A115303, A115304, A115305, A115306, A115307, A115308, A115309.

a[n_]:=FromDigits[Flatten[{IntegerDigits[n][[1]], Map[9-#&, Drop[IntegerDigits[n], 1]]}]];Table[a[n], {n, 0, 100}]

a(n) = n if n < 10, otherwise 10*a(floor(n/10)) + 9 - n mod 10; a self-inverse permutation of the natural numbers, A115310(n+8, 9) = a(n) for n > 0. - Reinhard Zumkeller, Jan 20 2006 [corrected by Georg Fischer, Jun 23 2024]

a(n) = A305238(n-9) for 10 <= n <= 99. - M. F. Hasler, Oct 16 2018

A118757 Permutation of the natural numbers such that the Levenshtein distance between decimal representations of successive terms is 1, and a(n+1) is the largest such m < a(n) if it exists, or else the smallest such m > a(n); a(0) = 0.

Original entry on oeis.org

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

Offset: 0

Reinhard Zumkeller, May 01 2006

a(n) = A003100(n) for n <= 100, a(100) = A003100(100) = 190, but a(101) = 180, A003100(101) = 191.

A118763 is the lexicographically smallest permutation with LevenshteinDistance[Base10](a(n),a(n+1)) = 1. - M. F. Hasler, Sep 12 2018

R. Zumkeller, Table of n, a(n) for n = 0..30000
Michael Gilleland, Levenshtein Distance, 2006. [Broken link fixed by _M. F. Hasler_, Sep 12 2018, cf A118763]
R. Zumkeller, Values of A118757 for n<=1200
Index entries for sequences that are permutations of the natural numbers

Cf. A118763.
Iterated twice: A118759(n) := a(a(n)).
Fixed points: A118761 = { n | n = a(n) }.
Inverse: A118758.
First difference: A118762(n) := a(n+1) - a(n).

a(n+1) = if U(n) is empty then Min(V(n)) else Max(U(n)), where the sets U and V are defined as: U(m) = {x < a(m) : LD10(a(m),x) = 1 and a(k) <> x for 0 <= k < m}, V(m) = {x > a(m) | LD10(a(m),x) = 1 and a(k) <> x for 0 <= k < m} with LD10 = Levenshtein distance in decimal representations of natural numbers.

a(n) = A118758(n) (self-inverse) for n < 100.

Correct definition and other edits by M. F. Hasler, Sep 12 2018

A098488 Decimal modular Gray code for n.

Original entry on oeis.org

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

Offset: 0

Jaume Simon Gispert (jaume(AT)nuem.com), Sep 10 2004

This is another decimal Gray code that considers that the distance between 9 and 0 is 1. Cyclic for (left-zero-padded) groups of n digits.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Martin Cohn, Affine m-ary Gray Codes, Information and Control, volume 6, 1963, pages 70-78. Example 4 column "Gray" is the present sequence.
Donald E. Knuth, The Art of Computer Programming, Pre-Fascicle 2A, Draft of Section 7.2.1.1. See subsection "Nonbinary Gray codes" page 18, and exercise 78 page 35 and answer page 54 (modular Gray g overline (k) for the case all m_j=10).
Index entries for sequences that are permutations of the natural numbers

Cf. A003100.

Cf. A226134 (inverse).

import Data.List (elemIndex); import Data.Maybe (fromJust)
a098488 = fromJust . (`elemIndex` a226134_list)
-- Reinhard Zumkeller, Jun 03 2013

# insert 10 into the second argument of the gray(.,.) function in A105530. - R. J. Mathar, Mar 10 2015

AltGray[In_] := { tIn = IntegerDigits[In]; Ac = 0; Do[tIn[[z]] = Mod[tIn[[z]] - Ac, 10]; Ac += tIn[[z]], {z, 1, Length[tIn]}]; FromDigits[tIn, 10] }

a(n) = my(v=digits(n)); forstep(i=#v,2,-1, v[i]=(v[i]-v[i-1])%10); fromdigits(v); \\ Kevin Ryde, May 15 2020

A261725 Lexicographically earliest sequence of distinct terms such that the absolute difference of two successive terms is a power of 10, and can be computed without carry.

Original entry on oeis.org

Offset: 0

Paul Tek, Aug 30 2015

In base 10, two successive terms have the same representation, except for one position, where the digits differ from exactly one unit. This difference can occur on a leading zero.
Conjectured to be a permutation of the nonnegative integers. See A261729 for putative inverse.
a(n) = A003100(n) for n < 101, but a(101) = 180, A003100(101) = 191.
a(n) = A118757(n) for n < 201, but a(201) = 281, A118757(201) = 290.
a(n) = A118758(n) for n < 100, but a(100) = 190, A118758(100) = 109.
a(n) = A174025(n) for n < 100, but a(100) = 190, A174025(100) = 199.
a(n) = A261729(n) for n < 100, but a(100) = 190, A261729(100) = 109.

Paul Tek, Table of n, a(n) for n = 0..10000
Paul Tek, PERL program for this sequence

Cf. A003100, A118757, A118763, A163252, A261729 (putative inverse).

Perl
```
See Links section.
```

A261729 Putative inverse of conjectured permutation in A261725.

Original entry on oeis.org

Offset: 0

Paul Tek, Aug 30 2015

a(n) = A003100(n) for n < 100, but a(100) = 109, A003100(100) = 190.
a(n) = A118757(n) for n < 100, but a(100) = 109, A118757(100) = 190.
a(n) = A118758(n) for n < 201, but a(201) = 209, A118758(201) = 211.
a(n) = A174025(n) for n < 100, but a(100) = 109, A174025(100) = 199.
a(n) = A261725(n) for n < 100, but a(100) = 109, A261725(100) = 190.

Paul Tek, Table of n, a(n) for n = 0..10000

Cf. A261725.

A143332 Related to Gray code representation of Fibonacci(n) in base 10.

Original entry on oeis.org

0, 1, 1, 3, 2, 7, 12, 11, 31, 51, 44, 117, 216, 157, 453, 851, 566, 803, 788, 127, 859, 931, 440, 521, 432, 409, 809, 739, 458, 239, 828, 947, 391, 531, 148, 173, 360, 837, 61, 1011, 942, 475, 36, 375, 307, 579, 496, 145, 864, 689, 465

Offset: 0

Roger L. Bagula and Gary W. Adamson, Oct 21 2008

This is not A003188(A000045(n)) for n >= 17. - Jose-Angel Oteo, Mar 09 2015

The Gray code of Fibonacci(n) is now listed in A255919 = A003188 o A000045. It would be appreciated to know the precise definition of the present sequence, presumably computed via the incomplete and somewhat obscure Mathematica code given below. In view of the definition, might it be related to the decimal Gray code A003100 or another variant? R. J. Mathar remarks that A143214 and A143210 have Mathematica code of a two-argument GrayCode[] function. - M. F. Hasler, Mar 11 2015

Cf. A255919, A003188, A000045, A003100, A143214, A143210.

GrayCodeList[k_] := Module[{b = IntegerDigits[k, 2], i}, Do[ If[b[[i - 1]] == 1, b[[i]] = 1 - b[[i]]], {i, Length[b], 2, -1} ]; b ]; FromGrayCodeList[d_] := Module[{b = d, i, j}, Do[ If[Mod[Sum[b[[j]], {j, i - 1}], 2] == 1, b[[i]] = 1 - b[[i]]], {i, n = Length[d], 2, -1} ]; FromDigits[b, 2] ]; GrayCode[i_, n_] :=

Edited by M. F. Hasler, Mar 11 2015

cp's OEIS Frontend

A174025 Inverse permutation to A003100.

Views

Author

Keywords

Links

Programs

PARI

A006068 a(n) is Gray-coded into n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

R

Formula

Extensions

A106649 Replace each digit d (except the leading one) of n with 9-d.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A118757 Permutation of the natural numbers such that the Levenshtein distance between decimal representations of successive terms is 1, and a(n+1) is the largest such m < a(n) if it exists, or else the smallest such m > a(n); a(0) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A098488 Decimal modular Gray code for n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

A261725 Lexicographically earliest sequence of distinct terms such that the absolute difference of two successive terms is a power of 10, and can be computed without carry.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Perl

A261729 Putative inverse of conjectured permutation in A261725.

Views

Author

Keywords

Comments

Links

Crossrefs

A143332 Related to Gray code representation of Fibonacci(n) in base 10.

Views

Author

Keywords

Comments

Crossrefs