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:
(2007-06-02)
Nim-sum of Fractions
Extending bitwise addition to ordinary rational numbers.
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.
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 antizero0 :
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).
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.
' 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)
Denominator
Binary
Period
Mersenne Multiple
1
1
1
3
2
3
5
4
15
7
3
7
9
6
63
11
10
1023
13
12
4095
15
4
15
17
8
255
19
18
262143
21
6
63
23
11
2047
25
20
1048575
27
18
262143
29
28
268435455
31
5
31
33
10
1023
35
12
4095
37
36
68719476735
39
12
4095
41
20
1048575
43
14
16383
45
12
4095
47
23
8388607
49
21
2097151
51
8
255
53
52
4503599627370495
55
20
1048575
57
18
262143
59
58
288230376151711743
61
60
1152921504606846975
63
6
63
65
12
4095
67
66
73786976294838206463
69
22
4194303
71
35
34359738367
73
9
511
75
20
1048575
77
30
1073741823
79
39
549755813887
81
54
18014398509481983
83
82
4835703278458516698824703
85
8
255
87
28
268435455
89
11
2047
91
12
4095
93
10
1023
95
36
68719476735
97
48
281474976710655
99
30
1073741823
101
100
1267650600228229401496703205375
103
51
2251799813685247
105
12
4095
107
106
81129638414606681695789005144063
109
36
68719476735
111
36
68719476735
113
28
268435455
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:
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.
(2007-06-05)
Nim-product of Fractions
Extending nim-multiplication to ordinary rational numbers.
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).
