This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/Nimber
http://en.wikipedia.org/wiki/Nimber
(Start R. J. Mathar) Note on an algorithm, R. J. Mathar, May 29 2011:
Let N* denote the Nim-multiplication and N+ the Nim-summation (A003987) of two numbers, and * and + the usual multiplication and summation.
To compute n N* m, write n and m separately as Nim-sums with the aid of the binary representation of n= n0 +n1*2 +n2*4 +n3*8 +n4*16.. and m= m0 +m1*2 +m2*4 +m3*8 +m4*16... . Because Nim-summation is the same as the binary XOR-function, the + may then be replaced by N+ in both sums:
n = Nim-sum_i 2^a(i) and m = Nim-sum_j 2^b(j) with two integer sequences a(i) and b(j).
Because N+ and N* are the operations in a field, N+ and N* are distributive, which is used to write the product over the sums as a double-Nim-sum over Nim-products:
n N* m = Nim-sum_{i,j} 2^a(i) N* 2^b(j) .
What remains is to compute the Nim-products of powers of 2.
Splitting a(i) and b(j) separately into (ordinary) products of Fermat numbers A001146 (i.e., writing a(i) and b(j) in binary), and noting that the ordinary product of distinct Fermat numbers equals the Nim-product of distinct Fermat numbers,
2^a(i) N* 2^b(j) = 2^(2^A0) N* 2^(2^A1) N* ... N* 2^(2^B0) N* 2^(2^B1) N* ... for two binary integer sequences A and B.
This finite product is regrouped by pairing the cases for the same bit in the A-sequence and in the B-sequence. If the bit is set in both sequences, use that the Nim-square of a Fermat number is 3/2 times (ordinary multiple of) that Fermat number; if the bit is set only in one of the two sequences, use (again) that the Nim-product of distinct Fermat numbers is the ordinary product.
Due to the potential presence of the Nim-squares, this leaves in general a Nim-product which is treated by recursion.
This algorithm is implemented in the Maple program in the b-file. nimprodP2() calculates the Nim-product of two powers of 2. (End R. J. Mathar)
Below I rewrote Mathar's Maple code http://oeis.org/A051775/b051775.txt to make it independet of additional librarys. Some small improvements and speed-ups were included; any bugs are due to me.
nimsum := proc(a::nonnegint,b::nonnegint)
option remember; local i;
# Take advantage of symmetry plus memoization.
if a > b then RETURN(nimsum(b,a)) fi;
zip((x,y)->`if`(x<>y,1,0),convert(a,base,2),convert(b,base,2),0);
add(`if`(%[i]=1,2^(i-1),0),i=1..nops(%)) end:
nimprod := proc(n::nonnegint,m::nonnegint)
option remember; local a,nbin,mbin,nlbin,mlbin,np2,i,j;
np2 := proc(a::nonnegint,b::nonnegint)
option remember; local abin,bbin,Z,c,i;
abin := convert(a,base,2); bbin := convert(b,base,2);
Z := zip((x,y)->`if`(x+y=2,1,0),abin,bbin,0);
if add(i,i=Z) = 0 then c := 2^(a+b)
else
Z := zip((x,y)->`if`(x*y=1,1,0),abin,bbin,0);
c := 2^nimsum(a,b);
for i from 1 to nops(Z) do
if Z[i] = 1 then c := nimprod(c,3*2^(2^(i-1)-1)) fi od
fi;
c end:
# Take advantage of symmetry plus memoization.
if n > m then RETURN(nimprod(m,n)) fi;
if n*m = 0 then a := 0
elif n = 1 or m = 1 then a := n*m
else
nbin := convert(n,base,2);
mbin := convert(m,base,2);
a := 0; i:=0;
for nlbin in nbin do
if nlbin > 0 then j:=0;
for mlbin in mbin do
if mlbin > 0 then a := nimsum(a,np2(i,j)) fi;
j := j+1;
od
fi; i := i+1;
od
fi;
a end:
Used in some sequences:
G := [0,1,2,3,4,5,6,7]:
for g in G do seq(nimsum(g,h),h = G) od;
0, 1, 2, 3, 4, 5, 6, 7
1, 0, 3, 2, 5, 4, 7, 6
2, 3, 0, 1, 6, 7, 4, 5
3, 2, 1, 0, 7, 6, 5, 4
4, 5, 6, 7, 0, 1, 2, 3
5, 4, 7, 6, 1, 0, 3, 2
6, 7, 4, 5, 2, 3, 0, 1
7, 6, 5, 4, 3, 2, 1, 0
G := [0,1,2,3,4,5,6,7]:
for g in G do seq(nimprod(g,h),h = G) od;
0, 0, 0, 0, 0, 0, 0, 0
0, 1, 2, 3, 4, 5, 6, 7
0, 2, 3, 1, 8, 10, 11, 9
0, 3, 1, 2, 12, 15, 13, 14
0, 4, 8, 12, 6, 2, 14, 10
0, 5, 10, 15, 2, 7, 8, 13
0, 6, 11, 13, 14, 8, 5, 3
0, 7, 9, 14, 10, 13, 3, 4
A003987_triangle := (n,k) -> nimsum(n-k,k):
for n from 0 to 11 do
seq(A003987_triangle(n,k),k = 0..n) od;
0
1, 1
2, 0, 2
3, 3, 3, 3
4, 2, 0, 2, 4
5, 5, 1, 1, 5, 5
6, 4, 6, 0, 6, 4, 6
7, 7, 7, 7, 7, 7, 7, 7
8, 6, 4, 6, 0, 6, 4, 6, 8
9, 9, 5, 5, 1, 1, 5, 5, 9, 9
10, 8, 10, 4, 2, 0, 2, 4, 10, 8, 10
11, 11, 11, 11, 3, 3, 3, 3, 11, 11, 11, 11
A051775_triangle := (n,k) -> nimprod(n-k,k):
for n from 0 to 11 do
seq(A051775_triangle(n,k),k = 0..n) od;
0
0, 0
0, 1, 0
0, 2, 2, 0
0, 3, 3, 3, 0
0, 4, 1, 1, 4, 0
0, 5, 8, 2, 8, 5, 0
0, 6, 10, 12, 12, 10, 6, 0
0, 7, 11, 15, 6, 15, 11, 7, 0
0, 8, 9, 13, 2, 2, 13, 9, 8, 0
0, 9, 12, 14, 14, 7, 14, 14, 12, 9, 0
0, 10, 14, 4, 10, 8, 8, 10, 4, 14, 10, 0
A051776_triangle := (n,k) -> nimprod(n-k,k):
for n from 1 to 11 do
seq(A051776_triangle(n,k),k = 1..n-1) od;
1
2, 2
3, 3, 3
4, 1, 1, 4
5, 8, 2, 8, 5
6, 10, 12, 12, 10, 6
7, 11, 15, 6, 15, 11, 7
8, 9, 13, 2, 2, 13, 9, 8
9, 12, 14, 14, 7, 14, 14, 12, 9
10, 14, 4, 10, 8, 8, 10, 4, 14, 10
A051911_triangle := (n,k) -> nimprod(n,k):
for n from 1 to 11 do
seq(A051911_triangle(n,k),k = 1..n) od;
1
2, 3
3, 1, 2
4, 8, 12, 6
5, 10, 15, 2, 7
6, 11, 13, 14, 8, 5
7, 9, 14, 10, 13, 3, 4
8, 12, 4, 11, 3, 7, 15, 13
9, 14, 7, 15, 6, 1, 8, 5, 12
10, 15, 5, 3, 9, 12, 6, 1, 11, 14
11, 13, 6, 7, 12, 10, 1, 9, 2, 4, 15
A006042 := n -> nimprod(n,n):
seq(A006042(i),i=1..16);
1, 3, 2, 6, 7, 5, 4, 13, 12, 14, 15, 11, 10,
A058734 := n -> nimprod(n,n+1):
seq(A058734(i),i=0..16);
0, 2, 1, 12, 2, 8, 3, 15, 5, 11, 4, 14, 7, 1,
A006015 := n -> nimprod(2,n):
seq(A006015(i),i=0..16);
0, 2, 3, 1, 8, 10, 11, 9, 12, 14, 15, 13, 4,
A038712 := n -> nimsum(n,n+1):
seq(A038712(i),i=0..16);
1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1,
# Input n is the number of rows.
A135521_list := proc(n) local i,k,NimSum;
NimSum := proc(a,b) option remember; local i;
zip((x,y)->`if`(x<>y,1,0),convert(a,base,2),convert(b,base,2),0);
add(`if`(%[i]=1,2^(i-1),0),i=1..nops(%)) end:
seq(seq(NimSum(i,i+1),i=0..2^k-1),k=0..n) end:
A135521_list(5);
1, 1, 3, 1, 3, 1, 7, 1, 3, 1, 7, 1, 3, 1, 15,
# Mathematica: A135521_list
# Flatten[Table[BitXor[i,i+1],{k,0,10},{i,0,-1+2^k}]]
