This article is a brief review of four problems we have attacked in the past few years. They all share the following characteristics: they are intuitively appealing and easy to pose; but they are (it seems) impossible to solve in any meaningful sense, and the only effective computational approach to them is direct enumeration; the functions f(n) involved grow exponentially, and with them the computing time required; but the computer space required is very small. Such problems are suitable for running in background mode on a large computer: i.e. the program occupies the memory more or less permanently, but is only actually obeyed when no other current program can proceed. The program costs virtually nothing to run, since the time it uses would otherwise go down the drain. It must be written in machine code, to minimise space and maximise speed; and it must incorporate a dump/restore mechanism so that the overall computation - which may last hundreds of hours - can be broken down into short independent segments.
One application of these calculations is in elucidating the asymptotic behaviour of the f(n) computed. In map-folding and polyominoes it is (very roughly) true that
...(1)
and by computing successively higher values of f(n) we can improve the lower bound on α. In addition we can extrapolate from the highest known values to guess at α itself: we use a curve-fitting process called LINFRAC, discussed in [11].
A major difficulty is to know whether the answers are right when we have computed them. A large-scale check uses the curve-fit in reverse: a new value of f(n) is compared with that predicted from previous values, and an unexpectedly large discrepancy indicates a possible error. Small-scale errors are more difficult, as number theoretic properties (e.g. f(n) is divisible by 2n in map-folding) tend to be converted into algorithmic improvements (calculate only f(n)/2n in the first place). On the whole we have found previous work very deficient in this respect: a sound principle is to treat the highest value of f(n) given as almost certainly wrong.
Brief tables of some of these functions, including the highest values, are given later in this paper. These were computed on the Atlas I's at both Manchester University and the Chilton Atlas Laboratory, for whose support we are most grateful.
A free n-celled polyomino, or just a n-mino, is a selection of n cells from a chessboard pattern. It must be edge-connected, and only the shape is important. Two views of the same 4-mino are shown at (2); there are five 4-minos altogether, PE(4) = 5.
PE(n), the number of different n-minos (7), has been computed on Atlas for n = 1(1)18 in about 175 hours. The program is still running on n = 19, but there is some doubt whether it will finish before Atlas is pensioned off. The computation is described in detail in [1]. On curve-fitting the original results we discovered an error of 0.1 % in PE(18), which we traced to the sub-total of 18-minos bounded by an 8 × 8 square and corrected. LINFRAC predicts that α = 4.062 ± 0.001 for PE(n) (see (1)), which rather upsets the attractive hypothesis that α = 4 exactly. It is known that 3,72 < α < 4,65.
Polyominoes first arose as a model of cell division, and appear in theoretical physics as one of many lattice-models (α is known as a critical point in this guise); they have also achieved some fame as a pure mathematical recreation [2]. We even received a request from an architect for a catalogue of all n-minos for n≤20: we had to tell him that there are about ⅓ 1010 of them, and could he make do with n ≤ 10 instead.
We have also investigated polyominoes on other patterns, in particular on triangles, hexagons and cubes. A. Dorran, a summer student at the Atlas Laboratory, wrote a program which produced the counts for up to 12 hexagons and 16 triangles [3]. We know of no cubical program, but as a first step we computed the types of symmetry a cubical n-mino may display (that is, we enumerated the conjugacy classes of the hyperoctahedral group of order 3). This is by no means a great feat. However, the models we constructed (this time without the computer) of the 33 types are quite pretty, and may be found in [4].
A strip of n stamps from a postage-stamp vending machine may be folded up on to one stamp in a variety of ways. We call each such configuration an n-folding; for example there are six 3-foldings, G(3) = 6, see (4).
G(n), the number of different n-foldings (8), has been computed on Atlas for n = 1(1)24 in about 45 hours [5]. We recently had a second try at this problem for n ≤ 28 on a 4/70 (akin to the Rutherford Laboratory 360/75), with a new program 15 times faster; but this computation is not yet complete [6].
Applying curve-fitting to the existing values we find α=3.5018 ± 0.0001 for G(n), which, once again, upsets the conjecture α=3½. It is known that 2.906 < α ≤ 4.
The above is the one-dimensional case of the map-folding problem. In two dimensions it becomes: how many ways can you fold up a map with n-l creases along one side and m-l along the other? We have done some computation on this, too - for example there are 1368 foldings of a 3 × 3 map - but have few theoretical results [7].
Consider the binary functions on n binary variables a, b, c, . . . If no constraints are placed on them, it is easy to show that there are
22n
...(5)
possible functions. Suppose now that we restrict ourselves to functions which can be constructed from and (.) and or (+) gates, excluding not which would give us the whole lot. Let IU(n) denote the number of functions now (9). Below are the IU(2) = 6 possibilities when n = 2:
O, I, a, b, a.b, a+b ...(6)
Clearly IU(n) is less than (5). But it is not much less: in fact,
that is, the problem is doubly exponential.
Atlas computed IU(6) in about 5 seconds and lU(7) in an hour; this appears in [8]. lU(8) might just be within the grasp of the very largest contemporary machines (STAR 100); IU(9), barring some unexpected mathematical advance, is quite hopeless. We later learnt that a certain R. Church had computed IU(7) already, and we were distressed (but not greatly surprised) to find that our respective values agree only in the first and last of 13 digits. This discrepancy has not been resolved: an independent third computation might help, or it might not!
A Post Office issues stamps of n different denominations and allows customers to attach at most m to a letter. How should they choose the set of denominations to permit the largest possible sequence of consecutive postal rates? We call the first missing value V(n,m). For example, when n = 4 and m = 3 the best set is (1,4,7,8): with at most 3 of these denominations any rate less than V(4,3) = 25 is obtainable. This problem is notable for the false trails it lays: e.g. the middle denomination, when n = 3 and m varies, takes the values 2, 3, 4, 5, 6, 7, 8, 9, 9, ...
We spent about 20 hours on the Manchester Atlas producing a few dozen solutions for various n, m, reported in [9], but have not so far made any deductions about their asymptotic behaviour; except that the figures do suggest that possibly
The denominator is the number of choices with repeats of up to m things from n, so we are claiming that the efficiency of the best set is not eventually zero.
An unexpected application of these results is in the construction of computer memories [10].
| n | PE(n) (polyominoes) |
G(n) (map-foldings) |
IU(n) (dedekind) |
|---|---|---|---|
| 1 | 1 | 1 | 3 |
| 2 | 1 | 2 | 6 |
| 3 | 2 | 6 | 20 |
| 4 | 5 | 16 | 168 |
| 5 | 12 | 50 | 7581 |
| 6 | 35 | 144 | 7828354 |
| 7 | 108 | 462 | 2208061288138 |
| 8 | 369 | 1392 | |
| 9 | 1285 | 4536 | |
| 10 | 4655 | 14060 | |
| 11 | 17073 | 46310 | |
| 12 | 63600 | 146376 | |
| 13 | 238591 | 485914 | |
| 14 | 901971 | 1557892 | |
| 15 | 3426576 | 5202690 | |
| 16 | 13079255 | 16861984 | |
| 17 | 50107911 | 56579196 | |
| 18 | 1926022052 | 184940388 | |
| 19 | 622945970 | ||
| 20 | 2050228360 | ||
| 21 | 6927964218 | ||
| 22 | 22930109884 | ||
| 23 | 77692142980 | ||
| 24 | 258360586368 | ||
| (7) | (8) | (9) |
1. Lunnon, W. F. (1971). Counting polyominoes, Computers in Number Theory, ed. Birch, B. J., and Atkin, A. O. L., Academic Press, 347-372.
2. Golomb, S. W. (1965). Polyominoes, Scribner's, New York.
3. Lunnon, W. F. (1972). Counting hexagonal and triangular polyominoes, Graph Theory and Computing, ed. Read, R. C., Academic Press.
4. Lunnon, W. F. (1972). Symmetry of cubical and general polyominoes, Graph Theory and Computing, ed. Read, R. C., Academic Press.
5. Lunnon, W. F. (1968). A map-folding problem, Math. Comp., 22, 193-199.
6. Lunnon, W. F. (to appear). Map-folding revisited, Math. Compo
7. Lunnon, W. F. (1971). Multidimensional map-folding, Compo J., 14, 75-80.
8. Lunnon, W. F. (1971). The IV function: the size of a free distributive lattice, ombinatorial Mathematics, ed. Welsh, D. J. A., Academic Press, 173-181.
9. Lunnon, W. F. (1969). A postage-stamp problem, Comp. J., 12, 377-380.
10. Hargraves, R. F. (1971). Application of the Postage Stamp Problem to Associative Cache Memory Design, Dartmouth College.
11. Lunnon, W. F. (to appear). Asymptotic estimates of exponential functions, Num. Math