github.com/PDP-10.its
1
0
Fork 0
mirror of https://github.com/PDP-10/its.git synced 2026-01-11 23:53:12 +00:00
Code Issues Releases Wiki Activity
PDP-10.its/doc/mb/hakmem.141
Eric Swenson 9a1cd96729 Adding two versions of HAKMEM. 
Setting date for HAKMEM 141 to be 1972-03-16.  Setting date for HAKMEM 17 to be 1971-01-01,
although this date is probably not correct, but we have no info to base its date on other than
that it was "before" 1972.
2025-10-30 08:18:58 -07:00

3513 lines
140 KiB
Plaintext
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

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 Rich Schroeppel
Bill Gosper Michael Speciner
Michael Beeler Gerald Sussman
John Roe Joe Cohen
Richard Stallman David Waltz
Jerry Freiberg David Silver
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
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
at Computer Corporation of America:
Bill Mann
in France:
Marco Schutzenberger Henry Cohen
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.
CONTENTS, HAKMEM 140
4 GEOMETRY, ALGEBRA, CALCULUS
7 RECURRENCE RELATIONS
11 BOOLEAN ALGEBRA
13 RANDOM NUMBERS
14 NUMBER THEORY, PRIMES, PROBABILITY
23 AUTOMATA THEORY
24 GAMES
26 PROPOSED COMPUTER PROGRAMS
29 CONTINUED FRACTIONS
30 GROUP THEORY
30 SET THEORY
31 QUATERNIONS
33 POLYOMINOS, ETC.
36 TOPOLOGY
39 SERIES
43 FLOWS AND ITERATED FUNCTIONS
45 PI
50 PROGRAMMING HACKS
60 PROGRAMMING ALGORITHMS, HEURISTICS
64 HARDWARE
note: this page will not be included in final publication;
it is for inter-hacker notes, etc.
INCLUDE: C CURVE gscale-invrse mirr, PEGSOLITAIRE self dual, XE+YPI, PUSH Q,6(R),
IO PHILOS., SPECINER NU FCN SUMS, SLIVER BOX ILLUSION uses, Y = A -1/X,
(X+Y)/(1+XY), HEWITT'S CLAIM--
R'S ALG FOR REGEXPR SERCH, POSSIBLE WINDOWING IN RECURRENCES,
Hilbert's tenth with reference, Recent history of 4 color theorem,
Risch on integration, Baker on effective solution of Diophantine eqs.
1 26 66 26 1 genfn, PERSPEC PROB., cf gamma,
cf hype (recip vs 10* etc),1/pi vs pi, bignum rep--quoti estm,
Approximants to 2^(n/12), Primes < 2^n, COROUTINES, CONTINUED FRACTION
ARITHMETIC ..6 0 9! gen cf techn--strang, cf interval trick,
LINEAR MEDIAN COMP?, g's sin & cos routines,
g: is bunchy sort (xor to get rel bit) in? -- mb, commut polyns frm higher
recurrence ntupication?, bum hamming aos, 36 cnt, fix bridgehands, 2nots
ES recrsv FFT, div by 0 trick, cf pi+1/pi, vis noise, jensen -digits,
Minsky's Venn diagram, rewrite para in search program
254 * 3937 (r)
*********************************************
GEOMETRY, ALGEBRA, CALCULUS
*********************************************
ITEM (Schroeppel):
(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:
Z!(-Z)! = pi*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)!
ITEM (Jan Kok):
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?
ITEM (Schroeppel):
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:
1 they do not converge
2 there is a dense set of points which involve division by zero
3 there is a dense set of points which loop, but roundoff error
propagates so all loops are unstable
4 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.)
ITEM (Schroeppel):
By Mathlab, the discriminant of X^4 + FX^3 + GX^2 + HX + I is
(as the discriminant of AX^2 + BX + C is B^2 - 4AC):
- 27 H^4 + 18 FGH^3 - 4 F^3H^3 - 4 G^3H^2 + F^2G^2H^2
+ I * [144 GH^2 - 6 F^2H^2 - 80 FG^2H
+ 18 F^3GH + 16 G^4 - 4 F^2G^3]
+ I^2 * [- 192 FH - 128 G^2 + 144 F^2G - 27 F^4]
- 256 I^3
ITEM:
In general, the discriminant of an n-th degree polynomial is
PRODUCT(ROOT - ROOT )^2 = square of determinant whose i,j element
i<j i j
i-1
is ROOT . (The discriminant is the lowest degree symmetric
j
function of the roots which is 0 when any two are equal.)
ITEM (Schroeppel):
If A is the first symmetric function of N variables
= X + Y + Z + ...
and B is the second symmetric function of N variables
= XY + XZ + ... + YZ + ...
(B = sum of pairs), then X^2 + Y^2 + Z^2 + ... = A^2 - 2B.
X^3 + Y^3 + Z^3 + ... = A^3 - 3AB + 3C.
X^4 + Y^4 + Z^4 + ... = A^4 - 4A^2B + 2B^2 + 4AC - 4D.
ITEM (Gosper):
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
sum f(I;X,Y,Z,...)*S = (1+XS)(1+YS)(1+ZS)...
I=0
ITEM (Schroeppel):
Solutions to F(X) = X^3 - 3BX^2 + CX + D = 0 are
B - K * CUBE ROOT [F(B)/2 + SQRT [(F(B)/2)^2 + (F'(B)/3)^3]]
- K^2 * CUBE ROOT [F(B)/2 - SQRT [(F(B)/2)^2 + (F'(B)/3)^3]]
where K is one of the three cuberoots of 1:
1, (-1+SQRT(-3))/2, (-1-SQRT(-3))/2.
ITEM (Schroeppel & Salamin):
If X^4 + BX^2 + CX + D = 0, then 2X = (SQRT Z1) + (SQRT Z2) + (SQRT Z3)
Z1, Z2, Z3 are roots of Z^3 + 2BZ^2 + (B^2 - 4D)Z - C^2 = 0.
The choices of square roots must satisfy (SQRT Z1)(SQRT Z2)(SQRT Z3) = -C.
ITEM (Salamin):
An easy solution of -4X^3 + 3X - 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.
ITEM (Salamin):
The following operations generate one-to-one conformal mappings
of Euclidean N-space onto itself.
1) Translate N-space.
2) Expand N-space about one of its points.
3) 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.
**************************************************
RECURRENCE RELATIONS
**************************************************
ITEM (Gosper & Salamin):
"the Fast Fibonacci Transform" (motivation for next item)
Define multiplication on ordered pairs
(A,B)(C,D)=(AC+AD+BC,AC+BD).
This is just (AX+B)*(CX+D) mod X^2-X-1, and so is associative,
etc. We note (A,B)(1,0)=(A+B,A), which is the Fibonacci
N
iteration. Thus, (1,0) = (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
(1,0) = (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.
-1
(A,B) = (-A,A+B)/(B^2+AB-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
(X,Y)
compute fractional Fibonaccis, and even e 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 of the method of Bernoulli and Whittaker (Rektorys,
Survey of Applicable Math., p 1172). For the general second
order recurrence, F(N+1) = XF(N) + YF(N-1), we have the
multiplication rule: (A,B)(C,D) = (AD+BC+XAC,BD+YAC).
-1
Inverse: (A,B) = (-A,XA+B)/(B^2+XAB-YA^2).
N
Two for the price of one: (F(1),YF(0))(1,0) = (F(N+1),YF(N)).
ITEM (Salamin & Gosper):
LINEAR RECURRENCE RELATIONS
Recurrence relation: A = C A + ... + C A (1)
k n-1 k-1 0 k-n
with A , ... , A given as initial values.
0 n-1
Consider the algebra with basis vectors
n-1
X^0, X^1, X^2, ... , X
n n-1
and the identification X = C X + ... + C X^0. (2)
n-1 0
Thus if U, V, W are vectors and W = U V, then componentwise
W = SUM T U V , (3)
i j,k ijk j k
where the T's depend only on the C's. The following simple
k
procedure yields A : express the vector X as a linear
k m
combination of the basis vectors, then set X = A (0 =< m < n).
k m
Computation of X 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.
k
PROOF: If 0 <= k < n, X is already a basis vector, so we get A .
L n L-n k
Suppose the procedure works for k < L. 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
m L
The procedure evaluates each X to A , so X evaluates to
m
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
X = (X - C X - ... - C )/C , (4)
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.
ITEM (Gosper & Salamin):
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+2Y)*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+3XY)*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
K
Q(K) = -(-Y)
K/2
P(K) = 2(-Y) *T(K;X/SQRT(-4Y)) 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) = (2P(N+1)-P(N))/5, which is a
complex but otherwise square root free closed form. (SQRT(-4) = 2i)
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.
ITEM (Chebychev):
The Nth Chebychev polynomial T(N) = T(N;x) = cos (N arccos x).
T(0) = 1, T(1) = x, T(N+1) = 2x T(N) - T(N-1).
N 1-N
T(N;T(M)) clearly = T(NM). x - 2 T(N), whose degree is N-2,
N
is the polynomial of degree < N which stays closest to x in the
1-N
interval (-1,1), deviating by at most 2 at the N+1 places
where x = cos(K*pi/N), K=0,1,...N.
N
Generating function: SUM T(N)*S = (1-xS)/(1-2xS+S^2).
First order (nonlinear) recurrence:
T(N+1) = xT(N) - SQRT((1-x^2)(1-T(N)^2)).
N
(T(N+1),-T(N)) = (T(1),-T(0))(1,0) ,
where (A,B)(C,D) = (AD+BC+2xAC,BD-AC).
ITEM: n n
1 (1+ix) - (1-ix)
tan (n arctan x) = - * -----------------
n n
i (1+ix) + (1-ix)
*********************************************
BOOLEAN ALGEBRA
*********************************************
ITEM (Schroeppel):
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.
ITEM (Speciner):
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. inf n inf k
The generating function is sum P(n) x = 1 / prod (1-x ) .
n=0 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. inf n inf k k
The generating function is sum PL(n) x = 1 / prod (1-x ) .
n=0 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.
ITEM (Schroeppel):
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).
ITEM (Roger Banks):
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.
ITEM (Schroeppel & Waltz):
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.
ITEM (Gosper):
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?
ITEM (Schroeppel):
(A AND B) + (A OR B) = A + B = (A XOR B) + 2(A AND B).
ITEM (Minsky):
There exists a convex figure n congruent copies of which,
for any n, form a Venn diagram of 2^n regions.
*********************************************
RANDOM NUMBERS
*********************************************
ITEM (Schroeppel):
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.
ITEM (? via Salamin):
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.
ITEM (Salamin):
PROBLEM: Generate random unit vectors in N-space uniform on the
unit sphere. SOLUTION: Generate N Gaussian random numbers and
normalize to unit length.
*********************************************
NUMBER THEORY, PRIMES, PROBABILITY
*********************************************
ITEM (Schroeppel):
After about 40 minutes of run time to verify the absence of
any non-trivial factors less than 2^35, the 125th Mersenne
number, 2^125 - 1, was factored on Tuesday, January 5, 1971,
in 371 seconds run time as follows: 2^125 - 1 =
31 * 601 * 1801 * 26 90898 06001 * 4710 88316 88795 06001.
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: 2^137 - 1 =
32032 21559 64964 35569 * 54 39042 18360 02042 90159.
ITEM (Schroeppel):
For a random number X, the probability of its largest prime
factor being (1) greater than the square root of X is LN 2.
(2) less than the cube root of X 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
the 20th root of X 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] 2.4
10^3 TO 252 40 48 ;252 = 10
252 TO 100 7 8 1.7
100 TO 52 1 1 ;52 = 10
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.
ITEM (Schroeppel):
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:
40T + 1, 62.5T + 1, 200T - 3, 500T - 1, 500T - 7.
ITEM (Fredkin):
3 3 3 3
3 + 4 + 5 = 6 .
ITEM (Schroeppel):
91038 90995 89338 00226 07743 74008 17871 09376^2 =
82880 83126 51085 58711 66119 71699 91017 17324
91038 90995 89338 00226 07743 74008 17871 09376
ITEM (Schroeppel): N
Ramanujan's problem of solutions to 2 - 7 = X^2 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.
ITEM (Schroeppel):
Take a random real number and raise it to large powers; we expect
the fraction part to be uniformly distributed. Some exceptions:
1 -- PHI = (1 + SQRT 5)/2
2 -- all -1 < X < 1
3 -- SQRT 2 (half are integers, other half
are probably uniformly distributed)
4 -- 1 + SQRT 2 -- Proof:
N N
(1 + SQRT 2) + (1 - SQRT 2) = integer (by induction);
N
the (1 - SQRT 2) goes to zero.
5 -- 2 + SQRT 2 -- similar to 1 + SQRT 2
6 -- 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?
ITEM (Schroeppel):
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.
ITEM (Schroeppel):
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!!).
ITEM (Schroeppel):
Take as many numbers as possible from 1 to N such that no 3 are
in arithmetic progression. CONJECTURE: As N approaches infinity, the
(LN 2)/(LN 3)
density of such sets approaches zero, probably like 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
(LN 2)/(LN 3)
N can be proved, it follows that there are
infinitely many primes P1, P2, P3 in arithmetic progression,
(LN 2)/(LN 3)
since primes are much more common than N .
ITEM (Schroeppel):
PROBLEM: How many squares have no zeros
in their decimal expression? Ternary?
ITEM (Gosper):
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, 2, ... . Eg., 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%.
ITEM (Fredkin):
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, ... .
ITEM (Schroeppel, etc.):
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.
ITEM (Salamin):
There are exactly 23000 primes less than 2^18.
ITEM (Gosper):
To show that N+1 L N+1 L
SUM (L=0 to N) (BINOMIAL N+L L)*(X (1-X) + (1-X) X ) = 1
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?
ITEM (Schroeppel):
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.
ITEM (Gosper):
Recurrences for multinomial coefficients:
(A,B,C,...) = (A+B,C,...)(A,B) = (A+B+C,...)(A,B,C) = ...
PROBLEM (Gosper):
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 +or- 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.
ITEM (Schroeppel):
The most probable 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.
ITEM (Beeler):
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
L = (prime - 1)/N, N covering all integers.
Primes with 2 sub-cycles seem to have lengths
M
L = (prime - (-1) )/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
L = 2 (prime + 1)/R or (prime - 1)/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. 25 X^2 + 16 Y^2 seems to express those which are
9 mod 40; (10 X + or - 1)^2 + 400 Y^2 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?
ITEM (Gosper, Schroeppel):
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 Chinese
remainder theorem, there exist invisible sets of every finite
shape. Excellent reference: Amer. Math. Monthly, May '71, p487.
ITEM :
There is a unique "magic hexagon" of side 3:
3 17 18 First discovered by Clifford W. Adams,
19 7 1 11 who worked on the problem from 1910.
16 2 5 6 9 In 1957, he found a solution.
12 4 8 14 (See Aug. 1963 Sci. Am., Math. Games.)
10 13 15 Other length sides are impossible.
ITEM (Schroeppel):
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 2 diagonals.
This covers the square entirely, and each corner twice again.
This adds to 6K, so twice the corner sum is 2K.
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+f = 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
ITEM (Schroeppel):
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.
ITEM (Salamin):
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.]
ITEM (Salamin):
The probability that N numbers will lack
a Pth power common divisor is 1/ZETA(NP).
ITEM (Salamin & Gosper):
The probability that a random rational number
has an even denominator is 1/3.
ITEM (Schroeppel): GAUSSIAN INTEGERS
See following illustrations; also PI section.
ITEM 56 (Beeler): page
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.
ITEM 57 (Beeler, Gosper):
There is at least one zero in the decimal expression of each
power of 2 between 2@8@6 = 77,371,252,455,336,267,181,195,264
and 2@3@0@7@3@9@0@1@4, 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@4@1@1@8@1@6. Assuming there aren't
any then 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:
a) None end in zero.
n
b) After the nth, they are all multiples of 2 .
n-1
c) They get into a loop of length 4 * 5 .
(Because 2 is a primitive root of powers of 5.)
n-1 n
But there are only 4 * 5 multiples of 2 which don't end with
n
zero and are < 10 , so we will see them all. In particular, we
will see the one composed entirely of 1's and 2's, which ends
...11112111211111212122112.
ANSWER (Schroeppel): Arbitrarily many. If we look at the last
n digits of consecutive powers of 2, we see:
a) None end in zero.
n
b) After the nth, they are all multiples of 2 .
n-1
c) They get into a loop of length 4 * 5 .
(Because 2 is a primitive root of powers of 5.)
n-1 n
But there are only 4 * 5 multiples of 2 which don't end with
n
zero and are < 10 , so we will see them all. In particular, we
will see the one composed entirely of 1's and 2's, which ends
...11112111211111212122112.
ITEM (Beeler):
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:
120 = 2^3 * 3 * 5 = 1111000 base 2
672 = 2^5 * 3 * 7 = 1010100000 base 2
523,776 = 2^9 * 3 * 11 * 31 = 1111111111000000000 base 2
ITEM (Root):
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
ITEM (Schutzenberger):
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 sequences exist of any particular length?
ITEM (Gosper):
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).
ITEM (Speciner):
The first four perfect numbers are 6, 28, 496, 8128.
Two-member loops (amicable pairs) are:
220 @E@T 284
1184 @E@T 1210
2620 @E@T 2924
5020 @E@T 5564
6232 @E@T 6368
10744 @E@T 10856
12285 @E@T 14595
17296 @E@T 18416
63020 @E@T 76084
66928 @E@T 66992
67095 @E@T 71145
69615 @E@T 87633
79750 @E@T 88730
100485 @E@T 124155
122265 @E@T 139815
122368 @E@T 123152
141644 @E@T 153176
142310 @E@T 168730
171856 @E@T 176336
176272 @E@T 180848
185368 @E@T 203432
196724 @E@T 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.
*********************************************
AUTOMATA THEORY
*********************************************
ITEM (Schroeppel):
A 2-counter machine, given N in one of the counters, cannot
N
generate 2 . Proven Saturday, September 26, 1970. (Independently
rediscovered by Frances Yao.) But (Minsky, Liknaitzky), given
N
N 2
2 , it can generate 2 . (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
unlimited counters. Such machines are known universal, but
(due to the above) they must have specially encoded inputs.)
ITEM (Schroeppel):
What effort is required to compute PI(X), .7
the number of primes < X? Shanks and Brillhart claim about X .
ITEM (Gosper):
See space-filling curve machine item in TOPOLOGY section.
*********************************************
GAMES
*********************************************
ITEM (Schroeppel):
Regarding "poker coins" game, whose rules are:
1 a player throws N coins;
he then puts one or more aside and rethrows the rest
2 this throwing is repeated until he no longer has any to throw
3 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.
ITEM (Schroeppel):
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.
ITEM:
Berlekamp of Bell Labs has done the 9 squares
(16 dots) Dots game; the 2nd player wins.
ITEM:
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.
ITEM (Beeler):
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.
ITEM (Beeler):
A window-dice game is as follows:
1 The player starts with each of nine windows open,
showing the digits 1 - 9.
2 Roll two dice.
3 Cover up any digits whose sum is the sum on the dice.
4 Iterate throwing and closing windows until the equality of sums
is impossible.
5 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.
ITEM (Beeler):
Sim is a game where two players alternately draw lines connecting
six dots. The first person to form a triangle in his color
loses. The second player 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?
ITEM (Beeler):
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).
ITEM (Beeler):
Triangular Hi-Q (or peg solitaire) is 15 pegs in a triangle.
One 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.
ITEM (Gosper, Brown, Rayfield):
A 1963 PDP-1 computer program gave us some interesting data on
the traditional game of peg solitaire (33 holes in a cross 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 cross 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 eight-membered
classes 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
*********************************************
PROPOSED COMPUTER PROGRAMS, IN ORDER OF
INCREASING RUNNING TIME (Schroeppel)
*********************************************
PROBLEM: 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+or-.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?
PROBLEM: 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).
PROBLEM: Solve the tiger puzzle, a sliding block puzzle mentioned
in Scientific American February 1964, pages 122 - 130.
PROBLEM: 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.
PROBLEM: Count the magic squares of order 5. There are
about 320 million, not counting rotations and reflections.
PROBLEM: List (that is, count) the semigroups of 7 elements;
also, the groups of 256 elements (estimated: 11000).
PROBLEM (Gosper): 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)?
PROBLEM: Solve pentominos on an 8 X 8 checkerboard game(s).
Rules:
1 The checkerboard is for aid in orienting only;
black and white are the same.
2 The two players may each have a full complement of 12
pentominos, or they may "choose up" their half of one set.
3 Players alternate placing pentominos on the board. Pentominos
must not overlap.
4 The last player to place a pentomino wins.
PROBLEM: 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.
PROBLEM: 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 mod 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.
PROBLEM: Analyze giveaway chess, which is as follows:
1 captures must be made,
although you can choose which capture to make
2 pawns must be promoted to queens
3 king is just another piece
4 player to give away all pieces first wins
PROBLEM: 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.
PROBLEM: 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.
PROBLEM: 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.
PROBLEM: Solve "five-in-a-row" on an infinite board.
PROBLEM: 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.
PROBLEM: Solve checkers. There are about a trillion positions.
(Computing time currently estimated (Schroeppel) at 1 year).
Programs below this line are considered unfeasible.
PROBLEM: 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.
PROBLEM: Solve chess. There are about 10^40 possible positions;
in most of them, one side is hopelessly lost.
PROBLEM: Solve Go. About 10^170 positions.
*********************************************
CONTINUED FRACTIONS
*********************************************
ITEM (Schroeppel):
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
X^2 - 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
Y^2 - 1 = 2
Y = SQRT 3
Similar proofs exist for SQRT 5 and SQRT 6; but SQRT 7 is hairy.
ITEM (Schroeppel):
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, ...].
ITEM (Schroeppel):
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.
I (2)
0
A special case is [1, 2, 3, 4, ...] = ------- .
I (2)
1
ITEM (Perron):
n
PRODUCT (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
ITEM (Gosper):
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, vol. 2, p. 316. (In what
follows, "regular" means that all numerators are 1, and any radix
can be read in place of decimal.)
0) 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 ... .
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 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.)
2) 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 2e, but even Schroeppel might not notice
that 6.1102966796... was (4 e^(2/3) - 2)/(e^(2/3) - 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.
3) 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) continued fraction at any
point, then the resulting rational number is a best approximation.
Furthermore, this remains true if the last term of this
approximation is replaced by any smaller positive integer other
than 1. 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 + or -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.
4) Numerical comparison of continued 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.
5) 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.)
6) 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) an initial 0 term.
To negate, negate all the terms, optionally observing that
-a, -b, -c, -d ... = -a-1, 1, b-1, c, d ... .
7) 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.
ITEM (Gosper):
Continued Fraction Arithmetic.
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 (e + 3/pi^2) /(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 p + q /(p + q /( ...
0 0 1 1
= p + q /x', where x' is again a continued fraction and
0 0
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"
p and q and, in effect, change itself into x'. Similarly,
0 0
let y be another procedurally represented continued fraction
r + s /y'. Our problem will be solved if we can write such
0 0
subroutines for z(x,y) = x+y, x-y, xy, 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) = (axy+bx+cy+d)/(exy+fx+gy+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: xy = (1 0 0 0)/(0 0 0 1), and
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 z 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 its 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 of its endpoints, x
constrains z (Inside 1 2), and at y's other extreme, z(x) 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 +or- .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 +or- .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
z(x) = (ax+b)/(cx+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
z(x) = (ax^2 + bx + c)/(dx^2 + ex + 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 ever
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
of 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
but one of the arguments to a function have terminated.
Then, we have the form z(x) = (ax+b)/(cx+d), known as
a homographic function. If ad-bc is +or- 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 not
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 greater than one. 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.
ITEM (Gosper):
Problem: Given an interval, find in it the rational number
with 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.)
*********************************************
GROUP THEORY
*********************************************
ITEM (Schroeppel):
As opposed to the usual formulation of a group,
where you are given
1 there exists an I such that A * I = I * A = A, and
2 for all A, B and C, (A * B) * C = A * (B * C), and
3 for each A there exists an ABAR such that
A * ABAR = ABAR * A = I, and
4 sometimes you are given that I and ABAR are unique.
If instead you are given A * I = A and A * ABAR = I, then
the above rules can be derived. But if you are given A * I = A
and ABAR * A = I, then something very much like a group, but not
necessarily a group, results. For example, every element is
duplicated.
ITEM (Gosper):
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?
ITEM (Schroeppel):
Any permutation on 72 bits can be coded with a routine
containing only the PDP-6/10 instructions "ROT" and "ROTC".
*********************************************
SET THEORY
*********************************************
ITEM (Komolgoroff, maybe?):
Given a set of real numbers, how many sets can you
get using only closure and complement? Answer: 14.
**************************************
QUATERNIONS
**************************************
ITEM (Salamin):
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 Q0^2 + Q1^2 + Q2^2 + Q3^2 = 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) = PQ (P a unit quaternion) is a rigid
rotation in 4-space. This can be verified by expressing PQ 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 NQ = -N.V + N S + N X V. Then it is seen
that (NQ).(NQ) = N.N = 1 and (NQ).Q = 0. Geometrically this
means that NQ 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(T/2) + N sin(T/2)). Then
Q W Q* = (cos T)W + (sin T)(N X W) + (1-cos T)N(N.W), which is W
rotated thru angle T 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 T about some
axis. If rotations are chosen "uniformly", what is the
probability distribution of T? By the above, we choose points
uniformly on the 3-sphere (or hemisphere since it is really
projective). Going into polar coordinates, one finds
P(T) = (2/pi) (sin T/2)^2, 0 < T < pi.
In particular, the expected value of T 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.
*********************************************
POLYOMINOS, ETC.
*********************************************
ITEM:
See the PROPOSED COMPUTER PROGRAMS section
for counts of polyominos of orders < 19.
ITEM (Schroeppel):
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
ITEM (Schroeppel):
PROBLEM: What rectangles are coverable
by various polyominos? For example,
XX can cover rectangles which are 3N by 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.
ITEM (Schroeppel):
PROBLEM: Find a necessary and sufficient condition for
an arbitrary shape in the plane to be domino coverable.
ITEM (Beeler):
"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 says this was found years ago on a 7094.
Verified by both Beeler and Clements.
*********************************************
TOPOLOGY
*********************************************
ITEM:
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 (1 + 48 * H))/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.
ITEM (Schroeppel):
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
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?
ITEM (Gosper):
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 I'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.
*********************************************
SERIES
*********************************************
ITEM (Schroeppel & Gosper):
The sum from N = 0 of [N!N!/(2N)!] = 4/3 + 2*pi/9*SQRT 3.
PROBLEM: Evaluate in closed form the sum from N = 0 of
[N!N!N!/(3N)!]. This sum has been shown equal to the following:
the integral from 0 to 1 of (P + Q arccos (R))dT
where
2 (8 + 7 T^2 - 7 T^3)
P = ---------------------
(4 - T^2 + T^3)^2
and
4 (T - T^2) (5 + T^2 - T^3)
Q = ------------------------------------------------
(4 - T^2 + T^3)^2 SQRT ((4 - T^2 + T^3) (1 - T))
and
T^2 - T^3
R = 1 - --------- .
2
ITEM (Euler):
The series accelerating transformation
(Abramowitz & Stegun, sec. 3.6.27)
K K K+1
A0-A1+A2-... = SUM (-) (DELTA A0)/2
K K-M
(where (DELTA A0) = SUM M=0 to K (-) (BINOMIAL K M) AM = Kth
forward difference on A0) when applied to
N-1 2
pi/4 = 1 - 1/3 + 1/5 - ... gives pi/4 = SUM 2 N! /(2N+1)! .
Applied to the formula for gamma in Amer. Math. Monthly
T
(vol. 76, #3, Mar69 p273) = SUM (-) [LOG2 T]/T
(brackets mean integer part of) we get
-(K+1) I
SUM K=1 to infinity 2 SUM J=0 to K-1 1/(BINOMIAL 2 +J J)
(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 members 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
N+1
The next to left diagonal is 2 ; the perpendicular one 3rd
from the right is 1, *9/1= 9, *10/2= 45, *11/3= 165, *12/4= 495.
ITEM (Henry Cohen):
Gamma = - LN X + X - X^2/2*2! + X^3/3*3! - X^4/4*4! ... + ERROR
-X
Where ERROR is of the order of (e )/X.
ITEM (Schroeppel): -Y
Differentiate Ye = X to get Y+YXY'-XY' = 0.
Substitute for Y a power series in X with coefficients to be determined.
One observes the curious identity:
J-1 N-J N
SUM J=1 to N of (BINOMIAL N J)J (N-J) = N (0^0=1)
N-1 N
and thus Y(X) = SUM N=1 N X /N!
ITEM (Schroeppel):
PROBLEM: Can someone square some series for pi to give
the series pi^2/6 = 1/1^2 + 1/2^2 + ... = SUM 1/N^2 ?
ITEM (Schroeppel):
Consider SUM 1/N^2 =
SUM 1/(N-1/2)-1/(N+1/2) + SUM 1/N^2-1/(N^2-1/4)
= 2 - SUM 1/((4N^2-1)*N^2).
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/18 - SUM 9/(N^2)(4N^2-1)(25N^4+5N^2+9)
where the denominator also =
(N^2)(2N+1)(2N-1)(5N^2+5N+3)(5N^2-5N+3)
ITEM (Polya):
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, vol. 2, page 46.
ITEM (Gosper):
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).
ITEM (Schroeppel, Gosper): inf -N
The "parity number" = 1/2 SUM (parity of N)*2
N=0
where the parity of N is the sum of 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
N N
i.e., stage 0 = 0 -2 -2
stage N+1 = stage N + (1-2 -stage N)/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
N N
NUM N+1 -2 -2
then ------- = 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,
N
an approximant of the regular fraction, roughly the 2 th.
In addition, 4*(parity number) =
2-(1/2)*(3/4)*(15/16)*(255/256)*(65535/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 (Schroeppel, Gosper, Salamin):
Consider the image of the circle ABS z = 1 under the function
n
2
z
f(z) = SUM --- . This is physically analogous to a series of
n
2
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
n
the 2 in the denominator. Thus it is unclear whether the speed
of the "last" hand is really infinite; or, whether the curve's
arc length is really infinite.
n!
z
Also, it is a visually interesting curve, as are f(z) = SUM --- ,
FIB(n) n!
z
and f(z) = SUM ------- . Gosper has programmed the one mentioned
FIB(n)
first, which makes an intriguing display pattern. See following
illustrations. If you write a program to display this, be sure
to allow the following variations:
_
(1) z and z on alternate terms (alternate hands rotate in
opposite directions),
(2) negation of alternate terms (alternate hands initially
point in opposite directions), and
(3) how many terms are used in the computation,
since these cause fascinating variations in the resulting curve.
*********************************************
FLOWS AND ITERATED FUNCTIONS
*********************************************
ITEM (Schroeppel):
An analytic flow for Newton's method square root:
Define F(X) by (X^2+K)/2X; then
N N
2 2
(X+SQRT K) + (X-SQRT K)
F(F(F(...(X)))) = SQRT K ---------------------------
[N times] N N
2 2
(X+SQRT K) - (X-SQRT K)
N
which = SQRT K (coth 2 (arccoth X/SQRT K))
ITEM (Schroeppel):
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:
1 Various linear things.
2 X to different powers, sometimes multiplied by roots of 1.
3 P and Q are each another polynomial R composed
with itself different numbers of times.
4 Solutions arising out of the flow of X^2-2, as follows:
suppose X = Y + 1/Y
N -N
then Y + Y 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-3X (N = 3)
5 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-2Y+2 and Q = 1+(Y-1)^3,
then P(Q) = 1+(Y-1)^6 = Q(P).
Similarly, replacing X with AY+B works.
6 There are no more through degrees 3 and 4 (checked with
Mathlab); but are there any more at all?
ITEM (Schroeppel):
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.
ITEM (Salamin): P
N N P
If F(X)=X , the P-th flow is X , which has a branch point if N
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
N
cases like X ?
ITEM (Schroeppel):
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)
ITEM (Gosper): LOOP DETECTOR
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
of 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 <= LOG2 (largest possible period).
Let C = the number of times 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
E+1
than the low E+2 bits of C - 2 .
ITEM (Schroeppel, Gosper, Henneman & Banks) (from Dana Scott?):
The "3N+1 problem" is iteratively replacing N by N/2 if N is even
or by 3N+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?
ITEM (Schroeppel, Gosper):
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.
ITEM (Gosper):
The "C" Curve
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
his 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 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.
****************************************
PI
****************************************
ITEM: GAUSSIAN INTEGERS (For use by next item.)
Reference: Hardy and Wright, Theory of Numbers. The Gaussian
integers are x+iy where x and y are integers. Unique
factorization holds, except for powers of i, and the Gaussian
primes are (1) a+bi if a^2+b^2 is prime and (2) integer primes
that = 3 mod 4. If N(x+iy) = x^2+y^2, then N(uv) = 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+iy into Gaussian primes, first factor N(x+iy).
(A) If 2 divides N(x+iy), then 1+i and 1-i divide x+iy.
Either factor may be used since i(i-1) = i+1.
(B) If p=3 mod 4 divides N(x+iy), then p divides x+iy.
(C) If p=1 mod 4 divides N(x+iy) and p = a^2+b^2,
then a+ib or b+ia = i(a-ib) divides x+iy.
If both do, then p divides x+iy.
ITEM (Salamin): GENERATION OF ARCTANGENT FORMULAS FOR PI
n1 atan(y1/x1) + n2 atan(y2/x2) + ...
= n1 arg(x1+iy1) + n2 arg(x2+iy2) + ...
If each x+iy 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+ib and a-ib can't both divide x+i.
Example:
8^2+1 = 13 * 5
18^2+1 = 13 * 5^2
57^2+1 = 13 * 5^3 * 2
From this we get the factorization
8+i = (3+2i) (2-i)
18+i = (3-2i) (2-i)^2 i
57+i = (3-2i) (2+i)^3 (1-i)
Since we only care about the phase, multiplication
by a positive real number may be ignored below.
a b c
(8+i) (18+i) (57+i) =
a-b-c -a-2b+3c c b
(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
(8+i)^5 (18+i)^2 (57+i)^3 = (1-i)^3 i^2
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:
atan(1/n) - atan(1/(n+1)) = atan(1/(n^2+n+1))
Let x =1, y =0, x =x +2y , y =x +y .
0 0 n n-1 n-1 n n-1 n-1
x /y are the continued fraction approximants to SQRT(2).
n n
atan(1/y ) + atan(1/x ) = atan(1/x )
2n 2n 2n-1
atan(1/y ) - atan(1/x ) = atan(1/x )
2n 2n 2n+1
ITEM (Gosper):
pi = 28 ARCTAN (3/79) + 20 ARCTAN (29/278)
pi = 48 ARCTAN (3/79) + 20 ARCTAN (1457/22049)
Which isn't too interesting except that it means that
(79+3i)^48 (22049+1457i)^20 is a negative real number.
ITEM (Ramanujan):
4/pi = SUM from N=0 to infinity
N
(-1) (1123 + 21460 N) (1*3*5*...*(2N-1)) (1*3*5*...*(4N-1))
------------------------------------------------------------
2N+1 N
(882 ) (32 ) (N!)^3
This series gives about 6 decimal places accuracy per term.
1/(sqrt(8) pi) = SUM from N=0 to infinity
(1103 + 26390 N) (1*3*5*...*(2N-1)) (1*3*5*...*(4N-1))
------------------------------------------------------
4N+2 N
(99 ) (32 ) (N!)^3
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).
ITEM:
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.)
ITEM:
The fraction part of pi 10^760 begins: .49999998...
ITEM (Salamin):
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
ITEM (Salamin):
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
1. ELLIPTIC INTEGRALS
Define elliptic integrals:
1 2 2
K(m) = INTEGRAL 1/SQRT[(1 - t ) (1 - m t )] dt
0
K'(m) = K(1 - m)
If A and B are given, and
0 0
A = arithmetic mean of A and B
n+1 n n
B = geometric mean of A and B ,
n+1 n n
then define
AGM(A ,B ) = lim A = lim B
0 0 n n
This is called the arithmetic-geometric mean.
Quadratic convergence rate:
A - B = (A - B )^2/8A
n+1 n+1 n n n+1
K'(x^2) AGM(1,x) = pi/2 [see A&S].
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.
2. LOGARITHMS
For small m,
K(m) = (pi/2) (1 + m/4 + O(m^2))
exp[-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
ABS[(K'(16/x^2) - log x)/log x] < EPSILON.
This becomes
ABS[(4/x^2) (1 - 1/log x)] < ABS(4/x^2) < EPSILON
ABS(x) > 2/SQRT(EPSILON).
x can be complex. If ABS(x) is not too close to 1, x can be
brought into range by reciprocating or repeated squaring.
3. PI n
Let x = e , then
-n
pi = 2 n AGM(1, 4 e ).
Suppose EPSILON = 10 to the minus a billion.
Then the above equation for pi is valid when n > 1.15 billion.
-n
e is calculated by starting with 1/e and squaring k times.
k
Thus n = 2 . 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.
ITEM (Schroeppel):
n n n
In the above, instead of x = e , use x = 2 and x = e*2 .
Then simultaneous equations can be solved to give both pi and
log 2. This avoids having to square e, but requires two AGM's,
and therefore takes longer.
*********************************************
PROGRAMMING HACKS
*********************************************
WARNING: Numbers in this section are octal
(and occasionally binary) unless followed by a decimal point.
105=69.. (And 105.=69 hexadecimal.)
ITEM (Gosper):
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
ITEM (Cohen):
Another simple display program: ("munching squares")
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 2,1
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, ...)
ITEM (Schroeppel):
Munching squares is just views of the graph Y = X XOR T
for consecutive values of T = time.
ITEM (Cohen, Beeler):
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.
ITEM (Minsky):
Here is an elegant way to draw almost circles on
a point-plotting display. CIRCLE ALGORITHM:
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.
ITEM (Schroeppel):
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.)
ITEM (Gosper):
Separating X from Y in the above recurrence,
X(N+1) = (2-EPS^2)*X(N) - X(N-1)
Y(N+1) = (2-EPS^2)*Y(N) - Y(N-1).
These are just the Chebychev recurrence with cos THETA (the
angular increment) = 1-EPS^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.
ITEM (Salamin):
With exact arithmetic, the circle algorithm is stable iff
ABS(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)).
ITEM (Minsky):
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.
ITEM (Gosper):
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.
ITEM (Liknaitzky):
To subtract the right half of an accumulator from the left
(as in restarting an AOBJN counter): IMUL A,[377777,,1]
ITEM (Mitchell):
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
ITEM (Freiberg):
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.
ITEM (Gosper, Salamin, Schroeppel):
A miniature (recursive) sine and cosine routine:
COS: FADR A,[1.57079632679] ;pi/2
SIN: MOVM B,A ;argument in A
CAMG B,[.00017] ;<= (CUBEROOT 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 ABS(sin) in B
;ABS(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.
X
In general, to compute functions like e , 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(2X) = 2F*(F+2) F(EPSILON) = -EPSILON^2/2
X
G(X) = e -1 G(2X) = 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.
ITEM (Gosper, Schroeppel):
(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 = (CUBEROOT 3) / 2^13.
ITEM (Gosper):
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
MOVEI 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.
ITEM (Gosper):
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.
ITEM (Gosper):
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.
ITEM (Sussman):
To exchange two variables in LISP without using a third variable:
(SETQ X (PROG2 0 Y (SETQ Y X)))
ITEM (Samson):
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
ITEM (Freiberg):
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.
ITEM (Gosper, Liknaitzky):
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.
ITEM (Gosper, Freiberg):
;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^12
ANDI A,41 ;"
DIVI A,1777 ;casting out 2^12-1's
ITEM (PDP-1 hackers):
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.
ITEM (in order of one-ups-manship:
Gosper, Mann, Lenard, [Root and Mann]):
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..
ITEM (Jensen):
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 DATAO 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.
ITEM (Gosper):
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.
ITEM (Gosper):
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,[...[PUSHJ 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.
ITEM (Gosper):
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,[+or-233000,,] ;not in PDP-6 repertoire
TLC A+1,233000 ;if those bits really bother you
When you know the sign of A, and ABS(A) < 2^26, you can
FAD A,[+or-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.
ITEM (Gosper, Nelson):
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.
ITEM (Gosper):
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
*********************************************
PROGRAMMING ALGORITHMS, HEURISTICS
*********************************************
ITEM (Gosper):
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 BANANANANANANANA....
We note an ambiguity in the phrase, "the Nth occurrence of."
In one 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.
ITEM (Gosper): DRAWING CURVES INCREMENTALLY
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
F = X^2+Y^2-R^2 = 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.
*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.
ITEM (Schroeppel, Salamin):
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
(for example, Bessel's equation, X^2Y''+XY'+(X^2-N^2)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.
X
Further, e 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.
ITEM (Gosper):
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 ;next
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 top 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 characters 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.
ITEM (Gosper):
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 others along the line.
The perpendicular distance which the vector C lies
from the line connecting vectors A and B is just
(C - A) CROSS (B - A)
----------------------- ,
2 ABS(A - B)
but maximizing this can lose on very pointy V's.
The distance sum hack can lose on very squashed Z's.
*********************************************
HARDWARE
*********************************************
ITEM (Gosper):
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:
1) An advantage is that negation and numerical comparison can
be accomplished with the same instructions for both fixed and
floating point numbers.
2) 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
n -n
negated powers of two. (That is, -(2 ), not (2) .)
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+EPS with minus 200777,,777777+2EPS. For
0 =< EPS =< 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.
ITEM (Roe): VOLTAGE REGULATORS
Fairchild is now supplying positive voltage
regulators costing about 2 dollars in lots
of 1 (for example, the uA7805 for +5 volts).
ITEM (Roe): CURRENT MIRRORS
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.)
ITEM (Roe): ONE-SHOT
A dual MOS D-type flip-flop (such as the CD4013AE)
can be used to make a one-shot as follows:
ITEM (Roe): OSCILLATORS
Everyone has their own favorite oscillator circuits;
here are some we like.
I crystal, overtone, transistor
II crystal, fundamental, transistor (drives at least 1 TTL load)
III 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)
IV 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
VI 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).
ITEM (Roe): FM RADIO LINK
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 +12 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.
ITEM (Roe): PHONE LINE XMTR, RCVR
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 ratio greater 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).
ITEM (Roe): DC MOTOR VELOCITY SERVO
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 foreward 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.
ITEM (Roe): OPTICAL COUPLER
When two circuits are at potentials differing by a few hundred
volts but wish to communicate with each other, one solution 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.
ITEM (Roe): PHOTOCATHODE CURRENT OSCILLATOR
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.
ITEM (Roe): DEFLECTION AMPLIFIER
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:
1 Except where noted, resistors 10%, 1/4 watt.
2 Capacitances in microfarads/volts; electrolytics aluminum.
3 Diodes 1N4727, 1N4154,1N4009 etc.; stored charge no more than
80 picocoulombs at 1 milliampere foreward current.
4 1D103 = GE thermistor mounted at center of main heat sink.
5 220J = Analog Devices chopper amplifier.
6 * = temperature protection circuit (overtemperature cutout).
7 Q2, Q3, Q4, Q5, Q6, Q12, 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.
8 All transistors Motorola.
9 All zeners 1 watt.
10 VE48X = Varo; could be two 2 A 50 PIV fast recovery.
11 Output capacitance about 800 pf; damping R about 150 ohms
for critical damping.
12 Slews from + (or -) 2 A to - (or +) 2 A in 4 microseconds;
dE/dt at hot side of deflection coil is about a billion v/sec.
13 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 becomming one.
14 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

Reference in New Issue View Git Blame Copy Permalink