A066194 -id:A066194 - cp's OEIS frontend

A342448 Partial sums of A066194.

1, 3, 7, 10, 18, 25, 30, 36, 52, 67, 80, 94, 103, 113, 125, 136, 168, 199, 228, 258, 283, 309, 337, 364, 381, 399, 419, 438, 462, 485, 506, 528, 592, 655, 716, 778, 835, 893, 953, 1012, 1061, 1111, 1163, 1214, 1270, 1325, 1378, 1432, 1465, 1499, 1535, 1570

Offset: 1

John Erickson, Mar 12 2021

n^2/2 + n/2 <= a(n) <= (31/50)*n^2 + n/2. The lower and upper bounds are attained at n=2^k and n=5*2^k for k >= 0.

Alois P. Heinz, Table of n, a(n) for n = 1..16384

Cf. A066194, A268836, A007814, A000120, A010060, A000035.

b:= proc(n) option remember; `if`(n<2, n,
      Bits[Xor](n, b(iquo(n, 2))))
    end:
a:= proc(n) a(n):= 1+`if`(n<2, 0, a(n-1)+b(n-1)) end:
seq(a(n), n=1..60);  # Alois P. Heinz, Mar 14 2021

a[1]=1;
a[n_/;EvenQ[n]]:= a[n] = 4a[n/2] - n/2;
a[n_/;OddQ[n]]:= a[n] = 2a[(n - 1)/2]+2a[(n + 1)/2]-(n-1)/2 - ThueMorse[n];
(* Second program: *)
b[n_] := If[n==0, 0, BitXor@@Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]];
A066194 = Table[b[n]+1, {n, 0, 60}];
A066194 // Accumulate (* Jean-François Alcover, Sep 10 2022 *)

a(n) = A268836(n)/2 + n. - Kevin Ryde, Mar 12 2021

a(1) = 1; a(n) = [n == 0 (mod 2)]*(4*a(n/2) - n/2) + [n == 1 (mod 2)]*(2*a((n - 1)/2)+2*a((n + 1)/2)-(n-1)/2 - A010060(n)) where [] is an Iverson bracket

A320667 First differences of A066194.

Original entry on oeis.org

1, 2, -1, 5, -1, -2, 1, 10, -1, -2, 1, -5, 1, 2, -1, 21, -1, -2, 1, -5, 1, 2, -1, -10, 1, 2, -1, 5, -1, -2, 1, 42, -1, -2, 1, -5, 1, 2, -1, -10, 1, 2, -1, 5, -1, -2, 1, -21, 1, 2, -1, 5, -1, -2, 1, 10, -1, -2, 1, -5, 1, 2, -1, 85, -1, -2, 1, -5, 1, 2, -1, -10

Offset: 1

John Erickson, Oct 18 2018

sign

			To obtain the first 2^n-1 entries if you have the first 2^(n-1)-1 entries, adjoin 1/6 (-3 + (-1)^(1 + n) + 2^(2 + n)) to the right end of the list, negate the signs of the first 2^(n-1)-1 entries, and then adjoin that list to the right. For example for n=3 {1,2,-1} becomes {1,2,-1,5,-1,-2,1}.

Cf. A066194.

Fold[Join[#1, {#2}, -#1] &, {1},
Table[1/6 (-3 + (-1)^(1 + n) + 2^(2 + n)), {n, 2, 6}]]
t[n_/;IntegerQ[Log2[n]]]:=1/6 (-3 + (-1)^IntegerExponent[n,2] + 8*n);
t[n_/;Not[IntegerQ[Log2[n]]]]:=-t[n-2^Floor[Log2[n]]];
Table[t[j],{j,1,15}](* recursive formulation *)
Table[1/6 (-3+(-1)^IntegerExponent[j,2]+2^(IntegerExponent[j,2]+3))(-1)^(Total[IntegerDigits[j,2]]+1),{j,1,15}] (* closed form *)

a(n) = A066194(n+1) - A066194(n).

a(n) = (1/6)*(-3 + (-1)^A007814(n) + 2^(A007814(n)+3))*(-1)^(A000120(n)+1).

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

Original entry on oeis.org

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

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.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Feb 12 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences that are permutations of the natural numbers

Inverse: A268718.
Cf. A000523, A003188, A003987, A006068, A010060, A066194, A101080, A171977, A268718, A268726, A268727.
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").

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

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

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

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

(define (A268717 n) (if (zero? n) n (A003188 (A066194 n))))

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.]
From Alan Michael Gómez Calderón, May 29 2025: (Start)
a(2*n) = (2*n-1) XOR (2-A010060(n-1)) for n >= 1;
a(n) = (A268718(n-1)-1) XOR (A171977(n-1)+1) for n >= 2. (End)

A105081 a(n) = 1 + A003188(n - 1), n >= 1.

Original entry on oeis.org

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

Offset: 1

Philippe Deléham, Apr 28 2005

A permutation of the natural numbers.

Inverse permutation: A066194.

Cf. A000069, A003188, A065621, A268718.

Nest[Join[#,Length[#]+Reverse[#]]&,{1},7] (* Vladimir Joseph Stephan Orlovsky, Feb 01 2012 *)

def A105081(n): return 1+(n-1^ n-1>>1) # Chai Wah Wu, Jun 29 2022

(define (A105081 n) (+ 1 (A003188 (- n 1)))) ;; Antti Karttunen, Feb 14 2016

a(1) = 1, a(2^k + j) = 2^k + a(2^k - j + 1) for 1 <= j <= 2^k.
A000069(a(n)) = A065621(n).
As a composition of related permutations:
a(n) = A268718(A003188(n)). - Antti Karttunen, Feb 14 2016

A268714 Square array A(i,j) = A006068(i) + A006068(j), read by antidiagonals.

Original entry on oeis.org

0, 1, 1, 3, 2, 3, 2, 4, 4, 2, 7, 3, 6, 3, 7, 6, 8, 5, 5, 8, 6, 4, 7, 10, 4, 10, 7, 4, 5, 5, 9, 9, 9, 9, 5, 5, 15, 6, 7, 8, 14, 8, 7, 6, 15, 14, 16, 8, 6, 13, 13, 6, 8, 16, 14, 12, 15, 18, 7, 11, 12, 11, 7, 18, 15, 12, 13, 13, 17, 17, 12, 10, 10, 12, 17, 17, 13, 13, 8, 14, 15, 16, 22, 11, 8, 11, 22, 16, 15, 14, 8, 9, 9, 16, 14, 21, 21, 9, 9, 21, 21, 14, 16, 9, 9

Offset: 0

Antti Karttunen, Feb 12 2016

			The top left [0 .. 15] x [0 .. 15] section of the array:
   0,  1,  3,  2,  7,  6,  4,  5, 15, 14, 12, 13,  8,  9, 11, 10
   1,  2,  4,  3,  8,  7,  5,  6, 16, 15, 13, 14,  9, 10, 12, 11
   3,  4,  6,  5, 10,  9,  7,  8, 18, 17, 15, 16, 11, 12, 14, 13
   2,  3,  5,  4,  9,  8,  6,  7, 17, 16, 14, 15, 10, 11, 13, 12
   7,  8, 10,  9, 14, 13, 11, 12, 22, 21, 19, 20, 15, 16, 18, 17
   6,  7,  9,  8, 13, 12, 10, 11, 21, 20, 18, 19, 14, 15, 17, 16
   4,  5,  7,  6, 11, 10,  8,  9, 19, 18, 16, 17, 12, 13, 15, 14
   5,  6,  8,  7, 12, 11,  9, 10, 20, 19, 17, 18, 13, 14, 16, 15
  15, 16, 18, 17, 22, 21, 19, 20, 30, 29, 27, 28, 23, 24, 26, 25
  14, 15, 17, 16, 21, 20, 18, 19, 29, 28, 26, 27, 22, 23, 25, 24
  12, 13, 15, 14, 19, 18, 16, 17, 27, 26, 24, 25, 20, 21, 23, 22
  13, 14, 16, 15, 20, 19, 17, 18, 28, 27, 25, 26, 21, 22, 24, 23
   8,  9, 11, 10, 15, 14, 12, 13, 23, 22, 20, 21, 16, 17, 19, 18
   9, 10, 12, 11, 16, 15, 13, 14, 24, 23, 21, 22, 17, 18, 20, 19
  11, 12, 14, 13, 18, 17, 15, 16, 26, 25, 23, 24, 19, 20, 22, 21
  10, 11, 13, 12, 17, 16, 14, 15, 25, 24, 22, 23, 18, 19, 21, 20

Antti Karttunen, Table of n, a(n) for n = 0..15050; the first 173 antidiagonals of the array

Cf. A003188, A268715.
Cf. A006068 (row 0, column 0).
Cf. A066194 (row 1, column 1).
Cf. A268716 (main diagonal).
Cf. also A268724.

A006068[n_] := BitXor @@ Table[Floor[n/2^m], {m, 0, Log[2, n]}]; A006068[0] = 0; A[i_, j_] := A006068[i] + A006068[j]; Table[A[i-j, j], {i, 0, 13}, {j, 0, i}] // Flatten (* Jean-François Alcover, Feb 17 2016 *)

\\ Produces the triangle when the array is read by antidiagonals
a(n) = if(n<2, n, 2*a(floor(n/2)) + (n%2 + a(floor(n/2))%2)%2); /* A006068 */
T(i,j) = a(i) + a(j);
for(i=0, 13, for(j=0, i, print1(T(i - j, j),", "););print();); \\ Indranil Ghosh, Mar 23 2017

# Produces the triangle when the array is read by antidiagonals
def A006068(n):
    return n if n<2 else 2*A006068(n//2) + (n%2 + A006068(n//2)%2)%2
def T(i,j): return A006068(i) + A006068(j)
for i in range(14):
    print([T(i - j, j) for j in range(i + 1)]) # Indranil Ghosh, Mar 23 2017

(define (A268714 n) (A268714bi (A002262 n) (A025581 n)))
(define (A268714bi row col) (+ (A006068 row) (A006068 col)))

A(i,j) = A006068(i) + A006068(j).

A(i,j) = A006068(A268715(i,j)). - Corrected Mar 23 2017

cp's OEIS Frontend

A342448 Partial sums of A066194.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320667 First differences of A066194.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

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

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.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Scheme

Formula

A105081 a(n) = 1 + A003188(n - 1), n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A268714 Square array A(i,j) = A006068(i) + A006068(j), read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula