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.

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	$2$	1	1	2	$2$
3	4	$2^{2}$	2	2	3	$2^{2}$
4*	6	$2\cdot 3$	1,1	2	4	$6$
5*	12	$2^{2}\cdot 3$	2,1	3	6	$2\cdot 6$
6	24	$2^{3}\cdot 3$	3,1	4	8	$2^{2}\cdot 6$
7	36	$2^{2}\cdot 3^{2}$	2,2	4	9	$6^{2}$
8	48	$2^{4}\cdot 3$	4,1	5	10	$2^{3}\cdot 6$
9*	60	$2^{2}\cdot 3\cdot 5$	2,1,1	4	12	$2\cdot 30$
10*	120	$2^{3}\cdot 3\cdot 5$	3,1,1	5	16	$2^{2}\cdot 30$
11	180	$2^{2}\cdot 3^{2}\cdot 5$	2,2,1	5	18	$6\cdot 30$
12	240	$2^{4}\cdot 3\cdot 5$	4,1,1	6	20	$2^{3}\cdot 30$
13*	360	$2^{3}\cdot 3^{2}\cdot 5$	3,2,1	6	24	$2\cdot 6\cdot 30$
14	720	$2^{4}\cdot 3^{2}\cdot 5$	4,2,1	7	30	$2^{2}\cdot 6\cdot 30$
15	840	$2^{3}\cdot 3\cdot 5\cdot 7$	3,1,1,1	6	32	$2^{2}\cdot 210$
16	1260	$2^{2}\cdot 3^{2}\cdot 5\cdot 7$	2,2,1,1	6	36	$6\cdot 210$
17	1680	$2^{4}\cdot 3\cdot 5\cdot 7$	4,1,1,1	7	40	$2^{3}\cdot 210$
18*	2520	$2^{3}\cdot 3^{2}\cdot 5\cdot 7$	3,2,1,1	7	48	$2\cdot 6\cdot 210$
19*	5040	$2^{4}\cdot 3^{2}\cdot 5\cdot 7$	4,2,1,1	8	60	$2^{2}\cdot 6\cdot 210$
20	7560	$2^{3}\cdot 3^{3}\cdot 5\cdot 7$	3,3,1,1	8	64	$6^{2}\cdot 210$
21	10080	$2^{5}\cdot 3^{2}\cdot 5\cdot 7$	5,2,1,1	9	72	$2^{3}\cdot 6\cdot 210$
22	15120	$2^{4}\cdot 3^{3}\cdot 5\cdot 7$	4,3,1,1	9	80	$2\cdot 6^{2}\cdot 210$
23	20160	$2^{6}\cdot 3^{2}\cdot 5\cdot 7$	6,2,1,1	10	84	$2^{4}\cdot 6\cdot 210$
24	25200	$2^{4}\cdot 3^{2}\cdot 5^{2}\cdot 7$	4,2,2,1	9	90	$2^{2}\cdot 30\cdot 210$
25	27720	$2^{3}\cdot 3^{2}\cdot 5\cdot 7\cdot 11$	3,2,1,1,1	8	96	$2\cdot 6\cdot 2310$
26	45360	$2^{4}\cdot 3^{4}\cdot 5\cdot 7$	4,4,1,1	10	100	$6^{3}\cdot 210$
27	50400	$2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7$	5,2,2,1	10	108	$2^{3}\cdot 30\cdot 210$
28*	55440	$2^{4}\cdot 3^{2}\cdot 5\cdot 7\cdot 11$	4,2,1,1,1	9	120	$2^{2}\cdot 6\cdot 2310$
29	83160	$2^{3}\cdot 3^{3}\cdot 5\cdot 7\cdot 11$	3,3,1,1,1	9	128	$6^{2}\cdot 2310$
30	110880	$2^{5}\cdot 3^{2}\cdot 5\cdot 7\cdot 11$	5,2,1,1,1	10	144	$2^{3}\cdot 6\cdot 2310$
31	166320	$2^{4}\cdot 3^{3}\cdot 5\cdot 7\cdot 11$	4,3,1,1,1	10	160	$2\cdot 6^{2}\cdot 2310$
32	221760	$2^{6}\cdot 3^{2}\cdot 5\cdot 7\cdot 11$	6,2,1,1,1	11	168	$2^{4}\cdot 6\cdot 2310$
33	277200	$2^{4}\cdot 3^{2}\cdot 5^{2}\cdot 7\cdot 11$	4,2,2,1,1	10	180	$2^{2}\cdot 30\cdot 2310$
34	332640	$2^{5}\cdot 3^{3}\cdot 5\cdot 7\cdot 11$	5,3,1,1,1	11	192	$2^{2}\cdot 6^{2}\cdot 2310$
35	498960	$2^{4}\cdot 3^{4}\cdot 5\cdot 7\cdot 11$	4,4,1,1,1	11	200	$6^{3}\cdot 2310$
36	554400	$2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7\cdot 11$	5,2,2,1,1	11	216	$2^{3}\cdot 30\cdot 2310$
37	665280	$2^{6}\cdot 3^{3}\cdot 5\cdot 7\cdot 11$	6,3,1,1,1	12	224	$2^{3}\cdot 6^{2}\cdot 2310$
38*	720720	$2^{4}\cdot 3^{2}\cdot 5\cdot 7\cdot 11\cdot 13$	4,2,1,1,1,1	10	240	$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:

$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 $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 $2^{14}\times 3^{9}\times 5^{6}\times \cdots \times 1451$).

Az 1–1000 közötti egész számok osztóinak száma. Az első 15 erősen összetett szám félkövéren látható.

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:

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

ahol $p_{1}<p_{2}<\cdots <p_{k}$ prímszámok, a $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:

$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:

$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 $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

$\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

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

és

$\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

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

egyenlőtlenségnek minden pozitív c,d-re, amennyiben $0,2\leq c\leq d\leq 0,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. 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)
• 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