

A051775


Table T(n,m) = Nimproduct of n and m, read by antidiagonals, for n >= 0, m >= 0.


29



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, 0, 11, 15, 7, 11
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,8


COMMENTS

Let N* denote the Nimproduct and N+ the Nimsum (A003987) of two numbers, and let * and + denote the usual multiplication and addition.
To compute n N* m, write n and m separately as Nimsums 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 Nimsummation is the same as the binary XORfunction, the + may then be replaced by N+ in both sums:
n = Nimsum_i 2^a(i) and m = Nimsum_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 doubleNimsum over Nimproducts:
n N* m = Nimsum_{i,j} 2^a(i) N* 2^b(j) .
What remains is to compute the Nimproducts 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 Nimproduct 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 Asequence and in the Bsequence. If the bit is set in both sequences, use that the Nimsquare 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 Nimproduct of distinct Fermat numbers is the ordinary product.
Due to the potential presence of the Nimsquares, this leaves in general a Nimproduct which is treated by recursion.
This algorithm is implemented in the Maple program in the bfile. nimprodP2() calculates the Nimproduct of two powers of 2. (End)


REFERENCES

J. H. Conway, On Numbers and Games, Academic Press, p. 52.


LINKS



EXAMPLE

The table begins:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 ...
0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 ...
0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 ...
0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 ...
(...)


MAPLE

We continue from A003987: to compute a Nimmultiplication table using (a) an addition table AT := array(0..NA, 0..NA) and (b) a nimsum procedure for larger values; MT := array(0..N, 0..N); for a from 0 to N do MT[a, 0] := 0; MT[0, a] := 0; MT[a, 1] := a; MT[1, a] := a; od: for a from 2 to N do for b from a to N do t1 := {}; for i from 0 to a1 do for j from 0 to b1 do u1 := MT[i, b]; u2 := MT[a, j];
if u1<=NA and u2<=NA then u12 := AT[u1, u2]; else u12 := nimsum(u1, u2); fi; u3 := MT[i, j]; if u12<=NA and u3<=NA then u4 := AT[u12, u3]; else u4 := nimsum(u12, u3); fi; t1 := { op(t1), u4}; #t1 := { op(t1), AT[ AT[ MT[i, b], MT[a, j] ], MT[i, j] ] }; od; od;
t2 := sort(convert(t1, list)); j := nops(t2); for i from 1 to nops(t2) do if t2[i] <> i1 then j := i1; break; fi; od; MT[a, b] := j; MT[b, a] := j; od; od;


PROG

(PARI) NP_table=Map(); NP(x, y)={ if(x<2  y<2, x*y, mapisdefined(NP_table, if(y>x, [x, y]=[y, x], [x, y])), mapget(NP_table, [x, y]), x==3, y1, x==2, 3, my(F=4); until(!F *= F, if(x<2*F, F=if(x>F, bitxor(NP(F, y), NP(xF, y)), y<x, x*y, x\2*3); break); my(t = 2*F); until(F*F <= t *= 2, if(x==t, if(y<F, F=NP(NP(y, t\F), F); break(2)); my(i = F); until(t <= i *= 2, if(y<2*i, F=if(y>i, bitxor(NP(t, i), NP(t, yi)), NP(F\2*3, NP(t/F, i/F))); break(3))); if(y==t, F=NP(F\2*3, NP(t/F, t/F)); break(2))); if(x<2*t, F=bitxor(NP(t, y), NP(xt, y)); break(2)))); mapput(NP_table, [x, y], F); F)} \\ M. F. Hasler, Jan 18 2021
A051775(n, m="")={if(m!="", NP(n, m), NP((1+m=sqrtint(8*n+1)\/2)*m/2n1, nm*(m1)/2))} \\ Then A051775(n) = a(n) [flattened sequence, cf. A025581 & A002262], A051775(n, m) = T(n, m): for example, {matrix(6, 15, m, n, A051775(m, n))}  M. F. Hasler, Jan 22 2021


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



