Nimber arithmetic
The nimbers, also known as Grundy numbers, are the values of the heaps in the game of Nim. They have addition and multiplication operations, unrelated to the addition and multiplication of the integers. Both operations are defined recursively:
The nim-sum of two integers m and n, denoted m⊕n is given by
m⊕n=mex(m'⊕n, m⊕ n' : m'<m, n'<n),
where the mex function returns the smallest integer not in the set. More simply: collect all the nim-sums of m and numbers smaller than n, and all nim-sums of n with all numbers less than m and find the smallest number not in that set. Fortunately, this also turns out to be equal to the bitwise xor of the two.
The nim-product is also defined recursively:
m⊗n=mex([m'⊗n]⊕[m⊗n']⊕[m'⊗n'] : m'<m, n'<n)
The product is more complicated and time-consuming to evaluate, but there are a few facts which may help:
- The operators ⊕ and ⊗ are commutative and distributive
- the nim-product of a Fermat power (22k) and a smaller number is their ordinary product
- the nim-square of a Fermat power x is the ordinary product 3x/2
Tasks:
- Create nimber addition and multiplication tables up to at least 15
- Find the nim-sum and nim-product of two five digit integers of your choice
FreeBASIC
<lang freebasic>function hpo2( n as uinteger ) as uinteger
'highest power of 2 that divides a given number return n and -n
end function
function lhpo2( n as uinteger ) as uinteger
'base 2 logarithm of the highest power of 2 dividing a given number
dim as uinteger q = 0, m = hpo2( n )
while m mod 2 = 0
m = m shr 1
q += 1
wend
return q
end function
function nimsum(x as uinteger, y as uinteger) as uinteger
'nim-sum of two numbers return x xor y
end function
function nimprod(x as uinteger, y as uinteger) as uinteger
'nim-product of two numbers if x < 2 orelse y < 2 then return x*y dim as uinteger h = hpo2(x) if x > h then return nimprod(h, y) xor nimprod(x xor h, y) 'recursively break x into its powers of 2 if hpo2(y) < y then return nimprod(y, x) 'recursively break y into its powers of 2 by flipping the operands 'now both x and y are powers of two dim as uinteger xp = lhpo2(x), yp = lhpo2(y), comp = xp and yp if comp = 0 then return x*y 'we have no fermat power in common h = hpo2(comp) return nimprod(nimprod(x shr h, y shr h), 3 shl (h - 1)) 'a fermat number square is its sequimultiple
end function
'print tables
function padto( i as ubyte, j as integer ) as string
return wspace(i-len(str(j)))+str(j)
end function
dim as uinteger a, b dim as string outstr
outstr = " + | " for a = 0 to 15
outstr += padto(2, a)+" "
next a print outstr print "--- -------------------------------------------------" for b = 0 to 15
outstr = padto(2, b)+ " | "
for a = 0 to 15
outstr += padto(2, nimsum(a,b))+" "
next a
print outstr
next b print outstr = " * | " for a = 0 to 15
outstr += padto(2, a)+" "
next a print outstr print "--- -------------------------------------------------" for b = 0 to 15
outstr = padto(2, b)+ " | "
for a = 0 to 15
outstr += padto(2, nimprod(a,b))+" "
next a
print outstr
next b print a = 21508 b = 42689
print using "##### + ##### = ##########"; a; b; nimsum(a,b) print using "##### * ##### = ##########"; a; b; nimprod(a,b)</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202