Massachusetts Institute of Technology A. I. Laboratory Artificial Intelligence Memo No. 239 February 29, 1972

M. Beeler [beeler@bbn.com] R. W. Gosper [rwg@newton.macsyma.com][R. Schroeppel](http://www.cs.arizona.edu/xkernel/www/people/rich.html) [rcs@cs.arizona.edu]

[Retyped and formatted in 'html' ('Web browser format) by Henry Baker, April, 1995. The goal of this 'html' document is to make HAKMEM available to the widest possible audience -- including those without bitmapped graphics browsers. Therefore, equations have been formatted to be readable even on ASCII browsers such as 'lynx'. Click here to get original AI Memo 239 in 400 dots/inch, 1 bit/pixel, Group 4 facsimile TIFF format (a single 5 megabyte gzip compressed tar file, AIM-239.tiff.tar.gz).]

Work reported herein was conducted at the Artificial Intelligence Laboratory, a Massachusetts Institute of Technology research program supported in part by the Advanced Research Projects Agency of the Department of Defense and monitored by the Office of Naval Research under Contract Number N00014-70-A-0362-0002.

Reproduction of this document, in whole or in part, is permitted for any purpose of the United States Government.

Compiled with the hope that a record of the random things people do around here can save some duplication of effort -- except for fun.

Here is some little known data which may be of interest to computer hackers. The items and examples are so sketchy that to decipher them may require more sincerity and curiosity than a non-hacker can muster. Doubtless, little of this is new, but nowadays it's hard to tell. So we must be content to give you an insight, or save you some cycles, and to welcome further contributions of items, new or used.

The classification of items into sections is even more illogical than necessary. This is because later elaborations tend to shift perspective on many items, and this elaboration will (hopefully) continue after publication, since this text is retained in "machinable" form. We forgive in advance anyone deterred by this wretched typography.

People referred to are from the A. I. Lab: ``

```
Marvin Minsky [minsky@ai.mit.edu]
Bill Gosper [rwg@newton.macsyma.com]
Michael Beeler [beeler@bbn.com]
Joe Cohen
Jerry Freiberg
John Roe
Rich Schroeppel [rcs@cs.arizona.edu]
David Silver
Michael Speciner
Richard Stallman [rms@ai.mit.edu]
Gerald Sussman [gjs@ai.mit.edu]
David Waltz
```

Once at the A. I. Lab but now elsewhere: ``

```
Jan Kok William Henneman
Rici Liknaitzky George Mitchell
Peter Samson Stuart Nelson
Roger Banks Rollo Silver
Mike Paterson [Mike.Paterson@dcs.warwick.ac.uk]
```

at Digital Equipment Corporation: ``

```
Jud Lenard Dave Plumer
Ben Gurley (deceased) Steve Root
```

elsewhere at M.I.T.: ``

```
Gene Salamin PDP-1 hackers
Eric Jensen Frances Yao
Edward Fredkin
```

once at M.I.T., but now elsewhere: ``

```
Jackson Wright Steve Brown
Malcolm Rayfield
```

in France: ``

`Marco Schutzenberger Henry Cohen`

at Computer Corporation of America: ``

`Bill Mann`

at BBN: ``

`Robert Clements`

CAVEATS:

Some of this material is very inside -- many readers will have to excuse cryptic references.

The label "PROBLEM" does not always mean exercise; if no solution is given, it means we couldn't solve it. If you solve a problem in here, let us know.

Unless otherwise stated, all computer programs are in PDP-6/10 assembly language.

(1/3)! and (2/3)! are interexpressible. (1/4)! and (3/4)! are interexpressible.

Thus these two pairs are of dimensionality one.

(1/10)! and (2/10)! are sufficient to express (N/10)! for all N. (1/12)! and (2/12)! are sufficient to express (N/12)! for all N. (1/3)! and (1/4)! are sufficient to express (N/12)! for all N.

Thus the three cases above are of dimensionality two.

PROBLEM: Find some order to this dimensionality business.

The reflection and multiplication formulas:

```
pi Z
Z! (-Z)! = ---------
sin(pi Z)
(N-1)/2 -NZ-1/2
(2 pi) N (NZ)! = Z! (Z-1/N)! (Z-2/N)! ... (Z-(N-1)/N)!
```

Problem: Given a regular n-gon with all diagonals drawn, how many regions are there? In particular, how many triple (or N-tuple) concurrences of diagonals are there?

Regarding convergence of Newton's method for quadratic equations: Draw the perpendicular bisector of the line connecting the two roots. Points on either side converge to the closest root.

On the line:

- they do not converge
- there is a dense set of points which involve division by zero
- there is a dense set of points which loop, but roundoff error propagates so all loops are unstable
- being on the line is also unstable (if the roots are imaginary and you are on the real axis, you may be doing exact computation of the imaginary part (0), hence stay on the line. Example: X^2 + 1 = 0, X0 = random real floating point number.)

By Mathlab, the *discriminant* of

```
4 3 2
X + F X + G X + H X + I is (as the discriminant of
2 2
A X + B X + C is B - 4 A C):
4 3 3 3 3 2 2 2 2
- 27 H + 18 F G H - 4 F H - 4 G H + F G H
2 2 2 2 3 4 2 3
+ I * [144 G H - 6 F H - 80 F G H + 18 F G H + 16 G - 4 F G ]
2 2 2 4
+ I * [- 192 F H - 128 G + 144 F G - 27 F ]
3
- 256 I
```

In general, the discriminant of an n-th degree polynomial is

```
/===
! ! 2
! ! (ROOT - ROOT ) = square of determinant whose i,j element is
! ! i j
i < j
i-1
ROOT .
j
```

(The *discriminant* is the lowest degree symmetric function of the roots which is 0 when any two are equal.)

If A is the first *symmetric function* of N variables ``

`= X + Y + Z + ...`

and B is the second symmetric function of N variables ``

`= X Y + X Z + ... + Y Z + ...`

(B = sum of pairs), then ``

```
2 2 2 2
X + Y + Z + ... = A - 2 B.
3 3 3 3
X + Y + Z + ... = A - 3 A B + 3 C.
4 4 4 4 2 2
X + Y + Z + ... = A - 4 A B + 2 B + 4 A C - 4 D.
```

If f(I;X,Y,...) is the Ith symmetric function on N variables, ``

```
/ 0 if I > N
f(I;X,Y,...) = ! 1 if I = 0
X*f(I-1;Y,Z...) + f(I;Y,Z,...) (N-1 variables)
```

The generating function is simply

```
N
====
I
> F(I; X, Y, Z) S = (1 + S X) (1 + S Y) (1 + S Z) ...
/
====
I=0
```

Solutions to

```
3 2
F(X) = X - 3 B X + C X + D = 0
```

are

```
------------------------------
/ ------------------
/ F(B) / F(B) 2 F'(B) 3
B - K * 3/ ---- + / [----] + [-----]
V 2 V 2 3
------------------------------
/ ------------------
2 / F(B) / F(B) 2 F'(B) 3
- K * 3/ ---- - / [----] + [-----]
V 2 V 2 3
```

where K is one of the three cuberoots of 1:

1, (-1+sqrt(-3))/2, (-1-sqrt(-3))/2.

If

```
4 2
X + B X + C X + D = 0,
```

then 2 X = sqrt(Z1) + sqrt(Z2) + sqrt(Z3), where Z1, Z2, Z3 are roots of

```
3 2 2 2
Z + 2 B Z + (B - 4 D) Z - C = 0.
```

The choices of square roots must satisfy

sqrt(Z1) sqrt(Z2) sqrt(Z3) = -C.

An easy solution of

```
3
-4 X + 3 X - a = 0
```

is X = sin((arcsin a)/3).

In a similar manner, the general *quintic* can be solved exactly by use of the elliptic modular function and its inverse. See Davis: *Intro. to Nonlinear Differential and Integral Equations* (Dover), p. 172. Unfortunately, there exists >= 1 typo, since his eqs. (7) and (13) are inconsistent.

The following operations generate one-to-one conformal mappings of Euclidean N-space onto itself.

- Translate N-space.
- Expand N-space about one of its points.
- Stereographically project N-space onto an N-sphere, rotate the sphere, then project back onto N-space.

PROBLEMS:

Show that all such conformal maps are generated by these operations for any N. If the one-to-one and onto conditions are removed, then for N = 2, conformal maps can be obtained by analytic functions. Show that for N > 2, no new conformal maps exist.

(motivation for next item)

Define multiplication on ordered pairs

`(A,B) (C,D) = (A C + A D + B C, A C + B D).`

This is just (A X + B) * (C X + D) mod X^2 - X - 1, and so is associative, etc. We note (A,B) (1,0) = (A + B, A), which is the Fibonacci iteration. Thus, (1,0)^N = (FIB(N), FIB(N-1)), which can be computed in log N steps by repeated squaring, for instance. FIB(15) is best computed using N = 16, thus pushing the minimal binary addition chain counterexample to 30 (Liknaitzky). (See Knuth vol. 2, p 398.) By the last formula,

`(1,0)^-1 = (FIB(-1),FIB(-2)) = (1, -1),`

which, as a multiplier, *backs up* one Fibonacci step (further complicating the addition chain question). Observing that

`(1,0)^0 = (FIB(0), FIB(-1)) = (0,1)`

= the (multiplicative) identity, equate it with scalar 1. Define addition and scalar multiplication as with ordinary vectors.

`(A,B)^-1 = (-A, A + B) / (B^2 + A B - A^2),`

so we can compute rational functions when the denominator isn't zero. Now, by using power series and Newton's method, we can compute fractional Fibonaccis, and even *e*^(X,Y) and log (X,Y). If we start with (1,0) and square iteratively, the ratio will converge to the larger root of x^2 - x - 1 (= the golden ratio) about as rapidly as with Newton's method.

This method generalizes for other polynomial roots, being an improvement on the method of Bernoulli and Whittaker (Rektorys, *Survey of Applicable Math.,* p. 1172). For the general second order recurrence, F(N+1) = X F(N) + Y F(N-1), we have the multiplication rule: (A,B) (C,D) = (A D + B C + X A C, B D + Y A C).

Inverse: (A,B)^-1 = (-A, X A + B) / (B^2 + X A B - Y A^2).

Two for the price of one: (F(1), Y F(0)) (1,0)^N = (F(N+1), Y F(N))).

Recurrence relation:

```
(1) A = C A + ... + C A
k n-1 k-1 0 k-n
with A , ..., A given as initial values.
0 n-1
```

Consider the algebra with basis vectors

```
0 1 2 n-1
X , X , X , ..., X
```

and the identification

```
n n-1 0
(2) X = C X + ... + C X .
n-1 0
```

Thus if U, V, W are vectors and W = U V, then componentwise

```
====
(3) W = > T U V ,
i / ijk j k
====
j,k
```

where the T's depend only on the C's. The following simple procedure yields A(k): express the vector X^k as a linear combination of the basis vectors, then set X^m = A(m) (0<=m<n). Computation of X^k can be done by k-n+1 applications of (2) or by computing the T's in (3) and then applying (3) O(log k) times.

PROOF: If 0 <= k < n, X^k is already a basis vector, so we get A(k). Suppose the procedure works for k < L.

```
L n L-n
X = X X
n-1 L-n
= (C X + ... + C ) X
n-1 0
L-1 L-n
= C X + ... + C X
n-1 0
```

The procedure evaluates each X^m to A(m), so X^L evaluates to

```
C A + ... + C A = A . QED
n-1 L-1 0 L-n L
```

The same procedure will work for negative k using

```
-1 n-1 n-2
(4) X = (X - C X - ... - C )/C ,
n-1 1 0
```

the unique vector which when multiplied by X yields X^0.

Let (2) be F(X) = 0 and V be the algebra constructed above. Then V is a field iff F(X) is irreducible in the field of the coefficients of V.

PROOF: Note that an element P of V is zero iff P(X) = 0 mod F(X). If G(X) H(X) = F(X), DEG G,H < DEG F, then the product of two non-zero elements is zero and so V can't be a field.

Let P be an arbitrary non-zero element of V.

DEG(GCD(P,F)) <= DEG P < DEG F.

If F(X) is irreducible, then GCD(P,F) = 1, so there exist Q(X), R(X) such that Q(X) P(X) + R(X) F(X) = 1. Then Q(X) P(X) = 1 mod F(X). Since P has an inverse, V is a field.

Yet another way to rapidly evaluate recurrences is to observe that if

```
F(N+1) = X * F(N) + Y * F(N-1), then
F(N+2) = (X^2 + 2 Y) * F(N) - Y^2 * F(N-2).
```

This rate doubling formula can be applied iteratively to compute the Nth term in about log N steps, e.g., to get the 69th term given terms 1 and 2, we form 1, 2, 3, 5, 9, 13, 21, 37, 69. This sequence is computed from right to left by iteratively subtracting half the largest possible power of 2. This is sufficient to guarantee that some term further left will differ from the left one by that same (halved) power of 2; e.g., 5, ..., 21, 37 have a common difference of 2^4, so that term 37 can be found from term 5 and term 21 using the fourth application of the rate doubling formula.

The rate tripling formula is F(N+3) = (X^3 + 3 X Y) * F(N) + Y^3 * F(N-3).

For the K-tupling formula:

F(N+K) = P(K) * F(N) + Q(K) * F(N-K) P(K+1) = X * P(K) + Y * P(K-1) (the same recurrence as F) Q(K+1) = -Y * Q(K) P(1) = X Q(1) = Y P(0) = 2 Q(0) = -1 Q(K) = -(-Y)^K P(K) = 2 (-Y)^K/2 * T(K; X/sqrt(-4 Y)), where T(K; X) is the Kth Chebychev polynomial = cos(K arccos X).

If A(I), B(I), and C(I) obey the same second order recurrence, ``

```
[ A B ] -1 [ C ]
[ I I ] [ I ]
(I) [ ] [ ]
[ A B ] [ C ]
[ J J ] [ J ]
```

is independent of I and J, provided the inverse exists. (This is true even if coefficients are not constant, since any two independent sequences form a basis.)

Plugging in F and P as defined above, we get an expression for the Nth term of the general second order recurrence in terms of P(N) and P(N+1): ``

```
[ P(N) P(N+1) ] [ P(0) P(1) ] -1 [ F(0) ]
[ P(1) P(2) ] [ F(1) ] = F(N).
```

Setting X = Y = 1, we get FIB(N) = (2 P(N+1) - P(N))/5, which is a complex but otherwise square root free closed form. (sqrt(-4) = 2*i*)

With constant coefficients, the invariance (I) implies: ``

```
[ A A ] [ A A ] -1 [ A ]
[ P+I P+J ] [ Q+I+K Q+J+K ] [ R+K ]
[ ] [ ] = A
[ A A ] [ A ] P-Q+R
[ Q+I+L Q+J+L ] [ R+L ]
```

These matrix relations generalize directly for Nth order recurrences.

The Nth Chebychev polynomial T(N) = T(N; x) = cos(N arccos x).

T(0) = 1, T(1) = x, T(N+1) = 2 x T(N) -T(N-1).

T(N; T(M)) clearly = T(N M).

x^N - 2^(1-N) T(N), whose degree is N-2, is the polynomial of degree < N which stays closest to x^N in the interval (-1,1), deviating by at most 2^(1-N) at the N+1 places where x = cos(K * pi/N), K=0, 1, ...N.

Generating function:

```
====
N 1 - x S
> T(N) S = --------------
/ 2
==== 1 - 2 x S + S
```

First order (nonlinear) recurrence:

```
-------------------
/ 2 2
T(N+1) = x T(N) - /(1 - x ) (1 - T(N) ) .
V
```

(T(N+1),-T(N)) = (T(1),-T(0)) (1,0),

where (A,B) (C,D) = (A D + B C + 2 x A C, B D - A C).

``

```
n n
1 (1+ix) - (1-ix)
tan (n arctan x) = - * -----------------
i n n
(1+ix) + (1-ix)
```

Problem: synthesize a given logic function or set of functions using the minimum number of two-input AND gates. NOT gates are assumed free. Feedback is not allowed. The given functions are allowed to have X (don't care) entries for some values of the variables. P XOR Q requires three AND gates. MAJORITY(P,Q,R) requires 4 AND gates. "PQRS is a prime number" seems to need seven gates. The hope is that the best Boolean networks for functions might lead to the best algorithms.

``

```
Number of monotonic increasing Boolean
N functions of N variables
- --------------------------------------
0 2 (T, F)
1 3 (T, F, P)
2 6 (T, F, P, Q, P AND Q, P OR Q)
3 20
4 168 = 8 * 3 * 7
5 7581 = 3 * 7 * 19^2
6 7,828,354 = 2 * 359 * 10903 (Ouch!)
```

N from 0 to 4 suggest that a formula should exist, but 5 and 6 are discouraging. A difficult generalization: Given two partial orderings, find the number of maps from one to the other that are compatible with the ordering. A related puzzle: A partition of N is a finite string of non-increasing integers that add up to N. Thus 7 3 3 2 1 1 1 is a partition of 18. Sometimes an infinite string of zeros is extended to the right, filling a half-line. The number of partitions of N, P(N), is a fairly well understood function.

The generating function is

```
infinity
======
n 1
> P(n) X = ------------------
/ infinity
====== /===
n = 0 ! ! k
! ! (1 - X )
! !
k = 1
```

A *planar* partition is like a partition, but the entries are in a two-dimensional array (the first quadrant) instead of a string. Entries must be non-increasing in both the x and y directions. A planar partition of 34 would be: ``

```
1
3 1
3 2 2 1
7 6 4 3 1
```

Zeros fill out the unused portion of the quadrant. The number of planar partitions of n, PL(n), is not a very well understood function.

The generating function is

```
infinity
======
n 1
> PL(n) X = -------------------
/ infinity
====== /===
n = 0 ! ! k k
! ! (1 - X )
! !
k = 1
```

No simple proof of the generating function is known. Similarly, one can define cubic partitions with entries in the first octant, but no one has been able to discover the generating function. Some counts for cubic partitions and a discussion appear in Knuth, Math. Comp. 1970 or so.

The 2-NOTs problem: Synthesize a black box which computes NOT-A, NOT-B, and NOT-C from A, B, and C, using an arbitrary number of ANDs and ORs, but only 2 NOTs.

Clue: (Stop! Perhaps you would like to work on this awhile.)

Lemma: Functions synthesizable with one NOT are those where the image of any upward path (through variable space) has at most one decrease (that is, from T to F).

A Venn diagram for N variables where the shape representing each variable is convex can be made by superimposing successive M-gons (M = 2, 4, 8, ...), every other side of which has been pushed out to the circumscribing circle. If you object to superimposed boundaries, you may shrink the nested M-gons a very slight amount which depends on N.

PROBLEM: Cover the Execuport character raster completely with the minimum number of characters. The three characters I, H and # works. Using capital letters only, the five characters B, I, M, V and X is a minimal solution. Find a general method of solving such problems.

PROBLEM: Given several binary numbers, how can one find a mask with a minimal number of 1 bits, which when AND-ed with each of the original numbers preserves their distinctness from each other? What about permuting bit positions for minimum numerical spread, then taking the low several bits?

`(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).`

There exists a convex figure n congruent copies of which, for any n, form a Venn diagram of 2^n regions.

Random number generators, such as Rollo Silver's favorite, which use SHIFTs and XORs, and give as values only some part of their internal state, can be inverted. Also, the outputs may often be used to obtain their total internal state. For example, 2 consecutive values from Rollo's suffice to allow prediction of its entire future. Rollo's is: ``

```
RANDOM: MOVE A,HI ;register A gets loaded with "high" word
MOVE B,LO ;register B gets loaded with "low" word
MOVEM A,LO ;register A gets stored in "low" word
LSHC A,35. ;shift the 72-bit register AB left 35
XORB A,HI ;bitwise exclusive-or of A and HI replaces both
```

This suggests a susceptibility to analysis of mechanical code machines.

See LOOP DETECTOR item in FLOWS AND ITERATED FUNCTIONS section.

A mathematically exact method of generating a Gaussian distribution from a uniform distribution: let x be uniform on [0,1] and y uniform on [0, 2 *pi*], x and y independent. Calculate r = sqrt(-log x). Then r cos y and r sin y are two independent Gaussian distributed random numbers.

PROBLEM: Generate random unit vectors in N-space uniform on the unit sphere. SOLUTION: Generate N Gaussian random numbers and normalize to unit length.

After about 40 minutes of run time to verify the absence of any non-trivial factors less than 235, the 125th Mersenne number,

```
125
2 - 1,
```

was factored on Tuesday, January 5, 1971, in 371 seconds run time as follows:

```
125
2 - 1 = 31 * 601 * 1801 * 269,089,806,001 * 4,710,883,168,879,506,001.
```

John Brillhart at the University of Arizona had already done this. M137 was factored on Friday, July 9, 1971 in about 50 hours of computer time:

```
137
2 - 1 = 32,032,215,596,496,435,569 * 5,439,042,183,600,204,290,159.
```

[Current prime records -- *H.B.*]

For a random number X, the probability of its largest prime factor being

- greater than sqrt(X)=X^(1/2) is ln 2.
- less than X^(1/3) is about 4.86%.

This suggests that similar probabilities are independent of X; for instance, the probability that the largest prime factor of X is less than X^(1/20) may be a fraction independent of the size of X.

RELEVANT DATA: ([] denote the expected value of adjacent entries.) ``

```
RANGE COUNT CUMULATIVE SUM OF COUNT
10^12 to 10^6 7198 [6944] 10018
10^6 to 10^4 2466 2820
10^4 to 10^3 354 402 [487]
10^3 to 252 40 48 ;252 = 10^2.4
252 to 100 7 8
100 to 52 1 1 ;52 = 10^1.7
51 to 1 0 0
```

where:

"COUNT" is the number of numbers between 10^12 + 1 and 10^12 + 10018 whose largest prime factor is in "RANGE". The number of primes in 10^12 + 1 to 10^12 + 10018 is 335; the prime number theorem predicts 363 in this range. This is relevant to Knuth's discussion of Legendre's factoring method, vol. 2, p. 351-354.

Twin primes:

- 166,666,666,667 = (10^12 + 2)/6
- 166,666,666,669

The number 166,666,666,666,667 is prime, but 166,666,666,666,669 is not.

The primes which bracket 10^12 are 10^12 + 39 and 10^12 - 11.

The primes which bracket 10^15 are 10^15 + 37 and 10^15 - 11.

The number 23,333,333,333 is prime.

Various primes, using T = 10^12, are:

40 T + 1, 62.5 T + 1, 200 T - 3, 500 T - 1, 500 T - 7.

Ramanujan's problem of solutions to

```
N 2
2 - 7 = X
```

was searched to about N = 10^40; only his solutions (N = 3, 4, 5, 7, 15) were found. It has recently been proven that these are the only ones. Another Ramanujan problem: Find all solutions of n! + 1 = x^2.

Take a random real number and raise it to large powers; we expect the fraction part to be uniformly distributed. Some exceptions:

*phi*= (1 + sqrt(5))/2- all - 1 < X < 1
- sqrt(2) (half are integers, other half are probably uniformly distributed)
1 + sqrt(2) -- Proof:

`N N (1 + sqrt(2)) + (1 - sqrt(2)) = integer (by induction); N the (1 - sqrt(2)) goes to zero.`

- 2 + sqrt(2) -- similar to 1 + sqrt(2)
any algebraic number whose conjugates are all inside the unit circle

Now, 3 + sqrt(2) is suspicious; it looks non-uniform, and seems to have a cluster point at zero. PROBLEM: Is it non-uniform?

Numbers whose right digit can be repeatedly removed and they are still prime: CONJECTURE: There are a finite number of them in any radix. In decimal there are 51, the longest being 1,979,339,333 and 1,979,339,339.

PROBLEM: Can every positive integer be expressed in terms of 3 and the operations factorial and integer square root? E.g., 5 = sqrt(sqrt(3!!)).

Take as many numbers as possible from 1 to N such that no 3 are in arithmetic progression. CONJECTURE: As N - > infinity, the density of such sets approaches zero, probably like

```
(ln 2)/(ln 3)
N .
```

- XX.XX is a known solution for N = 5
- XX.XX....XX.XX is a known solution for N = 14

Conjecture that XX.XX just keeps getting copied. If the N^{1} can be proved, it follows that there are infinitely many primes P1, P2, P3 in arithmetic progression, since primes are much more common than N^{2}.

PROBLEM: How many squares have no zeros in their decimal expression? Ternary?

The number of n digit strings base B in which all B digits occur at least once is just the Bth forward difference at 0 of the nth powers of 0, 1, ... . E.g., for n = 4: ``

```
0 1 16 81 256 625
1 15 65 175 369
14 50 110 194
36 60 84
24 24
0
```

so there are 14 (= 2^4 - 2) such 4-bit strings, 36 such 4-digit ternary strings, 24 (= 4!) such quaternary, and 0 for all higher bases. 27 (= 10e?) random decimal digits are required before it is more likely than not that every digit has occurred; with 50 digits the likelihood is 95%.

By the binomial theorem, the bth forward difference at 0 of the 0, 1, 2, ... powers of n is (n-1)^b. E.g., for n = 4: ``

```
1 4 16 64 256
3 12 48 192
9 36 144
27 108
81
```

In fact, any straight line with rational slope through such an array will always go through a geometric sequence with common ratio of the form n^a (n-1)^b. In the above, east by southeast knight's moves give the powers of 12: 1, 12, 144, ... .

PROBLEM: Using N digits, construct a string of digits which at no time has any segment appearing consecutively twice.

- N = 2 -> finite maximum string
- N = 10 -> known infinite

Determine maximum string length for N = 3.

SUB-PROBLEM: How many sequence exist for any particular length?

The variance of a pseudo-Gaussian distributed random variable made by adding T independent, uniformly distributed random integer variables which range from 0 to N-1, inclusive, is T((N^2 - 1)/12).

There are exactly 23000 primes less than 2^18.

To show that

```
N
====
L N + 1 N + 1 L
> BINOMIAL(N + L, L) ((1 - X) X + (1 - X) X ) = 1
/
====
L = 0
```

set N to 20 and observe that it is the probability that one or the other player wins at pingpong. (X = probability of first player gaining one point, L = loser's score, deuce rule irrelevant.) If this seems silly, try more conventional methods.

PROBLEM: If somehow you determine A should spot B 6 points for their probabilities of winning to be equal, and B should spot C 9 points, how much should A give C?

Let (A, B, C, ...) be the multinomial coefficient

```
(A + B + C....)!
----------------
A! B! C! ...
```

This is equal modulo the prime p to

`(A0, B0, C0...) (A1, B1, C1...) (A2, B2, C2...)...`

where AJ is the Jth from the right digit of A base p.

Thus BINOMIAL(A+B A) mod 2 is 0 iff (AND A B) is not.

The exponent of the largest power of p which divides (A, B, C,...) is equal to the sum of all the carries when the base p expressions for A, B, C, ... are added up.

Recurrences for multinomial coefficients:

(A,B,C,...) = (A+B,C,...)(A,B) = (A+B+C,...)(A,B,C) = ...

- Take a unit step at some heading (angle).
- Double the angle, step again.
- Redouble, step, etc.

For what initial heading angles is your locus bounded?

PARTIAL ANSWER (Schroeppel, Gosper): When the initial angle is a rational multiple of *pi,* it seems that your locus is bounded (in fact, eventually periodic) iff the denominator contains as a factor the square of an odd prime other than 1093 and 3511, which must occur at least cubed. (This is related to the fact that 1093 and 3511 are the only known primes satisfying

```
P 2
2 = 2 mod P ).
```

But a denominator of 171 = 9 * 19 never loops, probably because 9 divides *phi*(19). Similarly for 9009 and 2525. Can someone construct an irrational multiple of *pi* with a bounded locus? Do such angles form a set of measure zero in the reals, even though the "measure" in the rationals is about .155? About .155 = the fraction of rationals with denominators containing odd primes squared = 1 - product over odd primes of 1 - 1/P(P + 1). This product = .84533064 +- a smidgen, and is not, alas, sqrt(*pi*/2) ARCERF(1/4) = .84534756. This errs by 16 times the correction factor one expects for 1093 and 3511, and is not even salvaged by the hypothesis that all primes > a million satisfy the congruence. It might, however, be salvaged by quantities like 171.

The most probably suit distribution in bridge hands is 4-4-3-2, as compared to 4-3-3-3, which is the most evenly distributed. This is because the world likes to have unequal numbers: a thermodynamic effect saying things will not be in the state of lowest energy, but in the state of lowest disordered energy.

The Fibonacci series modulo P has been studied. This series has a cycle length L and within this cycle has sub-cycles which are bounded by zero members.

The length of powers of primes seems to be

```
power-1
L = (length of prime) * prime .
```

The length of products of powers of primes seems to be

`L = least common multiple of lengths of powers of primes which are factors.`

There can be only 1, 2, or 4 sub-cycles in the cycle of a prime.

Primes with 1 sub-cycle seem to have lengths

```
prime - 1
L = --------- ,
N
```

N covering all integers. Primes with 2 sub-cycles seem to have lengths

```
M
prime - (-1)
L = ------------- ,
M
```

M covering all integers except of form 10 K + 5.

Primes with 4 sub-cycles seem to always be of form 4 K + 1, and seem to have lengths

```
prime + 1 prime - 1
L = --------- or --------- ,
R S
```

R covering all integers of form 10 K + 1, 3, 7 or 9; S covering all integers.

At Schroeppel's suggestion, the primes have been separated mod 40, which usually determines their number of sub-cycles: ``

```
PRIME mod 40 SUB-CYCLES
1, 9 usually 2, occasionally 1 or 4 (about equally)
3, 7, 23, 27 2
11, 19, 31, 39 1
13, 17, 33, 37 4
21, 29 1 or 4 (about equally)
2 (only 2) 1
5 (only 5) 4
```

Attention was directed to primes which are 1 or 9 mod 40 but have 1 or 4 subcycles.

```
2 2
25 X + 16 Y
```

seems to express those which are 9 mod 40;

```
2 2
(10 X +- 1) + 400 Y
```

seems to express those which are 1 mod 40.

PROBLEM: Can some of the "seems" above be proved? Also, can a general test be made which will predict exact length for any number?

A point of the 2 dimensional lattice is called *visible* iff its coordinates are relatively prime. The invisible 2 by 2 square with smallest X has its near corner on (14,20). (I.e., (14,20), (15,20), (14,21), and (15,21) are all invisible.) The corresponding 3 by 3 is at (104,6200). By the chines remainder theorem, there exist invisible sets of every finite shape. Excellent reference: *Amer. Math. Monthly,* May '71, p487.

There is a unique "magic hexagon" of side 3: ``

```
3 17 18
19 7 1 11
16 2 5 6 9
12 4 8 14
10 13 15
```

First discovered by Clifford W. Adams, who worked on the problem from 1910. In 1957, he found a solution. (See Aug. 1963 *Sci. Am.,* Math. Games.) Other length sides are impossible.

There is no magic cube of order 4.

Proof: Let K (= 130) be the sum of a row.

Lemma 1: In a magic square of order four, the sum of the corners is K.

Proof: Add together each edge of the square and the two diagonals. This covers the square entirely, and each corner twice again. This adds to 6 K, so twice the corner sum is 2 K.

Lemma 2: In a magic cube of order 4, the sum of any two corners connected by an edge of the cube is K/2.

Proof: Call the corners a and b. Let c, d and e, f be the corners of any two edges of the cube parallel to ab. Then abcd, abef, and cdef are all the corners of magic squares. So a+b+c+d + a+b+e+f + c+d+e+f = 3K; a+b+c+d+e = 3K/2; a+b = K/2.

Proof of magic cube impossibility: Consider a corner x. There are three corners connected by an edge to x.

Each must have value K/2 - x. QED

By similar reasoning, the center of an order 5 magic cube must be 63 = K/5.

COROLLARY: There is no magic tesseract of order 5.

The probability that two random integers are relatively prime is 6/*pi*^2.

PSEUDO-PROOF: Let X be the probability. Let S be the set of points in the integer lattice whose coordinates are relatively prime, so that S occupies a fraction X of the lattice points. Let S(D) be the set of points whose coordinates have a GCD of D. S(D) is S expanded by a factor of D from the origin. So S(D) occupies a fraction X/D^2 of the lattice, or the probability that two random integers have a GCD of D is X/D^2. If D unequals D', then S(D) intersect S(D') is empty, and union of all S(D) is the entire lattice. Therefore X*(1/1 ^{2+1/2}2+1/3^2+...) = 1, so X = 6/*pi*^2. This argument is not rigorous, but can be made so.

The probability that N numbers will lack a Pth power common divisor is 1/*zeta*(NP).

The probability that a random rational number has an even denominator is 1/3.

See following illustrations; also PI section.

Figure 1(a). This diagram is to substantiate the claim that every Gaussian integer has a unique bit combination. Running through bit combinations 0, 1, 10, 11, ..., the diagram is a map of values, radix *i*-1. The origin is circled; the dot is at the 127th combination (1111111 = 2 + 5*i*), which is merely the last point drawn.

Figure 1(b). As 1(a), but radix *i*+1. Large circle is origin. Dashes indicate continuity of curve at confusing places. Dotted curve is with an infinity of ones to the left (big dot = ...1111 = i). The solid and dotted curves are symmetrical about the point marked with a small circle.

Figure 2. Similar to 1(a), but showing fraction parts as well. Reprinted by special permission from Knuth, *The Art of Computer Programming, Volume 2, Seminumerical Algorithms,* 1969, Addison-Wesley, Reading, Mass.

The "length" of an N-digit decimal number is defined as the number of times one must iteratively form the product of its digits until one obtains a one-digit product (see *Technology Review* Puzzle Corner, December 1969 and April 1970). For various N, the following shows the maximum "length", as well as how many distinct numbers (permutation groups of N digits) there are: ``

```
N MAX L DISTINCT
2 4 54
3 5 219
4 6 714
5 7 2,001
6 7 5,004
7 8 11,439
8 9 24,309
9 9 48,619
10 10 92,377
11 10 167.959
12 10 293,929
```

Also, for N = 10, 11 and 12, a tendency for there to be many fewer numbers of "length" = 7 is noted. Other than this, the frequency of numbers of any given N, through N = 12, decreases with increasing "length", CONJECTURE (Schroeppel): No L > 10.

There is at least one zero in the decimal expression of each power of 2 between

```
86 30739014
2 = 77,371,252,455,336,267,181,195,264 and 2 ,
```

where the program was stopped. If digits of such powers were random, the probability that there is another zeroless power would be about 1/10^411816. Assuming there aren't any raises the question:

How many final nonzero digits can a power of two have?

ANSWER (Schroeppel): Arbitrarily many. If we look at the last n digits of consecutive powers of 2, we see:

- None end in zero.
- After the nth, they are all multiples of 2^n.
- They get into a loop of length 4 * 5^(n-1). (Because 2 is a primitive root of powers of 5.)

But there are only 4 * 5(n-1) multiples of 2^n which don't end with zero and are < 10^n, so we will see them all. In particular, we will see the one composed entirely of 1's and 2's, which ends ...11112111211111212122112.

```
3 3 3 3
3 + 4 + 5 = 6 .
```

```
2
91038 90995 89338 00226 07743 74008 17871 09376 =
82880 83126 51085 58711 66119 71699 91017 17324
91038 90995 89338 00226 07743 74008 17871 09376
```

If S = the sum of all integers which exactly divide N, including 1 and N, then "perfect numbers" are S = 2 N; the first three numbers which are S = 3 N are:

```
3
120 = 2 * 3 * 5 = 1111000 base 2
5
672 = 2 * 3 * 7 = 1010100000 base 2
9
523,776 = 2 * 3 * 11 * 31 = 1111111111000000000 base 2
```

Consider iteratively forming the sum of the factors (including 1 but not N) of a number N. This process may loop; "perfect numbers" are those whose loop is one member, N. For example, N = 28 = 1 + 2 + 4 + 7 + 14. An example of a two-member loop is:

- sum of factors of 220 = 284
- sum of factors of 284 = 220

Two-member loops are called "amicable pairs."

A program to search for loops of length > 2, all of whose members are < 6,600,000,000 found the known loops of length 5 (lowest member is 12496) and 28 (lowest member is 14316), but also 13 loops of 4 members (lowest member is given): ``

```
1,264,460 = 2^2 * 5 * 17 * 3,719
2,115,324 = 2^2 * 3^2 * 67 * 877
2,784,580 = 2^2 * 5 * 29 * 4,801
4,938,136 = 2^3 * 7 * 109 * 809
7,169,104 = 2^4 * 17 * 26,357
18,048,976 = 2^4 * 11 * 102,551
18,656,380 = 2^2 * 5 * 932,819
46,722,700 = 2^2 * 5^2 * 47 * 9,941
81,128,632 = 2^3 * 13 * 19 * 41,057
174,277,820 = 2^2 * 5 * 29 * 487 * 617
209,524,210 = 2 * 5 * 7 * 19 * 263 * 599
330,003,580 = 2^2 * 5 * 16,500,179
498,215,416 = 2^3 * 19 * 47 * 69,739
```

The first four perfect numbers are 6, 28, 496, 8128.

Two-member loops (amicable pairs) are: ``

```
220 <-> 284
1184 <-> 1210
2620 <-> 2924
5020 <-> 5564
6232 <-> 6368
10744 <-> 10856
12285 <-> 14595
17296 <-> 18416
63020 <-> 76084
66928 <-> 66992
67095 <-> 71145
69615 <-> 87633
79750 <-> 88730
100485 <-> 124155
122265 <-> 139815
122368 <-> 123152
141644 <-> 153176
142310 <-> 168730
171856 <-> 176336
176272 <-> 180848
185368 <-> 203432
196724 <-> 202444
```

(Exhaustive to smaller member <= 196724 and larger member < 2^35.)

A prime decade is where N+1, N+3, N+7 and N+9 are all prime. The first occurrence of two prime decades with the theoretical minimum separation is N = 1006300 and N = 1006330. The 335th prime decade is N = 2342770. There are 172400 primes < 2342770.

The joys of 239 are as follows:

*pi*= 16 arctan (1/5) - 4 arctan(1/239),- which is related to the fact that 2 * 13^4 - 1 = 239^2,
- which is why 239/169 is an approximant (the 7th) of sqrt(2).
- arctan(1/239) = arctan(1/70) - arctan(1/99) = arctan(1/408)
- arctan(1/577)

- 239 needs 4 squares (the maximum) to express it.
- 239 needs 9 cubes (the maximum, shared only with 23) to express it.
- 239 needs 19 fourth powers (the maximum) to express it.
- (Although 239 doesn't need the maximum number of fifth powers.)
- 1/239 = .00418410041841..., which is related to the fact that
- 1,111,111 = 239 * 4,649.
- The 239th Mersenne number, 2^239 - 1, is known composite, but no factors are known.
- 239 = 11101111 base 2.
- 239 = 22212 base 3.
- 239 = 3233 base 4.
- There are 239 primes < 1500.
- K239 is Mozart's only work for 2 orchestras.
- Guess what memo this is.
- And 239 is prime, of course.

A 2-counter machine, given N in one of the counters, cannot generate 2^N. Proven Saturday, Sept. 26, 1970. (Independently rediscovered by Frances Yao). But (Minsky, Liknaitzky), given 2^N, it can generate 2^{2}N. (A 2-counter machine has a fixed, finite program containing only the instructions "ADD 1", "SUBTRACT 1", "JUMP IF NOT ZERO", which refer to either of two limited counters. Such machines are known universal, but (due to the above) they must have specially encoded inputs.)

What effort is required to compute *pi*(X), the number of primes < X? Shanks and Brillhart claim about X^.7.

See space-filling curve machine item in TOPOLOGY section.

Regarding "poker coins" game, whose rules are:

- a player throws N coins; he then puts one or more aside and rethrows the rest
- this throwing is repeated until he no longer has any to throw
- highest score (dice) or maximum number of heads (coins) wins

For poker coins, the optimal strategy, with N coins thrown, is:

Z = number of zeros (tails)

- if Z = 0, quit
- if Z = 1, throw the zero
- if 1 < Z < N, save one one, throw the other N-1 coins
- if Z = N, save a zero, throw the other N-1 coins

The optimal strategy for poker dice is hairier.

PROBLEM: Solve *Blackout*, a game as follows:

Two players alternate placing X's on a rectangular grid. No two X's may appear adjacent along a side or across the diagonal at a corner. The last X wins.

Some theory: The "indicator" for a position is: make all possible moves from the given position.

Evaluate the indicator of each of these successor positions.

The indicator of the first position is the smallest number which is not the indicator of a successor position. The indicator of the null position is 0. The second player wins iff the indicator is 0. Example of calculating an indicator for the 3 x 3 board: There are 3 distinct moves possible -- corner, side, center. Playing in the center leaves the null position, indicator 0. Playing on the side leaves a 1 x 3 line, indicator 2. Playing in the corner leaves a 3 x 3 L, indicator 3. The smallest number not appearing in our list is 1, so the indicator of a 3 x 3 square is 1. For two boards (not touching) played simultaneously, the indicator is the XOR of the indicators for the separate boards. For any position, the indicator is <= the maximum game length.

PROBLEM: Find some non-exponential way to compute the indicator of a given position. For lines, a period of 34 is entered after the line is about 80 long. For Ls: if one leg is held fixed, the indicator (as a function of the other leg) seems to become periodic with period 34. The time to enter the period becomes greater as the fixed leg increases.

- On an odd x odd board, the 1st player wins.
- On a 4 x N board, the 2nd player wins.
- On a 6 x 6 board, the 1st player wins by playing at the center of one quarter.

This indicator analysis is similar for many other take-away games, such as *Nim.*

Berlekamp of Bell Labs has done the 9 squares (16 dots) *Dots* game; the 2nd player wins.

A neat chess problem, swiped from "Chess for Fun and Chess for Blood", by Edward Lasker:

white: pawns at QN3 and KN7, knight at QN4, bishop at KB7, king at QB2;

black: pawn at QN3, king at QR6. White mates in three moves.

There is only one distinct solution to the commercial "Instant Insanity" colored-faces cubes puzzle, which is how it comes packed. (Independently discovered by Dave Plumer.) Mike Paterson has discovered a clever way to solve the puzzle.

A *window-dice* game is as follows:

- The player starts with each of nine windows open, showing the digits 1 - 9.
- Roll two dice.
- Cover up any digits whose sum is the sum on the dice.
- Iterate throwing and closing windows until the equality of sums is impossible.
- Your score is the total of closed windows (highest wins).

An optimum strategy has been tabulated. Usually it is best to take the largest digits possible, but not always; it also depends critically on the remaining numbers.

*Sim* is a game where two players alternately draw lines connecting six dots. The first person can always win, and whether his first move connects with the first player's first move doesn't matter; from there on, however, the strategy branches to a relatively gruesome degree.

PROBLEM: 6 dots is minimum to ensure no stalemate with 2 players; how many dots are required with 3 players?

The 4 x 4 game of Nim, also known as *Tactix*, is a win for the second player, who on his first move can reply center-symmetrically unless the first player's first move was B1 and B2 (analyzed on RLE PDP-1).

A 1963 PDP-1 computer program gave us some interesting data on the traditional game of *peg solitaire* (33 holes in a plus shape). ``

```
A B C
D E F
G H I J K L M
N P Q . S T U
V W X Y Z 1 2
3 4 5
6 7 8
```

From the starting position, complement the board. This is the ending position. Now from the starting position, make one move, then complement the board. This is a position one move from a win. By induction, you can win from the complement of any position you can reach. Thus every successful game has a dual game whose positions are the complements of the original ones. This debunks the heuristic of emptying the arms of the plus first and then cleaning up the middle, because there are just as many dual games which empty out the middle first and then the arms! The program found one counterintuitive win which at one point left the center nine empty but had ten in the arms. ``

```
. B .
D E .
. . . . . . .
. P . . . T U
V W . . . . .
. 4 .
. 7 .
```

By dualizing and permuting a solution from the folklore, we found a similar winning position with 20. (T Q 4 R 1 L J H W Y M J) leaves: ``

```
A B C
D E F
G H . . . L .
N . . . . . U
V W . . . 1 2
3 . 5
6 7 8
```

then (8 V A C/B 2 6 G M F/K S 8 1 Y V 3 Q A H E).

Another useful observation is that the pegs and their original hole positions fall into four equivalence classes in which they stay throughout the game. Thus the four pegs which can reach the center on the first move are the only ones that ever can. Similarly, the peg jumped over on the last move must be in one of the two classes of eight members which get reduced on the first move. The program's main heuristic was to reduce the larger classes first. ``

```
a b a
c d c
a b a b a b a
c d c . c d c
a b a b a b a
c d c
a b a
```

With its heuristics disabled, the program simply scanned lexicographically (left to right in the inner loop, then top to bottom) for a peg which could move. At one point, there is a peg which can move two ways; it chose west. Twelve moves from the end it stopped and went into an exhaustive tree search, in which it found two basically different wins. (Try it yourself.) ``

```
. . .
. . .
. . . . K . .
. . Q . . . .
. . X Y Z 1 2
3 4 5
6 7 8
```

Triangular *Hi-Q* (or peg solitaire) is 15 pegs in a triangle. Once peg is removed, and thereafter pegs jump others, which are removed. With pegs numbered 1 at the top, 2 and 3 in the next row, etc., ``

```
REMOVE CAN END WITH ONLY THE PEG
1 1, 7 = 10, 13
2 2, 6, 11, 14
4 3 = 12, 4, 9, 15
5 13
```

Removing only one, no way exists to get to either 1 + 11 + 15 (tips) or 4 + 6 + 13 (centers of sides). Starting with peg 1 removed, 3,016 positions are attainable (not turning board); the sum of ways to get to each of these is 10,306. An example is: remove peg 1, then jump as follows: 6, 13, 10, 1, 2, 11, 14/13, 6, 12/13, 15, 7/4, 13, 4; leaving peg 1.

Count the polyominos up to, say, order 20. From *Applied Combinatorial Mathematics,* pages 201 and 213: ``

```
ORDER E. H. NOT ENCLOSING HOLES
1 1 1
2 1 1
3 2 2
4 5 5
5 12 12
6 35 35
7 108 107
8 369 363
9 1285 1248
10 4655 4271
11 17073
12 63600
13 238591
14 901971
15 3426576
16 13079255
17 50107911
18 192622052
```

The order 13 through 18 data is from *Computers in Number Theory,* 1971, Atkin & Birch, ed., Academic Press, which has not been independently checked. It also gives bounds 3.72 < limit as N goes to infinity of Nth root of number of polyominos of order N (including those enclosing holes) < 4.5. Also an asymptotic formula for the number of polyominos:

```
N -.98+-.02
4.06 * (N ) * constant.
```

Polyominos may be constructed in 3-space (Soma-like) pieces) or higher dimensions; a curious thought is into how many dimensions does the average, say, 20-omino extend?

Solve "minichess", chess played on a 5 x 5 board where each side has lost the king's rook, knight, bishop, and 3 pawns, and the opponents are shoved closer together (1 empty row intervening, no double pawn moves).

Solve the tiger puzzle, a sliding block puzzle mentioned in *Scientific American* February 1964, pages 122-130.

Find smallest *squared square* (a square composed entirely of smaller, unequal squares). Smallest known has 24 small squares (Martin Gardner's *Scientific American* Book, vol. 2, page 206). See also the following two illustrations. Recently, someone constructed a squared rectangle with sides in the ratio 1:2. It contains 1353 squares.

Figure 3(a). The smallest known (in 1961, and yet today as far as we know) squared square. Reprinted by special permission from Martin Gardner, *The Second Scientific American Book of Mathematical Puzzles and Diversions,* 1961, Simon and Schuster, New York, New York.

Figure 3(b). A squared rectangle found by Schroeppel using "String Handling Interpretive Translator", a string processing language written by Samson. Sides are 884808 = 2^3 * 3^2 * 12289 and 752225 = 5^2 * 30089; semiperimeter is 1637033 = 419 * 3907. this has 28 squares, which is more than most published squared rectangles.

Count the magic squares of order 5. There are about 320 million, not counting rotations and reflections.

List (that is, count) the semigroups of 7 elements; also, the groups of 256 elements (estimated: 11000).

Compute the integer-valued step function F(R), 0<R<1, the number of circles of radius R which fit into a unit circle. F skips the value 6, and probably 18. How many and how big are the gaps in the range of F? What happens in n dimensions (including n = infinity)?

Solve pentominos on an 8 x 8 checkerboard game(s).

Rules:

- The checkerboard is for aid in orienting only; black and white are the same.
- The two players may each have a full complement of 12 pentominos, or they may "choose up" their half of one set.
- Players alternate placing pentominos on the board. Pentominos must not overlap.
- The last player to place a pentomino wins.

With regard to dissection theorems, the following are known: a triangle into a square, 4 pieces (proven minimal); a pentagon into a square, 6 pieces (best known) etc. ("Geometric Dissections" by Harry Lindgreen, *Scientific American* November 1961). A program can probably check the known dissections for minimality! See following illustration, for example.

Figure 4. A surprising square <--> hexagon dissection, adapted from page 164 of the November, 1961 issue of *Scientific American,* which see for further diagrams and discussion.

Find the number of *domino coverings* for various objects. for example, an asymptotic formula is known for rectangles; also, on a square board, if side mod 4 = 0, coverings appears to be a square; on a square board, if side mode 4 = 2, coverings appears to be twice a square. See *Applied Comb. Math.,* chap. 4.4-4.6, p. 105-121. Article by E. W. Montroll.

Analyze *giveaway chess,* which is as follows:

- captures must be made, although you can choose which capture to make
- pawns must be promoted to queens
- king is just another piece
- player to give away all pieces first wins

Analyze "escalation chess", where white gets 1 move, black 2, white 3, etc. If a player is in check, he must get out of check on his first move. He may not move into check. Taking your opponent's king is verboten, but you can pile up triple checks, etc. A player is checkmated if he can't get his king out of check on his first move.

In the game "4 pawns", black has 4 pawns, a king, and two moves to white's one. Prove the pawns win. The object in this game is to capture the king. Black is allowed to move through check.

Solve Scarne's game, "Teeko", which is played on a 5 x 5 board by two players who alternate placing, one at a time, their 4 counters each, after which the counters are moved around (including diagonally). 4 in a row or square wins.

Solve "five-in-a-row" on an infinite board.

Solve *Tic-Tac-Toe* on a 4 x 4 x 4 board. The consensus is a win for the first player, but it's unproven. The first player wins on 4 x 4 x 4 x 4.

Solve *checkers.* There are about 10^12 positions. (Computing time currently estimated (Schroeppel) at 1 year).

Programs below this line are considered unfeasible.

Solve *Hex* on large boards (11 to 23 on a side); through order 7 have been analyzed by hand. There is a proof that in games where having an extra move can never (repeat: never) hurt you, the worst the first player can be forced to do is draw. Thus, with *Hex,* in which there is no draw, the first player can always win.

Solve *chess.* There are about 10^40 possible positions; in most of them, one side is hopelessly lost.

Solve *Go.* About 10^170 positions.

Simple proofs that certain continued fractions are sqrt(2), sqrt(3), etc. Proof for sqrt(2):

```
X = [1, 2, 2, 2, ...]
(X-1) (X+1) = [0, 2, 2, 2, ...] * [2, 2, 2, 2, ...] = 1
2
X - 1 = 1
X = sqrt(2)
```

Proof for sqrt(3):

```
Y = [1, 1, 2, 1, 2, ...]
(Y + 1) (Y - 1) = [2, 1, 2, 1, 2, ...] * [0, 1, 2, 1, 2, ...]
= 2 * [1, 2, 1, 2, 1, ...] * [0, 1, 2, 1, 2, ...] = 2
2
Y - 1 = 2
Y = sqrt(3)
```

Similar proofs exist for sqrt(5) and sqrt(6); but sqrt(7) is hairy.

The continued fraction expansion of the positive minimum of the factorial function (about 0.46) is

`[0, 2, 6, 63, 135, 1, 1, 1, 1, 4, 1, 43, ...].`

The value of a continued fraction with partial quotients increasing in *arithmetic progression* is ``

```
I (2/D)
A/D
[A+D, A+2D, A+3D, ...] = -------------
I (2/D)
1+(A/D)
```

where the `I`

's are Bessel functions. A special case is ``

```
I (2)
0
[1, 2, 3, 4, ...] = ----- .
I (2)
1
```

``

```
n
/===
! ! 1
! ! (1 + --) =
! ! Ak
k = 1
1 (A1 + 1)A1 (A2 + 1)A2 (A(n-1) + 1)A(n-1)
1 + ----- ---------- ---------- ... ------------------ .
A1 - A1+A2+1 - A2+A3+1 - A(n-1)+An+1
```

On the theory that continued fractions are underused, probably because of their unfamiliarity, I offer the following propaganda session on the relative merits of continued fractions versus other numerical representations. For a good cram course in continued fractions, see Knuth, Volume 2, page 316 [1st Edition; s.4.5.3, p. 339 in 2nd Edition]. (In what follows, "regular" means that all numerators are 1, and any radix can be read in place of decimal.)

*pi*is 3. But not really 3, more like 3 + 1/7. But not really 7, more like 7 + 1/15. But not really 15, ... . So the regular continued fraction for*pi*is written 3 7 15 1 292 1 1 ... .The continued fractions for rational numbers always come out even, and rather quickly. Thus, the number of inches per meter is exactly 100/2.54 or 39 2 1 2 2 1 4. The corresponding decimal fraction is 39.3700787... has period 42, making it almost impossible to tell if the number is rational. (But if our data are ALL rational, the ordered pair 5000/127 is even more concise.)

Quadratic surds, which are of course inexpressible as rationals, are generally unrecognizable in decimal. Their continued fractions, on the other hand, are periodic. Nth roots of

*e*^2, ratios of Bessel functions, and ratios of linear functions of these all have regular continued fractions formed by interleaving one or more arithmetic sequences. These special properties will show up regardless of number base. You might recognize 5.436563... as 2*e*, but even Schroeppel might not notice that 6.1102966796... was ``2/3 4 e - 2 ---------- 2/3 e - 1

until he wrote it as 6 9 15 21 27 33 ... .

The familiar transcendental functions of rational arguments also have simple continued fractions, but these are generally not regular and cannot be reconstructed from numerical values by a simple algorithm, since nonregular representations aren't unique. The point is, however, that numbers like *e,* *pi,* sqrt(2), sin .5, sqrt(7) arctan sqrt(7), etc. can be expressed to unlimited precision by simple programs which produce the terms on demand.

- If we define a rational approximation to be "best" if it comes closer than any other rational with such a small denominator, then continued fractions give the complete set of best rational approximations to the value which they represent. That is, if you truncate a (regular) continue fraction at any point, then the resulting rational number is a best approximation. Furthermore, this remains true if the last term of the approximation is replaced by any smaller positive integer other than

All best approximations can be generated in this manner, in order of increasing denominators (or numerators). For example, the approximants to

*pi*= 3 7 15 1 292 ... are: ``3: 1/1, 2/1, 3/1 7: (4/1), 7/2, 10/3, 13/4, 16/5, 19/6, 22/7 15: (25/8), 47/15, 69/22, 91/29, 113/36, ... 311/99, 333/106 1: 355/113

... ...

Note that they are all automatically in lowest terms. the size of a denominator is greater than the product of the terms involved and less than the product of the numbers 1 greater than the terms. The approximations are low if the number of terms is odd, high if it's even. (Note that if a 1 ends a continued fraction, it should be added in to the previous term. Thus, to "round off" a continued fraction after a certain term, add in the next term iff it is +-1. In the above, 4/1 and 25/8 correspond to termination with a 1 and are not "best"; 355/113 is "best" because the corresponding term really should be 1.) The error is smaller than 1 over the product of the denominator squared and the first neglected term, so that the total number of digits (numerator and denominator) is usually slightly smaller than with equally accurate decimal fractions. 355/113 is good to 7.5 places instead of 5.5, due to the unusually large term (292) which follows.

Numerical comparison of continue fractions is slightly harder than in decimal, but much easier than with rationals -- just invert the decision as to which is larger whenever the first discrepant terms are even-numbered. Contrast this with the problem of comparing the rationals 113/36 and 355/113.

Regular continued fractions are in 1 to 1 correspondence with the real numbers, unlike decimal (.5 = .49999...) or rationals (2/3 = 6/9, sqrt(6) = ?). Even

*infinity*has a continued fraction, namely, the empty one! (Minus and plus infinity are the same in continued fraction notation.)Each representation favors certain operations. Decimal favors multiplication by powers of 10. Rationals favor reciprocation, as do continued fractions. To reciprocate a regular continued fraction, add (or if possible, delete) and initial 0 term. To negate, negate all the terms, optionally observing that

-a, -b, -c, -d ... = -a-1, 1, b-1, c, d ... .

- The strongest argument for positional (e.g., decimal or floating) representation for non-integers is that arithmetic is easy. Rational number arithmetic often loses because numerators and denominators grow so large as to require icky multiprecision. Algorithms for arithmetic on continued fractions seem generally unknown. The next items describe how to arithmetically combine continued fractions to produce new ones, one term at a time.

Unfortunately, the effort required to perform these operations manually is several times that for decimal, but the rewards for machine implementation are considerable (which can also be said of floating point). Specifically, these rewards will be seen to be: unlimited significance arithmetic without multiprecision multiplication or division, built in error analysis, immorally easy computation of algebraic functions, no unnecessary computations, no discarding of information (as with roundoff and truncation), reversibility of computations, and the terms of the answer start to come out right away and continue to do so until shut off.

Continued fractions let us perform numerical calculations a little at a time without ever introducing any error, such as roundoff or truncation. As if this weren't enough, the calculations provide automatic error analysis, and obviate most forms of successive approximation. This means we can start with an arithmetic expression like

```
sqrt(3/pi^2 + e)
-----------------------
tanh(sqrt(5)) - sin(69)
```

and immediately begin to produce the value as a sequence of continued fraction terms (or even decimal digits, if we should be so reactionary), limited only by time and storage. If there are quantities in the expression which are known only approximately, the calculation can provide error bounds on the answer as well as identify the quantity that limited the significance.

All this is possible because each operation (+, /, -, sqrt) in the arithmetic expression requests terms from the continued fractions of its operands only when necessary, and consequently produces terms of its own value as soon as possible. Numbers like *pi* and *e* and functions like `sin`

and `tanh`

have continued fraction terms in simple sequences which can be produced by short programs. Imprecise quantities can also be programs which deliver terms until they run out of confidence, whereupon they initiate special action. By then, the last guaranteeable term of the overall expression will have already been produced.

We see then that no calculation is performed unnecessarily, so that, for example, a subexpression which happened to be multiplied by zero would never be evaluated. Also, an operation detecting a deficiency in two or more of its operands provides a natural mechanism for allocating multiprocessor resources, should you have some.

Here are the algorithms for the elementary arithmetic operations on continued fractions.

Let `x`

be a continued fraction

`p0 + q0/(p1 + q1/( ... = p0 + q0/x'`

where `x'`

is again a continued fraction and the `p`

's and `q`

's are integers. We shall call a `(p q)`

pair a "term" of the continued fraction for `x`

. Often, only the `p`

's are mentioned, in which case the `q`

's are implicitly all 1, and x is called a "regular" continued fraction.

Instead of a list of `p`

's and `q`

's, let `x`

be a computer *subroutine* which produces its next `p`

and `q`

each time it is called. Thus on its first usage `x`

will "output" `p0`

and `q0`

and, in effect, change itself into `x'`

. Similarly, let `y`

be another procedurally represented continued fraction `r0 + s0/y'`

. Our problem will be solved if we can write such subroutines for `z(x,y)`

= `x+y`

, `x-y`

, `x y`

, and `x/y`

. When called upon to output a term of `z`

, the subroutine might in turn call for (or "input") terms from `x`

and `y`

until it is satisfied that the unread portions of `x`

and `y`

cannot affect the pending term of `z`

. Then it would output this term and change itself into `z'`

, so that it could produce the next term next time. Unfortunately, when we try to do this, our expressions quickly complicate. Let us preempt this complication by computing instead the more general function

`z(x,y) = (a x y + b x + c y + d) / (e x y + f x + g y + h)`

(or

`(a b c d) / (e f g h)`

for short)

where `a`

through `h`

are integer variables whose initial values we are free to choose. Various choices express ``

```
addition: x + y = (0 1 1 0) / (0 0 0 1),
subtraction: x - y = (0 1 -1 0) / (0 0 0 1),
multiplication: x y = (1 0 0 0) / (0 0 0 1),
division: x / y = (0 1 0 0) / (0 0 1 0).
```

As we shall see, the process of inputting terms of `x`

and `y`

and outputting terms of `z`

will reduce to replacing the eight integers `a`

through `h`

with linear combinations of each other.

When `z`

inputs a term of `x`

, `z`

becomes a new function of `x'`

. To see how this happens, substitute `p + q/x'`

for every occurrence of `x`

in the expression for `z(x,y)`

, then multiply numerator and denominator through by `x'`

:

`z(x',y) = (pa+c pb+d qa qb) / (pe+g pf+h qe qf).`

If `x`

was rational and has run out of terms, it has in effect become infinite:

`z(infinity,y) = (0 0 a b) / (0 0 e f)`

If instead we input a term of `y`

by substituting `r + s/y'`

for every occurrence of `y`

:

`z(x,y') = (ra+b sa rc+d sc) / (re+f se rg+h sg).`

If `y`

runs out of terms:

`z(x,infinity) = (0 a 0 c) / (0 e 0 g)`

To output the term `(t u)`

, so that `z = t + u/z'`

(i.e., `z' = u/(z-t)`

):

`z'(x,y) = (ue uf ug uh) / (a-te b-tf c-tg d-th).`

Thus this basic eight variable form is preserved by all three operations, which can be performed in any order since they represent independent substitutions.

For simplicity, let us assume that `z`

will output in standard form, that is, every `u`

= 1 (regular) and every output term `t`

>= 1 except perhaps the first. This means that `z'`

will always exceed 1 and thus 0 <= `u/z'`

< 1, so that the integer `t = z - u/z'`

must = `[z]`

, the greatest integer <= `z`

.

Since `z`

generally varies with `x`

and `y`

, it should not output unless `[z]`

is constant for the range of possible `x`

and `y`

. We can easily compute the range of given the ranges of `x`

and `y`

if we represent each range by the endpoints of an interval (in either order), along with a bit indicating *Inside* or *Outside*. Thus if `z`

is in standard form, we can say that `z`

will always be (Inside 1 infinity) (or (Outside -infinity 1)) after the first term. If `z`

were to always output its nearest integer instead of is greatest, then none of the terms after the first would be 1, although they would probably vary in sign. In this case, `z`

would be (Outside -2 2).

Now hold `y`

fixed and examine the behavior of `z`

with `x`

. If `x`

is (Inside `a`

`b`

) then `z`

is (Inside `z(a)`

`z(b)`

) unless the denominator of `z`

changes sign between `a`

and `b`

(i.e., `z`

has its pole in this interval), whereupon `z`

is (Outside z(a) z(b)). Symmetrically, when `x`

is (Outside `a`

`b`

) then `z`

is (Outside `z(a)`

`z(b)`

) unless the signs of the denominators of `z(a)`

and `z(b)`

differ, whereupon `z`

is (Inside `z(a)`

`z(b)`

). This argument still holds with `x`

and `y`

interchanged.

Now suppose that with `y`

fixed at one if its endpoints, `x`

constrains `z`

(Inside 1 2), and at `y`

's other extreme, `z(x)`

is `z(y)`

is (Outside 0 3). Suppose further that at the two extremes of `x`

, `z(y)`

is (Inside 1 3) and (Outside 0 2). Then `z(x,y)`

is (Outside 0 1), the union of the four ranges. (Outside 0 2) is the widest, indicating that `z`

will probably get more information from a term of `y`

than a term of `x`

. (Topology hackers should recognize this Inside-Outside nonsense as ordinary intervals in toroidal space. The clue is that both plus and minus infinity are denoted by the empty continued fraction.)

Due to the basically monotonic behavior of `z`

, we can guarantee that the actual range of `z`

will be the union of these four ranges, and that this range will be Inside or Outside some interval. If it is (Inside `z1`

`z2`

) and `[z1]`

= `[z2]`

, `z`

can output the term `t`

= `[z1]`

. Otherwise, `z`

must input a term from `x`

or `y`

, whichever was associated with the widest of the four ranges of `z`

. (Outside narrowness) is wider than (Outside wideness) is wider than (Inside wideness) is wider than (Inside narrowness).

Evaluating `z`

on these endpoints may be facilitated by keeping estimates for the integer variables in floating point.

Even if `z`

doesn't produce a term, narrowing the range of possible `z`

will still help in computing the range of a function of `z`

, especially if `z`

gets stuck trying to output the last term of a rational number resulting from irrational `x`

and `y`

. (There is no way to guarantee that `x`

or `y`

won't eventually deviate, whereupon `z`

would egest a gigantic term.)

`z`

can produce its value as decimal digits by multiplying by 10 instead of reciprocating, after outputting `t`

= `[z]`

:

`z'(x,y) = (10(a-te) 10(b-tf) 10(c-tg) 10(d-th)) / (e f g h).`

Strange to say, it is not serious if `z`

for some reason outputs the terms 7 5 1 when it should have produced 6 9. As soon as permitted, it will simply recant with 0 -1 -5 and continue with the correction -1 9. The sequence 7 5 1 0 -1 -5 -1 9 is equivalent to 6 9 because `b`

0 `c`

is the same as `b+c`

. In order to undo these computations, `z`

violates the condition (Outside -1 1) when it is 0 -1 -5 ... . This condition is obeyed by nearly all convergent continued fractions after their first term, and its violation will very probably cause further retractions among the functions dependent upon `z`

.

This computation reversal trick is also handy for mechanizing and denoting imprecise quantities. Instead of 2.997930+-.000003, we have 2 1 481 0 2, meaning between 2 1 481 and 2 1 483. Similarly, 137 26 0 1 replaces 137.0373+-.0006.

Successive approximations methods benefit considerably from not requesting terms until needed. Consider Newton's method for algebraic roots. We expect successive approximations to have about twice as many correct terms each time. Since the production of these terms cannot be aided by reading incorrect terms, the additional correct terms must be produced before the bad ones of the previous approximation are used. But this means that there is no need to read in the bad ones at all. By feeding back the output terms in place of the approximation, we get the correct answer directly! (69% of the credit for this goes to Schroeppel.)

The basic eight variable form exemplified above by `z(x,y)`

is not the only form preserved by continued fraction term transactions. We need only four variables and a single interval check to compute

```
a x + b
z(x) = ------- ,
c x + d
```

the *homographic function* of one argument. On the other hand, `z(w,x,y)`

(linear in all three arguments) requires *sixteen* variables and a *twelve* way interval check. Each of these forms can be solved for `x`

in terms of `z`

etc. to get a function of the same form. This is not true of

```
2
a x + b x + c
z(x) = -------------- ,
2
d x + e x + f
```

for example, even though this form is also preserved. This form is not guaranteed monotone, thus theoretically invalidating the interval check algorithm, but it hardly every errs. Even if it did, it would quickly correct itself anyway. This form is not only more economical than `z(x,x)`

, it is essential for the success of the Newton's method feedback trick, which must know when two variables are really the same one.

By choosing the eight coefficients `a`

through `h`

properly, it should be possible to rewrite arithmetic expressions as compositions of considerably fewer of these forms than one for each +, -, *, and /. The reader is invited to investigate the problem of trying to find minimal representations. Depending on the metric for minimality, the question can be complicated by allowing higher powers of `x`

and `y`

. If the highest powers of `x`

, `y`

, `z`

, ... in an invariant form are `i`

, `j`

, `k`

, .., then the number of integer variables required for the coefficients (mostly because of all the cross terms) is

`2 (i+1) (j+1) (k+1) ... .`

It is awkward in this system to evaluate transcendental functions of irrational arguments. The problem is that you may need any number of continued fraction (or series) terms which, instead of being numbers, are symbolic functions of `x`

, some infinite continued fraction. My suggestion is to represent each symbolic term of the function by a subroutine which is a function of `x`

and the next term, with this next term really a dummy until actually called upon for output, whereupon it replaces itself with a full-fledged term subroutine which in turn refers to `x`

and a new dummy.

Sad to say, the integer variables in these algorithms do not usually shrink on outputs as much as they grow on inputs. Fortunately, the operations for input and output only require (besides addition) multiplication by terms which are almost invariably small. (I have not seen a term exceed 20776 except in specially constructed numbers.) It is fairly safe, then to declare any function which has gotten (Outside -2^35 2^35) to be infinite, thus terminating its continued fraction. Better still, note that the term 20776 is equivalent to the terms 20000 0 700 0 70 0 6, i.e., a very large term can be transmitted piecewise. Although this is just thinly disguised multiprecision multiplication, that first piece of the term will probably satisfy its recipient for quite some time.

In some special cases, the integer variables will become *periodic* rather than large, especially when all by one of the arguments to a function have terminated. Then, we have the form

```
a x + b
z(x) = ------- ,
c x + d
```

known as a *homographic* function. If `ad-bc`

is +-1, then `a`

, `b`

, `c`

, `d`

will eventually become 1, 0, 0, 1, whereupon `z`

will output the terms of `x`

unmodified. Periodicity will also occur when `x`

is a *Hurwitz number,* i.e., when the terms of `x`

are the values of one or more polynomials evaluated on consecutive integers and then interleaved. Coth 1/69, sqrt(105), and *e* are Hurwitz numbers whose polynomials are linear or constant. Hurwitzness is preserved by homographic functions. If one can show that *pi* is a Hurwitz number, one confirms the long standing conjectures that *e***pi,* *e*+*pi,* *e*/*pi,* etc. are all irrational.

If `z`

, `x`

, and `y`

are all regular, then it generally won't be possible to reduce `z`

by finding a GCD of `a`

through `h`

which is > 1. However, it has been determined empirically that much reduction is often possible in other cases. This reduction is almost always by a divisor of an input or output term numerator (or 10 if output is decimal digits) and can be facilitated by keeping certain of the integer variables around modulo these quantities.

Problem: Given an interval, find in it the rational number with the smallest numerator and denominator.

Solution: Express the endpoints as continued fractions. Find the first term where they differ and add 1 to the lesser term, unless it's last. Discard the terms to the right. What's left is the continued fraction for the "smallest" rational in the interval. (If one fraction terminates but matches the other as far as it goes, append an infinity and proceed as above.)

As opposed to the usual formulation of a group, where you are given

- there exists an I such that A * I = I * A = A, and
- for all A, B and C, (A * B) * C = A * (B * C), and
- for each A there exists an A' such that A * A' = A' * A = I, and
- 4 sometimes you are given that I and A' are unique.

If instead you are given A * I = A and A * A' = I, then the above rules can be derived. But if you are given A * I = A and A' * A = I, then something very much like a group, but not necessarily a group, results. For example, every element is duplicated.

The Hamiltonian paths through the N! permutations of N objects using only SWAP (swap any specific pair) and ROTATE (1 position) are as follows: ``

```
N PATHS + DISTINCT REVERSES
2 2 + 0, namely, S, R
3 2 + 1, namely, SRRSR, RRSRR
4 3 + 3, namely:
SRR RSR SRR RSR RRS RSR RSR RR
RSR SRR RSR RRS RSR RRS RSR RR
SRR RSR RRS RRS RSR RRS RRR SR
```

PROBLEM: A questionable program said there are none for N = 5; is this so?

Any permutation on 72 bits can be coded with a routine containing only the PDP-6/10 instructions "ROT" and "ROTC".

Given a set of real numbers, how many sets can you get using only closure and complement? Answer: 14.

A *quaternion* is a 4-tuple which can be regarded as a scalar plus a vector. Quaternions add linearly and multiply (non-commutatively) by

`(S1+V1) (S2+V2) = S1 S2 - V1.V2 + S1 V2 + V1 S2 + V1 x V2`

where S=scalar part, V=vector part, .=dot product, x=cross product.

If Q = S+V = (Q0,Q1,Q2,Q3), then S = Q0, V = (Q1,Q2,Q3). Define *conjugation* by (S+V)* = S-V. The (*absolute value*)^2 of a quaternion is

```
2 2 2 2
Q0 + Q1 + Q2 + Q3 = Q Q* = Q* Q .
```

The non-zero quaternions form a group under multiplication with (1,0,0,0) = 1 as identity and

```
1 Q*
- = ---- .
Q Q* Q
```

The *unit* quaternions, which lie on a 3-sphere embedded in 4-space, form a subgroup. The mapping F(Q) = P Q (P a unit quaternion) is a rigid rotation in 4-space. This can be verified by expressing P Q as a 4x4 matrix times the 4-vector Q, and then noting that the matrix is orthogonal. F(Q) restricted to the *unit* quaternions is a rigid rotation of the 3-sphere, and because this mapping is a group translation, it has no fixed point.

We can define a dot product of quaternions as the dot product of 4-vectors. Then Q1.Q2 = 0 iff Q1 is *perpendicular* to Q2. Let N be a unit *vector.* To each *unit* quaternion Q = S+V, attach the quaternion

`N Q = -N.V + N S + N x V .`

Then it is seen that

`(N Q).(N Q) = N.N = 1 and (N Q).Q = 0 .`

Geometrically this means that N Q is a continuous unit 4-vector field tangent to the 3-sphere. No such tangent vector field exists for the ordinary 2-sphere. Clearly the 1-sphere has such a vector field.

PROBLEM: For which N-spheres does a continuous unit tangent vector field exist?

Let W be a *vector* (quaternion with zero scalar part) and Q = S+V. Then

`Q W Q* = (S^2 + V.V) W + 2 S V x W + 2 V (V.W) .`

Let N be a unit vector and Q the unit quaternion

`Q = +-(cos(theta/2) + N sin(theta/2)) .`

Then

`Q W Q* = (cos theta) W + (sin theta) (N x W) + (1-cos theta) N (N.W) ,`

which is W rotated thru angle theta about N. If Q thus induces rotation R, then Q1 Q2 induces rotation R1 R2. So the projective 3-sphere (+Q and -Q identified) is isomorphic to the rotation group (3x3 orthogonal matrices). Projectiveness is unavoidable since a 2 pi rotation about any axis changes Q = 1 continuously into Q = -1.

Let U be a neighborhood of the identity in the rotation group (ordinary 3 dimensional rotations) and U1 the corresponding set of unit quaternions in the neighborhood of 1. If a rotation R carries U into U', then a quaternion corresponding to R carries U1 into U1'. But quaternion multiplication is a rigid rotation of the 3-sphere, so U1 and U1' have equal volume. This shows that in the quaternion representation of the rotation group, the Haar measure is the Lebesgue measure on the 3-sphere.

Every rotation is a rotation by some angle theta about some axis. If rotations are chosen "uniformly", what is the probability distribution of theta? By the above, we choose points uniformly on the 3-sphere (or *hemisphere* since it is really projective). Going into polar coordinates, one finds

```
2 theta 2
P(theta) = -- (sin -----) , 0 < theta < pi .
pi 2
```

In particular, the *expected value* of theta is

```
pi 2
-- + -- .
2 pi
```

Quaternions form a convenient 4-parameter representation of rotations, since composition of rotations is done by quaternion multiplication. In contrast, 3-parameter representations like Euler angles or (roll, pitch, yaw) require trigonometry for composition, and orthogonal matrices are 9-parameter. In space guidance systems under development at D-lab, the attitude of the spacecraft is stored in the guidance computer as a quaternion.

See the PROPOSED COMPUTER PROGRAMS section for counts of polyominos of orders < 19.

Tessellating the plane with polyominos:

Through all hexominos, the plane can be tessellated with each piece (without even flipping any over). All but the four heptominos below can tessellate the plane, again without being flipped over. Thus, flipping does not buy you anything through order 7. (There are 108 heptominos). ``

```
H H HHH H H
HHHHH H H HHHH HHHH
HH H H
H H
```

PROBLEM: What rectangles are coverable by various polyominos? For example, ``

```
XX can cover rectangles which are 3N x M,
X except if N = 1, then M must be even.
YYYY can be shown by coloring to cover only rectangles
having at least one side divisible by four.
```

PROBLEM: Find a necessary and sufficient condition for an arbitrary shape in the plane to be domino coverable.

"Iamonds" are made of equilateral triangles, like diamonds.

"(Poly-)ominos" are made of squares, like dominos.

"Hexafrobs" are made of hexagons.

"Soma-like" pieces are made of cubes.

See also "Polyiamonds", Math. Games, *Sci. Am.,* December 1964. Left and right 3-dimensional forms are counted as distinct. ``

```
ORDER IAMONDS OMINOS HEXA'S SOMA-LIKE
1 1 1 1 1
2 1 1 1 1
3 1 2 3 2
4 3 5 7 8
5 4 12 22 29
6 12 35
7 24
8 66
9 160
10 448
```

Polyominos of order 1, 2 and 3 cannot form a rectangle. Orders 4 and 6 can be shown to form no rectangles by a checkerboard coloring. Order 5 has several boards and its solutions are documented (*Communications of the ACM,* October 1965): ``

```
BOARD DISTINCT SOLUTIONS
3 X 20 2
4 X 15 368
5 X 12 1010
6 X 10 2339 (verified)
two 5 x 6 -- 2
8 x 8 with 2 x 2 hole in center -- 65
```

CONJECTURE (Schroeppel): If the ominos of a given order form rectangles of different shapes, the rectangle which is more nearly square will have more solutions.

Order-4 hexafrob boards and solution counts:

- side 7 triangle -- no solutions
parallelogram, base 7, side 4 -- 9 distinct solutions, e.g., ``

`A A A A B C C D E B B C F C D E E B F G G D D E F F G G`

Order-6 iamond boards and solution counts (see illustration):

- side 9 triangle with inverted side 3 triangle in center removed -- no solutions
- trapezoid, side 6, bases 3 and 3+6 -- no solutions
- two triangles of side 6 -- no solutions
- trapezoid, side 4, bases 7 and 7+4 -- 76 distinct solutions
- parallelogram, base 6, side 6 -- 156 distinct solutions
- parallelogram, base 4, side 9 -- 37 distinct solutions
- parallelogram, base 3, side 12 --- no solutions
- triangle of side 9 with triangles of side 1, 2 and 2 removed from its corners (a commercial puzzle) -- 5885 distinct solutions

With Soma-like pieces, orders 1, 2 and 3 do not have interesting boxes. Order 4 has 1390 distinct solutions for a 2 x 4 x 4 box. 1124 of these have the four-in-a-row on an edge; the remaining 266 have that piece internal. 320 solutions are due to variations of ten distinct solutions decomposable into two 2 x 2 x 4 boxes. A soma-like 2 x 4 x 4 solution: ``

```
AAAA BBHH
BCCC BHHC
DDDE FGGE
FDGE FFGE
```

The commercial *Soma* has 240 distinct solutions; the booklet which comes with it say this was found years ago on a 7094. Verified by both Beeler and Clements.

Although not new (cf Coxeter, *Introduction to Geometry,* 1st ed. p393), the following coloring number (*chromatic number*) may be useful to have around:

`N = [[(7 + sqrt(48 H + 1))/2]]`

where N is the number of colors required to color any map on an object which has H holes (note: proof not valid for H = 0).

For example:

- A donut (holes = 1) requires 7 colors to color maps on it.
- A 17-hole frob requires 17 colors.
- An 18-hole frob requires 18 colors.

A most regular 7-coloring of the torus can be made by tiling the plane with the following repeating pattern of hexagons of 7 colors: ``

```
A A C C E E
A A A C C C E E E
A A F F C C A A E E
F F F A A A
B B F F D D A A F F
B B B D D D F F F
B B G G D D B B F F
G G G B B B
C C G G E E B B G G
C C C E E E G G G
C C A A E E C C G G
A A A C C C
D D A A F F C C A A
D D D F F F A A A
D D B B F F D D A A
B B B D D D
E E B B G G D D B B
E E E G G G B B B
E E C C G G E E B B
C C C E E E
C C E E
```

Draw an area 7 unit cell parallelogram by connecting, say, the center B's in each of the four ``

```
B B
B B B 's.
B B
```

Finally, join the opposite sides of the parallelogram to form a torus in the usual (Spacewar) fashion. QUESTION (Gosper): is there a toroidal heptahedron corresponding to this?

A spacefilling curve is a continuous map T -> X(T),Y(T), usually from the unit interval onto the unit square, often presented as the limit of a sequence of curves made by iteratively quadrisecting the unit square. Each member of the sequence is then 4 copies of its predecessor, connected in the shape of an inverted V, with the first member being a V which connects 0,0 to 1,0. The limiting map, X(T) and Y(T), can be computed instead by a simple, finite-state machine having 4 inputs (digits of T base 4), 4 outputs (one bit of X and one bit of Y), and 4 states (2 bits) of memory (the number modulo 2 of 0's and 3's seen in T).

Let T, X, and Y be written in binary as: ``

```
T=.A B A B A B ... X=.X X X X X X ... Y=.Y Y Y Y Y Y ...
1 1 2 2 3 3 1 2 3 4 5 6 1 2 3 4 5 6
```

ALGORITHM S: ``

```
C <- 0 ;# of 0's mod 4
0
C <- 0 ;# of 3's mod 4
1
S1: X <- A XOR C ;Ith bit of X
I I NOT B
I
Y <- X XOR B ;Ith bit of Y
I I I
C <- C XOR (NOT A AND NOT B ) ;count 00's
0 0 I I
C <- C XOR (A AND B ) ;count 11's
1 1 I I
GO S1
OLD NEW
C C A B X Y C C
0 1 I I I I 0 1
0 0 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 0 1 0 1 1 0 0
0 0 1 1 1 0 0 1
0 1 0 0 1 1 1 1
0 1 0 1 0 1 0 1 This is the complete
0 1 1 0 0 0 0 1 state transition table.
0 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0
1 0 0 1 1 0 1 0
1 0 1 0 1 1 1 0
1 0 1 1 0 1 1 1
1 1 0 0 1 1 0 1
1 1 0 1 1 0 1 1
1 1 1 0 0 0 1 1
1 1 1 1 0 1 1 0
```

To carry out either the forward or reverse map, label a set of columns as in the table above. Fill in whichever you know of AB or XY, with consecutive rows corresponding to consecutive 1's. Put 0 0 in the top position of the OLD CC column. Exactly one row of the above table will match the row you have written so far. Fill in the rest of the row. Copy the NEW CC entry to the OLD CC column in the next row. Again, only one row of the state table will match, and so forth. For example, the map 5/6 -> (1/2,1/2) (really .11010101... -> (.1000... ,.0111...)): ``

```
OLD NEW
C C A B X Y C C
0 1 I I I I 0 1
0 0 1 1 1 0 0 1
0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1
. . . . . . . .
. . . . . . . .
= 5/6 1/2 1/2
```

We note that since this is a one-to-one map on bit strings, it is not a one-to-one map on real numbers. For instance, there are 2 ways to write 1/2, .1000... and .0111..., and thus 4 ways to write (1/2,1/2), giving 3 distinct inverses, 1/6, 1/2, and 5/6. Since the algorithm is finite state, X and Y are rational iff T is, e.g., 898/4369 -> (1/5,1/3). The *parity number,* (see SERIES section) and 1-(parity number) are the only reals satisfying X(T)=T, Y(T)=1. This is related to the fact that they have no 0's and 3's base 4, and along with 0, 1/2, and 1=.111..., are the only numbers preserved by the deletion of their even numbered bit positions.

```
inf
====
N! N! 4 2 pi
> ------ = - + --------- .
/ (2 N)! 3 9 SQRT(3)
====
N=0
```

PROBLEM: Evaluate in closed form

```
inf
====
N! N! N!
> -------- , which =
/ (3 N)!
====
N=0
1
/
[
I (P + Q arccos (R)) dT , where
]
/
0
2 3
2 (8 + 7 T - 7 T )
P = ------------------- and
2 3 2
(4 - T + T )
2 2 3
4 (T - T ) (5 + T - T )
Q = ------------------------------------------ and
2 3 2 2 3
(4 - T + T ) SQRT((4 - T + T ) (1 - T))
2 3
T - T
R = 1 - ------- .
2
```

```
2 3 4
X X X
gamma = - ln X + X - ---- + ---- - ---- ... + ERROR
2 2! 3 3! 4 4!
```

Where ERROR is of the order of (*e*^-X)/X.

Differentiate

```
-Y
Y E = X to get Y + Y X Y' - X Y' = 0.
```

Substitute for Y a power series in X with coefficients to be determined. One observes the curious identity:

```
N
====
J - 1 N - J N 0
> J (N - J) BINOMIAL(N, J) = N (0 = 1)
/
====
J=1
```

and thus

```
==== N - 1 N
N X
Y(X) = > ---------
/ N!
====
N=1
```

PROBLEM: Can someone square some series for *pi* to give the series

```
2 ====
pi 1 1 1
-- = -- + -- + ... = > -- ?
6 2 2 / 2
1 2 ==== N
```

The series accelerating transformation

(Abramowitz & Stegun, se. 3.6.27)

```
==== K K
(-1) (delta A0)
A0 - A1 + A2 - ... = > -----------------
/ K+1
==== 2
K
====
K K-m
(where (DELTA A0) = > BINOMIAL(K, m) (-1) Am = Kth forward difference on A0)
/
====
m=0
```

when applied to

```
pi 1 1
-- = 1 - - + - - ...
4 3 5
```

gives

```
==== N-1 2
pi 2 N!
-- = > ----------
4 / (2 N + 1)!
====
N=0
```

Applied to the formula for *gamma* in *Amer. Math. Monthly* (vol. 76, #3, Mar69 p273) =

```
==== T
(- 1) [LOG2(T)]
> ---------------- ([ ] means integer part of)
/ T
====
T=0
```

we get

```
inf K-1
==== ====
-(K+1) 1
> 2 > ------------------
/ / I
==== ==== BINOMIAL(2 + J, J)
K=1 J=0
```

(Gosper) which converges fast enough for a few hundred digits.

The array of reciprocals of the terms follows, with powers of 2 factored out to the left from all member of each row. ``

```
4 1
8 1 3
16 1 5 6
32 1 9 15 10
64 1 17 45 35 15
128 1 33 153 165 70 21
256 1 65 561 969 495 126 28
```

The next to left diagonal is 2^(N+1); the perpendicular one 3rd from the right is 1, *9/1= 9, *10/2= 45, *11/3= 165, *12/4= 495.

Consider the triangular array: ``

```
1
1 1
1 4 1
1 11 11 1
1 26 66 26 1
1 57 302 302 57 1
```

This bears an interesting relationship to Pascal's triangle. The 302 in the 4th southeast diagonal and the 3rd southwest one = 4*26 + 3*66. Note that rows then sum to factorials rather than powers of 2. If the nth row of the triangle is dotted with any n consecutive elements of (either) n+1st diagonal of Pascal's triangle, we get the nth Bernoulli polynomial: for n = 5, 1(6,i) + 26(6,i+1) + 66(6,i+2) + 26(6,i+3) + 1(6,i+4) = sum of 5th powers of 1 thru i+5, where (j,i) = BINOMIAL (j+i j).

The "parity number" =

```
inf
====
1 PARITY(N)
- > ---------
2 / N
==== 2
N=0
```

where the parity of N is the sum the bits of N mod 2. The parity number's value is .4124540336401075977..., or, for hexadecimal freaks, .6996966996696996... . It can be written (base 2) in stages by taking the previous stage, complementing, and appending to the previous stage:

```
.0
.01
.0110
.01101001
.0110100110010110
.01101001100101101001... radix 2
```

i.e.,

```
stage 0 = 0
N
-2
1 - 2 - stage N
stage N+1 = stage N + ----------------- .
N
2
2
```

If

```
NUM 0 = 0, DEN 0 = 2
NUM N+1 = ((NUM N)+1) * ((DEN N)-1)
N+1
2 2
DEN N+1 = (DEN N) = 2
```

then

```
N N
NUM N+1 -2 -2
------- = stage N+1 = (stage N + 2 ) * (1 - 2 ) .
DEN N+1
```

Or, faster, by substituting in the string at any stage:

- the string itself for zeros, and
- the complement of the string for ones.

It is claimed (perhaps proven by Thue?) that the parity number is transcendental.

Its regular continued fraction begins: 0 2 2 2 1 4 3 5 2 1 4 2 1 5 44 1 4 1 2 4 1 1 1 5 14 1 50 15 5 1 1 1 4 2 1 4 1 43 1 4 1 2 1 3 16 1 2 1 2 1 50 1 2 424 1 2 5 2 1 1 1 5 5 2 22 5 1 1 1 1274 3 5 2 1 1 1 4 1 1 15 154 7 2 1 2 2 1 2 1 1 50 1 4 1 2 867374 1 1 1 5 5 1 1 6 1 2 7 2 1650 23 3 1 1 1 2 5 3 84 1 1 1 1284 ... and seems to continue with sporadic large terms in suspicious patterns. A non-regular fraction is

```
1/(3 -1/(2 -1/(4 -3/(16 -15/(256 -255/(65536 -65535/
N N
2 2
(...2 -(2 -1)/(... .
```

This fraction converges much more rapidly than the regular one, its Nth approximant being

```
1 + NUM N
--------- ,
1 + DEN N
```

which is, in fact, an approximant of the regular fraction, roughly the 2^N'th.

In addition, 4*(parity number) =

```
1 3 15 255 65535
2 - - * - * -- * --- * ----- * ...
2 4 16 256 65536
```

This gives still another non-regular fraction per the product conversion item in the CONTINUED FRACTION section.

For another property of the parity number, see the spacefilling curve item in the TOPOLOGY section.

ITEM 122 Consider the image of the circle |z| = 1 under the function

```
n
=== 2
z
f(z) = > --- .
/ n
=== 2
```

This is physically analogous to a series of clock hands placed end to end. The first hand rotates around the center (0,0) at some rate. the next hand is half as long and rotates around the end of the first hand at twice this rate. The third hand rotates around the end of the second at four times this rate; etc. It would seem that the end of the "last" hand (really there are infinitely many) would sweep through space very fast, tracing out an (infinitely) long curve in the time the first hand rotates once. The hands shrink, however, because of the 2^n in the denominator. Thus it is unclear whether the curve's arc length is really infinite.

Also, it is a visually interesting curve, as are

```
=== n! === FIB(n)
z z
f(z) = > --- and f(z) = > ------- .
/ n! / FIB(n)
=== ===
```

Gosper has programmed the one mentioned first, which makes an intriguing display pattern. see following illustrations. If you write a program to display this, be sure to allow easy changing of:

- z and z* on alternate terms (alternate hands rotate in opposite directions),
- negation of alternate terms (alternate hands initially point in opposite directions), and
- how many terms are used in the computation, since these cause fascinating variations in the resulting curve.

Figure 6(a). Image of circles |z| = 1/2, 3/4, 7/8, 1 under the function

```
inf
=== n!
z
f(z) = > --- .
/ n!
===
n=1
```

Figure 6(b). Image of circles |z| = 1/8, 2/8, ..., 8/8 under the function

```
inf n
=== 2
z
f(z) = > --- .
/ n
=== 2
n=0
```

Both [original] plots by Salamin on the RLE PDP-1.

Consider

```
==== ==== ====
1 1 1 1 1
> -- = > (-- - ------) + > (----- - -----) =
/ 2 / 2 2 1 / 1 1
==== N ==== N N - - ==== N - - N + -
4 2 2
```

ITEM 122 ==== 1 2 - > ------------- . / 2 2 ==== N (4 N - 1)

Take the last sum and re-apply this transformation. This may be a winner for computing the original sum. For example, the next iteration gives

```
====
31 1
-- - 9 > --------------------------------
18 / 2 2 4 2
==== N (4 N - 1) (25 N + 5 N + 9)
```

where the denominator also =

```
2 2 2
N (2 N - 1) (2 N + 1) (5 N - 5 N + 3) (5 N + 5 N + 3)
```

CONJECTURE: If a function has a power series with integer coefficients and radius of convergence 1, then either the function is rational or the unit circle is a natural boundary.

Reference: Polya, *Mathematics and Plausible Reasoning*, volume 2, page 46.

An analytic flow for Newton's method square root:

```
2
X + K
Define F(X) by ------ ; then
2 X
N N
2 2
(X + sqrt(K)) + (X - sqrt(K))
F(F(F(...(X)))) = sqrt(k) ---------------------------------
N N
2 2
(X + sqrt(K)) - (X - sqrt(K))
which = sqrt(K) (coth 2 (arccoth X/sqrt(K))).
```

P and Q are polynomials in X; when does P(Q(X)) = Q(P(X)) ? (That is, P composed with Q = Q composed with P.)

Known solutions are:

- Various linear things.
- X to different powers, sometimes multiplied by roots of 1.
- P and Q are each another polynomial R composed with itself different numbers of times.
Solutions arising out of the flow of X^2 - 2, as follows:

suppose X = Y + 1/Y, then Y^N + Y^-N can be written as a polynomial in X.

For example, P = the expression for squares = X^2 - 2 (N = 2) and Q = the expression for cubes = X^3 - 3 X (N = 3)

- Replace X by Y-A, then add A to the original constants in both P and Q. For example, P = X^2 and Q = X^3, then P = 1 + (Y-1)^2 = Y^2 - 2 Y + 2 and Q = 1 + (Y-1)^3, then P(Q) = 1 + (Y-1)^6 = Q(P). Similarly, replacing X with A Y + B works.
There are no more through degrees 3 and 4 (checked with Mathlab); but are there any more at all?

Figure 7. A map of the process n-> binary string -> interpret as radix -2, iterated. To convert a number to base -2:

(n + ...101010) XOR (...101010) (reversible).

PROBLEM: Given F(X) as a power series in X with constant term = 0, write the flow power series.

```
FLOW sub ZERO = X
FLOW sub ONE = F(X)
FLOW sub TWO = F(F(X))
etc.
```

NOTE (Gosper): If we remove the restriction that F has a power series, the functions that satisfy an equation of the form F(F(X)) = sin X can be put into one-to-one correspondence with the set of all functions.

If F(X) = X^N, the P-th flow is X^{N}P, which has a branch point if N^P is non-integer. Under the hypotheses of the previous problem, it is possible to find the power series coefficients for P rational, but there is no guarantee the series will converge.

PROBLEM: Is the flow interpolation unique? If it is not, what extra conditions are necessary to make it unique for natural cases like X^N ?

Taking any two numbers A and B, finding their arithmetic mean and their geometric mean, and using these means as a new A and B, this process, when repeated, will approach a limit which can be expressed in terms of elliptic integrals. (See PI section.)

If a function F maps a finite set into itself, then its flow must always be cyclic. If F is one step of a pseudorandom number generator, or the CDR operation on a self referent list, or any function where it is easy to supply former values as arguments, then there are easy ways to detect looping of the flow (Knuth, *The Art of Computer Programming, volume 2, Seminumerical Algorithms,* sec. 3.1, prob. 7, page 7). If, however, the process or iterated application of the function is inexorable, (i.e., there is no easy way to switch arguments to the function), then the following algorithm will detect repetition before the third occurrence of any value.

Set aside a table TAB(J), 0 <= J <= log 2 (Largest possible period). Let C = the number of time F has been applied, initially 0. Compare each new value of F for equality with those table entries which contain old values of F. These will be the first S entries, where S is the number of times C can be right shifted before becoming 0. No match means F hasn't been looping very long, so increment C and store this latest value of F into TAB(J), where J is the number of trailing zero bits in the binary of C. (The first 16 values of J are: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...; Eric Jensen calls this the RULER function.) A match with entry E means the loop length is 1 more than the low E+2 bits of C - 2^(E+1).

The "3N+1 problem" is iteratively replacing N by N/2 if N is even or by 3 N + 1 if N is odd. Known loops for N to fall into are:

- 1 the zero loop, 0 -> 0
- 2 a positive loop, 4 -> 2 -> 1 -> 4
- 3 three negative loops (equivalent to the 3N-1 problem with positive N)
- -2 -> -1 -> -2
- -5 -> -7 -> -10 -> -5
- -17 -> -25 -> -37 -> -55 -> -82 -> -41 -> -61 -> -91 -> -136 -> -68 -> -34 -> -17

In the range -10^8 < N < 6 * 10^7, all N fall into the above loops. Are there any other loops? Does N ever diverge to infinity?

Let N be iteratively replaced by (FLATSIZE (LONGHAND N)), the number of letters in N written longhand (e.g., 69 -> SIXTY NINE -> 9 (10 counting blanks)). The process invariably loops at 4 = FOUR.

A brilliant archeologist is photographing a strange drawing on the wall of a cave. He holds the camera upright for some shots, moves it, and turns it 90 degrees for the rest. When he sees is prints he is amazed to find one of them apparently taken with the camera turned 45 degrees. After a moment's reflection, he correctly concludes that it is merely a double exposure.

What was the drawing?

Answer: It is a cousin to both the dragon and snowflake curves (and arose as a bug in a spacefilling curve). It can be constructed as follows. Start with a line segment. Replace it with the two legs of the isosceles right triangle of which it is the hypotenuse. Repeat this for the two new segments, always bulging outward in the same direction. We now have four segments forming half a square, with the middle two segments collinear. Replacing these four segments with eight and then sixteen, we find the middle two segments superimposed. As the process continues, the curve crosses itself more and more often, eventually taking on the shape of a wildly curly letter C which forms the envelope of a myriad of epicyclic octagons.

A faster way to approach the same limiting curve is to substitute the curve itself for each of its 2^{2}n segments, starting with a 90 degree "<".

Yet another way to construct it is to iteratively connect opposite ends of two copies at a 90 degree angle. (The archeologist did this with his double exposure.) If we reduce the scale by sqrt(2) each time, the distance between the endpoints stays the same. If the initial line segment is red and there is some other blue shape elsewhere in the picture, the iteration will simultaneously proliferate and shrink the blue shapes, until they are all piled up along the red "C". Thus, no matter what you start with, you eventually get something that looks like the "C" curve.

There are other pictures besides the C curve which are preserved by this process, but they are of infinite size. You can get them by starting with anything and running the iteration backwards as well as forwards, superimposing all the results. A backward step consists of rotating the two copies in directions opposite those in the forward step and stretching by sqrt(2) instead of shrinking. David silver has sketched an arrangement of mirrors which might do this to a real scene.

Figure 8. Two orders of the "C" curve.

Reference: Hardy and Wright, *Theory of Numbers.* The *Gaussian integers* are x+*i*y where x and y are integers. Unique factorization holds, except for powers of *i*, and the Gaussian primes are

- a+b
*i*if a^{2+b}2 is prime and - integer primes that = 3 mod 4.

If N(x+*i*y) = x^{2+y}2, then N(u v) = N(u) N(v). If p is prime and not= 3 mod 4, then p = a^{2+b}2 has exactly one solution. If n = 3 mod 4, then n = a^{2+b}2 has no solution.

To factor x+*i*y into Gaussian primes, first factor N(x+*i*y).

- If 2 divides N(x+
*i*y), then 1+*i*and 1-*i*divide x+*i*y. Either factor may be used since*i*(*i*-1) =*i*+1. - if p = 3 mod 4 divides N(x+
*i*y), then p divides x+*i*y. - If p = 1 mod 4 divides N(x+
*i*y) and p = a^{2+b}2, then a+*i*b or b+*i*a =*i*(a-*i*b) divides x+*i*y. If both do, then p divides x+*i*y.

n1 atan(y1/x1) + n2 atan(y2/x2) + ... = n1 arg(x1+*i*y1) + n2 arg(x2+*i*y2) + ...

If each x+*i*y is factored and the n's chosen so all prime factors except 1+*i* cancel out, the right hand side is a multiple K of *pi*/4. Some care is needed because of the multiple valuedness of arg. Then, if K = 0, we get an arctangent identity, otherwise we get a *pi* formula. In the special case of atan(1/x), factorization of x+*i* is needed. Then case (B) above can't occur, and in case (C), a+*i*b and a-*i*b can't both divide x+*i*.

Example:

```
2
8 + 1 = 13 x 5
2 2
18 + 1 = 13 x 5
2 3
57 + 1 = 13 x 5 x 2
```

From this we get the factorization

```
8+i = (3+2i) (2-i)
2
18+i = (3-2i) (2-i) i
3
57+i = (3-2i) (2+i) (1-i)
```

Since we only care about the phase, multiplication by a positive real number may be ignored below.

```
a b c a-b-c -a-2b+3c c b
(8+i) (18+i) (57+i) = (3+2i) (2+i) (1-i) i
```

We require a-b-c = 0 and -a-2b+3c = 0, which has the minimal non-trivial solution a = 5, b = 2, c = 3. Then we have

```
5 2 3 3 2
(8+i) (18+i) (57+i) = (1-i) i
```

Taking the phase of both sides, we get

`5 atan(1/8) + 2 atan(1/18) + 3 atan(1/57) = pi/4.`

*pi* formulas:

```
pi/4 = atan(1/2) + atan(1/3)
pi/4 = 2 atan(1/3) + atan(1/7)
pi/4 = 4 atan(1/5) - atan(1/239)
pi/4 = 2 atan(1/4) + atan(1/7) + 2 atan(1/13)
pi/4 = 3 atan(1/4) + atan(1/13) - atan(1/38)
pi/4 = 4 atan(1/5) - atan(1/70) + atan(1/99)
pi/4 = 5 atan(1/8) + 2 atan(1/18) + 3 atan(1/57)
pi/2 = 7 atan(1/4) - 5 atan(1/32) + 3 atan(1/132) - 4 atan(1/378)
```

This last angle has been measured against the International Standard Platinum-Iridium Right angle and certified adequate for any purpose of the U.S. Government, when used in conjunction with a conscientiously applied program of oral hygiene and regular professional care.

```
pi/4 = 7 atan(1/9) + atan(1/32) - 2 atan(1/132) - 2 atan(1/378)
pi/4 = 7 atan(1/13) + 8 atan(1/32) - 2 atan(1/132) + 5 atan(1/378)
```

There are many easily found arctangent identities. Some are:

```
atan(1/31) = atan(1/57) + atan(1/68)
= atan(1/44) + atan(1/105)
atan(1/50) = atan(1/91) + atan(1/111)
atan(1/239) = atan(1/70) - atan(1/99)
= atan(1/408) + atan(1/577)
atan(1/2441) = atan(1/1164) - atan(1/2225)
= atan(1/4774) + atan(1/4995)
atan(1/32) = atan(1/38) + atan(1/132) - atan(1/378)
= 2 atan(1/73) + atan(1/239) - atan(1/2943)
```

Infinite sets of arctangent identities:

```
1 1 1
atan(-) - atan(---) = atan(------)
n n+1 2
n +n+1
```

Let x(0) = 1, y(0) = 0, x(n) = x(n-1) + 2 y(n-1), y(n) = x(n-1) + y(n-1).

x(n)/y(n) are the continued fraction approximants to sqrt(2).

```
1 1 1
atan(-----) + atan(-----) = atan(-------)
y(2n) x(2n) x(2n-1)
1 1 1
atan(-----) - atan(-----) = atan(-------)
y(2n) x(2n) x(2n+1)
```

*pi* = 28 arctan (3/79) + 20 arctan (29/278)

*pi* = 48 arctan (3/79) + 20 arctan (1459/22049)

Which isn't too interesting except that it means that

```
48 20
(79+3i) (22049+1457i)
```

is a negative real number.

```
4
-- =
pi
inf
==== N
(-1) (1123 + 21460 N) (1 3 5 ... (2N-1)) (1 3 5 ... (4N-1))
> ------------------------------------------------------------
/ 2N+1 N 3
==== 882 32 N!
N=0
```

This series gives about 6 decimal places accuracy per term.

```
1
---------- =
sqrt(8) pi
inf
====
(1103 + 26390 N) (1 3 5 ... (2N-1)) (1 3 5 ... (4N-1))
> ------------------------------------------------------
/ 4N+2 N 3
==== 99 32 N!
N=0
```

This series gives about 8 decimal places accuracy per term. For other *pi* series, see Ramanujan's paper "Modular Equations and Approximations to Pi" in *Quarterly Journal of Pure and Applied Mathematics,* vol. 45, page 350 (1914). For more goodies, see "Collected Papers of Srinivasa Ramanujan", Cambridge U. Press (1927).

Counting the initial 3 as the zeroth, the 431st denominator in the regular continued fraction for *pi* is 20776. (Choong, Daykin & Rathbone, *Math. of Computation* 25 (1971) p. 387).

(Gosper) In the first 26491 terms of *pi,* the only other 5 digit terms are the 15543rd = 19055 and the 23398th = 19308. (Computed from 35570 terms of the (nonregular) fraction for 4 arctan 1.)

The fraction part of 10^760 *pi* begins: .49999998...

Some super-fast convergents to *pi* if one already has a super-fast computation of trig functions.

X approx *pi*:

- X <- X + sin X, epsilon <- epsilon^3/6
- X <- X - tan X, epsilon <- -epsilon^3/3

X approx pi/2:

- X <- X + cos X, epsilon <- epsilon^3/6
- X <- X + cot X, epsilon <- -epsilon^3/3

Computation of elliptic integrals, log, and *pi*.

REFERENCES

- Whittaker & Watson,
*Modern Analysis,*chap. 22. - Abramowitz & Stegun,
*Handbook of Mathematical Functions,*sect. 17.3, 17.6

Define elliptic integrals:

```
1
/
[ 1
K(m) = I ------------------------- dt
] 2 2
/ sqrt((1 - t ) (1 - m t ))
0
K'(m) = K(1 - m).
```

If A(0) and B(0) are given, and

- A(n+1) =
*arithmetic*mean of A(n) and B(n) - B(n+1) =
*geometric*mean of A(n) and B(n)

then define

AGM(A(0),B(0)) = lim A(n) = lim B(n)

This is called the *arithmetic-geometric* mean.

Quadratic convergence rate:

```
2
(A(n)-B(n))
A(n+1) - B(n+1) = -----------
8A(n+1)
```

It is known that

```
2 pi
K'(x ) AGM(1, x) = -- [see A&S]
2
```

This gives a super fast method of computing elliptic integrals. It is easy to compute AGM(1, x) for x in the complex plane cut from zero to infinity along the negative real axis. So K'(m) can be computed for -2*pi* < arg(m) < 2*pi*, which covers the complex m-plane twice. Handling the phase when taking square roots will permit exploration of more of the Riemann surface.

For small m,

K(m) = (pi/2) (1 + m/4 + O(m^2))

e^-pi(K'(m)/K(m)) = (m/16) (1 + m/2 + O(m^2))

Solve for K'(m) and let m = 16/x^2.

K'(16/x^2) = log x + (4/x^2) (log x - 1) + O(log x/x^4).

For x sufficiently large,

log x = K'(16/x^2) = pi/(2 AGM(1, 4/x)).

Requiring a given number of bits accuracy in log x is equivalent to requiring

|K'(16/x^2) - log x)/log x| < *epsilon*

this becomes

|(4/x^2) (1 - 1/log x)| < |4/x^2| < *epsilon*

|x| > 2/sqrt(*epsilon*).

x can be complex. If |x| is not too close to 1, x can be brought into range by reciprocating or repeated squaring.

let x = *e*^n, then

*pi* = 2 n AGM(1, 4 e^-n).

Suppose *epsilon* = 10 to the minus a billion.

Than the above equation for *pi* is valid when n > 1.15 billion.

*e*^-n is calculated by starting with 1/*e* and squaring k times.

Thus n = 2^k. 2^30 = 1.07 billion and 2^31 = 2.15 billion, so k = 30 gives 0.93 billion places accuracy and k = 31 gives 1.86 billion places.

In the above, instead of x = *e*^n, use x = 2^n and x = *e**2^n. Then simultaneous equations can be solve to give both *pi* and log 2. This avoids having to square *e*, but requires two AGM's, and therefore takes longer.

WARNING: Numbers in this section are *octal* (and occasionally *binary*) unless followed by a decimal point. 105=69.. (And 105.=69 hexadecimal.) [PDP-10 Info]

Proving that short programs are neither trivial nor exhausted yet, there is the following: ``

```
0/ TLCA 1,1(1)
1/ see below
2/ ROT 1,9
3/ JRST 0
```

This is a display hack (that is, it makes pretty patterns) with the low 9 bits = Y and the 9 next higher = X; also, it makes interesting, related noises with a stereo amplifier hooked to the X and Y signals. Recommended variations include: ``

```
CHANGE: GOOD INITIAL CONTENTS OF 1:
none 377767,,377767; 757777,,757757; etc.
TLC 1,2(1) 373777,,0; 300000,,0
TLC 1,3(1) -2,,-2; -5,,-1; -6,,-1
ROT 1,1 7,,7; A0000B,,A0000B
ROTC 1,11 ;Can't use TLCA over data.
AOJA 1,0
```

Another simple display program. It is thought that this was discovered by Jackson Wright on the RLE PDP-1 circa 1962. ``

```
DATAI 2
ADDB 1,2
ROTC 2,-22
XOR 1,2
JRST .-4
```

2=X, 3=Y. Try things like 1001002 in data switches. This also does interesting things with operations other than XOR, and rotations other than -22. (Try IOR; AND; TSC; FADR; FDV(!); ROT -14, -9, -20, ...)

Munching squares is just views of the graph Y = X XOR T for consecutive values of T = time.

A modification to munching squares which reveals them in frozen states through opening and closing curtains: insert FADR 2,1 before the XOR. Try data switches = ``

`4000,,4 1000,,2002 2000,,4 0,,1002`

(Notation: <left half>,,<right half>)

Also try the FADR after the XOR, switches = 1001,,1.

Here is an elegant way to draw almost circles on a point-plotting display:

NEW X = OLD X - *epsilon* * OLD Y NEW Y = OLD Y + *epsilon* * NEW(!) X

This makes a very round ellipse centered at the origin with its size determined by the initial point. *epsilon* determines the angular velocity of the circulating point, and slightly affects the eccentricity. If *epsilon* is a power of 2, then we don't even need multiplication, let alone square roots, sines, and cosines! The "circle" will be perfectly stable because the points soon become periodic.

The circle algorithm was invented by mistake when I tried to save one register in a display hack! Ben Gurley had an amazing display hack using only about six or seven instructions, and it was a great wonder. But it was basically line-oriented. It occurred to me that it would be exciting to have curves, and I was trying to get a curve display hack with minimal instructions.

PROBLEM: Although the reason for the circle algorithm's stability is unclear, what is the number of distinct sets of radii? (Note: algorithm is invertible, so all points have predecessors.)

Separating X from Y in the above recurrence,

X(N+1) = (2 - *epsilon*^2) * X(N) - X(N-1) Y(N+1) = (2 - *epsilon*) * Y(N) - Y(N-1).

These are just the Chebychev recurrence with cos *theta* (the angular increment) = 1-*epsilon*^2/2. Thus X(N) and Y(N) are expressible in the form R cos(N *theta* + *phi*). The *phi*'s and R for X(N) and Y(N) can be found from N=0,1. The *phi*'s will differ by less than *pi*/2 so that the curve is not really a circle. The algorithm is useful nevertheless, because it needs no sine or square root function, even to get started.

X(N) and Y(N) are also expressible in closed form in the algebra of ordered pairs described under linear recurrences, but they lack the remarkable numerical stability of the "simultaneous" form of the recurrence.

With exact arithmetic, the circle algorithm is stable iff |*epsilon*| < 2. In this case, all points lie on the ellipse

X^2 - *epsilon* X Y + Y^2 = constant,

where the constant is determined by the initial point. This ellipse has its major axis at 45 degrees (if *epsilon* > 0) or 135 degrees (if *epsilon* < 0) and has eccentricity

sqrt(*epsilon*/(1 + *epsilon*/2)).

To portray a 3-dimensional solid on a 2-dimensional display, we can use a single circle algorithm to compute orbits for the corners to follow. The (positive or negative) radius of each orbit is determined by the distance (forward or backward) from some origin to that corner. The solid will appear to wobble rigidly about the origin, instead of simply rotating.

The myth that any given programming language is machine independent is easily exploded by computing the sum of powers of 2.

- If the result loops with period = 1 with sign +, you are on a sign-magnitude machine.
- If the result loops with period = 1 at -1, you are on a twos-complement machine.
- If the result loops with period > 1, including the beginning, you are on a ones-complement machine.
- If the result loops with period > 1, not including the beginning, your machine isn't binary -- the pattern should tell you the base.
- If you run out of memory, you are on a string or Bignum system.
- If arithmetic overflow is a fatal error, some fascist pig with a read-only mind is trying to enforce machine independence. But the very ability to trap overflow is machine dependent.

By this strategy, consider the universe, or, more precisely, algebra:

let X = the sum of many powers of two = ...111111 now add X to itself; X + X = ...111110 thus, 2X = X - 1 so X = -1 therefore algebra is run on a machine (the universe) which is twos-complement.

To subtract the right half of an accumulator from the left (as in restarting an AOBJN counter): ``

` IMUL A,[377777,,1]`

To make an AOBJN pointer when the origin is fixed and the length is a variable in A: ``

```
HRLOI A,-1(A)
EQVI A,ORIGIN
```

If instead, A is a pointer to the last word ``

```
HRLOI A,-ORIGIN(A)
EQVI A,ORIGIN
```

Slightly faster: change the HRLOIs to MOVSIs and the EQVI addresses to -ORIGIN-1. These two routines are clearly adjustable for BLKOs and other fenceposts.

A miniature (recursive) sine and cosine routine follows. ``

```
COS: FADR A,[1.57079632679] ;pi/2
SIN: MOVM B,A ;ARGUMENT IN A
CAMG B,[.00017] ; <= 3^(1/3) / 2^13
POPJ P, ;sin X = X, within 27. bits
FDVRI A,(-3.0)
PUSHJ P,SIN ;sin -X/3
FMPR B,B
FSC B,2
FADRI B,(-3.0)
FMPRB A,B ;sin X = 4(sin -X/3)^3 - 3(sin -X/3)
POPJ P, ;sin in A, sin or |sin| in B
;|sin| in B occurs when angle is smaller than end test
```

Changing both -3.0's to +3.0's gives sinh:

sinh X = 3 sinh X/3 + 4 (sinh X/3)^3.

Changing the first -3.0 to a +9.0, then inserting PUSHJ P,.+1 after PUSHJ P,SIN gains about 20% in speed and uses half the pushdown space (< 5 levels in the first 4 quadrants). PUSHJ P,.+1 is a nice way to have something happen twice. Other useful angle multiplying formulas are

tanh X = (2 tanh X/2) / (1 + (tanh X/2)^2)

tan X = (2 tan X/2) / (1 - (tan X/2)^2),

if infinity is handled correctly. For cos and cosh, one can use

cos X = 1 - 2 (sin X/2)^2, cosh X = 1 + 2 (sinh X/2)^2.

In general, to compute functions like *e*^X, cos X, elliptic functions, etc. by iterated application of double and triple argument formulas, it is necessary to subtract out the constant in the Taylor series and transform the range reduction formula accordingly. Thus:

F(X) = cos(X)-1 F(2 X) = 2 F*(F+2) F(*epsilon*) = -*epsilon*^2/2

G(X) = *e*^X - 1 G(2 X) = G*(G+2) G(*epsilon*) = *epsilon*

This is to prevent the destruction of the information in the range-reduced argument by the addition of a quantity near 1 upon the success of the *epsilon* test. The addition of such a quantity in the actual recurrences is OK since the information is restored by the multiply. In fact, a cheap and dirty test for F(*epsilon*) sufficiently small is to see if the addition step has no effect. People lucky enough to have a square root instruction can get *natural log* by iterating

X <- X/(sqrt(1+X) + 1) until 1+X = 1.

Then multiply by 2^(number of iterations). Here, a LSH or FSC would work.

(Numbers herein are decimal.)

The correct *epsilon* test in such functions as the foregoing SIN are generally the largest argument for which addition of the second term has no effect on the first. In SIN, the first term is x and the second is -x^3/6, so the answer is roughly the x which makes the ratio of those terms 1/2^27; so x = sqrt(3) / 2^13. But this is not exact, since the precise cutoff is where the neglected term is the power of 2 whose 1 bit coincides with the first neglected (28th) bit of the fraction. Thus, x^3/6 = 1/2^27 * 1/2^13, so x = 3^(1/3) / 2^13.

Here is a way to get *log base 2*. A and B are consecutive. Call by PUSHJ P,LOG2 with a floating point argument in A. ``

```
LOG2: LSHC A,-33
MOVSI C,-201(A)
TLC C,211000 ;Speciner's bum
MOVI A,200 ;exponent and sign sentinel
LOGL: LSH B,-9
REPEAT 7, FMPR B,B ;moby flunderflo
LSH B,2
LSHC A,7
SOJG A,LOGL ;fails on 4th try
LSH A,-1
FADR A,C
POPJ P, ;answer in A
```

Basically you just square seven times and use the low seven bits of the exponent as the next seven bits of the log.

To swap the contents of two locations in memory: ``

```
EXCH A,LOC1
EXCH A,LOC2
EXCH A,LOC1
```

Note: LOC1 must not equal LOC2! If this can happen use MOVE-EXCH-MOVEM, clobbering A.

To swap two bits in an accumulator: ``

```
TRCE A,BITS
TRCE A,BITS
TRCE A,BITS
```

Note (Nelson): last TRCE never skips, and used to be a TRC, but TRCE is less forgettable. Also, use TLCE or TDCE if the bits are not in the right half.

To exchange two variables in LISP without using a third variable:

(SETQ X (PROG2 0 Y (SETQ Y X)))

To take MAX in A of two byte pointers (where A and B are consecutive accumulators): ``

```
ROTC A,6
CAMG A,B
EXCH A,B
ROTC A,-6
```

A byte pointer can be converted to a character address < 2^18 by MULI A,<# bytes/word> followed by SUBI B,1-<# b/w>(A). To get full word character address, use SUB into a magic table.

To rotate three consecutive accumulators N < 37. places: ``

```
ROTC A,N
ROT B,-N
ROTC B,N
```

Thus M AC's can be ROTC'ed in 2M-3 instructions. (Stallman): For 73. > N > 35.: ``

```
ROTC A,N-36.
EXCH A,C
ROT B,36.-N
ROTC A,N-72.
```

``

```
;B gets 7 bit character in A with even parity
IMUL A,[2010040201] ;5 adjacent copies
AND A,[21042104377] ;every 4th bit of left 4 copies + right copy
IDIVI A,17<-7 ;casting out 15.'s in hexadecimal shifted 7
;odd parity on 7 bits (Schroeppel)
IMUL A,[10040201] ;4 adjacent copies
IOR A,[7555555400] ;leaves every 3rd bit+offset+right copy
IDIVI A,9<-7 ;powers of 2^3 are +-1 mod 9
;changing 7555555400 to 27555555400 gives even parity
;if A is a 9 bit quantity, B gets number of 1's (Schroeppel)
IMUL A,[1001001001] ;4 copies
AND A,[42104210421] ;every 4th bit
IDIVI A,17 ;casting out 15.'s in hexadecimal
;if A is 6 bit quantity, B gets 6 bits reversed (Schroeppel)
IMUL A,[2020202] ;4 copies shifted
AND A,[104422010] ;where bits coincide with reverse repeated base 2^8
IDIVI A,377 ;casting out 2^8 - 1's
;reverse 7 bits (Schroeppel)
IMUL A,[10004002001] ;4 copies sep by 000's base 2 (may set arith. o'flow)
AND A,[210210210010] ;where bits coincide with reverse repeated base 2^8
IDIVI A,377 ;casting out 377's
;reverse 8 bits (Schroeppel)
MUL A,[100200401002] ;5 copies in A and B
AND B,[20420420020] ;where bits coincide with reverse repeated base 2^10
ANDI A,41 ;"
DIVI A,1777 ;casting out 2^10 - 1's
```

``

```
foo, lat /DATAI switches
adm a /ADDB
and (707070
adm b
iot 14 /output AC sign bit to a music flip-flop
jmp foo
```

Makes startling chords, arpeggios, and slides, with just the sign of the AC. This translates to the PDP-6 (roughly) as: ``

```
FOO: DATAI 2
ADDB 1,2
AND 2,[707070707070] ;or 171717171717, 363636363636, 454545454545, ...
ADDB 2,3
LDB 0,[360600,,2]
JRST FOO
```

Listen to the square waves from the low bits of 0.

To count the ones in a PDP-6/10 word: ``

```
LDB B,[014300,,A] ;or MOVE B,A then LSH B,-1
AND B,[333333,,333333]
SUB A,B
LSH B,-1
AND B,[333333,,333333]
SUBB A,B ;each octal digit is replaced by number of 1's in it
LSH B,-3
ADD A,B
AND A,[070707,,070707]
IDIVI A,77 ;casting out 63.'s
```

These ten instructions, with constants extended, would work on word lengths up to 62.; eleven suffice up to 254..

Useful strings of non-digits and zeros can arise when carefully chosen negative numbers are fed to unsuspecting decimal print routines. Different sets arise from different methods of character-to-digit conversion. Example (Gosper): ``

```
DPT: IDIVI F,12
HRLM G,(P) ;tuck remainder on pushdown list
SKIPE F
PUSHJ P,DPT
LDB G,[220600,,(P)] ;retrieve low 6 bits of remainder
TRCE G,"0 ;convert digit to character
SETOM CCT ;that was no digit!
TYO: .IOT TYOCHN,G ;or DATA0 or IDPB ...
AOS G,CCT
POPJ P,
```

This is the standard recursive decimal print of the positive number in F, but with a LDB instead of a HLRZ. It falls into the typeout routine which returns in G the number of characters since the last carriage return. When called with a -36., DPT types carriage return, line feed, and resets CCT, the character position counter.

Since integer division can never produce a larger quotient than dividend, doubling the dividend and divisor beforehand will distinguish division by zero from division by 1 or anything else, in situations where division by zero does nothing.

The fundamental operation for building list structure, called CONS, is defined to: find a free cell in memory, store the argument in it, remove it from the set of free cells, return a pointer to it, and call the garbage collector when the set is empty. This can be done in two instructions: ``

```
CONS: EXCH A,[EXCH A,[...[PUSH P,GC]...]]
EXCH A,CONS
```

Of course, the address-linked chain of EXCH's indicated by the nested brackets is concocted by the garbage collector. This method has the additional advantage of not constraining an accumulator for the free storage pointer. ``

```
UNCONS: HRLI A,(EXCH A,)
EXCH A,CONS
EXCH A,@CONS
```

Returns cell addressed by A to free storage list; returns former cell contents in A.

The incantation to fix a floating number is usually ``

```
MULI A,400 ;exponent to A, fraction to A+1
TSC A,A ;1's complement magnitude of excess 200 exponent
ASH A+1,-200-27.-8(A) ;answer in A+1
```

If number is known positive, you can omit the TSC.

On the PDP-10 ``

```
UFA A,[+-233000,,] ;not in PDP-6 repertoire
TLC A+1,233000 ;if those bits really bother you
```

When you know the sign of A, and |A| < 2^26, you can ``

```
FAD A,[+-233400,,] ;or FADR for rounded fix!
TLC A,233400 ;if those bits are relevant
```

where the sign of the constant must match A's. This works on both machines and doesn't involve A+1. On the 10, FADRI saves a cycle and a constant, and rounds.

21963283741 . = 243507216435 is a fixed point of the float function on the PDP-6/10, i.e., it is the only positive number whose floating point representation equals its fixed.

To get the next higher number (in A) with the same number of 1 bits: (A, B, C, D do not have to be consecutive) ``

```
MOVE B,A
MOVN C,B
AND C,B
ADD A,C
MOVE D,A
XOR D,B
LSH D,-2
IDIVM D,C
IOR A,C
```

The "banana phenomenon" was encountered when processing a character string by taking the last 3 letters typed out, searching for a random occurrence of that sequence in the text, taking the letter following that occurrence, typing it out, and iterating. This ensures that every 4-letter string output occurs in the original. The program typed BANANANANANANANANA.... We note an ambiguity in the phrase, "the Nth occurrence of". In once sense, there are five 00's in 0000000000; in another, there are nine. The editing program TECO finds five. Thus it finds only the first ANA in BANANA, and is thus obligated to type N next. By Murphy's Law, there is but one NAN, thus forcing A, and thus a loop. An option to find overlapped instances would be useful, although it would require backing up N-1 characters before seeking the next N character string.

Certain plotters and displays are constrained to approximate curves by a sequence of king-moves between points on a lattice.

Many curves and contours are definable by F(X,Y) = 0 with F changing sign on opposite sides of the curve. The following algorithm will draw most such curves more accurately than polygonal approximations and more easily than techniques which search for a "next" X and Y just one move away.

We observe that a good choice of lattice points is just those for which F, when evaluated on one of them, has opposite sign and smaller magnitude than on one or more of its four immediate neighbors. This tends to choose the nearer endpoint of each graph paper line segment which the curve crosses, if near the curve F is monotone with distance from the curve.

First, divide the curve into arcs within which the curve's tangent lies within one 45 degree semiquadrant. We can show that for reasonable F, only two different increments (say north and northwest) are needed to visit the desired points.

Thus, we will be changing one coordinate (incrementing Y) every step, and we have only to check whether changing the other (decrementing X) will reduce the magnitude of F. (If F increases with Y, F(X,Y+1) > -F(X-1,Y+1) means decrement X.) F can often be manipulated so that the inequality simplifies and so that F is easily computed incrementally from X and Y.

As an example, the following computes the first semiquadrant of the circle

```
2 2 2
F = X + Y - R = 0.
C0: F <- 0, Y <- 0, X <- R
C1: F <- F+2Y+1, Y <- Y+1
C2: if F >= X, F <- F-2X+1, X <- X-1
C3: if Y < X-1, go to C1
C4: (Link to next arc) if Y = X-1, Y <- Y+1, X <- X-1
```

This can be bummed by maintaining Z = 2Y+1 instead of Y. Symmetry may be used to compute all eight semiquadrants at once, or the loop may be closed at C2 and C3 with two PUSHJ's to provide the palindrome of decisions for the first quadrant. There is an expression for the number of steps per quadrant, but it has a three-way conditional dependent upon the midpoint geometry. Knowing this value, however, we can replace C3 and C4 with a simple loop count and an odd-even test for C4.

The loop must be top-tested (C3 before C1) if the "circle" R = 1, with four diagonal segments, is possible.

All this suggests that displays might be designed with an increment mode which accepts bit strings along with declarations of the form: "0 means north, 1 means northwest". 1100 (or 0011) will not occur with a curve of limited curvature; thus, it could be used as an escape code, but this would be an annoying restriction.

See the following illustration of circles drawn this way.

[In case of a tie, i.e., F has equal magnitudes with opposite signs on adjacent points, do not choose both points but rather have some arbitrary yet consistent preference for, say, the outer one. The problem can't arise for C2 in the example because the inequality F >= X is really F > -(F-2X+1) or F > X-.5.]

Suppose Y satisfies a differential equation of the form

`P(X) Y(Nth derivative) + ..... + Q(X) = R(X)`

where P, ..... Q, and R are polynomials in X

```
2 2 2
(for example, Bessel's equation, X Y'' + X Y' + (X - N ) Y = 0)
```

and A is an algebraic number. Then Y(A) can be evaluated to N places in time proportional to N(ln N)^3.

Further, e^X and ln X or any elementary function can be evaluated to N places in N(ln N)^2 for X a real number. If F(X) can be evaluated in such time, so can the inverse of F(X) (by Newton's method), and the first derivative of F(X). Also, *zeta*(3) and *gamma* can be done in N(ln N)^3.

A program which searches a character string for a given substring can always be written by iterating the sequence fetch-compare-transfer (ILDB-CAIE-JRST on the PDP6/10) once for each character in the sought string. The destinations of the transfers (address fields of the JRST's) must, however, be computed as functions of the sought string. Let ``

```
0 1 2 3 4
S A S S Y
0 1 0 2 2
```

stand for the program ``

```
T0: ILDB C,A ;C gets next char from pointer in A
T1: CAIE C,"S ;skip if it's an S
JRST T0 ;loop back on failure
ILDB C,A ;next
T2: CAIE C,"A ;skip if A
JRST T1 ;could be an S
ILDB C,A
T3: CAIE C,"S
JRST T0 ;S, A, non S, so start over
ILDB C,A
T4: CAIE C,"S
JRST T2 ;could be SAS.ASSY
ILDB C,A
CAIE C,"Y
JRST T2 ;could be SASS.ASSY
;found SASSY
```

In other words, a number > 0 in the top row is a location in the program where the corresponding letter of the middle row is compared with a character of the input string. If it differs, the number in the bottom row indicates the location where comparison is to resume. If it matches, the next character of the middle row is compared with the next character of the input string.

Let J be a number in the to row and K be the number below J, so that TK is the address field of the Jth JRST. For each J = 1, 2, ... we compute K(J) as follows: K(1) = 0. Let P be a counter, initially 0. For each succeeding J, increment P. If the Pth letter = the Jth, K(J) = K(P). Otherwise, K(J) = P, and P is reset to 0. (P(J) is the largest number such that the first P characters match the last P character in the first J characters of the sought string.) ``

```
J= 0 1 0 1 2 3 4 5
M I S S I S S I P P I I S S I S S I P P I
K(J)= 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 5 1 0
0 1 2 3 0 1 2 3
C O C A C O L A S A S S A F R A S
0 1 0 2 0 1 3 1 0 1 0 2 1 3 1 1 0
```

To generalize this method to search for N strings at once, we produce a program of ILDB-CAIE-JRST's for each of the sought strings, omitting the initial ILDB from all but the first. We must compute the destination of the Jth JRST in the Ith program, TKM(I,J), which is the location of the Kth compare in the Mth program.

It might be reasonable to compile such an instruction sequence whenever a search is initiated, since alternative schemes usually require saving or backing up the character pointer.

A problem which may arise in machine processing of visual information is the identification of corners on a noisy boundary of a polygon. Assume you have a broken line. If it is a closed loop, find the vertex furthest from the centroid (or any place). Open the loop by making this place both endpoints and calling it a corner. We define the corner of a broken line segment to be the point the sum of whose distances from the endpoints is maximal. This will divide the segment in two, allowing us to proceed recursively, until our corner isn't much cornerier than the other along the line.

The perpendicular distance which the vector C lies from the line connecting the vectors A and B is just ``

```
(C - A) x (B - A)
----------------- ,
2 |A - B|
```

but maximizing this can lose on very pointy V's. The distance sum hack can lose on very squashed Z's.

A bug you might try to avoid when designing floating point hardware, relating to excess-200, 1's complement exponent, 2's complement fraction convention:

- An advantage is that negation and numerical comparison can be accomplished with the same instructions for both fixed and floating point numbers.
- A disadvantage is that the termination of the normalization process is ambiguous. Normally, when the sign bit unequals the highest bit of fraction, the number is normalized. A special case arises with negated powers of two. (That is, -(2^n), not (2)^-n.) Then the fraction is 400,,0 and the sign is - also.

This means it is necessary to check whether shifting left one more bit will bring in a one:

- if it brings in a zero, you will over-normalize
- if it brings in a one, you should do it

If you should but don't, rounding will un-normalize, and when you then re-normalize, the normalizing amount will be doubled, so you will be off by 2 smidgens (that is, the next to low order bit). Note that rounding can over-normalize as well as un-normalize, so you can't just stop normalization after rounding.

You might check this in your PDP-6/10. For example, combine 201400,,0+delta with minus 200777,,777777+2delta. For 0 <= delta <= 7777, the correct FMP result is minus 200777,,777776, and the correct FMPR result is minus 200777,,777777.

Over-normalized negative powers of 2 work in compares and most floating arithmetic. They lose with MOVN and as dividends. Unnormalized floating operands win completely on the PDP-10, except as divisors and dividends, the latter suffering truncation error.

Fairchild is now supplying positive voltage regulators costing about 2 dollars in lots of 1 (for example, the uA7805 for +5 volts).

The CA3083 (and CA3084) transistor arrays can be used to make neat current mirrors. (A current mirror supplies a current on one wire equal to that drawn from a second wire.)

A dual MOS D-type flip-flop (such as the CD4013AE) can be used to make a one-shot as follows:

Everyone has their own favorite oscillator circuits; here are some we like.

- I. crystal, overtone, transistor
- crystal, fundamental, transistor (drives at least 1 TTL load)

- crystal, fundamental, CMOS, low frequency (drives 1 TTL load at 5.4 volts and no load, draws 330 microamperes; with a 165 KHz, 32 pf crystal, varies about 10 Hz per volt of Vcc)

- crystal, fundamental, IC (a favorite of Nelson's, but be careful and lucky or it may oscillate at a frequency determined by the crystal holder capacitance and not by the crystal; note similarity to non-crystal oscillator V)

- V. not crystal controlled; for comparison with IV
- The following blocking oscillator is quite uncritical of component values, with the exception that the turns ratio be such that -Vb (see graph) not exceed BVebo (about 5 volts for silicon transistors).

In work on education at our lab, we built a motorized "turtle" controlled by computer commands in the child-oriented language "Logo". The following is a transmitter designed as a radio link between the computer and turtle. Input (modulation) is either 0 or +1 volts; output is about 88MHz. Use a commercial FM tuner as receiver. Note: this transmitter is ILLEGAL no matter what; part 15 low power rule only allows if duty is less than about 1 second per 15 minutes. Don't worry about it unless you interfere with broadcast stations.

When the chess program written at our lab is playing in a chess tournament, a human attendant at the tournament moves the pieces, punches the clock, and communicates with the program via a portable terminal coupled to a telephone line. It is desirable that the program know when its chess clock is running, even though the attendant may not notice immediately that the opponent has made his move and punched the clock. Therefore we built a clock holder with a microswitch to sense the clock state. The following is a 10 mw transmitter whose input is the microswitch and whose output goes onto the phone line. It switches between two frequencies, about 320 and 470 Hz. Also shown is the receiver. Input should be at least 100 mv rms (threshold is 20 mv and overload is above 68 volts) with peak to peak signal to noise ration grater than 4:1. As we all know, connections to phone lines are illegal unless made through a data coupler supplied by TPC (The Phone Company).

One version of the "turtle" mentioned above (see RADIO LINK) uses a DC motor to drive each of its two powered wheels. since its path is to be as straight as possible, a triangular pulse is generated (to represent one "step" of the motor) and the motor's velocity servoed to this analog command. An additional digital command enables forward or reverse motion. Diagram I shows a simplified velocity servoing circuit. It has the disadvantage that only half the maximum voltage available (-V to +V) can be applied across the motor at any one time. Diagram II shows the actual circuit used in the turtle.

When two circuits are at potentials differing by a few hundred volts but wish to communicate with each other, one solutions is to use an optical coupler. these employ a light-emitting device placed close to a light-sensitive device. diodes make very fast-responding sensors, but the signal from a light-sensitive transistor is much stronger. shown is a compromise, using a transistor as a diode, with associated cleverness to get the delay (from input to output) down from 10 microseconds to 1.

In our fourth computer-interfaced image sensing device, TVD (really a vidissector, not a TV), the photocathode sits at several thousand volts negative. Nevertheless, one wishes to sense the current it draws, since overcurrent should shut down the photocathode voltage to avoid damage to the photocathode. The following circuit draws no more than 400 microamperes at 10 volts (at 20 KHz out; about 200 microamperes at 10 KHz) and couples the current information out as the frequency sent to T2, whose coils are wound on opposite sides of a ceramic ferrite.

TVD, mentioned above, uses a very carefully designed printed circuit amplifier to supply current to its magnetic deflection coils. Except for the notes with the diagram, we submit it without further explanation or cautions.

Notes:

Except where noted, resistors 10%, 1/4 watt.

Capacitances in microfarads/volts; electrolytics aluminum.

Diodes 1N4727, 1N4154, 1N4009 etc.; stored charge no more than 80 picocoulombs at 1 milliampere forward current.

1D103 = GE thermistor mounted at center of main heat sink.

220J = Analog Devices chopper amplifier.

- = temperature protection circuit (overtemperature cutout).

Q2, Q3, Q4, Q5, Q6, Q12,l Q13, Q14, Q15, Q16 mounted on one 1 Centigrade degree per watt heat sink (e.g., Wakefield 621K 1/2 inch in front of Rotron Muffin fan). Case temperature about 70 degrees C max. Ground heat sink and insulate transistors.

All transistors Motorola.

All zeners 1 watt.

VE48X = Varo; could be two 2 A 50 PIV fast recovery.

Output capacitance about 800 pf; damping R about 150 ohms for critical damping.

Slews from + (or -) 2 A to - (or +) 2 A in 4 microseconds; dE/dt is hot side of deflection coil is about a billion v/sec.

Layout is critical, as with most fast high-gain circuits.

- A By-passing and lead inductance: Short wide strips (or, better, a ground plane) should be used for ground bus, and ceramic capacitors with leads as short as practicable used for bypassing. Best bypass capacitor is Allen-Bradley CL series.
- B Ground loops: reference ground (triangles) and power ground must be interconnected only at the cold side of the sense resistor; take care to avoid stray current through the cold side of the signal input.
- C In general, the device should be constructed like a 144 MHz transmitter to avoid its becoming one.

The 100 pf stabilizing capacitor may want to be higher to decrease hunting and ringing, which could improve settling time more than the reduced gain-bandwidth would increase it.

```
Q1, Q12, Q13 MPS-U01
Q11, Q2, Q3 MPS-U51
Q4, Q5, Q6 2N5194
Q14, Q15, Q16 2N5191
Q7 MPS-U02
Q17 MPS-U52
Q8, Q19 2N3906
Q9, Q18 2N3904
```

- HAKMEM
- GEOMETRY, ALGEBRA, CALCULUS
- RECURRENCE RELATIONS
- BOOLEAN ALGEBRA
- RANDOM NUMBERS
- NUMBER THEORY, PRIMES, PROBABILITY
- ITEM 28 (Schroeppel):
- ITEM 29 (Schroeppel):
- ITEM 30 (Schroeppel):
- ITEM 31 (Schroeppel):
- ITEM 32 (Schroeppel):
- ITEM 33 (Schroeppel):
- ITEM 34 (Schroeppel):
- ITEM 35 (Schroeppel):
- ITEM 36 (Schroeppel):
- ITEM 37 (Gosper):
- ITEM 38 (Fredkin):
- ITEM 39 (Schutzenberger):
- ITEM 40 (Gosper):
- ITEM 41 (Salamin):
- ITEM 42 (Gosper):
- ITEM 43 (Schroeppel):
- ITEM 44 (Gosper):
- PROBLEM 45 (Gosper):
- ITEM 46 (Schroeppel):
- ITEM 47 (Beeler):
- ITEM 48 (Gosper, Schroeppel):
- ITEM 49:
- ITEM 50 (Schroeppel):
- ITEM 51 (Schroeppel):
- ITEM 52 (Salamin):
- ITEM 53 (Salamin):
- ITEM 54 (Salamin & Gosper):
- ITEM 55 (Schroeppel): GAUSSIAN INTEGERS
- ITEM 56 (Beeler):
- ITEM 57 (Beeler, Gosper):
- ITEM 58 (Fredkin):
- ITEM 59 (Schroeppel):
- ITEM 60 (Beeler):
- ITEM 61 (Root):
- ITEM 62 (Speciner):
- ITEM 63 (Schroeppel, etc.):

- AUTOMATA THEORY
- GAMES
- PROPOSED COMPUTER PROGRAMS, IN ORDER OF INCREASING RUNNING TIME (Schroeppel)
- CONTINUED FRACTIONS
- GROUP THEORY
- SET THEORY
- QUATERNIONS
- POLYOMINOS, ETC.
- TOPOLOGY
- SERIES
- FLOWS AND ITERATED FUNCTIONS
- PI
- PROGRAMMING HACKS
- ITEM 145 (Gosper):
- ITEM 146: MUNCHING SQUARES
- ITEM 147 (Schroeppel):
- ITEM 148 (Cohen, Beeler):
- ITEM 149 (Minsky): CIRCLE ALGORITHM
- ITEM 150 (Schroeppel):
- ITEM 151 (Gosper):
- ITEM 152 (Salamin):
- ITEM 153 (Minsky):
- ITEM 154 (Gosper):
- ITEM 155 (Liknaitzky):
- ITEM 156 (Mitchell):
- ITEM 157 (Freiberg):
- ITEM 158 (Gosper, Salamin, Schroeppel):
- ITEM 159 (Gosper, Schroeppel):
- ITEM 160 (Gosper):
- ITEM 161 (Gosper):
- ITEM 162 (Gosper):
- ITEM 163 (Sussman):
- ITEM 164 (Samson):
- ITEM 165 (Freiberg):
- ITEM 166 (Gosper, Liknaitzky):
- ITEM 167 (Gosper, Freiberg):
- ITEM 168 (PDP-1 hackers):
- ITEM 169 (in order of one-ups-manship: Gosper, Mann, Lenard, [Root and Mann]):
- ITEM 170 (Jensen):
- ITEM 171 (Gosper):
- ITEM 172 (Gosper):
- ITEM 173 (Gosper):
- ITEM 174 (Gosper, Nelson):
- ITEM 175 (Gosper):

- PROGRAMMING ALGORITHMS, HEURISTICS
- HARDWARE
- ITEM 181 (Gosper):
- ITEM 182 (Roe): VOLTAGE REGULATORS
- ITEM 183 (Roe): CURRENT MIRRORS
- ITEM 184 (Roe): ONE-SHOT
- ITEM 185 (Roe): OSCILLATORS
- ITEM 186 (Roe): FM RADIO LINK
- ITEM 187 (Roe): PHONE LINE XMTR, RCVR
- ITEM 188 (Roe): DC MOTOR VELOCITY SERVO
- ITEM 189 (Roe): OPTICAL COUPLER
- ITEM 190 (Roe): PHOTOCATHODE CURRENT OSCILLATOR
- ITEM 191 (Roe): DEFLECTION AMPLIFIER