Regular number
Encyclopedia
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.
- In number theoryNumber theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, these numbers are called 5-smooth, because they can be characterized as having only 2, 3, or 5 as prime factorPrime factorIn number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s. This is a specific case of the more general k-smooth numberSmooth numberIn number theory, a smooth number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization.-Definition:...
s, i.e., a set of numbers that have no prime factor greater than k. - In the study of Babylonian mathematicsBabylonian mathematicsBabylonian mathematics refers to any mathematics of the people of Mesopotamia, from the days of the early Sumerians to the fall of Babylon in 539 BC. Babylonian mathematical texts are plentiful and well edited...
, 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 music theoryMusic theoryMusic theory is the study of how music works. It examines the language and notation of music. It seeks to identify patterns and structures in composers' techniques across or within genres, styles, or historical periods...
, regular numbers occur in the ratios of tones in just intonationJust intonationIn music, just intonation is any musical tuning in which the frequencies of notes are related by ratios of small whole numbers. Any interval tuned in this way is called a just interval. The two notes in any just interval are members of the same harmonic series...
, also called 5-limit tuningLimit (music)In music theory, limit or harmonic limit is a way of characterizing the harmony found in a piece or genre of music, or the harmonies that can be made using a particular scale. The term was introduced by Harry Partch, who used it to give an upper bound on the complexity of harmony; hence the name...
for this reason. - In computer scienceComputer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, regular numbers are often called Hamming numbers, after Richard HammingRichard HammingRichard Wesley Hamming was an American mathematician whose work had many implications for computer science and telecommunications...
, who proposed the problem of finding computer algorithmAlgorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s for generating these numbers in order.
Number theory
Formally, a regular number is an integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
of the form 2i·3j·5k, for nonnegative integers i, j, and k. Such a number is a divisor of
. The regular numbers are also called 5-smoothSmooth number
In number theory, a smooth number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization.-Definition:...
, indicating that their greatest prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
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, ... .
Several other sequences at OEIS have definitions involving 5-smooth numbers.
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 = 2i·3j·5k is less than or equal to N if and only if the point (i,j,k) belongs to the tetrahedron
Tetrahedron
In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...
bounded by the coordinate planes and the plane
as can be seen by taking logarithms of both sides of the inequality 2i·3j·5k ≤ N.
Therefore, the number of regular numbers that are at most N can be estimated as the volume
Volume
Volume is the quantity of three-dimensional space enclosed by some closed boundary, for example, the space that a substance or shape occupies or contains....
of this tetrahedron, which is
Even more precisely, using big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
, the number of regular numbers up to N is
A similar formula for the number of 3-smooth numbers up to N is given by Srinivasa Ramanujan
Srinivasa Ramanujan
Srīnivāsa Aiyangār Rāmānujan FRS, better known as Srinivasa Iyengar Ramanujan was a Indian mathematician and autodidact who, with almost no formal training in pure mathematics, made extraordinary contributions to mathematical analysis, number theory, infinite series and continued fractions...
in his first letter to G. H. Hardy
G. H. Hardy
Godfrey Harold “G. H.” Hardy FRS was a prominent English mathematician, known for his achievements in number theory and mathematical analysis....
.
Babylonian mathematics
In the Babylonian sexagesimal notation, the reciprocalMultiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the...
of a regular number has a finite representation, thus being easy to divide by. Specifically, if n divides 60k, then the sexagesimal representation of 1/n is just that for 60k/n, shifted by some number of places.
For instance, suppose we wish to divide by the regular number 54 = 2133. 54 is a divisor of 603, and 603/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/602 + 40/603, also denoted 1:6:40 as Babylonian notational conventions did not specify the power of the starting digit. Conversely 1/4000 = 54/603, 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.
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
Cuneiform script
Cuneiform script )) is one of the earliest known forms of written expression. Emerging in Sumer around the 30th century BC, with predecessors reaching into the late 4th millennium , cuneiform writing began as a system of pictographs...
tablet
Clay tablet
In the Ancient Near East, clay tablets were used as a writing medium, especially for writing in cuneiform, throughout the Bronze Age and well into the Iron Age....
Plimpton 322
Plimpton 322
Plimpton 322 is a Babylonian clay tablet, notable as containing an example of Babylonian mathematics. It has number 322 in the G.A. Plimpton Collection at Columbia University...
has been interpreted by Neugebauer
Otto E. Neugebauer
Otto Eduard Neugebauer was an Austrian-American mathematician and historian of science who became known for his research on the history of astronomy and the other exact sciences in antiquity and into the Middle Ages...
as listing Pythagorean triple
Pythagorean triple
A Pythagorean triple consists of three positive integers a, b, and c, such that . Such a triple is commonly written , and a well-known example is . If is a Pythagorean triple, then so is for any positive integer k. A primitive Pythagorean triple is one in which a, b and c are pairwise coprime...
s
generated by p, q both regular and less than 60.Music theory
In music theoryMusic theory
Music theory is the study of how music works. It examines the language and notation of music. It seeks to identify patterns and structures in composers' techniques across or within genres, styles, or historical periods...
, the just intonation
Just intonation
In music, just intonation is any musical tuning in which the frequencies of notes are related by ratios of small whole numbers. Any interval tuned in this way is called a just interval. The two notes in any just interval are members of the same harmonic series...
of the diatonic scale
Diatonic scale
In music theory, a diatonic scale is a seven note, octave-repeating musical scale comprising five whole steps and two half steps for each octave, in which the two half steps are separated from each other by either two or three whole steps...
involves regular numbers: the pitches
Pitch (music)
Pitch is an auditory perceptual property that allows the ordering of sounds on a frequency-related scale.Pitches are compared as "higher" and "lower" in the sense associated with musical melodies,...
in a single octave
Octave
In music, an octave is the interval between one musical pitch and another with half or double its frequency. The octave relationship is a natural phenomenon that has been referred to as the "basic miracle of music", the use of which is "common in most musical systems"...
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 harmonic
Harmonic
A harmonic of a wave is a component frequency of the signal that is an integer multiple of the fundamental frequency, i.e. if the fundamental frequency is f, the harmonics have frequencies 2f, 3f, 4f, . . . etc. The harmonics have the property that they are all periodic at the fundamental...
s of a single fundamental frequency
Fundamental frequency
The fundamental frequency, often referred to simply as the fundamental and abbreviated f0, is defined as the lowest frequency of a periodic waveform. In terms of a superposition of sinusoids The fundamental frequency, often referred to simply as the fundamental and abbreviated f0, is defined as the...
. This scale is called a 5-limit
Limit (music)
In music theory, limit or harmonic limit is a way of characterizing the harmony found in a piece or genre of music, or the harmonies that can be made using a particular scale. The term was introduced by Harry Partch, who used it to give an upper bound on the complexity of harmony; hence the name...
tuning, meaning that the interval
Interval (music)
In music theory, an interval is a combination of two notes, or the ratio between their frequencies. Two-note combinations are also called dyads...
between any two pitches can be described as a product 2i3j5k 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: 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
Tonnetz
In musical tuning and harmony, the Tonnetz is a conceptual lattice diagram representing tonal space first described by Leonhard Euler in 1739....
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
Regular grid
A regular grid is a tessellation of n-dimensional Euclidean space by congruent parallelotopes . Grids of this type appear on graph paper and may be used in finite element analysis as well as finite volume methods and finite difference methods...
. 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
Consonance and dissonance
In music, a consonance is a harmony, chord, or interval considered stable, as opposed to a dissonance , which is considered to be unstable...
. However the equal temperament
Equal temperament
An equal temperament is a musical temperament, or a system of tuning, in which every pair of adjacent notes has an identical frequency ratio. As pitch is perceived roughly as the logarithm of frequency, this means that the perceived "distance" from every note to its nearest neighbor is the same for...
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) 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
Octave
In music, an octave is the interval between one musical pitch and another with half or double its frequency. The octave relationship is a natural phenomenon that has been referred to as the "basic miracle of music", the use of which is "common in most musical systems"...
), 3/2 (the perfect fifth
Perfect fifth
In classical music from Western culture, a fifth is a musical interval encompassing five staff positions , and the perfect fifth is a fifth spanning seven semitones, or in meantone, four diatonic semitones and three chromatic semitones...
), 4/3 (the perfect fourth
Perfect fourth
In classical music from Western culture, a fourth is a musical interval encompassing four staff positions , and the perfect fourth is a fourth spanning five semitones. For example, the ascending interval from C to the next F is a perfect fourth, as the note F lies five semitones above C, and there...
), 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
Syntonic comma
In music theory, the syntonic comma, also known as the chromatic diesis, the comma of Didymus, the Ptolemaic comma, or the diatonic comma is a small comma type interval between two musical notes, equal to the frequency ratio 81:80, or around 21.51 cents...
).
Algorithms
Algorithms for calculating the regular numbers in ascending order were popularized by Edsger DijkstraEdsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
. 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 2h, 3h, and 5h, where h is any Hamming number.
- Therefore, the sequence H may be generated by outputting the value 1, and then mergingMerge algorithmMerge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. This is well-suited for machines with tape drives...
the sequences 2H, 3H, and 5H.
This algorithm is often used to demonstrate the power of a lazy
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
functional programming language, because (implicitly) concurrent efficient implementations, using a constant number of arithmetic operations per generated value, are easily constructed as described above. Similarly efficient strict functional or imperative sequential implementations are also possible whereas explicitly concurrent generative solutions might be non-trivial.
In the Python programming language
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, lazy functional code for generating regular numbers is used as one of the built-in tests for correctness of the language's implementation.
A related problem, discussed by , 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 60k to 60k + 1.
See 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 , for generating the six-digit numbers more quickly but that does not generalize in a straightforward way to larger values of k. describes an algorithm for computing tables of this type in linear time for arbitrary values of k.
Other applications
show that, when n is a regular number and is divisible by 8, the generating function of an n-dimensional extremal even unimodular latticeUnimodular lattice
In mathematics, a unimodular lattice is a lattice of determinant 1 or −1.The E8 lattice and the Leech lattice are two famous examples.- Definitions :...
is an nth power of a polynomial.
As with other classes of smooth number
Smooth number
In number theory, a smooth number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization.-Definition:...
s, regular numbers are important as problem sizes in computer programs for performing the fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
, a technique for analyzing the dominant frequencies of signals in time-varying data
Signal (electrical engineering)
In the fields of communications, signal processing, and in electrical engineering more generally, a signal is any time-varying or spatial-varying quantity....
. For instance, the method of requires that the transform length be a regular number.
Book VIII of Plato
Plato
Plato , was a Classical Greek philosopher, mathematician, student of Socrates, writer of philosophical dialogues, and founder of the Academy in Athens, the first institution of higher learning in the Western world. Along with his mentor, Socrates, and his student, Aristotle, Plato helped to lay the...
's Republic involves an allegory of marriage centered around the highly regular number 604 = 12,960,000 and its divisors. Later scholars have invoked both Babylonian mathematics and music theory in an attempt to explain this passage.
External links
- Table of reciprocals of regular numbers up to 3600 from the web site of Professor David E. Joyce, Clark University