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: Sablon:OEIS

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 Sablon:OEIS.

A Sablon:Szám. 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} \dots 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 \dots \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:

n = p_{1}^{c_{1}} \times p_{2}^{c_{2}} \times \dots \times p_{k}^{c_{k}} (1)

ahol $p_{1} < p_{2} < \dots < 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 \dots \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 \dots \times (c_{k} + 1) . (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 \dots \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^[3]

1, 13862 < lim inf \frac{\log Q (x)}{\log \log x} \leq 1, 44

és

lim sup \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 Sablon:Szám, melynek számjegyösszege 27, ami nem osztója a Sablon:Szám-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 Sablon:OEIS részsorozata a pontosan n osztóval rendelkező legkisebb k számok sorozatának Sablon:OEIS.

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$ .^[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

Fordítás

Sablon:Fordítás

Jegyzetek

Sablon:Reflist

Sablon:Cite journal (online Sablon:Wayback)
Sablon:Cite book
Sablon:Cite journal
Sablon:Cite journal
Sablon:Cite journal Annotated and with a foreword by Jean-Louis Nicolas and Guy Robin.

További információk

Sablon:Osztóosztályok Sablon:Természetes számok

↑ Sablon:Citation. Kahane cites Plato's Laws, 771c.
↑ Sablon:Citation.
↑ Sándor et al (2006) p.45
↑ Sándor et al (2006) p.46
↑ Sablon:Cite journal
↑ Sablon:Citation.

[1] Sablon:Citation. Kahane cites Plato's Laws, 771c.

[2] Sablon:Citation.

[HBI45-3] Sándor et al (2006) p.45

[HNTI46-4] Sándor et al (2006) p.46

[Nic79-5] Sablon:Cite journal

[6] Sablon:Citation.

[1]

[2]

[3]

[4]

[5]

[6]

Erősen összetett számok

Tartalomjegyzék

Példák

Prímtényezős felbontás

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

Kapcsolódó sorozatok

Kapcsolódó szócikkek

Fordítás

Jegyzetek

További információk

Navigációs menü

Erősen összetett számok

Példák

Prímtényezős felbontás

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

Kapcsolódó sorozatok

Kapcsolódó szócikkek

Fordítás

Jegyzetek

További információk

Navigációs menü

Keresés