A006042 The nim-square of n. (Formerly M2251)

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

Offset

0,3

Comments

This is a permutation of the natural numbers; A160679 is the inverse permutation. - Jianing Song, Aug 10 2022

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

R. J. Mathar, Table of n, a(n) for n = 0..1000

G. P. Michon, Discussion of Conway's On2 [From John W. Layman, Nov 05 2010]

Index entries for sequences related to Nim-multiplication

Index entries for sequences that are permutations of the natural numbers

Formula

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

From Jianing Song, Aug 10 2022: (Start)

If n = Sum_j 2^e(j), then a(n) is the XOR of A006017(e(j))'s. Proof: let N+ = XOR and N* denote the nim addition and the nim multiplication, then n N* n = (Sum_j 2^e(j)) N* (Sum_j 2^e(j)) = (Nim-sum_j 2^e(j)) N* (Nim-sum_j 2^e(j)) = (Nim-sum_j (2^e(j) N* 2^e(j))) N+ (Nim-sum_{i<j} ((2^e(i) N* 2^e(j)) N+ (2^e(j) N* 2^e(i)))) = (Nim-sum_j (2^e(j) N* 2^e(j))) N+ (Nim-sum_{i<j} 0) = Nim-sum_j (2^e(j) N* 2^e(j)).

For example, for n = 11 = 2^0 + 2^1 + 2^3, a(11) = A006017(0) XOR A006017(1) XOR A006017(3) = 1 XOR 3 XOR 13 = 15.

More generally, if n = Sum_j 2^e(j), k is a power of 2, then the nim k-th power of n is the XOR of (nim k-th power of 2^e(j))'s. (End)

Maple

read("transforms") ;
# insert source of nimprodP2() and A051775() from the b-file at A051776 here...
A006042 := proc(n)
     A051775(n, n) ;
end proc:
L := [seq( A006042(n), n=1..1000) ]; # R. J. Mathar, May 28 2011

Crossrefs

Diagonal of A051775. Without 0, diagonal of A051776.

Column 2 of array in A335162.

Other nim k-th powers: A051917 (k=-1), A160679 (k=1/2), A335170 (k=3), A335535 (k=4), A335171 (k=5), A335172 (k=6), A335173 (k=7), A335536 (k=8).

Cf. A212200, A006017.

Sequence in context: A360982 A268831 A154435 * A100280 A268827 A092745

Adjacent sequences: A006039 A006040 A006041 * A006043 A006044 A006045

Keyword

nonn,nice,easy,look

Author

N. J. A. Sloane

Extensions

a(1)-a(49) confirmed, a(50)-a(71) added by John W. Layman, Nov 05 2010

a(0) prepended by Jianing Song, Aug 10 2022

Status

approved