

A160679


Square root of n under Nim (or Conway) multiplication


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Because Conway's field On2 (endowed with Nimmultiplication and [bitwise] Nimaddition) has characteristic 2, the Nimsquare 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 Nimsquare have the same bit length). Therefore the Nim squareroot function is also a field homomorphism (the squareroot of a Nimsum is the Nimsum of the square roots) which can be defined as the inverse permutation of A006042 (as such, it preserves bitlength too).


LINKS

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


FORMULA

Letting NIM (= XOR) TIM and RIM denote respectively the sum, product and square root in Conway's Nimfield On2, we see that the bitlength 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)


EXAMPLE

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


CROSSREFS

A006042 (Nimsquares). A051917 (Nimreciprocals).
Sequence in context: A265345 A154448 A099896 * A233276 A304083 A276441
Adjacent sequences: A160676 A160677 A160678 * A160680 A160681 A160682


KEYWORD

easy,nonn


AUTHOR

Gerard P. Michon, Jun 25 2009


STATUS

approved



