# Nim Multiplication

### Background

If you do much code golfing, you're likely aware of the bitwise XOR operation. Given two integers, it gives another integer with 1s in the bits where the two inputs differ. So, for example, 1010 XOR 0011 = 1001.

It turns out to be very useful in game theory, where it's better known as the "nim sum". If you have the sum of two games (that is, you're making moves in one game at a time), the value of the position is the nim sum of the values of the positions in each individual game.

But we can take this a step further. With nim addition and an appropriate definition of nim multiplication, we can form a field from the nonnegative integers. So the challenge is to golf nim multiplication.

### Definition

Nim multiplication obeys the following rules:
The nim product of a Fermat 2-power n = (2^(2^k)) with any smaller number is the ordinary product.
The nim product of a Fermat 2-power n with itself is 3n/2.
Nim multiplication distributes over nim addition.
Nim multiplication is commutative and associative (as is nim addition).
The multiplicative identity is 1 (and the additive identity is 0).

Any nonnegative integer can be written as the nim sum of distinct powers of two, and any power of two can be written as the product of distinct Fermat numbers, so this is sufficient to define nim multiplication for all nonnegative integers.

### Example

That was all pretty abstract, so let's work through an example. I'll use + to denote nim addition (XOR) and * for nim multiplication.

6 * 13
= (4 + 2) * (8 + 4 + 1)
= (4 + 2) * ((4 * 2) + 4 + 1)
= (4 * 4 * 2) + (4 * 2 * 2) + (4 * 4) + (4 * 2) + (4 * 1) + (2 * 1)
= (6 * 2) + (4 * 3) + 6 + 8 + 4 + 2
= ((4 + 2) * 2) + 12 + 6 + 8 + 4 + 2
= (4 * 2) + (2 * 2) + 12 + 6 + 8 + 4 + 2
= 8 + 3 + 12 + 6 + 8 + 4 + 2
= 15


4, 4 -> 6
4, 3 -> 12
4, 7 -> 10
2, 4 -> 8
2, 3 -> 1
1, 42 -> 42


### Challenge

Write a program or function which, given two nonnegative integers in any convenient form, computes their nim product.

This is , so shortest submission wins.

• In case it's not clear to readers, this is different from XOR (carryless) multiplication, and so not a duplicate of that challenge.
– xnor
May 7 '18 at 15:21
• Nim multiplication tables in OEIS: A051775, A051776, A051910, A051911. May 7 '18 at 15:26
• Also note that there are no intuitive way to understand nimber multiplication (according to that post). May 7 '18 at 16:24
• Fermat numbers are of the form 2^(2^k)+1, so what you're calling a Fermat number is actually one less. May 7 '18 at 20:11
• @KellyLowder Yes, it's really a Fermat 2-power.
– user48543
May 7 '18 at 20:14

# Nim, 120 bytes

proc f(a,b:int):int=
var s={0..a*b}
for i in 0..<a*b:s=s-{f(i%%a,i/%a)xor f(a,i/%a)xor f(i%%a,b)}
for i in s:return i


Try it online!

OK, this might be crazy, but somebody had to do Nim multiplication in Nim...

This is standard algorithm from Wikipedia. The problem is that I don't know the language, so had to learn the basics on the fly. In particular, I was surprised that -= and min didn't work for sets, and the best way I managed to find for extracting the minimum was to use the iterator and return the first value. Hopefully, Nim experts will help me to improve this.

• I was wondering when someone would try this.
– user48543
May 8 '18 at 13:39

# Python 2, 85 bytes

f=lambda x,y:min(set(range(x*y+1))-{f(i%x,i/x)^f(x,i/x)^f(i%x,y)for i in range(x*y)})


Try it online!

Slow as heck. Computes mex({α′ β ⊕ α β′ ⊕ α' β′ : α′ < α, β′ < β}) recursively.

# Jelly, 16 bytes

p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ  Uses the recursive formula xy = mex({ay ⊕ xb ⊕ ab : a < x, b < y}) for nimber multiplication. Try it online! ### How it works p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ  Main link. Left argument: x. Right argument: y.

p                 Cartesian product; yield the array of all pairs [a, b] such that
0 < a ≤ x and 0 < b ≤ y.
’                Decrement, changing the conditions to 0 ≤ a < x and 0 ≤ b < y.
ṭ       Tack; yield [y, x].
ʋ€        Combine the four links to the left into a dyadic chain. Call it
with right argument [y, x] and each of the [a, b] as left one.
ß/                  Reduce [a, b] by the main link, computing the product ab.
ß"               Zip [a, b] with [y, x] using the main link, computing the
array of products [ay, xb].
;                 Concatenate, yielding [ab, ay, xb].
^/             Reduce by bitwise XOR, yielding ab ⊕ ay ⊕ xb.
All that's left is to compute the minimum excluded (mex) non-
negative integer.
\$    Combine the two links to the left into a monadic chain.
‘          Increment the XOR sums.
ḟ         Filterfalse; remove all incremented sums that appear in the
original sums.
Ṃ  Take the minimum if the resulting array is non-empty or yield 0.
If x = 0 or y = 0, the array of sums is empty and Ṃ yields 0.
If x > 0 and y > 0, since 0 is among the sums, this finds the
smallest non-sum n+1 such that n ≥ 0 is a sum.
In either case, Ṃ yields xy.


# CGSuite, 5239 22 bytes

(a,b)->a.NimProduct(b)


Didn't realize it has this builtin, and anonymous "procedures".

Original version, 36 bytes:

(a,b)->*a.ConwayProduct(*b).NimValue


Or 25 bytes if the input/output could be nimbers:

(a,b)->a.ConwayProduct(b)


Well, I hoped *a**b/a*b to work, but it doesn't.

• Definitely the right tool for the job.
– user48543
May 8 '18 at 16:32

# Pyth, 21 bytes

Mf-TsmmxxgkdgkHgGdGH0


Demonstration

Uses the minimum excluded element formulation of nim multiplication, as given here.

Two nested maps are used to iterate over all smaller values (mm ... GH), then the results are flattened (s). The clever part comes with f-T ... 0, where we iterate over integers upward from 0 to find the first one not contained in the set mentioned above. By doing it this way, we don't need to calculate an iteration upper bound, saving a few bytes.

In the end, the function g computes the nim product.

## JavaScript (ES6), 142 128 bytes

f=(x,y,z=Math.log2,v=x&-x,t=z(x),u=z(y),s=t&u,r=s&-s)=>x<2|y<2?x*y:x>v?f(v,y)^f(x^v,y):y&y-1?f(y,x):r?f(f(x>>r,y>>r),3<<r-1):x*y
<div oninput=o.textContent=f(x.value,y.value)><input id=x><input id=y><pre id=o>

The first step is to split both x and y into an XOR of powers of 2, take their pairwise nim products, and then XOR the results (because nim product distributes over XOR). Once we have recursed to the case of x and y both powers of 2, we note that Fermat powers multiply with each other using ordinary arithmetic, so we can therefore factorise x and y into Fermat powers. If x and y don't share a Fermat power we can reverse the process and simply return x * y. However if they share a Fermat power, then we divide both x and y by that power, calculate the nim product, then take the nim product with the nim square of that Fermat power. Ungolfed:

function nimprod(x, y) {
if (x < 2 || y < 2) return x * y;
var v = x & -x;
if (x > v) return nimprod(v, y) ^ nimprod(x ^ v, y); // nimprod distributes over ^
if (y & (y - 1)) return nimprod(y, x); // x is a power of 2 but y is not
var t = Math.log2(x);
var u = Math.log2(y);
var s = t & u;
if (!s) return x * y; // x and y do not share a Fermat power
var r = s & -s;
return nimprod(nimprod(x >> r, y >> r), 3 << r - 1); // square the Fermat power
}


# Wolfram Language (Mathematica), 81 bytes

x_±y_:=Min@Complement[Range[0,x*y],##&@@Array[BitXor[x±#2,#±y,±##]&,{x,y},0]]


Try it online!

Using the formula:

$\alpha \beta = \operatorname{mex}(\{\,\alpha' \beta + \alpha \beta' + \alpha' \beta' : \alpha' < \alpha , \beta' < \beta \,\}).$