HAKMEM - collection of mathematical curiosities and useful algorithms

[lpetrich]

I first learned of HAKMEM from The Jargon File - a 1990's compendium of computer-whiz slang.

HAKMEM -- CONTENTS -- DRAFT, NOT YET PROOFED - from February 29, 1972

It's rather interesting to review this 48-year-old document.

GEOMETRY, ALGEBRA, CALCULUS

It starts off with fractional factorials and how they are interrelated. I must note that they are more usually written with the Euler-Legedre gamma functions:
\( x! = \Gamma(x+1) \)
That document also states the gamma-function reflection and multiplication identities, though written in factorial form.

\( \Gamma(z) \Gamma(1-z) = \frac{\pi}{\sin \pi z} \)
\( \prod_{k=0}^{n-1} \Gamma(1 + k/n) = (2\pi)^{(n-1)/2} n^{1/2-nz} \Gamma(nz) \)


ITEM 2 (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?

I wrote a Mathematica program for drawing regular polygons with all their diagonals, and I counted interior regions up to an octagon:

0, 0, 1, 4, 11, 24, 50, 80

I then plugged these numbers into the Online Encyclopedia of Integer Sequences (oeis.org), and I found
A007678 - OEIS - Number of regions in regular n-gon with all diagonals drawn.

Related:
A135565 - OEIS - Number of line segments
A007569 - OEIS - Number of vertices

 

[lpetrich]

Item 5: The discriminant of a polynomial:

\( \prod_{i,j>i} (r_i - r_j)^2 = \left( \det ((r_i)^p) \right)^2 \)

for all roots r_i and powers p from 0 to (number of roots) - 1

A polynomial's discriminant can be calculated with simple arithmetic on its coefficients.

ITEM 6: symmetric functions and powers of lists of variables

a = x + y + z + ...
b = x*y + x*z + y*z + ...
c = x*y*z + ...

x + y + z + ... = a
x^2 + y^2 + z^2 + ... = a^2 - 2*b
x^3 + y^3 + z^3 + ... = a^3 - 3*a*b + 3*c
x^4 + y^4 + z^4 + ... = a^4 - 4*a^2*b + 2*b^2 + 4*a*c - 4*d

These are  Newton's identities and there are recurrences for them in both directions. One can find sums of powers of polynomial roots by doing simple arithmetic on the polynomial's coefficients. This is because these coefficients are symmetric functions of the polynomial's roots.

ITEM 7 (Gosper): Generating polynomial of symmetric function:

\( \sum_i s^i p(i;x_1,x_2,x_3,\cdots) = (1 + s x_1) (1 + s x_2) (1 + s x_3) \cdots \)

Then solutions of cubic and quartic polynomials.

Quadratic: square root
Cubic: square root, then cube root
Quartic: solution of cubic equation, then some square roots
Quintic and higher: no general solution using nth roots

 

[lpetrich]

I like this:

ITEM 11 (Salamin):
The following operations generate one-to-one conformal mappings of Euclidean N-space onto itself.

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

PROBLEMS:

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

One-to-one = injection = for function f, if y != x, then f != f(x)

RECURRENCE RELATIONS

ITEM 14 (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 + 2 Y) * F(N) - Y^2 * F(N-2).

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

Also gives general formulas for bigger steps.

Mentions Chebyshev polynomials: T(n,x) = cos(n*arccos(x)) -- for integer n, it's easy to show that that's a polynomial
A companion one for that is U(n,x) = sin((n+1)*arccos(x))/sqrt(1-x^2)

Then this formula:
\( \tan(n \arctan x) = \frac{1}{i} \cdot \frac{(1 + ix)^n - (1-ix)^n}{(1 + ix)^n + (1-ix)^n} \)

 

[lpetrich]

BOOLEAN ALGEBRA

ITEM 17 (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.

Trying to minimize the number of components needed is a big problem in computer-chip design.

RANDOM NUMBERS

ITEM 26 (? 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 27 (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.

That last one works because of the Gaussian distribution. It won't work for uniformly-distributed random numbers, the easiest kind to generate.

 

[lpetrich]

NUMBER THEORY, PRIMES, PROBABILITY

ITEM 28 (Schroeppel): - factoring some Mersenne numbers M = 2^n-1: M(125), M(137)

For n composite, M is also composite. For n prime, M may or may not be prime. I will call composite M(prime) a Mersenne pseudoprime. It is unknown whether or not there is an infinite number of Mersenne primes or Mersenne pseudoprimes.

 Mersenne prime
List of known Mersenne prime numbers - PrimeNet

The first Mersenne primes are for 2, 3, 5, 7, but 11 gives a pseudoprime: M(11) = 2047 = 23*89

Largest known one: M(82,589,933)

Mersenne primes are related to even perfect numbers (number = sum of factors less than it): if M(p) is a prime, then the corresponding perfect number is 2^(p-1)*M(p) Every even perfect number has that form, and it is unknown whether any odd perfect numbers exist.


ITEM 31 (Schroeppel): A Ramanujan problem: find integer solutions to 2^n - 7 = x^2. The only solutions were found by R himself: n = 3, 4, 5, 7, 15

A similar problem: solutions of n! + 1 = x^2

Only ones I found are n = 4, 5, 7
I tested up to n = 1000 - it took nearly 6 seconds with Mathematica on my 2018 iMac.

 

[lpetrich]

AUTOMATA THEORY

GAMES

ITEM 75 (Gosper, Brown, Rayfield): solving peg solitaire

It's 32 pegs in 33 holes in a plus shape, starting with the center hole empty. One moves by making a peg jumping over another peg, with that peg being removed.

Every position has a dual position, with the peg presence/absence inverted. Thus, the initial position has the final position as its dual, one move after initial has dual one move before final.

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

The classes are (even, even), (even, odd), (odd, even), (odd, odd) by coordinates.

So the only peg that can remain at the end is one that can jump to the center in the first move.

 

[lpetrich]

PROPOSED COMPUTER PROGRAMS, IN ORDER OF INCREASING RUNNING TIME (Schroeppel)

PROBLEM 77: Count the polyominos up to, say, order 20.

 Polyomino extends dominos to multiple squares

Equivalence is to within translation, rotation, reflection, and glide reflection.
A000105 - OEIS (28) - polyominoes
A001419 - OEIS (26) - polyominoes with holes
A000104 - OEIS (26) - polyominoes without holes
A030227 - OEIS (36) - achiral polyominoes (those with reflection symmetry)
A030228 - OEIS (28) - chiral polyominoes (those without reflection symmetry)
A000988 - OEIS (30) - one-sided polyominoes (mirror images counted separately)
A001168 - OEIS (28) - fixed polyominoes (rotations and mirror images counted separately)

Polyominoes broken down by symmetry. Those with some symmetry are not counted among those with a subset symmetry.
A142886 - OEIS (65) - fully-symmetric polyominoes (all rotations and reflections, group D4)
A144553 - OEIS (59) - fully rotation-symmetric polyominoes (all rotations, no reflections, group C4)
A056878 - OEIS (52) - polyominoes symmetric around both diagonals (diagonal reflections, 180d rotations, group D2)
A056877 - OEIS (48) - polyominoes symmetric around both axes (axial reflections, 180d rotations, group D2)
A006747 - OEIS (28) - 180d-rotation-symmetric polyominoes (group C2)
A006748 - OEIS (28) - diagonally-symmetric polyominoes (one reflection, group D1)
A006746 - OEIS (28) - axially-symmetric polyominoes (one reflection, group D1)
A006749 - OEIS (28) - asymmetric polyominoes (group D1)

 

[lpetrich]

PROBLEM 81:
Count the magic squares of order 5. There are about 320 million, not counting rotations and reflections.
PROBLEM 82:
List (that is, count) the semigroups of 7 elements; also, the groups of 256 elements (estimated: 11000).

From  Magic square - A006052 - OEIS - the number of magic squares is known up to size 5:
1, 0, 1, 880, 275305224

A027851 - OEIS - the number of semigroups is known up to size 9:
1, 5, 24, 188, 1915, 28634, 1627672, 3684030417, 105978177936292

Mathematica's function FiniteGroupCount[256] returns 56092
Its function FiniteAbelianGroupCount[256] returns 22

 

[lpetrich]

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

 3D tic-tac-toe - there is a strategy that will make the first player always win, but it's rather complicated.

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

 Draughts - Checkers was weakly solved in 2007 by Jonathan Schaeffer. From the standard starting position with perfect play, both players can force a draw.

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

PROBLEM 96:
Solve Go. About 10^170 positions.

Not likely to be solved anytime soon.

 

[lpetrich]

CONTINUED FRACTIONS

ITEM 97 (Schroeppel): CONTINUED FRACTIONS

These are rather arcane. Here is a simple one:

\( x = \frac{a}{b + x} = \frac{a}{b +} \cdot \frac{a}{b +} \cdot\frac{a}{b +} \dots \)

It's a continued-fraction solution for x of equation x^2 + b*x + a = 0


ITEM 99 (Schroeppel):
The value of a continued fraction with partial quotients increasing in arithmetic progression is

\( [A+D, A+2D, A+3D, \dots] = \frac{I_{A/D}(2/D)}{I_{1+A/D}(2/D) \)

ITEM 100 (Perron):

\( \prod_{k=1}{n} \left( 1 + \frac{1}{a_k} \right) = 1 + \frac{1}{a_1 - } \cdot \frac{(a_1+1)a_1}{a_1+a_2+1 -} \cdot \frac{(a_2+1)a_2}{a_2+a_3+1 -} \cdots \frac{(a_{n-1}+1)a_{n-1}}{a_{n-1}+a_n+1} \)

 Continued fraction has more on this subject, including a forward algorithm to calculate them, an an alternative to the backward algorithm that one may first think of using.

 

[lpetrich]

GROUP THEORY

ITEM 103 (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: (notation not very clear in his example)

But one can construct *every* permutation using only swaps:  Heap's algorithm - it generates all n! permutations for n symbols using only one swap for each new permutation.

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

I had to look this up: PDP-10 Shifting

ROT rotates over the upper or lower 36 bits of a 72-bit set, ROTC over all 72.

I got a swap out of these two operations, and I'm sure it's possible to get any swap, and from there, any permutation.

 

[lpetrich]

SET THEORY

QUATERNIONS

They have a scalar part and a vector part (S,V), they add component-by-component, and they follow this multiplication law:
(s1,v1) * (s2,v2) = (s1*s2 - v1.v2, s1*v2 + s2*v1 + (v1)x(v2))

I've seen a - sign for the crossed part. One can implement quaternions with Pauli matrices:
scalar * (2*2 identity matrix) + vector. (vector of Pauli matrices)

Pauli matrices appear in the quantum-mechanical theory of spin 1/2.

Though quaternion multiplication is not commutative, it is associative, and a set of quaternions can form a group under multiplication, with identity (1,0) and inverse of (s,v) = (s,-v)/(s^2 + v.v)

The absolute square of a quaternion is (s^2 + v.v) and absolute squares are multiplied in quaternion multiplication.

One can easily find a rotation matrix from a unit quaternion, and for this reason, quaternions are often used for handling rotations in computer graphics and in navigation and guidance.

 

[lpetrich]

POLYOMINOS, ETC.

ITEM 109 (Schroeppel):
Tessellating the plane with polyominos:

Possible up to size 6, and possible for all but 4 of the 108 size-7 ones. None of the plane-tiling ones need flipping for doing the tiling.

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

One can find a necessary condition with a checkerboard covering. For a red-and-black board, count how many red squares and how many black squares. For a domino covering to be possible, the two numbers must be equal, since they are equal for a domino. This is a necessary condition but not a sufficient one, since it's hard for me to think of what would guarantee that such a covering is possible.


ITEM 112 (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.

Iamonds: 1,1,1,3,4,12,24,66,160,448 -- triangular polyominoes -- A000577 - OEIS

Ominos: 1,1,1,2,5,12,35 -- polyominoes -- A000105 - OEIS

Hexafrobs: 1,1,3,7,22 -- hexagonal polyominoes -- A000228 - OEIS

Soma-like: 1,1,2,8,29 -- 3D polyominoes (polycubes) -- A000162 - OEIS

 

[lpetrich]

Triangular polyominoes
A000577 - OEIS (30) - tri polys
A070765 - OEIS (30) - tri polys without holes
A006534 - OEIS (28) - one-sided tri polys
A001420 - OEIS (32) - fixed tri polys
A030223 - OEIS (28) - tri polys with bilateral symmetry
A001420 - OEIS (28) - tri polys without bilateral symmetry

Hexagonal polyominoes
A000228 - OEIS (21) - hex polys
A006535 - OEIS (20) - one-sided hex polys
A001207 - OEIS (35) - fixed hex polys
A030225 - OEIS (20) - hex polys with bilateral symmetry

Pentagonal polyominoes
A103465 - OEIS (16) - pent polys

Cubical polyominoes
A000162 - OEIS (16) - 3D polycubes

I think I'll leave off here.

 

[lpetrich]

The OEIS has polyomino counts for all the subgroups of the symmetry group of the square:
D4, D2(ax), D2(dg), D1(ax), D1(dg), C4, C2, C1
ax = axial
dg = diagonal
D1 has one each for each axis and diagonal

For the other kinds of polyominoes, the counts are much more limited.

For triangular and hexagonal ones, here are the subgroups of the symmetry group of the hexagon:
D6, D3(ax), D3(dg), D2, D1(ax), D1(dg), C6, C3, C2, C1

For pentagonal ones, here are the subgroups of the symmetry group of the pentagon:
D5, D1, C5, C1

The OEIS has counts of cubical polyominoes with various sizes of symmetry group: 1, 2, 3, 4, 6, 8, 24

But that is an incomplete count of subgroups of the symmetry group of the cube, the octahedral group. Full octahedral group/List of all subgroups - Wikiversity - grouped by group order (how many members)

• 48: Oh (S4*Z2)
• 24: O (S4), Td (S4), Th (A4*Z2)
• 16: D4h (Dih4*Z2)
• 12: T (A4), D3d (Dih3)
• 8: D2h (Z2*Z2*Z2), C4h (Z4*Z2), C4v (Dih4), D2d (Dih4), D4 (Dih4)
• 6: C3v (S3), D3 (S3), S6 (Z6)
• 4: S4 (Z4), C4 (Z4), C2h=D1d (Z2*Z2), C2v (Z2*Z2), D2 (Z2*Z2)
• 3: C3 (Z3)
• 2: S2 (Z2), Cs=C1v (Z2), C2 (Z2)
• 1: C1 (Z1: identity group, trivial group)

The page uses Cn for Zn (order-n cyclic group)

 

[lpetrich]

TOPOLOGY

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

\( n = \left\lfloor \frac{1 + \sqrt{48h+1}}{2} \right\rfloor \)

The number of colors needed for a surface with h "holes".

ITEM 115 (Gosper):

Mentions  Space-filling curve -  Peano curve -  Hilbert curve -  Z-order curve

These curves are constructed iteratively, each little bit being a miniature version of the full-sized curve.

This gives them a fractal dimension of 2 (or n for a n-D version). I don't recall HAKMEM mentioning fractals anywhere, however. I'm sure that its authors would have gone ape over them.

 

[lpetrich]

SERIES

ITEM 118 (Schroeppel):

Start with \( y e^{-y} = x \) and differentiate by x: \( y + y x y' - x y' = 0 \) Use this curious identity:

\( \sum_{j=1}^{n} j^{j-1} (n-j)^{n-j} B(n,j) = n^n \)

where B is the binomial function. We find

\( y = \sum_{n=1}^{\infty} \frac{n^{n-1} x^n}/{n!} \)


ITEM 120 (Euler):

Series-acceleration transformation:

\( a_0 - a_1 + a_2 - ... = \sum_k \frac{(-1)^k \Delta^{(k)} (a_0)}{2^k} \)

Where the Delta's are forward differences on the series.

 

[lpetrich]

FLOWS AND ITERATED FUNCTIONS

ITEM 126 (Schroeppel):

Analytic flow for Newton's method for finding a square root:

\( f(x) = \frac{x^2 + a}{2x}\)

\( f^{(n)}(x) = \sqrt{a} \cdot \coth( 2^n \text{arccoth} (x/\sqrt{a})) \)

For iterating n times.

ITEM 127 (Schroeppel):

When is polynomial composition commutative? For p and q, p(q(x)) = q(p(x))?

It's commutative for purely linear polynomials, polynomials that are repeated compositions of some other polynomial, and in some other cases.

 

[lpetrich]

PI

Lots of stuff on Archimedes's constant.

Sum of arctangents:

\( \sum_i n_i \arctan (y_i/x_i) = \sum_i n_i \arg (x_i + i y_i) = \arg \prod_i (x_i + i y_i)^{n_i} \)

ITEM 139 (Ramanujan):

Some of his complicated but fast-converging formulas. How did he prove them?

ITEM 143 (Salamin):

How to compute elliptic integrals (integrals over square roots of cubic or quartic polynomials)

There is a nice little algorithm for doing so called arithmetic-geometric mean. Start with some values connected to what one wants to compute. Then calculate their arithmetic and geometric means. Repeat on these results until the two values converge. For example:

Complete elliptic integral of the first kind: K(m) = (pi/2)/agm(1,sqrt(1-m))

 

[lpetrich]

ITEM 146: MUNCHING SQUARES --  Munching square -- cute display hack

ITEM 149 (Minsky): CIRCLE ALGORITHM

x' = x - e*y
y' = y + e*x'
(using the new x in the second equation)

One can also do a Chebyshev recurrence:

x'' = (2-e^2)*x' - x

ITEM 154 (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.

I wrote a short program to do that, and I find that my iMac, with its Intel Core i7 CPU, does twos-complement integer arithmetic in every integer data type that it supports: 8-bit, 16-bit, 32-bit, and 64-bit.

Twos-complement seems to be universal among CPU chips, though it was anything but universal in older mainframe and minicomputer architectures. That's also true of power-of-2 data sizes.