| The Games and Puzzles Journal — Issue 27, May-June 2003 |
We walk in the footsteps of Eratosthenes as he sieves the primes, then line them up with Euclid and Dirichlet. Then it's back to basics to consider what numbers are, and how they are named, or might be by Altairians. To conclude T. W. Marlow studies decimal digitology of automorphic cubes.
| (41) In the Footsteps of Eratosthenes | é |
(a) Paths of Eratosthenes
In most introductions to number theory there is mention of the Sieve of Eratosthenes, which is constructed by making a list of numbers from 2 upwards as far as some number N, then striking out all multiples of the first number in the sequence (but not the number itself), then all multiples of the second remaining number in the sequence, then all multiples of the third remaining number in the sequence and so on, as far as the square root of N. The final result is a list of the prime numbers up to N.
Here is a puzzle based on this sieving process. The numbers struck out beginning at p are p×2, p×3, p×4, ... that is numbers of the form p×m where the factor m is continually increased by 1 while the other p, the prime, is kept constant. Generalising this process I call a move from p×q to p×(q+1) or to p×(q–1) or to (p+1)×q or to (p–1)×q, where the unchanged factor must be a prime number, a footstep of Eratosthenes and a series of such moves a path of Eratosthenes. By permitting either factor to be varied and to increase or decrease by 1 in this way more complex paths than simple progressions are possible.
For example, starting from 25 = 5² = 5×5 we can reach 49 = 7² = 7×7 by the steps:
Similarly we can form closed paths such as
My puzzle is a more complex path:
The Puzzle: Construct a path of Eratosthenes from 5³ to 7³ (remember that one of the factors p×q must always be a prime). It should be noted that a number with three factors can sometimes be split into two factors in different ways: a×b×c = a×(b×c) = (a×b)×c.
Solution at the end of this section.
(b) Sieving out all the primes less than 100
Here is the start of a cylindrical sieve of Eratosthenes. We write the successive numbers on a helix wound round a cylinder divided into six columns headed 0 1 2 3 4 5. Duplicating the column headed 3 and opening the cylinder out flat we get a pattern like this (the rows should be imagined sloping downwards slightly so that the 3, 9, 15, ... on the right are on the same level as the 3, 9, 15, ... on the left):
In the diagram multiples of 2 and 3 are shaded grey; it will be seen that they occupy the columns headed 0, 2, 3, 4, leaving only columns 1 and 5 to contain the primes greater than 3. This illustrates the result, mentioned in The Games and Puzzles Journal several times in the past, that all primes, other than 2 and 3, are of the form 6n ± 1. The column headed 0 consists of 6 and its multiples.
If, with Eratosthenes, we now put a line through all multiples of 5 it will be seen that it is a helical line that starts at 0 and goes down the cylinder diagonally to the left (0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 55 and so on). Similarly if we put a line through all multiples of 7 it goes helically down the cylinder diagonally to the right (0, 7, 14, 21, 28, 35, 42, 49, 56 and so on). These lines meet columns 1 and 5 in the numbers shown in blue. These numbers are composites whose factors are primes greater than 3, namely:
Multiples of higher primes, 11, 13 and so on, can be shown by similar helical lines which however get steeper and steeper. All these lines can be visualised as starting from 0 with the initial section 0–5, 0–7, 0–11, 0–13 and so on indicating the direction and length of the subsequent moves. It so happens that in the section of the table shown the higher primes do not identify any further composites (because 11×11 = 121 is in the next, three-figure, section of the table). So the numbers in the white cells are all the prime numbers less than 100.
(c) Sieving out the Primes less than 1000
If we wish to continue the search for higher primes it seems sensible therefore to confine our attention to the columns headed 1 and 5. It occurred to me to see if it was possible to arrange these numbers on the cylinder so that multiples of 5 and 7 formed closer-spaced lines, similar to the multiples of 2 and 3 in the original array. Looking down these two columns we find that the multiples of 5 differ by 30 = 6×5 and the multiples of 7 differ by 42 = 6×7. So I tried arranging the numbers in rows with common difference 30 and columns with common difference 42. In the following diagrams the blue cells mark multiples of 5 and 7.
These tables show all numbers of the forms 6n – 1 and 6n + 1 that are less than 1000. The remaining composites in these tables therefore have as smallest factors 11, 13, 17, 19, 23, 29, 31. They are shaded grey. Here is a complete list of them:
Note that products of numbers in the same class are of the form 6n + 1, while products of numbers in different classes are of the form 6n – 1.
The following tables are the result. That on the left is for numbers of the form 6n – 1, and that on the right is for numbers of the form 6n + 1. Numbers in corresponding cells thus differ by 2. The rows should be regarded as drawn on the cylinder sloping down to the right, so that in wrapping round the cylinder the right-hand column meets the left-hand column after a downward shift of 5 rows. For example, in the row beginning with 5 after travelling across to 185 we re-enter on the left at 215.
Unlike the previous diagram, this does not reveal any obvious pattern in the higher primes.
(d) Solution to the Path of Eratosthenes Puzzle
The path required from 5³ to 7³ takes 18 steps (with 222 as the mid-point):
The condition that one factor must always be a prime prevents the short cut:
where the co-factors of 6 are the composites 25, 35, 49.
| (42) Prime Number Arrangements | é |
(a) Questions on Euclidean Numbers
Euclid famously proved that it is always possible to find a prime higher than any given prime p. His method was to consider the product of all primes up to and including p, and add 1. The resulting number E(p) = (2 × 3 × 5 × 7 × 11 × ... × p) + 1 then gives remainder 1 when divided by each of these primes, so it does not have any of these primes as a factor. Hence it must either be a prime greater than p or have a prime factor greater than p. This result is also expressed by saying that there is no largest prime or that the set of primes is infinite.
We may call the numbers E(p) Euclidean numbers. Euclid could equally well have used p! + 1, meaning (1 × 2 × 3 × 4 × 5 × ... × p) + 1, in his argument since it also leaves a remainder 1 when divided by every prime up to p.
Here are some simple questions prompted by Euclid's argument.
Answers at the end of this section. Case (d) is unsolved (by me) since it leads rapidly to high numbers that cannot be handled on a normal calculator, or even on Tom Marlow's program that can handle high numbers up to 60 digits.
(b) Euclid's Reduction to Absurdity
The Maths Gene: why everyone has it, but most people don't use it by Keith Devlin (2000) is another of those popularising books about mathematics and science that contain hardly any mathematical formulae. In fact he has the cheek to admit (p.12): “It has been said that every equation an author includes in a ‘popular’ science book halves its sales.” The only lengthy formula in the book is the above expression for E(p). Devlin cites Euclid's proof as an example which is “regarded as one of the most brilliant pieces of mathematics ever produced.” Unfortunately he garbles it!
He begins by defining ‘prime number’ and stating the ‘fundamental theorem of arithmetic’, (that every number is a product of primes). He then has Euclid suppose that there is a largest prime P, and denotes by N the product of all primes (i.e. 2 to P inclusive). “Now look at the number N + 1. It is obviously larger than P.” Here he fails to make the immediate deduction that N + 1 is non-prime (since it is larger than the largest prime). Instead he says: “Euclid claimed that this number N + 1 is a prime number.” This makes Euclid look a bit stupid.
He takes another paragraph before giving an argument to prove N + 1 prime, and he does it confusingly by taking the fact that N + 1 is non-prime as a second supposition. The argument of course is that since N + 1 is non-prime it has a prime divisor M (by the fundamental theorem), but we know that M divides N (since by definition N is the product of all primes). So when M divides N + 1 it leaves a remainder of 1. So N + 1 has no such divisor M, and must be prime (since a prime number is one that has no divisors). This gives a contradiction.
“That's Euclid's proof. Mathematicians regard it as one of the best examples ever of a neat, concise, and elegant proof. Elegant? If you are a mathematician, it is hard to imagine that anyone cannot see the logical elegance in Euclid's proof. ... And yet I know from teaching mathematics to hundreds of students that a great many not only fail to see how Euclid's proof could be described as ‘elegant’ but are not able to follow the argument, and hence are unconvinced by it.” The sad truth is it's Devlin's garblement of it they cannot follow!
Euclid's proof can indeed be presented in the form of a ‘reductio ad absurdum’ (in Devlin's form it becomes an even more absurd double reductio), but in fact it can be presented more straight-forwardly as I have done at the start of this section, without generating a contradiction. Why try to present it more cleverly?
(c) Dirichlet's Theorem
When the numbers 0, 1, 2, ... are arranged in a rectangular formation with a fixed number n of rows or columns (as in the first figure in the Eratosthenes section above, with n = 6) the effect is to arrange them in n different ‘arithmetical progressions’ with constant difference n and initial values 0, 1, 2, ..., k, ..., (n – 1). In particular, by Euclid's theorem, the listing of the numbers 0, 1, 2, ... in a single row is an arithmetical progression with common difference 1 containing an infinity of primes.
This result of Euclid was extended by P. G. L. Dirichlet who in 1837 proved the result, apparently known to A. M. Legendre earlier but not successfully proved by him [Ref. 1], that any arithmetical progression k, n+k, 2n + k, 3n + k, ..., mn + k, ... contains an infinity of primes provided that k and n have no common factor other than 1. [This condition is also expressed by saying that the ‘highest common factor’ of k and n is 1, abbreviated hcf (k, n) = 1, or by saying that k and n are ‘relatively prime’. In the case with n = 6, k = 1 or 5 as shown in the previous section on the sieve of Eratosthenes.] Euclid's result is the special case with k = 0, n = 1.
The proof of Dirichlet's general result is said by Baker [Ref. 2] to “lie quite deep”, and indeed is too much even for Hardy and Wright who admit: “The proof of this theorem is too difficult for insertion in this book” [Ref. 3] so who am I to attempt a sketch of it here! A short proof, but using long theory (congruences, logarithms, infinite series, etc), is given by Wall [Ref. 4].
References:
[1] H. Davenport, The Higher Arithmetic, Hutchinson, London 1952 (page 37).
[2] Alan Baker, A Concise Introduction to the Theory of Numbers, Cambridge University Press, 1984 (1994 reprint, page 6).
[3] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938 (fifth edition 1979, page 14).
[4] Charles R. Wall, Selected Topics in Elementary Number Theory, University of South Carolina Press, 1974 (pages 179–181).
(d) Euler's Function
When n = 2 we have 2 rows and of these 1 row (consisting of the odd numbers) contains an infinity of primes. In the general case we have n rows and of these a certain number q will contain an infinity of primes. The problem of finding those values of n which will make q relatively small, i.e. will squeeze the primes up into relatively few rows, was raised by Ted Clarke in his magazine WordsWorth (volume 3 issue 3, July 2000, page 79).
The relation deriving q from n is known as Euler's function, usually expressed as q = f(n), defined as the number of numbers k with 0 < k < n such that hcf (k, n) = 1. These rules enable us to calculate the values of f(n): [1] When n is a prime number p we have f(p) = p – 1, since the numbers 1, 2, 3, ..., p – 1 are all relatively prime to p. [2] When n is a power of a prime, n = p^c, we have f(n) = n(p – 1)/p. [3] The multiplication property: When x and y are relatively prime then f(x×y) = f(x)×f(y). For example f(3) = 2 and f(5) = 4 by rule [1] and f(9) = 6 by rule [2] so f(45) = 24 by rule [3].
When n is a prime p or power of a prime p^c it follows that the ratio of number of rows to number of rows with primes is n/f(n) = p/(p – 1) = 1 + 1/(p – 1), the minimum value of which is 2, occurring when p = 2, the smallest prime. Thus a ratio of 2 is achieved by arranging the numbers in 2^c rows, i.e. 2, 4, 8, 16, 32, 64, .... In other words half the rows contain multiple primes and half do not.
To get a larger ratio n has to have two or more different prime factors. If it is of the form (p^c)(q^d) then we have n/f(n) = [p/(p – 1)][q/(q – 1)]. This value is maximised by taking p and q as the two smallest different primes, i.e. 2 and 3, giving the value (2/1)(3/2) = 3. This value 3 thus occurs for the numbers (2^c)(3^d), that is for 6, 12, 18, 24, 48, 54, 72, 96, ...
The first three primes 2, 3, 5 give 30, 60, 90, 120, 150, 180, 240, ..., all giving a value for n/f(n) of 3(5/4) = 3.75. Four primes 2, 3, 5, 7, lowest n = 210, give (15/4)(7/6) = 4.375. Five primes 2, 3, 5, 7, 11, lowest n = 2310, give the ratio (35/8)(11/10) = 4.8125. Six primes 2, 3, 5, 7, 11, 13, lowest n = 30030, give (77/16)(13/12) = 5.2135 and so on.
Let k be the number of primes then lowest n = 2 × 3 × 5 × 7 × 11 × ... × p(k) and n/f(n) = 2 × 3/2 × 5/4 × 7/6 × 11/10 × ... ×p(k)/(p(k) – 1). Although the factor p/(p – 1) gets closer to 1 nevertheless the product increases without bound [for proof see Wall, p.158]. So if we take the simple ratio n/f(n) as a valid measure of the compactness of the array then there is no best answer to Ted Clarke's problem.
I tried to work out an alternative measure that took into account the fact that the primes thin out as we approach higher numbers, so that the more lines they are in the more sparsely they are distributed. According to the prime number (distribution) theorem the number of primes up to x approaches x/log x (I'm not sure if it matters what base of logarithms is used). However I have not made progress with this approach.
A simpler approach is to ask What is the first composite number, in an arrangement of n rows, that breaks up the continuous sequence of primes? The answer is the square of the first prime that is not a divisor of n. Thus for all odd numbers the first composite in a prime line is 4, and for all even numbers that are not divisible by three the answer is 9. For all numbers that are divisible by 2 and 3 but not by 5 the answer is 25. The first case where the first composite is 49 is when n = 30 which has 2, 3 and 5 as factors.
(e) Answers to the Euclidean Number Questions
If E(p) is the product of the primes up to p, plus 1, then we have
(a) The first non-prime is E(13).
(b) The case E(17) is divisible by the next prime, 19.
We have the successive values of p! + 1 (with p a prime):
(c) the first non-prime is case p = 5.
(d) We still don't know whether there is a prime p such that p! + 1 is divisible by the next prime greater than p.
Note that cases p = 5 and p = 7 are squares. An obvious question is whether there are any further squares of this form.
The results p = 11 to p = 19 have been provided by Tom Marlow. In these the larger factor in each case is either prime or has a factor larger than 9999. Tom Marlow notes, concerning his extended arithmetic program: “I wrote it some years ago for my Acorn computer - a descendant of the BBC computer intended for schools. As written it only multiplies, squares, cubes and seeks factors up to 9999 but the answer can be up to 120 digits and any input can be up to 60 digits.”
| (43) Positional Numeration | é |
(a) A Reciprocal Question
Incidental to the astronomical considerations in Issue 23 I noted that Patrick Moore, in his Atlas of the Universe, mentioned that the ratio of the Moon to the Earth by mass is 1 to 81. I converted this to a decimal fraction on my calculator and was surprised to find that 1/81 = 0.0123456 (the digits in numerical sequence!). But more accurately it works out as 0.012345679 (where underline indicates recurrence).
(a) Explain this regular sequence and the absence of the 8.
(b) What fractions in lowest terms give the recurring decimals 0.01, 0.012, 0.0123, ... 0.0123456789?
(b) General Principles of Numeration
What are numbers? Most books on mathematics and arithmetic do not even bother to define what they mean by ‘number’, or even ‘mathematics’ for that matter. Here is a quick run-down of a possible approach.
By mathematics we mean the study of systems. A system is a thing defined in terms of other things called its parts. Systems S and T are said to be isomorphic if their parts can be matched in such a way that any proposition p(a, b, c, ...) about parts of S is true if and only if a corresponding proposition p'(a', b', c', ..) is true about corresponding parts of T. Isomorphic systems are said to have the same structure. We denote the structure of S by |S|. A set is a system in which there are no propositions relating its parts to each other (in other words it has no internal structure). The structure of a set is its size, that is the number of its parts.
Visual Numeration. The earliest way to represent numbers was in physical form as sets of pebbles, sticks, fingers or other counters. From the representation of numbers by sets of counters, it is a small step to the written tally method, whereby the set is represented by a group of repeated identical signs within a designated space, the tally marks representing pebbles or sticks used for counting. Thus, using round brackets to enclose space ( ) and a stroke / as tally mark, we get number symbols: ( ), (/), (//), (///), (////), (/////), and so on. Another way of representing numbers is simply to use a standard sequence of letters such as the alphabet or special signs such as the Hindu-Arabic numerals 0,1,2,3,4,5,6,7,8,9. But soon the tally symbols get unwieldy or we run out of signs.
Positional Numeration. When counting large numbers with pebbles we can reach higher numbers by agreeing that when we have a heap of a certain size, k, we will remove it and represent it by a single pebble alongside, to the left, starting a second heap, and, when we have filled this second heap with k pebbles we empty its space and start a third heap. This is the origin of the method of positional numeration with base k.
In this method we only need individual symbols for the numbers less than k, since a heap never contains more than k counters. These number symbols are the digits 0, 1, ..., h. (where h denotes the number one less than k). The next higher numbers are shown by pairs of digits, in the sequence 10, 11, ..., 1h, ..., h0, h1, ..., hh. Then we go to triplets of digits: 100, 101, ..., hhh. Then to four digits 1000, 1001, ..., hhhh, and so on.
It will be seen that in any positional number system the symbol 10 (read as one zero, not as ten) represents the base, 100 represents the square of the base, 1000 the cube of the base and 1 followed by n zeros the n-th power of the base. Multiplying a number by the base simply puts an extra digit 0 on the end of the positional expression for the number. For example a four-digit expression pqrs = p000 + q00 + r0 + s = p×(k^3) + q×(k^2) + r×k + s.
Primals, Basals and Normals. Numbers that have only divisors of the base k as divisors I call basals in the base k system of numeration. Thus if k = (p^x)×(q^y)×(r^z)×... where p, q, r, ... are increasing primes, then all numbers of the form (p^u)×(q^v)×(r^w)× ... are basals. In particular 1 = (p^0)×(q^0)×(r^0)× ... is basal in any system. For example in bases 6 and twelve the basals are of the form (2^c)(3^d), while in bases ten and twenty the basals are (2^c)(5^d).
Numbers that are not divisible by any divisor of k I call primal. In particular, all primes greater than k are primal, and any primes less than k that do not divide k are primal. In base 6 the only primal less han 6 is 5. In base ten the primals less than ten are 3 and 7. If the base is an odd number then 2 is a primal.
Numbers that are neither primal nor basal I call normal. A normal can be expressed uniquely as the product of a basal and a primal. The product of two basals is a basal, the product of two primals is a primal, and the product of two normals is a normal, thus these three classes of numbers are all closed with respect to multiplication. The product of two numbers from different sets is a normal.
[This ‘basal, primal, normal’ nomenclature is my own innovation. I have used it previously in The Games and Puzzles Journal but applied to the particular case k = 6.]
(c) Fractional Numeration
Positional Fractions. A later development of the positional system of numeration was the discovery that fractional numbers could be represented by extending the positional notation to the right, a unit in the next position to the right in base k always representing 1/k of a unit in the preceding position. The start of the fractional part is marked by a positional point (called a ‘decimal point’ in base ten). Multiplying by k (= 10) moves the point to the right, while dividing by k moves it to the left. Thus p.qrs = p + q/10 + r/100 + s/1000 = pqrs/1000.
To calculate the successive digits in the positional expression for p/q (assuming p < q and that p and q have no common factor) we multiply p/q by k and note the integral part of the result, this is the first digit after the point. We then multiply the fractional part by k again, and the integral part now gives the second digit, and so on. This process either terminates when the fractional part becomes zero or recurs when the fractional part becomes the same as it was at an earlier stage in the sequence of calculations. We adopt the notation of showing the recurring part by underlining the sequence of repeating digits.
| base | 1/2 | 1/3 | 1/4 | 1/5 | 1/6 | 1/7 | 1/8 | 1/9 |
| 2 | 0.1 | 0.01 | 0.01 | 0.0011 | 0.001 | 0.001 | 0.0001 | 0.000111 |
| 3 | 0.1 | 0.1 | 0.02 | 0.0121 | 0.01 | 0.010212 | 0.01 | 0.01 |
| 4 | 0.2 | 0.1 | 0.1 | 0.03 | 0.02 | 0.021 | 0.02 | 0.013 |
| 6 | 0.3 | 0.2 | 0.13 | 0.1 | 0.1 | 0.05 | 0.043 | 0.04 |
| 8 | 0.4 | 0.25 | 0.2 | 0.1463 | 0.125 | 0.1 | 0.1 | 0.07 |
| A (10) | 0.5 | 0.3 | 0.25 | 0.2 | 0.16 | 0.142857 | 0.125 | 0.1 |
| C (12) | 0.6 | 0.4 | 0.3 | 0.2497 | 0.2 | 0.186A35 | 0.16 | 0.14 |
| G (16) | 0.8 | 0.5 | 0.4 | 0.3 | 0.2A | 0.249 | 0.2 | 0.1C7 |
The Period Function. Let P(n, k) denote the period of n in base k; that is the number of repeating digits in the positional expression for 1/n, terminating fractions having period 0.
To transform a circulating positional fraction x = 0.lmn--- to a rational fraction we multiply by the smallest power of 10 (i.e. 10^y = 100...0 with y occurrences of 0) that will shift the repeating block until it is aligned with another copy of itself. Thus: (100...0)x = lmn---.lmn---. Then subtract to obtain: [(100...0) – 1]x = lmn---, whence x = lmn---/hh---h (where there are y occurrences of the digit h, denoting k – 1).
For any base k, 1/n terminates if and only if n divides k^y (i.e. 100...00) for some non-zero number y, i.e. if and only if every prime divisor of n also divides k. In other words, the condition for the sequence to terminate is that n is a basal number (as defined above).
Basic results on geometric series may be used to evaluate the period function. We have 1/(k – 1) = 1/k + 1/(k^2) + 1/(k^3) + ..., so that 1/(k – 1) = 0.111... = 0.1 in base k, and hence P((k–1), k) = 1. Similarly 1/(k + 1) = (k – 1)/(k^2 – 1) = (k – 1)/(k^2){1/[1 – 1/(k^2)]} = (k – 1)[1/(k^2) + 1/(k^4) + 1/(k^6) + ...] so that 1/11 = 0.0h0h0h... = 0.0h in base k, and hence P((k + 1), k) = 2. Thus 0.1 is always the expression for 1/h and 0.0h for 1/11.
We can write n = p×b where p is the largest divisor of n such that hcf(p, k) = 1 (i.e. p is the ‘primal’ part of n with respect to k). Then every prime divisor of b divides k, (i.e. b is the ‘basal’ part of n with respect to k). For all n and k we have P(n, k) = P(p, k), that is the period of a number is the same as the period of its primal part.
| n \ k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
| 4 | 1 | 0 | 2 | 0 | 1 | 0 | 2 | 0 | 1 | 0 | 2 | 0 | 1 | 0 | 2 | 0 | 1 | 0 |
| 5 | 1 | 4 | 4 | 2 | 0 | 1 | 4 | 4 | 2 | 0 | 1 | 4 | 4 | 2 | 0 | 1 | 4 | 4 |
| 6 | 1 | 2 | 1 | 1 | 2 | 0 | 1 | 2 | 1 | 1 | 2 | 0 | 1 | 2 | 1 | 1 | 2 | 0 |
| 7 | 1 | 3 | 6 | 3 | 6 | 2 | 0 | 1 | 3 | 6 | 3 | 6 | 2 | 0 | 1 | 3 | 6 | 3 |
| 8 | 1 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | 1 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | 1 | 0 |
| 9 | 1 | 6 | 0 | 3 | 6 | 0 | 3 | 2 | 0 | 1 | 6 | 0 | 3 | 6 | 0 | 3 | 2 | 0 |
| 10 | 1 | 4 | 4 | 2 | 1 | 1 | 4 | 4 | 2 | 0 | 1 | 4 | 4 | 2 | 1 | 1 | 4 | 4 |
| 11 | 1 | 10 | 5 | 5 | 5 | 10 | 10 | 10 | 5 | 2 | 0 | 1 | 10 | 5 | 5 | 5 | 10 | 10 |
| 12 | 1 | 2 | 2 | 1 | 2 | 0 | 2 | 2 | 1 | 1 | 2 | 0 | 1 | 2 | 2 | 1 | 2 | 0 |
| 13 | 1 | 12 | 3 | 6 | 4 | 12 | 12 | 4 | 3 | 6 | 12 | 2 | 0 | 1 | 12 | 3 | 6 | 4 |
| 14 | 1 | 3 | 6 | 3 | 6 | 2 | 1 | 1 | 3 | 6 | 3 | 6 | 2 | 0 | 1 | 3 | 6 | 3 |
| 15 | 1 | 4 | 4 | 2 | 2 | 1 | 4 | 4 | 2 | 1 | 2 | 4 | 4 | 2 | 0 | 1 | 4 | 4 |
| 16 | 1 | 0 | 4 | 0 | 4 | 0 | 2 | 0 | 2 | 0 | 4 | 0 | 4 | 0 | 2 | 0 | 1 | 0 |
| 17 | 1 | 8 | 16 | 4 | 16 | 16 | 16 | 8 | 8 | 16 | 16 | 16 | 4 | 16 | 8 | 2 | 0 | 1 |
| 18 | 1 | 6 | 1 | 3 | 6 | 0 | 3 | 2 | 1 | 1 | 6 | 0 | 3 | 6 | 1 | 3 | 2 | 0 |
The period function is periodic with respect to the base: P(n, (k + n)) = P(n, k). By defining P(1, 1) = 0 and P(n, 1) = 1 for n > 1 the repeating sequence is shown by the first n figures in the n-th row, i.e. the shaded area in the table, below the principal diagonal.
(d) Is there a Best Number Base?
The origin of our counting in tens is usually blamed on the anatomical accident that most of us have ten bony appendages at the ends of our arms, conveniently handy for counting on. But is this really a good enough reason for adopting ten as our base of numeration? Is it possible to decide, on objective criteria, on one base that is best?
Bit-power. The digits in base 2 (0 and 1) are binary digits, known as bits for short, and they provide a convenient unit for measuring the information provided by digits in other systems. Thus base 4 uses on average 1 digit for every 2 in base 2, while base 8 uses 1 digit for every 3 bits. Generally the bit power of a digit in base k is log k (using base 2 logarithms) since by definition this is the number y such that k = 2^y. For bases between 2^y and 2^(y+1) the bit power is fractional. As the number of different digits (k) increases, the bit-power (y) of each digit increases also, but more slowly. The maximum value of the ratio y/k occurs when k = 3 (for 2 and 4 it is 1/2, for higher k it is less than 1/2 and continually reduces).
Divisor-richness. In all systems in which the base is an even number divisibility by 2 is shown by an even final digit. This is a particular case of the general rule that in a system with composite base k = m×n (where m and n are between 1 and k) a given number is divisible by m if and only if its final digit is divisible by m. Thus if we want simple rules for divisibility we should choose as base a composite number with plenty of divisors. Base 6 is the first with two distinct divisors (2 and 3). Base 12 is the first with 3 divisors, and in fact it has four (2, 3, 4, 6). The first base with five distinct divisors, and in fact six, is 24 (2, 3, 4, 6, 8, 12). The first base with 7 distinct divisors is 36, the first with 8 is 48, the first with 9, and in fact 10 is 60. Note that all these are multiples of six. To decide which is the best base on this criterion, we want the smallest base with the comparatively most divisors. Let d be the number of divisors then the maximum value for d/k is 1/3 for bases 6 and 12, it goes down to 1/4 for for base 24, 1/5 for base 36 and 1/6 for bases 48 and 60.
In an article in the Dozenal Society of Great Britain webpages on “Utility of a Base” the usefulness of a base k is measured by a function (P^2)/S where P is the number of proper factors (excluding 1 and k) and S is the their sum. I can't see the justification of squaring the P. It just seems to be a way of getting 12 to come out as the best answer.
Tests for Divisibility. Simple tests are available in any base k for divisibility by k – 1 and k + 1. The k – 1 test is to add the digits. If the result is divisible by k – 1 so is the original number. The k + 1 test is to add alternate digits; if the two sums are the same or differ by a multiple of k + 1 the number is divisible by k + 1. Since tests for divisibility by prime numbers are what we need, this again points toward a base that is a multiple of 6, since then k – 1 and k + 1 are more likely to be primes. Thus base 6 has simple tests for divisibility by the first four primes 2, 3, 5, 7. Base twelve provides simple tests for 2, 3, 11, 13. In base 6 prime numbers, apart from 2 and 3, end with the digits 1 or 5. In base 12 primes end in 1, 5, 7, or B (eleven).
Terminating Fractions. As we have seen in an earlier section when a fraction p/q is expressed in the base k positional notation for fractions, the condition for the expression to terminate is that all the factors of q divide the base k, i.e. q is a basal number. So again, if we want a system in which recurring fractions are avoided as much as possible, the base must be a composite number with plenty of divisors. If the base k is a prime the only fractions that terminate are those of the type p/100...0.
In the table in the previous section for the period function we may note: (a) Only columns 1, 4, 9, 16 (squares) contain no double figures. (b) Columns 3, 5, 8, 10, 12, 13, 14, 15, 17, 18 have one double figure. (c) Column 12 has the most zeros 10 (i.e terminating fractions).
Squares. The bases 2, 3, 4, 5, 8, 12, 16, and no others, have the property that the last digit of a square is a square [proved by M. Muller 1955]. This is an interesting property but it is not clear that it offers any advantages for these systems. The last digits of squares in base 6 follow the sequence 014341... and in base 12 they follow the sequence 014941... and in base 16 the sequence is 01490941... In both base 6 and base 12 the squares of primals always end in 1.
The Dirichlet Criterion. It was shown above by calculating k/f(k) for successive values of k that this ratio increases indefinitely, so does not seem to provide a convenient criterion for selection of a base, but once again multiples of 6 give the most compressed arrangements of the primes, at least for low values.
Conclusion. The evidence seems to me, on balance, to favour base 6. It has the advantage over base twelve of not needing any new digits. If readers have other arguments for or against particular bases please let us know.
(e) Answer to the Reciprocal Question
(a) 1/9 = 0.1111... and 81 = 9×9 so
1/81 = (1/9)/9
= 0.1111.../9
= 0.1/9 + 0.01/9 + 0.001/9 + ...
= 0.0111111111111...
+ 0.0011111111111...
+ 0.0001111111111...
+ 0.0000111111111...
+ 0.0000011111111...
+ 0.0000001111111...
+ 0.0000000111111...
+ 0.0000000011111...
+ 0.0000000001111...
+ ...
= 0.0123456789999...
+ 0.0000000000123456789999...
+ 0.0000000000000000000123456789999 ...
+ ...
= 0.012345679012345679012345679 ...
The sequences ...89999... can be replaced by ...90000 since .9 = 1.
(b) The results are:
0.01 = 1/99,
0.012 = 12/999 = 4/333,
0.0123 = 123/9999 = 41/3333,
0.01234 = 1234/99999, 0.012345 = 12345/999999 = 4115/333333,
0.0123456 = 123456/9999999 = 41152/3333333,
0.01234567 = 1234567/99999999,
0.012345678 = 12345678/999999999 = 1371742/111111111
0.0123456789 = 123456789/9999999999 = 13717421/1111111111.
| (44) Altairian Arithmetic | é |
There seems to be an assumption among searchers for extraterrestrial life, and science fiction writers, that the arithmetic of aliens would necessarily be the same as ours, making communication of numerical information simple. But I think alien arithmetical notation could be quite different from our own. Here I present a method of numeration considerably different from our usual method and yet, I maintain, eminently practical. Readers are invited to contribute other possible systems.
The results in this article were first presented at a meeting of the Outlanders (Leicester Science Fiction, Fantasy and Horror Group) on 4 April 2003.
Provisionally I call the system described here Altairian (or Alterian) Arithmetic. The symbols the Altairians use for the numbers are those of their own alphabet but, for ease of understanding, I show the examples here in our own familiar alphabet, printed bold.
The values of the letters representing a number are combined additively (as in basic Roman numerals) and the letters can therefore be presented in any order without ambiguity, though for purposes of practical arithmetical calculation they are generally presented in alphabetical order. When properly expressed a number has no duplicate letters.
As may be expected, the later letters in the alphabet represent higher numbers, but not in the simple arithmetical progression (1, 2, 3, 4, ...). Beginning with a = 1 each letter represents twice the value of its predecessor. Thus b = 2, c = 4, d = 8, e = 16, f = 32, g = 64, and so on. (Thus, in our aphabet z would represent 2^25 = 33,554,432.)
The important point to realise is that any number can be expressed uniquely as a sum of different powers of two. So any number has a unique name. Since their numbers are represented by the letters of their alphabet Altairians are inveterate anagrammatists, numerologists and cabalists, associating names with numbers and vice versa.
The number represented by outlanders = adelnorstu = 2^0 + 2^3 + 2^4 + 2^11 + 2^13 + 2^14 + 2^17 + 2^18 + 2^19 + 2^20 = 1 + 8 + 16 + 2048 + 8192 + 16384 + 131072 + 262144 + 524288 + 1048576 = 1,992,729.
The Altairians are not keen on really high numbers, but their system allows for extension to any length by using a break symbol, which we can write ', to indicate that one complete alphabet has been exhausted and a new one has started. The first number after the break, using our alphabet, is 'a = 2^26 rising to 'z = 2^51 then comes ''a = 2^52 and so on. (Actually the Altairian alphabet has 32 letters, a power of 2 as might be expected, consisting of 16 consonants and 16 vowels — but that's a story for another day).
To show the practicality of this system, here is a brief outline of the basic arithmetical manipulations required for doing simple calculations.
Doubling. Since each letter represents twice its predecessor and letters placed together are added it follows that aa = b expresses the equation 1 + 1 = 2, and bb = c means 2 + 2 = 4. Thus multiplying by two is elementary: one simply replaces every letter in the number by its successor. For example bcdkm × b = cdeln.
Addition. The letters of two numbers to be added are arranged together in one alphabetical sequence, so that repeated letters are adjacent. Then, starting with the smaller numbers, pairs of repeated letters are replaced by their successor letters, until finally all repeated letters are eliminated. For example: bcdkm + acku = abccdkkmu = abddkkmu = abekkmu = abelmu. Of course with practice the number of steps can be reduced, by conflating steps or by carrying them out in a different order.
Multiplication. To multiply by a single letter-number one repeatedly doubles the number to be multiplied, and repeatedly reduces the multiplying letter to its preceding letter until a is reached. For example: e × akm = d × bln = c × cmo = b × dnp = a × eoq = eoq. The rote method of multiplying by a compound number is to multiply by each of the letters of the multiplying number and then to add all the results.
Finding the Successor. To find the number that follows the number abcdk, we proceed by adding a unit (a) giving the improperly expressed number aabcdk Then using aa = b we get bbcdk, and using bb = c we get ccdk and using cc = d we get ddk and using dd = e we get ek which is the final simplified form. In other words we have shown that abcdk + a = ek.
Finding the Predecessor. The example just given indicates that to subtract one from a power of two in this notation one replaces the letter by all its predecessors: e – a = abcd. In Earthly notation: 2^n – 1 = 1 + 2 + 4 + ... + 2^(n – 1). More generally one replaces the highest letter in the name of the number by all its predecessors and then eliminates all the duplications by the addition process. Sometimes it may be convenient to use a hyphen notation, writing a-k as an abbreviation for "all the letters a to k".
Subtraction. To subtract a number from a larger number that uses the same letters one simply strikes out the duplicate letters. For example bcdkmu – dku = bcm. Where the larger number does not show all the letters of the smaller number we replace the largest digit (or a sufficiently large digit) by all its predecessors plus an extra a, then strike out the digits of the number to be subtracted, and tidy up the result. For example akm – bfl = ak + a + abcdefghijkl – bfl = aaacdeghijkk = abcdeghijl. Using the hyphen notation this result can be expressed a-eg-jl.
Division. To divide by a single letter-number one repeatedly halves the number to be divided (numerator), and also repeatedly halves the dividing letter (denominator) to its preceding letter, until the denominator is reduced to a, or until the numerator is an odd number (i.e. it begins with a). For example, reversing the multiplication example: eoq/e = dnp/d = cmo/c = bln/b = akm/a = akm.
Divisibility Tests. Any number beginning with a is odd and any number not beginning with a is even (i.e. a multiple of 2).
Any number formed of pairs of successive letters is divisible by ab (= 3), since bc (= 6), cd (= 12), de (= 24) etc are all divisible by 3, because n + 2n = 3n. Similarly a pair of letters with two missing between, such as ad, be, cf, is a multiple of 3, in fact a multiple of 9, because n + 8n = 9n, and generally two letters with an even number of letters missing between represents a multiple of 3. The next case is n + 32n = 33n.
Similarly letters with a single gap between are indicative of multiples of ac (= 5). Thus bd (= 10), ce (= 20), df (= 40), this is because n + 4n = 5n.
Order of Magnitude. An important property of Altairian notation is that we can tell from their names which of two numbers is the larger. If the last letter in one is different from that in the other then whichever number has the later letter is the higher. This is because the sum of all the lower letters is one less than the given letter so any number ending in x, say, is less than its successor y by at least one. Where both numbers have the same last letter we compare the preceding letters, and so on.
Conversion to Binary Notation. To express an Altairian number in our binary positional notation, write 1 for the last letter and, working backwards through the alphabet, write 1 for each letter present in the number and 0 for each letter absent. Thus bcdkm in binary is the number 1010000001110. And outlanders = 111100110100000011001.
|
Automorphic Cubes
by T. W. Marlow | é |
Numbers which re-appear at the start (right-hand end) of their own squares have been described as automorphic. [Ref. 1] An example is 25^2 = 625. The two numbers below compactly show all cases up to 30 digits length. Both can be truncated from the left, one digit at a time, and each time retain the automorphic property.
106 619 977 392 256 259 918 212 890 625
893 380 022 607 743 740 081 787 109 376
The same concept can be applied to cubes and automorphic cubes prove to be commoner than automorphic squares. The following is a complete listing as far as each goes to the left. Each chain must start from the right and can extend as far left as required. Also at many stages a digit shown above can be used but that chain cannot then go any further left; e.g. 51, 751, 8751 and so on qualify and so do 251 and 3751 but these last two numbers do not extend further to the left.
In two cases a row of dots denotes that as many 0s or 9s as required can be inserted. The 9s row can be terminated by a 9 or a 4.
Reference:
[1] Beiler, A.H, Recreations in the Theory of Numbers, Dover, New York, 1963, p.147.
[Editor's Note: The above article on Automorphic Cubes was received by e-mail on 5 May 2003. However the work was apparently carried out on 4 October 1999.]
Erratum: The Tethered Goat. In the solution given to this problem in the last printed issue, Issue 18, p.344, there is an error in the arithmetical value cited; though the preceding analysis seems to be correct. The correct figure is r = 1.1588R. Thanks to Ted Clarke for noticing this.