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 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= 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: ,,) 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