A006015 Nim product 2*n. (Formerly M0412)

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

Offset

0,2

Comments

From Jianing Song, Aug 10 2022: (Start)

Write n in quaternary (base 4), then replace each 1,2,3 by 2,3,1.

This is a permutation of the natural numbers; A004468 is the inverse permutation (since the nim product of 2 and 3 is 1). (End)

References

J. H. Conway, On Numbers and Games. Academic Press, NY, 1976, pp. 51-53.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..16383 (first 1001 terms from R. J. Mathar)

Index entries for sequences related to Nim-multiplication

Index entries for sequences that are permutations of the natural numbers

Formula

From Jianing Song, Aug 10 2022: (Start)

a(n) = A051775(2,n).

a(n) = 2*n if n has only digits 0 or 1 in quaternary (n is in A000695). Otherwise, a(n) < 2*n.

a(n) = n/3 if n has only digits 0 or 3 in quaternary (n is in A001196). Otherwise, a(n) > n/3.

a(n) = 3*n/2 if and only if n has only digits 0 or 2 in quaternary (n is in A062880). Proof: let n = Sum_i d_i*4^i, d(i) = 0,1,2,3. Write A = Sum_{d_i=1} 4^i, B = Sum_{d_i=3} 4^i, then a(n) = 3*n/2 if and only if 2*A + B = 3/2*(A + 3*B), or A = 7*B. If B != 0, then B is of the form (4*s+1)*4^t, but 7*B is not of this form. So the only possible case is A = B = 0, namely n has only digits 0 or 2. (End)

Maple

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

Mathematica

a[n_] := a[n] = If[n == 0, 0, {q, r} = QuotientRemainder[n, 4]; a[q]*4 + {0, 2, 3, 1}[[r + 1]]];
Table[a[n], {n, 0, 70}] (* Jean-François Alcover, May 20 2022, after Alois P. Heinz *)

Prog

(PARI) a(n) = my(v=digits(n, 4), w=[0, 2, 3, 1]); for(i=1, #v, v[i] = w[v[i]+1]); fromdigits(v, 4) \\ Jianing Song, Aug 10 2022
(Python)
def a(n, D=[0, 2, 3, 1]):
    r, k = 0, 0
    while n>0: r+=D[n%4]*4**k; n//=4; k+=1
    return r
# Onur Ozkan, Mar 07 2023

Crossrefs

Row 2 of array in A051775.

Cf. A004468-A004480, A000695, A062880, A001196.

Sequence in context: A101281 A106033 A121634 * A301332 A110292 A138672

Adjacent sequences: A006012 A006013 A006014 * A006016 A006017 A006018

Keyword

nonn,easy,look

Author

N. J. A. Sloane.

Extensions

More terms from Erich Friedman.

Status

approved