Erősen összetett számok

Egy erősen összetett szám (highly composite number, HCN) olyan pozitív egész szám, melynek több osztója van bármelyik nála kisebb pozitív egésznél. A kifejezést elsőként Rámánudzsan használta 1915-ben – Jean-Pierre Kahane szerint azonban visszavezethető Platónig, aki szerint 5040 a városlakók ideális száma, mivel 5040-nek több osztója van a kisebb számoknál.^[1]

Kapcsolódó fogalom a nagyon összetett szám, ami olyan pozitív egészekre vonatkozik, aminek legalább annyi osztója van, mint bármely nála kisebb pozitív egésznek.

Példák

Az első, avagy legkisebb 38 erősen összetett szám listája: (A002182 sorozat az OEIS-ben)

Sorszám	HCN n	prímtényezős felbontás	prímek kitevői	prím- tényezők	d(n)	prímoriális felbontás
1	1			0	1
2*	2	${\displaystyle 2}$	1	1	2	${\displaystyle 2}$
3	4	${\displaystyle 2^{2}}$	2	2	3	${\displaystyle 2^{2}}$
4*	6	${\displaystyle 2\cdot 3}$	1,1	2	4	${\displaystyle 6}$
5*	12	${\displaystyle 2^{2}\cdot 3}$	2,1	3	6	${\displaystyle 2\cdot 6}$
6	24	${\displaystyle 2^{3}\cdot 3}$	3,1	4	8	${\displaystyle 2^{2}\cdot 6}$
7	36	${\displaystyle 2^{2}\cdot 3^{2}}$	2,2	4	9	${\displaystyle 6^{2}}$
8	48	${\displaystyle 2^{4}\cdot 3}$	4,1	5	10	${\displaystyle 2^{3}\cdot 6}$
9*	60	${\displaystyle 2^{2}\cdot 3\cdot 5}$	2,1,1	4	12	${\displaystyle 2\cdot 30}$
10*	120	${\displaystyle 2^{3}\cdot 3\cdot 5}$	3,1,1	5	16	${\displaystyle 2^{2}\cdot 30}$
11	180	${\displaystyle 2^{2}\cdot 3^{2}\cdot 5}$	2,2,1	5	18	${\displaystyle 6\cdot 30}$
12	240	${\displaystyle 2^{4}\cdot 3\cdot 5}$	4,1,1	6	20	${\displaystyle 2^{3}\cdot 30}$
13*	360	${\displaystyle 2^{3}\cdot 3^{2}\cdot 5}$	3,2,1	6	24	${\displaystyle 2\cdot 6\cdot 30}$
14	720	${\displaystyle 2^{4}\cdot 3^{2}\cdot 5}$	4,2,1	7	30	${\displaystyle 2^{2}\cdot 6\cdot 30}$
15	840	${\displaystyle 2^{3}\cdot 3\cdot 5\cdot 7}$	3,1,1,1	6	32	${\displaystyle 2^{2}\cdot 210}$
16	1260	${\displaystyle 2^{2}\cdot 3^{2}\cdot 5\cdot 7}$	2,2,1,1	6	36	${\displaystyle 6\cdot 210}$
17	1680	${\displaystyle 2^{4}\cdot 3\cdot 5\cdot 7}$	4,1,1,1	7	40	${\displaystyle 2^{3}\cdot 210}$
18*	2520	${\displaystyle 2^{3}\cdot 3^{2}\cdot 5\cdot 7}$	3,2,1,1	7	48	${\displaystyle 2\cdot 6\cdot 210}$
19*	5040	${\displaystyle 2^{4}\cdot 3^{2}\cdot 5\cdot 7}$	4,2,1,1	8	60	${\displaystyle 2^{2}\cdot 6\cdot 210}$
20	7560	${\displaystyle 2^{3}\cdot 3^{3}\cdot 5\cdot 7}$	3,3,1,1	8	64	${\displaystyle 6^{2}\cdot 210}$
21	10080	${\displaystyle 2^{5}\cdot 3^{2}\cdot 5\cdot 7}$	5,2,1,1	9	72	${\displaystyle 2^{3}\cdot 6\cdot 210}$
22	15120	${\displaystyle 2^{4}\cdot 3^{3}\cdot 5\cdot 7}$	4,3,1,1	9	80	${\displaystyle 2\cdot 6^{2}\cdot 210}$
23	20160	${\displaystyle 2^{6}\cdot 3^{2}\cdot 5\cdot 7}$	6,2,1,1	10	84	${\displaystyle 2^{4}\cdot 6\cdot 210}$
24	25200	${\displaystyle 2^{4}\cdot 3^{2}\cdot 5^{2}\cdot 7}$	4,2,2,1	9	90	${\displaystyle 2^{2}\cdot 30\cdot 210}$
25	27720	${\displaystyle 2^{3}\cdot 3^{2}\cdot 5\cdot 7\cdot 11}$	3,2,1,1,1	8	96	${\displaystyle 2\cdot 6\cdot 2310}$
26	45360	${\displaystyle 2^{4}\cdot 3^{4}\cdot 5\cdot 7}$	4,4,1,1	10	100	${\displaystyle 6^{3}\cdot 210}$
27	50400	${\displaystyle 2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7}$	5,2,2,1	10	108	${\displaystyle 2^{3}\cdot 30\cdot 210}$
28*	55440	${\displaystyle 2^{4}\cdot 3^{2}\cdot 5\cdot 7\cdot 11}$	4,2,1,1,1	9	120	${\displaystyle 2^{2}\cdot 6\cdot 2310}$
29	83160	${\displaystyle 2^{3}\cdot 3^{3}\cdot 5\cdot 7\cdot 11}$	3,3,1,1,1	9	128	${\displaystyle 6^{2}\cdot 2310}$
30	110880	${\displaystyle 2^{5}\cdot 3^{2}\cdot 5\cdot 7\cdot 11}$	5,2,1,1,1	10	144	${\displaystyle 2^{3}\cdot 6\cdot 2310}$
31	166320	${\displaystyle 2^{4}\cdot 3^{3}\cdot 5\cdot 7\cdot 11}$	4,3,1,1,1	10	160	${\displaystyle 2\cdot 6^{2}\cdot 2310}$
32	221760	${\displaystyle 2^{6}\cdot 3^{2}\cdot 5\cdot 7\cdot 11}$	6,2,1,1,1	11	168	${\displaystyle 2^{4}\cdot 6\cdot 2310}$
33	277200	${\displaystyle 2^{4}\cdot 3^{2}\cdot 5^{2}\cdot 7\cdot 11}$	4,2,2,1,1	10	180	${\displaystyle 2^{2}\cdot 30\cdot 2310}$
34	332640	${\displaystyle 2^{5}\cdot 3^{3}\cdot 5\cdot 7\cdot 11}$	5,3,1,1,1	11	192	${\displaystyle 2^{2}\cdot 6^{2}\cdot 2310}$
35	498960	${\displaystyle 2^{4}\cdot 3^{4}\cdot 5\cdot 7\cdot 11}$	4,4,1,1,1	11	200	${\displaystyle 6^{3}\cdot 2310}$
36	554400	${\displaystyle 2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7\cdot 11}$	5,2,2,1,1	11	216	${\displaystyle 2^{3}\cdot 30\cdot 2310}$
37	665280	${\displaystyle 2^{6}\cdot 3^{3}\cdot 5\cdot 7\cdot 11}$	6,3,1,1,1	12	224	${\displaystyle 2^{3}\cdot 6^{2}\cdot 2310}$
38*	720720	${\displaystyle 2^{4}\cdot 3^{2}\cdot 5\cdot 7\cdot 11\cdot 13}$	4,2,1,1,1,1	10	240	${\displaystyle 2^{2}\cdot 6\cdot 30030}$

A következő táblázat megmutatja az egyik ilyen szám összes osztóját.

Az erősen összetett szám: 10080 10080 = (2 × 2 × 2 × 2 × 2)  ×  (3 × 3)  ×  5  ×  7
1 × 10080	2 × 5040	3 × 3360	4 × 2520	5 × 2016	6 × 1680
7 × 1440	8 × 1260	9 × 1120	10 × 1008	12 × 840	14 × 720
15 × 672	16 × 630	18 × 560	20 × 504	21 × 480	24 × 420
28 × 360	30 × 336	32 × 315	35 × 288	36 × 280	40 × 252
42 × 240	45 × 224	48 × 210	56 × 180	60 × 168	63 × 160
70 × 144	72 × 140	80 × 126	84 × 120	90 × 112	96 × 105
Megjegyzés:  A félkövér számok maguk is erősen összetett számok. Csak a huszadik erősen összetett szám, 7560 (= 3 × 2520) hiányzik. A 10080 egy úgynevezett 7-sima szám (A002473 sorozat az OEIS-ben).

A 15 000. erősen összetett szám megtalálható Achim Flammenkamp weboldalán. 230 prím szorzata adja ki:

${\displaystyle a_{0}^{14}a_{1}^{9}a_{2}^{6}a_{3}^{4}a_{4}^{4}a_{5}^{3}a_{6}^{3}a_{7}^{3}a_{8}^{2}a_{9}^{2}a_{10}^{2}a_{11}^{2}a_{12}^{2}a_{13}^{2}a_{14}^{2}a_{15}^{2}a_{16}^{2}a_{17}^{2}a_{18}^{2}a_{19}a_{20}a_{21}\cdots a_{229},}$

ahol ${\displaystyle a_{n}}$ egymást követő prímszámok sorozata, és a kihagyott tagok (a₂₂-tól a₂₂₈-ig) egyes kitevőjű tényezők (tehát másként felírva a szám ${\displaystyle 2^{14}\times 3^{9}\times 5^{6}\times \cdots \times 1451}$).^[2]

Prímtényezős felbontás

Ahhoz, hogy egy szám erősen összetett legyen, nagyjából arra van szükség, hogy lehetőleg minél kisebb prímtényezői legyenek, de ne legyen túl sok egyforma belőlük. A számelmélet alaptétele szerint minden pozitív egész n egyedi prímtényezős felbontással rendelkezik:

${\displaystyle n=p_{1}^{c_{1}}\times p_{2}^{c_{2}}\times \cdots \times p_{k}^{c_{k}}\qquad (1)}$

ahol ${\displaystyle p_{1}<p_{2}<\cdots <p_{k}}$ prímszámok, a ${\displaystyle c_{i}}$ kitevők pedig pozitív egész számok.

Az n bármely osztójának prímenként kisebb vagy egyenlő multiplicitással kell rendelkeznie, mint n-nek:

${\displaystyle p_{1}^{d_{1}}\times p_{2}^{d_{2}}\times \cdots \times p_{k}^{d_{k}},0\leq d_{i}\leq c_{i},0<i\leq k}$

Tehát n osztóinak száma:

${\displaystyle d(n)=(c_{1}+1)\times (c_{2}+1)\times \cdots \times (c_{k}+1).\qquad (2)}$

Ezért, n akkor lehet erősen összetett szám, hogyha

• a k db p_i prímszám pontosan az első k prímszámmal (2, 3, 5, ...) egyezik meg; ha nem így lenne, valamelyik prímszámot lecserélhetnénk kisebb prímszámra, így n-nél kisebb számot kapnánk ugyanannyi osztóval (például a 10 = 2 × 5 esetében a lecserélt 6 = 2 × 3 számnak ugyanúgy 4 osztója van);

• a kitevők sorozatának nem növekvőnek kell lennie, tehát ${\displaystyle c_{1}\geq c_{2}\geq \cdots \geq c_{k}}$; egyébként két kitevő kicserélésével az előző példához hasonlóan n-nél kisebb számot kapnánk ugyanannyi osztóval (például 18 = 2¹ × 3² kicserélhető a 12 = 2² × 3¹ számra; mindkettőnek 6 osztója van).

Továbbá, a két speciális eset n = 4 és n = 36 kivételével, az utolsó c_k kitevőnek 1-nek kell lennie. Ez azt jelenti, hogy kizárólag az 1, a 4 és a 36 négyzetszám az erősen összetett számok közül. Az, hogy a kitevők sorozata nem növekvő, ekvivalens azzal az állítással, hogy az erősen összetett számok prímoriálisok szorzataként állnak elő.

Aszimptotikus növekedés és sűrűség

Ha Q(x) jelöli az x-nél nem nagyobb erősen összetett számok számát, akkor létezik két, 1-nél nagyobb a és b konstans, melyekre igaz, hogy

${\displaystyle \ln(x)^{a}\leq Q(x)\leq \ln(x)^{b}\,.}$

Az egyenlőtlenség első részét Erdős Pál bizonyította 1944-ben, a másodikat Jean-Louis Nicolas 1988-ban. A konstansokra a jelenlegi legjobb közelítés^[3]

${\displaystyle 1,13862<\liminf {\frac {\log Q(x)}{\log \log x}}\leq 1,44\ }$

és

${\displaystyle \limsup {\frac {\log Q(x)}{\log \log x}}\leq 1,71\ .}$

Kapcsolódó sorozatok

A 6-nál nagyobb erősen összetett számok egyben bővelkedő számok is, ami egy adott erősen összetett szám három-négy legnagyobb osztójára nézve azonnal nyilvánvaló. Téves az az állítás, hogy az erősen összetett számok tízes számrendszerben mind Harshad-számok lennének. Az első HCN, ami nem Harshad-szám a 245 044 800, melynek számjegyösszege 27, ami nem osztója a 245 044 800-nak.

Az első 38 erősen összetett számból 10 egyben kiváló erősen összetett szám is. Az erősen összetett számok sorozata (A002182 sorozat az OEIS-ben) részsorozata a pontosan n osztóval rendelkező legkisebb k számok sorozatának (A005179 sorozat az OEIS-ben).

Egy n pozitív egész nagyon összetett szám, ha d(n) ≥ d(m) minden m ≤ n-re. A nagyon összetett számokat számláló Q_L(x) függvény eleget tesz a

${\displaystyle (\log x)^{c}\leq \log Q_{L}(x)\leq (\log x)^{d}\ }$

egyenlőtlenségnek minden pozitív c,d-re, amennyiben ${\displaystyle 0,2\leq c\leq d\leq 0,5}$.^[4][5]

Mivel az erősen összetett számok prímtényezős felbontásában az első k prím hiány nélkül szerepel, ezért minden erősen összetett szám egyben praktikus szám is.^[6] Az ilyen számok közül sokat használtak hagyományos mértékegységrendszerek váltószámaként, mérnöki tervekben, mert jól kezelhetők a törtekkel való számítások során.

Kapcsolódó szócikkek

• Erősen tóciens szám
• Euler-függvény

Fordítás

• Ez a szócikk részben vagy egészben a Highly composite number című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• (1915) „Highly composite numbers”. Proc. London Math. Soc. (2) 14, 347–409. o. DOI:10.1112/plms/s2_14.1.347.   (online Archiválva 2014. szeptember 3-i dátummal a Wayback Machine-ben)
• Handbook of number theory I. Dordrecht: Springer-Verlag, 45–46. o. (2006). ISBN 1-4020-4215-9 
• Erdős, P. (1944). „On highly composite numbers”. Journal of the London Mathematical Society 19, 130–133. o. DOI:10.1112/jlms/19.75_part_3.130.  
• (1944) „On highly composite and similar numbers”. Transactions of the American Mathematical Society 56 (3), 448–469. o. DOI:10.2307/1990319.  
• Ramanujan, Srinivasa (1997). „Highly composite numbers”. Ramanujan Journal 1 (2), 119–153. o. DOI:10.1023/A:1009764017495.   Annotated and with a foreword by Jean-Louis Nicolas and Guy Robin.

További információk

• Weisstein, Eric W.: Highly Composite Number (angol nyelven). Wolfram MathWorld
• Algorithm for computing Highly Composite Numbers
• First 10000 Highly Composite Numbers
• Achim Flammenkamp, First 779674 HCN with sigma,tau,factors
• Online Highly Composite Numbers Calculator