A. I. Laboratory

Artificial Intelligence Memo No. 239

February 29, 1972

R. W. Gosper [rwg@newton.macsyma.com]

R. Schroeppel [rcs@cs.arizona.edu]

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

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

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

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

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

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

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

Once at the A. I. Lab but now elsewhere:Marvin Minsky [minsky@ai.mit.edu] Bill Gosper [rwg@newton.macsyma.com] Michael Beeler [beeler@bbn.com] Joe Cohen Jerry Freiberg John Roe Rich Schroeppel [rcs@cs.arizona.edu] David Silver Michael Speciner Richard Stallman [rms@ai.mit.edu] Gerald Sussman [gjs@ai.mit.edu] David Waltz

Jan Kok William Henneman Rici Liknaitzky George Mitchell Peter Samson Stuart Nelson Roger Banks Rollo Silver Mike Paterson

Jud Lenard Dave Plumer Ben Gurley (deceased) Steve Root

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

Jackson Wright Steve Brown Malcolm Rayfield

Marco Schutzenberger Henry Cohen

Bill Mann

Robert Clements

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.

- Geometry, Algebra, Calculus
- Item 1 Fractional factorials
- Item 2 N-gon diagonals
- Item 3 Convergence of Newton's square roots
- Item 4 Quartic discriminant
- Item 5 General discriminant
- Item 6 Symmetric functions
- Item 7 Symmetric functions
- Item 8 Cubic solution
- Item 9 Quartic solution
- Item 10 Trigonometric cubic solution
- Item 11 Conformal mappings of N-space

- Recurrence Relations
- Boolean Algebra
- Random Numbers
- Number Theory, Primes, Probability
- Item 28 Mersenne 125 is composite
- Item 29 Probability of largest prime factor
- Item 30 Twin Primes
- Item 31 A Ramanujan problem
- Item 32 Distribution of fractions
- Item 33 Russian doll primes
- Item 34 Factorial and integer square root
- Item 35 Arithmetic progressions
- Item 36 Squares with no zero digits
- Item 37 Numbers with each digit
- Item 38 Forward differences
- Item 39 Sequences of digits
- Item 40 Variance of a sum
- Item 41 Number of primes less than 2^18
- Item 42 Probability of PingPong winner
- Item 43 Multinomial coefficients
- Item 44 Recurrences for multinomial coefficients
- Item 45 Locus of steps
- Item 46 Distribution of bridge hands
- Item 47 Fibonacci series mod P
- Item 48 Visibility on 2D lattice
- Item 49 Magic hexagon
- Item 50 No magic cubes of order 4
- Item 51 No magic tesseract of order 5
- Item 52 Relatively prime probability
- Item 53 Lack of common divisors
- Item 54 Probability of even denominators
- Item 55 Gaussian integers
- Item 56 "Length" of a number
- Item 57 Zero digits in powers of two
- Item 58 Sum of cubes
- Item 59 Interesting square
- Item 60 Perfect numbers
- Item 61 Amicable pairs
- Item 62 Amicable pairs
- Item 63 Joys of 239

- Automata Theory
- Games
- Proposed Computer Programs
- Problem 77 Counting polyominos
- Problem 78 Solve
*minichess* - Problem 79 Solve the
*tiger puzzle* - Problem 80 Find smallest
*squared square* - Problem 81 Counting
*magic squares* - Problem 82 Counting semigroups
- Problem 83 Counting inscribed circles
- Problem 84 Solve pentominos
- Problem 85 Geometric dissections
- Problem 86 Domino coverings
- Problem 87 Analyze
*giveaway chess* - Problem 88 Analyze
*escalation chess* - Problem 89 Analyze "4 pawns"
- Problem 90 Solve Scarne's game
*Teeko* - Problem 91 Solve "five-in-a-row"
- Problem 92 Solve 4x4x4
*Tic-Tac-Toe* - Problem 93 Solve
*checkers* - Problem 94 Solve
*Hex* - Problem 95 Solve
*chess* - Problem 96 Solve
*Go* - Continued Fractions
- Group Theory
- Set Theory
- Item 105 Closure and complement

- Quaternions
- Item 107 Quaternions

- Polyominos, etc.
- Topology
- Series
- Flows and Iterated Functions
- Item 126 Flow for Newton's square root
- Item 127 Polynomial functions which commute
- Item 128 Binary/negative binary radix flow
- Item 129 Flow power series
- Item 130 Flow power series
- Item 131 Arithmetic geometric mean
- Item 132 Loop detector
- Item 133 3 N + 1 problem
- Item 134 Numbers to English words flow
- Item 135 The "C" Curve

- Pi
- Programming Hacks
- Item 145 Display/sound
- Item 146 Munching squares
- Item 147 Munching squares
- Item 148 Munching squares
- Item 149 Circle algorithm
- Item 150 Circle algorithm
- Item 151 Circle algorithm
- Item 152 Circle algorithm
- Item 153 3D solids on 2D display
- Item 154 Twos-complement arithmetic
- Item 155 Subtract right from left
- Item 156 Make AOBJN pointer
- Item 157 Make AOBJN pointer
- Item 158 Recursive SIN/COS
- Item 159 Recursive SIN/COS
- Item 160 Log base 2
- Item 161 Swap two locations
- Item 162 Swap two bits
- Item 163 Exchange two Lisp variables
- Item 164 Max of byte pointers
- Item 165 Byte pointers
- Item 166 Rotate 3 accumulators
- Item 167 Parity, count, reverse bits
- Item 168 PDP-1 sounds
- Item 169 Count ones
- Item 170 Decimal print routines
- Item 171 Division by zero
- Item 172 Two word Lisp CONS
- Item 173 Fix float
- Item 174 Fix point of float function
- Item 175 Next higher

- Programming Algorithms, Heuristics
- Hardware