HAKMEM

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

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

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

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

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

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

Marvin Minsky        [minsky@ai.mit.edu]
Bill Gosper          [rwg@newton.macsyma.com]
Michael Beeler       [beeler@bbn.com]
Joe Cohen
Jerry Freiberg
John Roe
Rich Schroeppel      [rcs@cs.arizona.edu]
David Silver
Michael Speciner     [ms@color_age.com]
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            [Mike.Paterson@dcs.warwick.ac.uk]

Jud Lenard               Dave Plumer
Ben Gurley (deceased)    Steve Root

Gene Salamin    [Gene_Salamin@cohr.com]
Eric Jensen              Frances Yao
Edward Fredkin           PDP-1 hackers

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.

CONTENTS, HAKMEM 140

• 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
  • Item 12 Fast Fibonacci Transform
  • Item 13 Linear Recurrence Relations
  • Item 14 Rapid Recurrences
  • Item 15 Chebychev polynomials
  • Item 16 Tangents and arctangents
• Boolean Algebra
  • Item 17 Minimize AND's
  • Item 18 Count monotonic Boolean functions
  • Item 19 2-NOT's
  • Item 20 Venn Diagrams
  • Item 21 Cover character raster
  • Item 22 Binary masks
  • Item 23 Plus and XOR
  • Item 24 Venn Diagrams
• Random Numbers
  • Item 25 Random number generators
  • Item 26 Gaussian distribution
  • Item 27 Random unit vectors in N-space
• 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
  • Item 64 2-counter machines
  • Item 65 Complexity of pi(X)
  • Item 66 Space-filling curves
• Games
  • Item 67 "Poker coins"
  • Item 68 Blackout
  • Item 69 Dots
  • Item 70 Chess problem
  • Item 71 Instant Insanity
  • Item 72 Window-dice
  • Item 73 Sim
  • Item 74 Tactix
  • Item 75 Peg solitaire
  • Item 76 Hi-Q
• 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
  • Item 97 Sqrt(2), Sqrt(3)
  • Item 98 Minimum of factorial function
  • Item 99 Partial quotients in arithmetic progression
  • Item 100 Product
  • Item 101A Continued fraction representation
  • Item 101B Continued fraction arithmetic
  • Item 101C Rationals in intervals
• Group Theory
  • Item 102 Group-like definitions
  • Item 103 Hamiltonian paths
  • Item 104 Permuting bits on PDP-6/10
• Set Theory
  • Item 105 Closure and complement
• Quaternions
  • Item 107 Quaternions
• Polyominos, etc.
  • Item 108 Counting polyominos
  • Item 109 Tessellating the plane
  • Item 110 Covering rectangles
  • Item 111 Domino covering
  • Item 112 Polyiamonds
• Topology
  • Item 113
  • Item 114
  • Item 115
• Series
  • Item 116
  • Item 117 Gamma
  • Item 118 N^N
  • Item 119 Pi series
  • Item 120 Accelerating series
  • Item 121 Bernoulli polynomials
  • Item 122 Parity number
  • Item 123 Fourier clocks
  • Item 124
  • Item 125 Radius of convergence
• 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
  • Item 136 Gaussian integers
  • Item 137 Arctangent formulas for pi
  • Item 138 Arctangent formulas for pi
  • Item 139 Ramanujan formulas for pi
  • Item 140 Continued fraction for pi
  • Item 141 Pi digits
  • Item 142 Pi from fast trig functions
  • Item 143 AGM for elliptic integrals, log, and pi
  • Item 144 AGM for 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
  • Item 176 BANANA Phenomenon
  • Item 177 Drawing Curves Incrementally
  • Item 178 Evaluating Functions
  • Item 179 Searching Character Strings
  • Item 180 Finding Corners in Images
• Hardware
  • Item 181 Floating Point
  • Item 182 Voltage regulators
  • Item 183 Current mirrors
  • Item 184 One-shot
  • Item 185 Oscillators
  • Item 186 FM Radio Link
  • Item 187 Phone Line XMTR, RCVR
  • Item 188 DC Motor Velocity Servo
  • Item 189 Optical Coupler
  • Item 190 Photocathode Current Oscillator
  • Item 191 Deflection Amplifier

Figures

• 1a, 1b Binary integers radix i-1, i+1.
• 2 Radix i-1 fraction parts (Knuth).
• 3a, 3b Squared square, rectangle.
• 4 Square, hexagon dissection.
• 5 Hexiamond solutions.
• 6a, 6b "clock hands" series.
• 7 Binary numbers radix -2.
• 8 "C" curves.
• 9 Incremental curve drawing.