Notations: Numbers are normally expressed in decimal. Binary expansions are underlined (e.g., 10 = 1010). In what follows, the plus sign (+) is used for Nim addition or bitwise addition (binary addition without carry). Following a convention introduced by John H. Conway (1937-2020) in the same context (On Numbers and Games, 1976) we put expressions using ordinary arithmetic between square brackets:
We may investigate what happens when bitwise (exclusive-or) addition is applied to the binary expansions of ordinary fractions. (Those are ultimately periodic.)
Adding bitwise two periodic expansions of periods p and q yields an expansion whose period divides the lowest common multiple (LCM) of p and q.
[1/3] = 0.010101010101010101010101... [1/5] = 0.001100110011001100110011... [1/3] + [1/5] = 0.011001100110011001100110... [2/5] = 0.011001100110011001100110...
Therefore, [1/3] + [1/5] = [2/5]. Equivalently, [1/5] + [2/5] = [1/3]
The nonzero fractions whose denominator is a power of 2, have two binary expansions (one ending with infinitely many zeros, the other ending with infinitely many ones). The issue is resolved by introducing the binary antizero 0 :
0 = ....111111111111111111.111111111111111111...
Note that if we add (in the ordinary sense) any nonzero number to 0, we obtain that same number, represented either by its unique binary expansion or by one of two equivalent ones, (Indeed, adding 0 in the ordinary way lets you switch from one such representation to the other.) With ordinary arithmetic, there's no difference (literally!) between 0 and 0 or between ½ and [ 0+½ ]. With Nim-arithmetic, on the other hand, 0 cannot be eliminated except with the use of a unary minus (there's no need for a binary minus operator, since addition and subtraction are the same operation). The relation to remember is:
x + [-x] = 0 = -0
So, the antizero 0 may also be called "-0" (minus zero).
0 = ....111111111111111111.111111111111111111... [-1] = ....111111111111111111.000000000000000000... [-1] + 0 = ....000000000000000000.111111111111111111... [1/3] + 0 = ....111111111111111111.101010101010101010... [-1/3] = ....111111111111111111.101010101010101010...
Nim-addition endows the binary expansions with the structure of a group (each expansion is its own opposite). We call such a binary expansion a nimber. One or two nimbers are associated with each number.
Nimbers form an Abelian group under Nim-addition. The subgroups correspond to fractions with a binary period that divides a given n. Those are fractions whose denominators are divisors of 2n-1. They are of the form [x+y/(2n-1)] where y is an integer from 0 to 2n-1. (both extremes being excluded if we rule out numbers whose denominators are powers of 2). The structure is thus homomorphic to a simple cartesian product of two groups: The integer nimbers on one hand (to which x belongs) and, on the other hand, the finite group of 2n integer nimbers to which y belongs.
[画像: Come back later, we're still working on this one... ]
' Nim-addition generalized to positive fractions in UBASIC:
'
fnSim(X,Y)
local D,N,Z,S
S=1:while or{even(den(X)),even(den(Y))}:X*=2:Y*=2:S*=2:wend
'Both denominators are now odd. Divisor S is a power of 2.
D=lcm(den(X),den(Y))
if D>1 then Z=2:N=1:while Z<>1:inc N:Z=(Z+Z)@D:wend:D=2^N-1
N=floor(X):X=X-N
Z=floor(Y):Y=Y-Z
Z=bitxor(N,Z)+bitxor(num(X)*D\den(X),num(Y)*D\den(Y))//D
return(Z//S)
Recall that a long prime to some base of numeration is a prime p whose inverse 1/p has period p-1 in that base. In binary, the long primes are:
3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947... (A001122)
Likewise, here are the prime numbers p whose binary periods are (p-1)/2 :
7, 17, 23, 41, 47, 71, 79, 97, 103, 137, 167, 191, 193, 199, 239, 263, 271, 311, 313, 359, 367, 383, 401, 409, 449, 463, 479, 487, 503, 521, 569, 599, 607, 647, 719, 743, 751, 761, 769, 809, 823, 839, 857, 863, 887, 929, 967, 977, 983, 991, 1009, 1031, 1033, 1039... (A115591)
By Fermat's little theorem, the binary period of a prime p divides p-1. Composite numbers for which this is true are the (rare) pseudoprime to base 2. The smallest of these is 341 = 11×13, whose binary period is 10:
For example, 953 is prime. So, its binary period divides 952 = 23. 7 . 17. It's actually 68 = 22. 17 because the following characterization holds:
953 divides 268-1 but divides neither 268/2-1 nor 268/17-1.
The period of a product of integers divides the LCM of their periods.
All we have to do is define the product of two 2-powers. Among integers, this is done by specifying that the product of a Fermat 2-power by any lesser integer is equal to their ordinary product.
Let's introduce [½] into the picture. The product of ½ by any integer can't be an integer (or else multiplying the result by the inverse of that integer would yield an integer instead of ½ as it should). More generally, [½] cannot be the root of any quadratic polynomial with integer coefficients (the integer nimbers are quadratically closed).
[ 1/2 ] 3 = 2
[ 1/2 ] 2
= [ 1/4 ]
[ 1/8 ] 3
= [ 1/2 ]
[ 1/512 ] 3
= [ 1/8 ]
On2 : transfinite number hacking
by Lieven Le Bruyn (2009年01月08日).
On2 : Conway's nim-arithmetics
by Lieven Le Bruyn (2009年01月26日).
On2 : Conway's nim-arithmetics
by Lieven Le Bruyn (2009年01月27日).
Conway polynomials