Szabályos számok

A szabályos számok oszthatósági kapcsolatait bemutató Hasse-diagram (400-ig). A függőleges tengely logaritmikus.

A szabályos számok vagy reguláris számok (regular numbers) azok a számok, melyek maradék nélkül osztják 60, illetve ezzel ekvivalensen 30 hatványait. Például 60² = 3600 = 48 × 75, ezért 48 és 75 is osztója egy 60-hatványnak. Ezért mindkettő szabályos szám. Ezzel ekvivalens állítás, hogy a szabályos számok azok a számok, melyek egyedüli prímosztói a 2, 3 és/vagy 5.

A 60 hatványait maradék nélkül osztó számok sok helyen játszanak szerepet a matematikában, tudományterületenként más-más néven.

• A számelmélet területén ezeket a számokat 5-simának nevezik, mivel csak 2, 3 vagy 5 szerepel prímtényezőik között. Ez az általánosabb k-sima számok egy specifikus esete (olyan számok, melyek nem rendelkeznek k-nál nagyobb prímtényezővel).
• A babiloni matematikában ezeket a számokat szabályos számoknak vagy szabályos szexagezimális számoknak hívták, és fontos szerepük volt a babiloniak által használt hatvanas számrendszer miatt.
• A zeneelméletben a szabályos számok a tiszta hangolás frekvenciaarányaiban játszanak szerepet.
• A számítástudományban a szabályos számokat gyakran Hamming-számoknak nevezik Richard Hamming után, aki a reguláris számok sorrendben történő előállítására keresett algoritmusokat.

Számelmélet

Formálisan, egy szabályos szám olyan szám, mely felírható 2ⁱ·3^j·5^k alakban, ahol i, j és k természetes számok. Az ilyen számok $\scriptstyle 60^{\max(\lceil i\,/2\rceil ,j,k)}{}$ osztói. A szabályos számokat nevezik 5-sima számoknak is, mivel legnagyobb prímtényezőjük legfeljebb 5 lehet.

Az első néhány szabályos szám:

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, ... (A051037 sorozat az OEIS-ben).

Az OEIS-ben lévő számos sorozatnak van köze az 5-sima számokhoz.

Bár a szabályos számok sűrűnek látszanak 1–60 között, a nagyobb számok között elég ritkák. Egy n = 2ⁱ·3^j·5^k szabályos szám akkor és csak akkor nem nagyobb N-nél, ha az (i,j,k) pont eleme a tetraédernek, amit a koordinátasíkok mellett a

$(\ln 2)i+(\ln 3)j+(\ln 5)k\leq \ln N$

sík határol, ami jobban érthető, ha vesszük a 2ⁱ·3^j·5^k ≤ N egyenlőtlenség mindkét oldalának logaritmusát. Ezért az N-nél nem nagyobb szabályos számok mennyisége jól becsülhető az említett tetraéder térfogatával, ami

${\frac {\log _{2}N\,\log _{3}N\,\log _{5}N}{6}}.$

Még pontosabban, az O jelölést használva, az N-nél nem nagyobb szabályos számok mennyisége

${\frac {\left(\ln(N{\sqrt {30}})\right)^{3}}{6\ln 2\ln 3\ln 5}}+O(\log N),$

és egy sejtés szerint a közelítés hibatagja éppen $O(\log \log N)$. Hasonló képletet adott meg a 3-sima számok mennyiségére Rámánudzsan G. H. Hardy-hoz írt első levelében.

Babiloni matematika

A babiloni hatvanas számrendszerben a szabályos számok reciprokai véges alakba írhatók, ezért könnyű osztani velük. Specifikusan, ha n osztója 60^k-nak, akkor az 1/n 60-as számrendszerbeli alakja 60^k/n, néhány helyi értékkel elcsúsztatva.

Tegyük fel például, hogy a szabályos 54 = 2¹3³-gyel kívánunk osztani. az 54 osztója 60³-nek, továbbá 60³/54 = 4000, ezért a 60-as számrendszerbeli 54-gyel való osztás elvégezhető 4000-rel való szorzással és három helyi érték csúsztatással. 4000₆₀= 1×3600 + 6×60 + 40×1 vagy (ahogy Joyce írja) 1:6:40. Ezért 1/54 hatvanas számrendszerben 1/60 + 6/60² + 40/60³, amit 1:6:40-nel is jelölnek, mivel a hagyományos babiloni lejegyzés nem határozta meg a kezdő számjegy hatványát. Megfordítva, 1/4000 = 54/60³, tehát az 1:6:40 = 4000-rel történő osztás megvalósítható 54-gyel való szorzással és három helyi értékkel való csúsztatással.

A babiloniak táblázatokban gyűjtötték a szabályos számok reciprokait, ezen táblák némelyike máig fennmaradt (Sachs, 1947). A táblázatok tartalma nem sokat változott a babiloni idők óta.

Bár a szabályos számok előnyben részesítésének fő oka reciprokaik véges hosszúságú kifejezése, a babiloniak a reciprokképzésen kívül is felhasználták a szabályos számokat. Például szabályos számok négyzeteit tartalmazó táblákat találtak, és egy törött ékírásos agyagtábla, a Plimpton 322 Neugebauer értelmezése szerint $(p^{2}-q^{2},\,2pq,\,p^{2}+q^{2})$ pitagoraszi számhármasokat sorolt, ahol p és q 60-nál kisebb szabályos számok.

Zeneelmélet

A zeneelméletben a tiszta hangolású diatonikus hangsor is összefüggésbe hozható a szabályos számokkal: ennek a skálának egy oktávjában lévő hangmagasságok frekvenciái a csaknem egymást követő szabályos számok sorozatával, a 24, 27, 30, 32, 36, 40, 45, 48 számokkal arányosak. Ezért egy ilyen hangolású hangszer hangmagasságai mind szabályos számú harmonikusai egyetlen alapfrekvenciának.

Algoritmusok

A szabályos számok emelkedő sorrendbeli generálásának algoritmusait Edsger Dijkstra hozta be a köztudatba. Dijkstra (1976, 1981) Hamming-nek tulajdonítja az 5-sima számok végtelen növekvő sorozatának megkonstruálását; ez ma Hamming-probléma néven ismert, és az így képezett számok a Hamming-számok. Dijkstra így gondolta el a számok kiszámítását:

• A Hamming-számok sorozata 1-gyel kezdődik.
• A sorozat többi eleme 2h, 3h vagy 5h alakú, ahol h bármely Hamming-számot jelöli.
• Ezért a H sorozat generálható úgy, hogy kiírjuk az 1-et, majd összefésüljük a 2H, 3H és 5H sorozatot.

A fenti algoritmust gyakran idézik a lusta kiértékelésű funkcionális programnyelvek erejének demonstrálására, mivel a fentiekből könnyen következnek az (implicit) konkurens hatékony megvalósítások, kiszámolt értékenként konstans számú aritmetikai művelettel. Hasonlóan hatékony szigorúan funkcionális vagy imperatív szekvenciális megvalósítások szintén lehetségesek, míg expliciten konkurens generatív megoldások létrehozása valószínűleg nem triviális.

A Python programozási nyelvben a szabályos számokat generáló lusta funkcionális kód a nyelv implementációjának korrektségét tesztelő beépített tesztek egyike.

Az előzővel összefüggő probléma, amit (Knuth 1972) tárgyal, az összes hatvanas számrendszerbeli k-jegyű szabályos szám sorrendben történő listázása, ahogy azt (k = 6-ra) Inakibit-Anu tette, a Szeleukida Birodalom korából származó AO6456 táblán. Algoritmikus értelemben ez megegyezik a szabályos számok végtelen sorozatából a 60^k és 60^k + 1 közötti részsorozat előállításával. (Gingerich 1965) adta az egyik korai megoldást a számok nem sorrendi előállítására, majd sorba rendezésére. Knuth leír egy ad hoc algoritmust, amit (Bruins 1970)-nak tulajdonít, a hatjegyű számok gyorsabb előállítására, de a megoldás nem könnyen általánosítható nagyobb k értékekre. (Eppstein 2007) ír le végül egy algoritmust, ami lineáris időben állítha elő az ilyen jellegű táblázatokat tetszőleges k-ra.

Irodalom

• Aaboe, Asger (1965), "Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)", Journal of Cuneiform Studies (The American Schools of Oriental Research) 19 (3): 79–86, DOI 10.2307/1359089.
• Asmussen, Robert (2001), Periodicity of sinusoidal frequencies as a basis for the analysis of Baroque and Classical harmony: a computer based study, Ph.D. thesis, University of Leeds, <http://www.terraworld.net/c-jasmussen/thesis_asmussen.pdf>. Hozzáférés ideje: 2016-04-14 Archiválva 2016. április 24-i dátummal a Wayback Machine-ben.
• Barton, George A. (1908), "On the Babylonian origin of Plato's nuptial number", Journal of the American Oriental Society (American Oriental Society) 29: 210–219, DOI 10.2307/592627.
• Bruins, E. M. (1970), "La construction de la grande table le valeurs réciproques AO 6456", in Finet, André, Actes de la XVII^e Rencontre Assyriologique Internationale, Comité belge de recherches en Mésopotamie, pp. 99–115.
• Conway, John H. & Guy, Richard K. (1996), The Book of Numbers, Copernicus, pp. 172–176, ISBN 0-387-97993-X.
• Dijkstra, Edsger W. (1976), "17. An exercise attributed to R. W. Hamming", A Discipline of Programming, Prentice-Hall, pp. 129–134, ISBN 978-0132158718, <http://web.cecs.pdx.edu/~cs410aph/Lectures/Smalltalk%20II/Dijkstra%20on%20Hamming's%20Problem.pdf> Archiválva 2016. március 3-i dátummal a Wayback Machine-ben
• Dijkstra, Edsger W. (1981), Hamming's exercise in SASL, Report EWD792. Originally a privately circulated handwitten note, <http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF>.
• Eppstein, David (2007), The range-restricted Hamming problem, <http://11011110.livejournal.com/95519.html>. Hozzáférés ideje: 2016-04-14 Archiválva 2011. július 21-i dátummal a Wayback Machine-ben.
• Gingerich, Owen (1965), "Eleven-digit regular sexagesimals and their reciprocals", Transactions of the American Philosophical Society (American Philosophical Society) 55 (8): 3–38, DOI 10.2307/1006080.
• Habens, Rev. W. J. (1889), "On the musical scale", Proceedings of the Musical Association (Royal Musical Association) 16: 16th Session, p. 1.
• Halsey, G. D. & Hewitt, Edwin (1972), "More on the superparticular ratios in music", American Mathematical Monthly (Mathematical Association of America) 79 (10): 1096–1100, DOI 10.2307/2317424.
• Hemmendinger, David (1988), "The "Hamming problem" in Prolog", ACM SIGPLAN Notices 23 (4): 81–86, DOI 10.1145/44326.44335.
• Heninger, Nadia; Rains, E. M. & Sloane, N. J. A. (2006), "On the integrality of nth roots of generating functions", Journal of Combinatorial Theory, Series A 113 (8): 1732–1745, DOI 10.1016/j.jcta.2006.03.018}.
• Honingh, Aline & Bod, Rens (2005), "Convexity and the well-formedness of musical objects", Journal of New Music Research 34 (3): 293–303, DOI 10.1080/09298210500280612.
• Knuth, D. E. (1972), "Ancient Babylonian algorithms", Communications of the ACM 15 (7): 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.
• Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (no. August): 244–248.
• McClain, Ernest G. (1974), "Musical "Marriages" in Plato's "Republic"", Journal of Music Theory (Duke University Press) 18 (2): 242–272, DOI 10.2307/843638.
• Sachs, A. J. (1947), "Babylonian mathematical texts. I. Reciprocals of regular sexagesimal numbers", Journal of Cuneiform Studies (The American Schools of Oriental Research) 1 (3): 219–240, DOI 10.2307/1359434.
• Silver, A. L. Leigh (1971), "Musimatics or the nun's fiddle", American Mathematical Monthly (Mathematical Association of America) 78 (4): 351–357, DOI 10.2307/2316896.
• Størmer, Carl (1897), "Quelques théorèmes sur l'équation de Pell x² − Dy² = ±1 et leurs applications", Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl. I (2).
• Temperton, Clive (1992), "A generalized prime factor FFT algorithm for any N = 2^p3^q5^r", SIAM Journal on Scientific and Statistical Computing 13 (3): 676–686, DOI 10.1137/0913039.
• Yuen, C. K. (1992), "Hamming numbers, lazy evaluation, and eager disposal", ACM SIGPLAN Notices 27 (8): 71–75, DOI 10.1145/142137.142151.

További információk

• Table of reciprocals of regular numbers up to 3600 from the web site of Professor David E. Joyce, Clark University.
• RosettaCode Generation of Hamming_numbers in ~ 50 programming languages