A059905 -id:A059905 - cp's OEIS frontend

A072661 Composition of the A059905 and A048679, i.e., a(n) = A059905(A048679(n)).

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

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

The other side of this projection is A072662. Used to construct the permutations A072657 and A072659.

A327857 a(n) = A091255(1+A059905(n), 1+A059906(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 2, 3, 3, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 3, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 4, 5, 3, 3, 6, 1, 1, 1, 2, 1, 1, 1, 2, 7, 1, 1, 8, 1, 1, 1, 2, 1, 1, 1, 2, 3, 3, 1, 2, 1, 3, 1, 4, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 4, 3, 5, 3, 6, 1, 3, 1, 6, 7, 1

Offset: 0

Antti Karttunen, Sep 28 2019

nonn

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for sequences operating on polynomials in ring GF(2)[X]

Cf. A059905, A059906, A091255.

A059905(n) = { my(t=1,s=0); while(n>0, s += (n%2)*t; n \= 4; t *= 2); (s); };
A059906(n) = { my(t=1,s=0); while(n>0, s += ((n%4)>=2)*t; n \= 4; t *= 2); (s); };
A091255sq(a,b) = fromdigits(Vec(lift(gcd(Pol(binary(a))*Mod(1, 2),Pol(binary(b))*Mod(1, 2)))),2);
A327857(n) = A091255sq(1+A059905(n), 1+A059906(n));

a(n) = A091255(1+A059905(n), 1+A059906(n)) = A091255(1+A059906(n), 1+A059905(n)).

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

Original entry on oeis.org

0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 1024, 1025, 1028, 1029, 1040, 1041, 1044, 1045, 1088, 1089, 1092, 1093, 1104, 1105, 1108, 1109, 1280, 1281, 1284, 1285

Offset: 0

N. J. A. Sloane

Although this is a list, it has offset 0 for both historical and mathematical reasons.
Numbers whose set of base-4 digits is a subset of {0,1}. - Ray Chandler, Aug 03 2004, corrected by M. F. Hasler, Oct 16 2018
Numbers k such that the sum of the base-2 digits of k = sum of the base-4 digits of k. - Clark Kimberling
Numbers having the same representation in both binary and negabinary (A039724). - Eric W. Weisstein
This sequence has many other interesting and useful properties. Every term k corresponds to a unique pair i,j with k = a(i) + 2*a(j) (i=A059905(n), j=A059906(n)) -- see A126684. Every list of numbers L = [L1,L2,L3,...] can be encoded uniquely by "recursive binary interleaving", where f(L) = a(L1) + 2*a(f([L2,L3,...])) with f([])=0. - Marc LeBrun, Feb 07 2001
This may be described concisely using the "rebase" notation b[n]q, which means "replace b with q in the expansion of n", thus "rebasing" n from base b into base q. The present sequence is 2[n]4. Many interesting operations (e.g., 10[n](1/10) = digit reverse, shifted) are nicely expressible this way. Note that q[n]b is (roughly) inverse to b[n]q. It's also natural to generalize the idea of "basis" so as to cover the likes of F[n]2, the so-called "fibbinary" numbers (A003714) and provide standard ready-made images of entities obeying other arithmetics, say like GF2[n]2 (e.g., primes = A014580, squares = the present sequence, etc.). - Marc LeBrun, Mar 24 2005
a(n) is also equal to the product n X n formed using carryless binary multiplication (A059729, A063010). - Henry Bottomley, Jul 03 2001
Numbers k such that A004117(k) is odd. - Pontus von Brömssen, Nov 25 2008
Fixed point of the morphism: 0 -> 01; 1 -> 45; 2 -> 89; ...; n -> (4n)(4n+1), starting from a(0)=0. - Philippe Deléham, Oct 22 2011
If n is even and present, so is n+1. - Robert G. Wilson v, Oct 24 2014
Also: interleave binary digits of n with 0's. (Equivalent to the "rebase" interpretation above.) - M. F. Hasler, Oct 16 2018
Named after the Austrian-Canadian mathematician Leo Moser (1921-1970) and the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - Amiram Eldar, Jun 19 2021
Conjecture: The sums of distinct powers of k > 2 can be constructed as the following (k-1)-ary rooted tree. For each n the tree grows and a(n) is then the total number of nodes. For n = 1, the root of the tree is added. For n > 1, if n is odd one leaf of depth n-2 grows one child. If n is even all leaves of depth >= (n - 1 - A000225(A001511(n/2))) grow the maximum number of children. An illustration is provided in the links. - John Tyler Rascoe, Oct 09 2022

			G.f.: x + 4*x^2 + 5*x^3 + 16*x^4 + 17*x^5 + 20*x^6 + 21*x^7 + 64*x^8 + ...
If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = 4^4 + 4^3 + 4 + 1 = 325; k = b_0 + b_2*2 + b_4*2^2 = 5, l = b_1 + b_3*2 = 3, such that a(5)=17, a(3)=5 and 27 = 17 + 2*5. - _Vladimir Shevelev_, Nov 10 2008

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
David Applegate, Marc LeBrun and N. J. A. Sloane, Carryless Arithmetic (I): The Mod 10 Version.
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), pp. 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
David Applegate, Marc LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq., Vol. 14 (2011), Article 11.9.8.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 59-60, pp. 750-751.
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
N. G. de Bruijn, Some direct decompositions of the set of integers, Math. Comp., Vol. 18, No. 88 (1964), pp. 537-546.
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22, No. 2 (2015), #P2.24.
Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
S. J. Eigen, Y. Ito, and V. S. Prasad, Universally bad integers and the 2-adics, J. Number Theory, Vol. 107, No. 2 (2004), pp. 322-334.
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. 44.
Bin Lan and James A. Sellers, Properties of a Restricted Binary Partition Function a la Andrews and Lewis, Electronic Journal of Combinatorial Number Theory, Volume 15 #A23.
Lukasz Merta, Composition inverses of the variations of the Baum-Sweet sequence, arXiv:1803.00292 [math.NT], 2018. See m(n) p. 11.
Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38.
Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38. [Annotated scanned copy]
John Tyler Rascoe, Illustration of terms.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016-2017.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Stephen Nicholas Swatman, Ana-Lucia Varbanescu, Andy D. Pimentel, Andreas Salzburger, and Attila Krasznahorkay, Finding Morton-Like Layouts for Multi-Dimensional Arrays Using Evolutionary Algorithms, arXiv:2309.07002 [cs.NE], 2023.
Eric Weisstein's World of Mathematics, Moser-de Bruijn Sequence.
Eric Weisstein's World of Mathematics, Negabinary.
Wikipedia, Morton code. (also known as Z-order curve. Cf. Marc LeBrun's comments about binary interleaving.)
Index entries for 2-automatic sequences.

For generating functions Product_{k>=0} (1 + a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
Main diagonal of A048720, second column of A048723.
Cf. A000225, A000302, A001511, A007583, A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684, A145812.
A062880(n) = 2*a(n); A001196(n) = 3*a(n).
Row 4 of array A104257.

uint32_t a_next(uint32_t a_n) { return (a_n + 0xaaaaaaab) & 0x55555555; } /* Falk Hüffner, Jan 24 2022 */

a000695 n = if n == 0 then 0 else 4 * a000695 n' + b
            where (n',b) = divMod n 2
-- Reinhard Zumkeller, Feb 21 2014, Dec 03 2011

function a(n)
    m, r, b = n, 0, 1
    while m > 0
        m, q = divrem(m, 2)
        r += b * q
        b *= 4
    end
r end; [a(n) for n in 0:51] |> println # Peter Luschny, Jan 03 2021

m:=60; R:=PowerSeriesRing(Integers(), m); [0] cat Coefficients(R!( (&+[4^k*x^(2^k)/(1+x^(2^k)): k in [0..20]])/(1-x) )); // G. C. Greubel, Dec 06 2018

a:= proc(n) local m, r, b; m, r, b:= n, 0, 1;
      while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*4 od; r
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 16 2013

Table[FromDigits[Riffle[IntegerDigits[n, 2], 0], 2], {n, 0, 51}] (* Jacob A. Siehler, Jun 30 2010 *)
Table[FromDigits[IntegerDigits[n, 2], 4], {n, 0, 51}] (* IWABUCHI Yu(u)ki, Apr 06 2013 *)
Union@ Flatten@ NestList[ Join[ 4#, 4# + 1] &, {0}, 6] (* Robert G. Wilson v, Aug 30 2014 *)
Select[ Range[0, 1320], Total@ IntegerDigits[#, 2] == Total@ IntegerDigits[#, 4] &] (* Robert G. Wilson v, Oct 24 2014 *)
Union[FromDigits[#,4]&/@Flatten[Table[Tuples[{0,1},n],{n,6}],1]] (* Harvey P. Dale, Oct 03 2015 *)
a[ n_] := Which[n < 1, 0, EvenQ[n], a[n/2] 4, True, a[n - 1] + 1]; (* Michael Somos, Nov 30 2016 *)

a(n)=n=binary(n);sum(i=1,#n,n[i]*4^(#n-i)) \\ Charles R Greathouse IV, Mar 04 2013

{a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* Michael Somos, Nov 30 2016 */

A000695(n)=fromdigits(binary(n),4) \\ M. F. Hasler, Oct 16 2018

def a(n):
    n = bin(n)[2:]
    x = len(n)
    return sum(int(n[i]) * 4**(x - 1 - i) for i in range(x))
[a(n) for n in range(101)] # Indranil Ghosh, Jun 25 2017

def a():
    x = 0
    while True:
        yield x
        y = ~(x << 1)
        x = (x - y) & y # Falk Hüffner, Dec 21 2021

from itertools import count, islice
def A000695_gen(): # generator of terms
    yield (a:=0)
    for n in count(1):
        yield (a := a+((1<<((~n & n-1).bit_length()<<1)+1)+1)//3)
A000695_list = list(islice(A000695_gen(),30)) # Chai Wah Wu, Feb 22 2023

def A000695(n): return int(bin(n)[2:],4) # Chai Wah Wu, Aug 21 2023

s=(sum(4^k*x^(2^k)/(1+x^(2^k)) for k in range(10))/(1-x)).series(x, 60); s.coefficients(x, sparse=False) # G. C. Greubel, Dec 06 2018

G.f.: 1/(1-x) * Sum_{k>=0} 4^k*x^2^k/(1+x^2^k). - Ralf Stephan, Apr 27 2003
Numbers k such that the coefficient of x^k is > 0 in Product_{n>=0} 1+x^(4^n). - Benoit Cloitre, Jul 29 2003
For n >= 1, a(n) = a(n-1) + (4^t+2)/6, where t is such that 2^t||2n,or t=A007814(2n). a(n) = (A145812(n+1) - 1)/2. - Vladimir Shevelev, Nov 07 2008
To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_j*2^(2j). The Diophantine equation a(k)+2a(l)=n has the unique solution: k=Sum b_(2j)*2^j, l=Sum b_(2j+1)*2^j. - Vladimir Shevelev, Nov 10 2008
If a(k)*a(l)=a(m), then k*l=m (the inverse, generally speaking, is not true). - Vladimir Shevelev, Nov 21 2008
Let F(x) be the generating function, then F(x)*F(x^2) = 1/(1-x). - Joerg Arndt, May 12 2010
a(n+1) = (a(n) + 1/3) & -1/3, where & is bitwise AND, -1/3 is represented as the infinite dyadic ...010101 (just as -1 is ...111111 in two's complement) and +1/3 is ...101011. - Marc LeBrun, Sep 30 2010
a(n) = Sum_{k>=0} {A030308(n,k)*b(k)} with b(k) = 4^k = A000302(k). - Philippe Deléham, Oct 18 2011
A182560(6*a(n)) = 0. - Reinhard Zumkeller, May 05 2012
G.f.: x/(1-x^2) + 4*x^2/((1-x)*(W(0) - 4*x - 4*x^2)), where W(k) = 1 + 4*x^(2^k) + 5*x^(2^(k+1)) - 4*x^(2^(k+1))*(1 + x^(2^(k+1)))^2/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Jan 04 2014
liminf a(n)/n^2 = 1/3 and limsup a(n)/n^2 = 1. - Gheorghe Coserea, Sep 15 2015
Let f(x) = (Sum_{k=-oo..oo} floor(x*2^k)/4^k)/2. Then f(x) is a real-valued extension of a(n), which a(n) approximates in the sense that f(x) = lim_{k->oo} a(floor(x*2^k))/a(2^k). - Velin Yanev, Nov 28 2016
G.f. A(x) satisfies x/(1 - x^2) = A(x) - 4 * (1+x) * A(x^2). - Michael Somos, Nov 30 2016
a(2^k) = 4^k = A000302(k). a(n + 2^k) = a(n) + a(2^k) for 2^k > n >= 1. - David A. Corneth, Oct 16 2018
Sum_{n>=1} 1/a(n) = 1.886176434476107244547259512076353532930680508099044818673061351780360211128... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

A057300 Binary counter with odd/even bit positions swapped; base-4 counter with 1's replaced by 2's and vice versa.

Original entry on oeis.org

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

Offset: 0

Marc LeBrun, Aug 24 2000

A self-inverse permutation of the integers.
a(n) = n if and only if n can be written as 3*Sum_{k>=0} d_i*4^k, where d_i is either 0 or 1. - Jon Perry, Oct 06 2012
From Veselin Jungic, Mar 03 2015: (Start)
In 1988 A. F. Sidorenko, see the Sidorenko reference, used this sequence as an example of a permutation of the set of positive integers with the property that if positive integers i, j, and k form a 3-term arithmetic progression then the corresponding terms a(i), a(j), and a(k) do not form an arithmetic progression.
In the terminology introduced in the Brown, Jungic, and Poelstra reference, the sequence does not contain "double 3-term arithmetic progressions".
It is not difficult to check that this sequence is with unbounded gaps, i.e., for any positive number m there is a natural number n such that a(n+1) - a(n) > m.
It is an open question if every sequence of integers with bounded gaps must contain a double 3-term arithmetic progression. This problem is equivalent to the well known additive square problem in infinite words: Is it true that any infinite word with a finite set of integers as its alphabet contains two consecutive blocks of the same length and the same sum? For more details about the additive square problem in infinite words see the following references: Ardal, et al.; Brown and Freedman; Freedman; Grytczuk; Halbeisen and Hungerbuhler, and Pirillo and Varricchio.
The sequence was attributed to Sidorenko in P. Hegarty's paper "Permutations avoiding arithmetic patterns". In his paper Hegarty characterized the countably infinite abelian groups for which there exists a bijection mapping arithmetic progressions to non-arithmetic progressions. This was further generalized by Jungic and Sahasrabudhe. (End)

			a(31) = a(4*7+3) = 4*a(7) + a(3) = 4*11 + 3 = 47.

Paul Tek, Table of n, a(n) for n = 0..16383
H. Ardal, T. Brown, V. Jungic, and J. Sahasrabudhe, On Additive and Abelian Complexity in Infinite Words, INTEGERS: Elect. J. Combin. Number Theory, 12 (2012), A21.
T. C. Brown and A. R. Freedman, Arithmetic progressions in lacunary sets, Rocky Mountain J. Math., 17 Number 3 (1987), 587-596. doi:10.1216/RMJ-1987-17-3-587
T. Brown, V. Jungic, and A. Poelstra, On 3-term double arithmetic progressions, INTEGERS: Elect. J. Combin. Number Theory, 14 (2014), A43.
A. R. Freedman, Sequences on sets of four numbers, INTEGERS: Elect. J. Combin. Number Theory, 16 (2016), A33.
J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
L. Halbeisen and N. Hungerbuhler, An application of van der Waerden's theorem in additive number theory, INTEGERS: Elect. J. Combin. Number Theory, 0 (2000), A7.
Peter Hegarty, Permutations avoiding arithmetic patterns, The Electronic Journal of Combinatorics, 11 (2004), #R39.
V. Jungic and J. Sahasrabudhe, Permutations destroying arithmetic structure, The Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.5.
G. Pirillo and S. Varricchio, On uniformly repetitive semigroups, Semigroup Forum, 49 (1994), 125-129.
A. F. Sidorenko, An infinite permutation without arithmetic progressions, Discrete Math., 69 (1988), 211.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers

Sequences used in definitions of this sequence: A000695, A059905, A059906.
Sequences with similar definitions: A057301, A126006, A126007, A126008, A163241, A163327.
A003986, A003987, A004198, A053985, A054240 are used to express relationships between sequence terms.

#include 
uint32_t a(uint32_t n) { return ((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >> 1); } /* Falk Hüffner, Jan 23 2022 */

a:= proc(n) option remember; `if`(n=0, 0,
      a(iquo(n, 4, 'r'))*4+[0, 2, 1, 3][r+1])
    end:
seq(a(n), n=0..69);  # Alois P. Heinz, Jan 25 2022

Table[FromDigits[IntegerDigits[n,4]/.{1->2,2->1},4],{n,0,70}] (* Harvey P. Dale, Aug 24 2017 *)

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); }; \\ Antti Karttunen, Apr 14 2018

Conjecture: a(2*n) = -2*a(n) + 5*n, a(2*n+1) = -2*a(n) + 5*n + 2. - Ralf Stephan, Oct 11 2003
a(4n+k) = 4a(n) + a(k), 0 <= k <= 3. - Jon Perry, Oct 06 2012
a(n) = A000695(A059906(n)) + 2*A000695(A059905(n)). - Antti Karttunen, Apr 14 2018
From Peter Munn, Dec 10 2019: (Start)
a(a(n)) = n.
a(A000695(m) + 2*A000695(n)) = 2*A000695(m) + A000695(n).
a(n OR k) = a(n) OR a(k), where OR is bitwise-or (A003986).
a(n XOR k) = a(n) XOR a(k), where XOR is bitwise exclusive-or (A003987).
a(n AND k) = a(n) AND a(k), where AND is bitwise-and (A004198).
a(A054240(n,k)) = A054240(a(n), a(k)). (End)
a(n) = 5*n/4 - 3*A053985(2*n)/8. - Alan Michael Gómez Calderón, May 20 2025

A054238 Array read by downward antidiagonals: T(i,j) = bits of binary expansion of i interleaved with that of j.

Original entry on oeis.org

0, 1, 2, 4, 3, 8, 5, 6, 9, 10, 16, 7, 12, 11, 32, 17, 18, 13, 14, 33, 34, 20, 19, 24, 15, 36, 35, 40, 21, 22, 25, 26, 37, 38, 41, 42, 64, 23, 28, 27, 48, 39, 44, 43, 128, 65, 66, 29, 30, 49, 50, 45, 46, 129, 130, 68, 67, 72, 31, 52, 51, 56, 47, 132, 131, 136, 69, 70, 73, 74

Offset: 0

Marc LeBrun, Feb 07 2000

Inverse of sequence A054239 considered as a permutation of the nonnegative integers.
Permutation of nonnegative integers. Can be used as natural alternate number casting for pairs/tables (vs. usual diagonalization).
This array is a Z-order curve in an N x N grid. - Max Barrentine, Sep 24 2015
Each row n of this array is the lexicographically earliest sequence such that no term occurs in a previous row, no three terms form an arithmetic progression, and the k-th term in the n-th row is equal to the k-th term in row 0 plus some constant (specifically, T(n,k) = T(0,k) + A062880(n)). - Max Barrentine, Jul 20 2016

			From _Philippe Deléham_, Oct 18 2011: (Start)
The array starts in row n=0 with columns k >= 0 as follows:
   0  1  4  5 16 17 20 21 ...
   2  3  6  7 18 19 22 23 ...
   8  9 12 13 24 25 28 29 ...
  10 11 14 15 26 27 30 31 ...
  32 33 36 37 48 49 52 53 ...
  34 35 38 39 50 51 54 55 ...
  40 41 44 45 56 57 60 61 ...
  42 43 46 47 58 59 62 63 ...
(End)
T(6,5)=57 because 1.1.0. (6) merged with .1.0.1 (5) is 111001 (57). [Corrected by _Georg Fischer_, Jan 21 2022]

Robert Israel, Table of n, a(n) for n = 0..10000
G. M. Morton, A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, IBM, 1966.
Wikipedia, Z-order Curve
Index entries for sequences that are permutations of the natural numbers

Cf. A000695 (row n=0), A062880 (column k=0), A001196 (main diagonal).
Cf. A059905, A059906, A346453 (by upwards antidiagonals).
See also A163357 and A163334 for other fractal curves in N x N grids.

N:= 4: # to get the first 2^(2N+1)+2^N terms
G:= 1/(1-y)/(1-x)*(add(2^(2*i+1)*x^(2^i)/(1+x^(2^i)),i=0..N) + add(2^(2*i)*y^(2^i)/(1+y^(2^i)),i=0..N)):
S:= mtaylor(G,[x=0,y=0],2^(N+1)):
seq(seq(coeff(coeff(S,x,i),y,m-i),i=0..m),m=0..2^(N+1)-1); # Robert Israel, Jul 21 2016

Table[Total@ Map[FromDigits[#, 2] &, Insert[#, 0, {-1, -1}] &@ Map[Riffle[IntegerDigits[#, 2], 0, 2] &, {n - k, k}]], {n, 0, 11}, {k, 0, n}] // Flatten (* Michael De Vlieger, Jul 21 2016 *)

T(n,k) = A000695(k) + 2*A000695(n). - Philippe Deléham, Oct 18 2011
From Robert Israel, Jul 21 2016: (Start)
G.f. of array: g(x,y) = (1/(1-x)*(1-y)) * Sum_{i>=0}
(2^(2*i+1)*x^(2^i)/(1+x^(2^i)) + 2^(2*i)*y^(2^i)/(1+y^(2^i))).
T(2*n+i,2*k+j) = 4*T(n,k) + 2*i+j for i,j in {0,1}. (End)

A059906 Index of second half of decomposition of integers into pairs based on A000695.

Original entry on oeis.org

0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 5, 5, 4, 4, 5, 5, 6

Offset: 0

Marc LeBrun, Feb 07 2001

One coordinate of a recursive non-self-intersecting walk on the square lattice Z^2.

			A000695(A059905(14)) + 2*A000695(a(14)) = A000695(2) + 2*A000695(3) = 4 + 2*5 = 14.
If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = b_1 + b_3*2 = 3. - _Vladimir Shevelev_, Nov 13 2008

Rémy Sigrist, Table of n, a(n) for n = 0..8192
G. M. Morton, A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, IBM, 1966, with a(n) being section 5.1 step (b).
Index entries for sequences related to coordinates of 2D curves

Cf. A000695, A057300, A059905.

a[n_] := Module[{P}, (P = Partition[IntegerDigits[n, 2]//Reverse, 2][[All, 2]]).(2^(Range[Length[P]]-1))]; Array[a, 105, 0] (* Jean-François Alcover, Apr 24 2019 *)

A059906(n) = { my(t=1,s=0); while(n>0, s += ((n%4)>=2)*t; n \= 4; t *= 2); (s); }; \\ Antti Karttunen, Apr 14 2018

def a(n):
    x=[int(t) for t in list(bin(n)[2:])[::-1]]
    return sum(x[2*i + 1]*2**i for i in range(int(len(x)//2)))
print([a(n) for n in range(105)]) # Indranil Ghosh, Jun 25 2017

def A059906(n): return 0 if n < 2 else int(bin(n)[-2:1:-2][::-1],2) # Chai Wah Wu, Jun 30 2022

n = A000695(A059905(n)) + 2*A000695(a(n))
To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_(2j+1)*2^j. - Vladimir Shevelev, Nov 13 2008
a(n) = Sum_{k>=0} A030308(n,k)*b(k) with b(0)=0 and b(k)=A077957(k-1) for k>0. - Philippe Deléham, Oct 18 2011
Conjecture: a(n) = n - (1/2)*Sum_{k=1..n} (sqrt(2)^A007814(k) + (-sqrt(2))^A007814(k)) = -Sum_{k=1..n} (-1)^k * 2^floor(k/2) * floor(n/2^k). - Velin Yanev, Dec 01 2016

A059253 Hilbert's Hamiltonian walk on N X N projected onto y axis: m'(3).

Original entry on oeis.org

0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 6, 6, 7, 7, 6, 5, 5, 4, 4, 4, 4, 5, 5, 6, 7, 7, 6, 6, 7, 7, 6, 5, 5, 4, 4, 3, 2, 2, 3, 3, 3, 2, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 3, 3, 2, 2, 3, 3, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 3, 4, 5, 5, 4, 4, 4

Offset: 0

Claude Lenormand (claude.lenormand(AT)free.fr), Jan 23 2001

nonn

This is the Y-coordinate of the n-th term in the type I Hilbert's Hamiltonian walk A163359 and the X-coordinate of its transpose A163357.

Antti Karttunen, Table of n, a(n) for n = 0..65535
J. Shallit, Hilbert's spacefilling curve described by automatic, regular, and synchronized sequences, arXiv:2106.01062 [cs.FL], June 2 2021.
Index entries for sequences related to coordinates of 2D curves

See also the y-projection, m(3), A059252 as well as A163538, A163540, A163542, A059261, A059285, A163547 and A163528.

C
```
See A059252.
```

Initially [m(0) = 0, m'(0) = 0]; recursion: m(2n + 1) = m(2n).m'(2n).f(m'(2n), 2n).c(m(2n), 2n + 1); m'(2n + 1) = m'(2n).f(m(2n), 2n).f(m(2n), 2n).mir(m'(2n)); m(2n) = m(2n - 1).f(m'(2n - 1), 2n - 1).f(m'(2n - 1), 2n - 1).mir(m(2n - 1)); m'(2n) = m'(2n - 1).m(2n - 1).f(m(2n - 1), 2n - 1).c(m'(2n - 1), 2n); where f(m, n) is the alphabetic morphism i := i + 2^n [example: f(0 0 1 1 2 3 3 2 2 3 3 2 1 1 0 0, 2) = 4 4 5 5 6 7 7 6 6 7 7 6 5 5 4 4]; c(m, n) is the complementation to 2^n - 1 alphabetic morphism [example: c(0 0 1 1 2 3 3 2 2 3 3 2 1 1 0 0, 3) = 7 7 6 6 5 4 4 5 5 4 4 5 6 6 7 7]; and mir(m) is the mirror operator [example: mir(0 1 1 0 0 0 1 1 2 2 3 3 3 2 2 3) = 3 2 2 3 3 3 2 2 1 1 0 0 0 1 1 0].

a(n) = A025581(A163358(n)) = A002262(A163360(n)) = A059905(A163356(n)).

Extended by Antti Karttunen, Aug 01 2009

A163356 Inverse permutation to A163355, related to Hilbert's curve in N x N grid.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 29 2009

nonn

Inverse: A163355.
Second and third "powers": A163906, A163916. See also A059252-A059253.
In range [A000302(n-1)..A024036(n)] of this permutation, the number of cycles is given by A163910, number of fixed points seems to be given by A147600(n-1) (fixed points themselves: A163901). Max. cycle sizes is given by A163911 and LCM's of all cycle sizes by A163912.
Cf. A059252, A059253, A059905, A059906.
Cf. also A302844, A302846, A302781.

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)))); \\ Antti Karttunen, Apr 14 2018

a(0) = 0, and provided that d=1, 2 or 3, then a((d*(4^i))+r) = (((2+(i mod 2))^d mod 5)-1) * [either A024036(i) - a(r), if d is 3, and A057300(a(r)) in other cases].
From Antti Karttunen, Apr 14 2018: (Start)
A059905(a(n)) = A059253(n).
A059906(a(n)) = A059252(n).
a(n) = A000695(A059253(n)) + 2*A000695(A059252(n)).
(End)

Links to further derived sequences and a nicer Scheme function & formula added by Antti Karttunen, Sep 21 2009

A163241 Simple self-inverse permutation: Write n in base 4, then replace each digit '2' with '3' and vice versa, then convert back to decimal.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 29 2009

			43 in quaternary base (A007090) is written as '223' (2*16 + 2*4 + 3), which is then mapped to '332' = 3*16 + 3*4 + 2 = 62, thus a(43) = 62, and likewise a(62) = 43.

Cf. A048647, A007090, A003987.

uint32_t a(uint32_t n) { return n ^ ((n >> 1) & 0x55555555); } // Falk Hüffner, Jan 22 2022

a:= proc(n) option remember; `if`(n=0, 0,
      a(iquo(n, 4, 'r'))*4+[0, 1, 3, 2][r+1])
    end:
seq(a(n), n=0..71);  # Alois P. Heinz, Jan 25 2022

Table[FromDigits[IntegerDigits[n,4]/.{2->a,3->b}/.{a->3,b->2},4],{n,0,75}] (* Harvey P. Dale, Nov 29 2011 *)

f(d) = if (d==2, 4, if (x==d, 2, d));
a(n) = fromdigits(apply(f, digits(n, 4)), 4); \\ Michel Marcus, Jun 28 2017

def a000695(n):
    n=bin(n)[2:]
    x=len(n)
    return sum([int(n[i])*4**(x - 1 - i) for i in range(x)])
def a059905(n): return sum([(n>>2*i&1)<Indranil Ghosh, Jun 26 2017

Scheme

(define (A163241 n) (+ (A000695 (A003987bi (A059905 n) (A059906 n))) (* 2 (A000695 (A059906 n)))))

Formula

a(n) = A000695(A003987bi(A059905(n),A059906(n))) + 2*A000695(A059906(n)), where A003987bi is binary XOR.

Extensions

Edited by Charles R Greathouse IV, Nov 01 2009

A064706 Square of permutation defined by A003188.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Oct 13 2001

Inverse of sequence A064707 considered as a permutation of the nonnegative integers.

Not the same as A100282: a(n) = A100282(n) = A100280(A100280(n)) only for n < 64. - Reinhard Zumkeller, Nov 11 2004

Cf. A064707 (inverse), A165211 (mod 2).
Cf. A003188, A000695, A059905, A059906.
Cf. also A054238, A163233, A302846.

A = 1; for i = 1:7 B = A(end:-1:1); A = [A (B + length(A))]; end A(A) - 1

Array[BitXor[#, Floor[#/4]] &, 72, 0] (* Michael De Vlieger, Apr 14 2018 *)

PARI
```
a(n)=bitxor(n,n\4)
```

{ for (n=0, 1000, write("b064706.txt", n, " ", bitxor(n, n\4)) ) } \\ Harry J. Smith, Sep 22 2009

def A064706(n): return n^ n>>2 # Chai Wah Wu, Jun 29 2022

maxn <- 63 # by choice
b <- c(1,0,0)
for(n in 4:maxn) b[n] <- b[n-1] - b[n-2] + b[n-3]
# c(1,b) is A133872
a <- 1
for(n in 1:maxn) {
a[2*n  ] <- 2*a[n] + 1 - b[n]
a[2*n+1] <- 2*a[n] +     b[n]
}
(a <- c(0,a))
# Yosu Yurramendi, Oct 25 2020

a(n) = A003188(A003188(n)).
a(n) = n XOR floor(n/4), where XOR is binary exclusive OR. - Paul D. Hanna, Oct 25 2004
a(n) = A233280(A180201(n)), n > 0. - Yosu Yurramendi, Apr 05 2017
a(n) = A000695(A003188(A059905(n))) + 2*A000695(A003188(A059906(n))). - Antti Karttunen, Apr 14 2018

More terms from David Wasserman, Aug 02 2002

cp's OEIS Frontend

A072661 Composition of the A059905 and A048679, i.e., a(n) = A059905(A048679(n)).

Views

Author

Keywords

Crossrefs

A327857 a(n) = A091255(1+A059905(n), 1+A059906(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Python

Sage

Formula

A057300 Binary counter with odd/even bit positions swapped; base-4 counter with 1's replaced by 2's and vice versa.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Maple

Mathematica

PARI

Formula

A054238 Array read by downward antidiagonals: T(i,j) = bits of binary expansion of i interleaved with that of j.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059906 Index of second half of decomposition of integers into pairs based on A000695.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula