Regular number

The numbers that evenly divide the powers of 60 arise in several areas of mathematics and its applications, and have different names coming from these different areas of study. As an example, 60² = 3600 = 48 × 75, so both 48 and 75 are divisors of a power of 60.

In the study of Babylonian mathematics, the divisors of powers of 60 are called regular numbers or regular sexagesimal numbers, and are of great importance due to the sexagesimal number system used by the Babylonians. In number theory, these numbers are called 5-smooth, because they can be characterized as having only 2, 3, or 5 as prime factors. They are a specific case of what are called "k"-smooth numbers, those sets of numbers that have no prime factors greater than "k".In music theory, regular numbers occur in the ratios of tones in just intonation, also called 5-limit tuning for this reason. In computer science, regular numbers are often called Hamming numbers, after Richard Hamming, who proposed the problem of finding computer algorithms for generating these numbers in order.

Number theory

Formally, a regular number is an integer of the form 2^"i"·3^"j"·5^"k", for nonnegative integers "i", "j", and "k". Such a number is a divisor of $scriptstyle\; 60^\{max(lceil\; i,/2\; ceil,j,k)\}\{\}$. The regular numbers are also called 5-smooth, indicating that their greatest prime factor is at most 5.

The first few regular numbers are:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, ... OEIS | id = A051037.

Several other sequences at OEIS have definitions involving 5-smooth numbers. [ [http://www.research.att.com/~njas/sequences/?q=5-smooth OEIS search for sequences involving 5-smoothness] .]

Although the regular numbers appear dense within the range from 1 to 60, they are quite sparse among the larger integers. A regular number "n" = 2^"i"·3^"j"·5^"k" is less than or equal to "N" if and only if the point ("i","j","k") belongs to the tetrahedron bounded by the coordinate planes and the plane $frac\{1\}\{ln\; 2\}i\; +\; frac\{1\}\{ln\; 3\}j\; +\; frac\{1\}\{ln\; 5\}kleln\; N$, so the number of regular numbers that are at most "N" can be estimated as the volume of this tetrahedron, $frac\{log\_2\; N,log\_3\; N,log\_5\; N\}\{6\}.$ [A more precise version of this formula, accurate to within $O(loglog\; N)$ of the exact cardinality, appears [http://www.research.att.com/~njas/sequences/A051037 on OEIS] attributed to Benoit Cloitre.]

Babylonian mathematics

In the Babylonian sexagesimal notation, the reciprocal of a regular number has a finite representation, thus being easy to divide by. Specifically, if "n" divides 60^k, then the sexagesimal representation of 1/"n" is just that for 60^k/"n", shifted by some number of places.

For instance, suppose we wish to divide by the regular number 54 = 2¹3³. 54 is a divisor of 60³, and 60³/54 = 4000, so dividing by 54 in sexagesimal can be accomplished by multiplying by 4000 and shifting three places. In sexagesimal 4000 = 1×3600 + 6×60 + 40×1, or (as listed by Joyce) 1:6:40. Thus, 1/54, in sexagesimal, is 1/60 + 6/60² + 40/60³, also denoted 1:6:40 as Babylonian notational conventions did not specify the power of the starting digit. Conversely 1/4000 = 54/60³, so division by 1:6:40 = 4000 can be accomplished by instead multiplying by 54 and shifting three sexagesimal places.

The Babylonians used tables of reciprocals of regular numbers, some of which still survive (Sachs, 1947). These tables existed relatively unchanged throughout Babylonian times.harvtxt|Aaboe|1965.]

Although the primary reason for preferring regular numbers to other numbers involves the finiteness of their reciprocals, some Babylonian calculations other than reciprocals also involved regular numbers. For instance, tables of regular squares have been found and the broken cuneiform tablet Plimpton 322 has been interpreted by Neugebauer as listing Pythagorean triples $(\; p^2\; -\; q^2,,\; 2pq,,\; p^2\; +\; q^2\; )$ generated by "p", "q" both regular and less than 60. [See harvtxt|Conway|Guy|1996 for a popular treatment of this interpretation. Plimpton 322 has other interpretations, for which see its article, but all involve regular numbers.]

Music theory

In music theory, the just intonation of the diatonic scale involves regular numbers: the pitches in a single octave of this scale have frequencies proportional to the numbers in the sequence 24, 27, 30, 32, 36, 40, 45, 48 of nearly-consecutive regular numbers. Thus, for an instrument with this tuning, all pitches are regular-number harmonics of a single fundamental frequency. This scale is called a 5-limit tuning, meaning that the interval between any two pitches can be described as a product 2ⁱ3^j5^k of powers of the prime numbers up to 5, or equivalently as a ratio of regular numbers.

5-limit musical scales other than the familiar diatonic scale of Western music have also been used, both in traditional musics of other cultures and in modern experimental music: harvtxt|Honing|Bod|2005 list 31 different 5-limit scales, drawn from a larger database of musical scales. Each of these 31 scales shares with diatonic just intonation the property that all intervals are ratios of regular numbers. Euler's tonnetz provides a convenient graphical representation of the pitches in any 5-limit tuning, by factoring out the octave relationships (powers of two) so that the remaining values form a planar grid. Some music theorists have stated more generally that regular numbers are fundamental to tonal music itself, and that pitch ratios based on primes larger than 5 cannot be consonant. [harvtxt|Asmussen|2001, for instance, states that "within any piece of tonal music" all intervals must be ratios of regular numbers, echoing similar statements by much earlier writers such as harvtxt|Habens|1889. In the modern music theory literature this assertion is often attributed to harvtxt|Longuet-Higgins|1962, who used a graphical arrangement closely related to the tonnetz to organize 5-limit pitches.] However the equal temperament of modern pianos is not a 5-limit tuning, and some modern composers have experimented with tunings based on primes larger than five.

In connection with the application of regular numbers to music theory, it is of interest to find pairs of regular numbers that differ by one. There are exactly ten such pairs ("x", "x"+1) [harvtxt|Halsey|Hewitt|1972 note that this follows from Størmer's theorem harv|Størmer|1897, and provide a proof for this case; see also harvtxt|Silver|1971.] and each such pair defines a superparticular ratio ("x" + 1)/"x" that is meaningful as a musical interval. These intervals are 2/1 (the octave), 3/2 (the perfect fifth), 4/3 (the perfect fourth), 5/4 (the just major third), 6/5 (the just minor third), 9/8 (the just major tone), 10/9 (the just minor tone), 16/15 (the just diatonic semitone), 25/24 (the just chromatic semitone), and 81/80 (the syntonic comma).

Computation of regular numbers

Algorithms for calculating the regular numbers in ascending order were popularized by Edsger Dijkstra. harvtxt|Dijkstra|1981 attributes to Hamming the problem of building the infinite ascending sequence of all 5-smooth numbers; this problem is now known as Hamming's problem, and the numbers so generated are also called the Hamming numbers. Dijkstra's ideas to compute these numbers are the following:

* The sequence of Hamming numbers begins with the number 1.

* The remaining values in the sequence are of the form 2"h", 3"h", and 5"h", where "h" is any Hamming number.

* Therefore, the sequence "H" may be generated by outputting the value 1, and then merging the sequences 2"H", 3"H", and 5"H".

This algorithm is often used to demonstrate the power of a lazy functional programming language, because this algorithm can be implemented as described above, using a constant number of arithmetic operations per generated value, while a similarly efficient implementation for a strict functional or imperative programming language is non-trivial. [See, e.g., harvtxt|Hemmendinger|1988 or harvtxt|Yuen|1992.]

In the Python programming language, lazy functional code for generating regular numbers is used as one of the built-in tests for correctness of the language's implementation. [Function m235 in [http://svn.python.org/projects/python/trunk/Lib/test/test_generators.py test_generators.py] .]

A related problem, discussed by harvtxt|Knuth|1972, is to list all "k"-digit sexagesimal numbers in ascending order, as was done (for "k" = 6) by Inakibit-Anu, the Seleucid-era scribe of tablet AO6456. In algorithmic terms, this is equivalent to generating (in order) the subsequence of the infinite sequence of regular numbers, ranging from 60^"k" to 60^{"k" + 1}.See harvtxt|Gingerich|1965 for an early description of computer code that generates these numbers out of order and then sorts them; Knuth describes an ad-hoc algorithm, which he attributes to harvtxt|Bruins|1970, for generating the six-digit numbers more quickly but that does not generalize in a straightforward way to larger values of "k".

Other applications

harvtxt|Heninger|Rains|Sloane|2005 show that, when "n" is a regular number and is divisible by 8, the generating function of an "n"-dimensional extremal even unimodular lattice is an "n"th power of a polynomial.

As with other classes of smooth numbers, regular numbers are important as problem sizes in computer programs for performing the fast Fourier transform, a technique for analyzing the dominant frequencies of signals in time-varying data. For instance, the method of harvtxt|Temperton|1992 requires that the transform length be a regular number.

Book VIII of Plato's Republic involves an allegory of marriage centered around the highly regular number 60⁴ = 12,960,000 and its divisors. Later scholars have invoked both Babylonian mathematics and music theory in an attempt to explain this passage. [harvtxt|Barton|1908; harvtxt|McClain|1974.]

Notes

References

*citation
last = Aaboe | first = Asger
title = Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)
journal = Journal of Cuneiform Studies
volume = 19
issue = 3
pages = 79–86
year = 1965
id = MathSciNet | id = 0191779
doi = 10.2307/1359089.

*citation
last = Asmussen | first Robert
title = Periodicity of sinusoidal frequencies as a basis for the analysis of Baroque and Classical harmony: a computer based study
year = 2001
url = http://www.terraworld.net/c-jasmussen/thesis_asmussen.pdf
publisher = Ph.D. thesis, Univ. of Leeds.

*citation
last = Barton | first = George A.
title = On the Babylonian origin of Plato's nuptial number
year = 1908
journal = Journal of the American Oriental Society
volume = 29
pages = 210–219
doi = 10.2307/592627.

*citation
last = Bruins | first = E. M.
contribution = La construction de la grande table le valeurs réciproques AO 6456
title = Actes de la XVII^e Rencontre Assyriologique Internationale
editor-last = Finet | editor-first = André
publisher = Comité belge de recherches en Mésopotamie
year = 1970
pages = 99–115.

*citation
authorlink1 = John H. Conway | last1 = Conway | first1 = John H.
authorlink2 = Richard K. Guy | last2 = Guy | first2 = Richard K.
title = The Book of Numbers
pages = 172–176
publisher = Copernicus
year = 1996
isbn = 0-387-97993-X.

*citation
authorlink = Edsger W. Dijkstra | last = Dijkstra | first = Edsger W.
title = Hamming's exercise in SASL
year = 1981
url = http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
id = Report EWD792. Originally a privately-circulated handwitten note.

*citation
last = Gingerich | first = Owen
title = Eleven-digit regular sexagesimals and their reciprocals
year = 1965
journal = Transactions of the American Philosophical Society
volume = 55
issue = 8
pages = 3–38
doi = 10.2307/1006080.

*citation
last = Habens | first = Rev. W. J.
title = On the musical scale
journal = Proceedings of the Musical Association
year = 1889
pages = 16th Session, p. 1
url = http://www.jstor.org/stable/765355.

*citation
last1 = Halsey | first1 = G. D. | last2 = Hewitt | first2 = Edwin
title = More on the superparticular ratios in music
journal = American Mathematical Monthly
volume = 79
year = 1972
pages = 1096–1100
id = MathSciNet | id = 0313189
doi = 10.2307/2317424.

*citation
last = Hemmendinger | first = David
journal = ACM SIGPLAN Notices
year = 1988
title = The “Hamming problem” in Prolog
volume = 23
issue = 4
pages = 81–86
doi = 10.1145/44326.44335.

*citation
last1 = Heninger | first1 = Nadia | last2 = Rains | first2 = E. M.
authorlink3 = Neil Sloane | last3 = Sloane | first3 = N. J. A.
title = On the integrality of "n"th roots of generating functions
year = 2005
id = arxiv | archive = math.NT | id = 0509316.

*citation
last1 = Honingh | first1 = Aline | last2 = Bod | first2 = Rens
title = Convexity and the well-formedness of musical objects
journal = Journal of New Music Research
year = 2005
volume = 34
issue = 3
pages = 293–303
doi = 10.1080/09298210500280612.

*citation
last = Knuth | first = D. E. | authorlink = Donald Knuth
title = Ancient Babylonian algorithms
journal = Communications of the ACM
volume = 15 | issue = 7 | year = 1972 | pages = 671–677
doi = 10.1145/361454.361514. Errata in "CACM" 19(2), 1976. Reprinted with a brief addendum in "Selected Papers on Computer Science", CSLI Lecture Notes 59, Cambridge Univ. Press, 1996, pp. 185–203.

*citation
last = Longuet-Higgins | first = H. C.
year = 1962
title = Letter to a musical friend
journal = Music Review
issue = August
pages = 244–248.

*citation
last = McClain | first = Ernest G.
authorlink = Ernest G. McClain
year = 1974
title = Musical “Marriages” in Plato's “Republic”
journal = Journal of Music Theory
volume = 18
issue = 2
pages = 242–272
doi = 10.2307/843638.

*citation
last = Sachs | first = A. J.
year = 1947
title = Babylonian mathematical texts. I. Reciprocals of regular sexagesimal numbers
journal = Journal of Cuneiform Studies
volume = 1
issue = 3
pages = 219–240
id = MathSciNet | id = 0022180
doi = 10.2307/1359434.

*citation
last = Silver | first = A. L. Leigh
title = Musimatics or the nun's fiddle
journal = American Mathematical Monthly
volume = 78
year = 1971
issue = 4
pages = 351–357
doi = 10.2307/2316896.

*citation
last = Størmer | first = Carl
authorlink = Carl Størmer
title = Quelques théorèmes sur l'équation de Pell "x"² - "Dy"² = ±1 et leurs applications
journal = Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl.
volume = I
issue = 2
year = 1897.

*citation
last = Temperton | first = Clive
title = A generalized prime factor FFT algorithm for any "N" = 2^"p"3^"q"5^"r"
journal = SIAM Journal on Scientific and Statistical Computing
volume = 13
issue = 3
year = 1992
pages = 676–686
doi = 10.1137/0913039.

*citation
last = Yuen | first = C. K.
title = Hamming numbers, lazy evaluation, and eager disposal
journal = ACM SIGPLAN Notices
year = 1992
volume = 27
issue = 8
pages = 71–75
doi = 10.1145/142137.142151.

External links

* [http://aleph0.clarku.edu/~djoyce/ma105/reciprocals3600.html Table of reciprocals of regular numbers up to 3600] from the web site of Professor David E. Joyce, Clark University