A160679 Square root of n under Nim (or Conway) multiplication.

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

Offset: 0

Author

Gerard P. Michon, Jun 25 2009

Keywords

• easy
• nonn
• changed

Comments

Because Conway's field On2 (endowed with Nim-multiplication and [bitwise] Nim-addition) has characteristic 2, the Nim-square function (A006042) is an injective field homomorphism (i.e., the square of a sum is the sum of the squares). Thus the square function is a bijection within any finite additive subgroup of On2 (which is a fancy way to say that an integer and its Nim-square have the same bit length). Therefore the Nim square-root function is also a field homomorphism (the square-root of a Nim-sum is the Nim-sum of the square roots) which can be defined as the inverse permutation of A006042 (as such, it preserves bit-length too).

Examples

			a(2) = 3 because TIM(3,3) = 2
More generally, a(x)=y because A006042(y)=x.
		

Links

• Paul Tek, Table of n, a(n) for n = 0..576
• G. P. Michon, Nim-multiplication in Conway's algebraically complete field On2
• Index entries for sequences that are permutations of the natural numbers
• Index entries for sequences related to Nim-multiplication
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A006042 (Nim-squares). A051917 (Nim-reciprocals), A335162, A212200.

Formula

Letting NIM (= XOR) TIM and RIM denote respectively the sum, product and square root in Conway's Nim-field On2, we see that the bit-length of NIM(x,TIM(x,x)) is less than that of the positive integer x. This remark turns the following relations into an effective recursive definition of a(n) = RIM(n) which uses the fact that RIM is a field homomorphism in On2:

a(0) = 0

a(n) = NIM(n, a(NIM(n, a(n, TIM(n,n)) )

Note: TIM(n,n) = A006042(n)

From Jianing Song, Aug 10 2022: (Start)

For 0 <= n <= 2^2^k-1, a(n) = A335162(n, 2^(2^k-1)). This is because {0,1,...,2^2^k-1} together with the nim operations makes a field isomorphic to GF(2^2^k).

Also for n > 0, a(n) = A335162(n, (A212200(n)+1)/2). (End)