Majdnem prímek

A számelméletben egy természetes szám majdnem prím (almost prime), ha létezik olyan K konstans, hogy a számnak legfeljebb K prímtényezője van.^[1]^[2] Egy n majdnem prímet jelölje P_r, amennyiben n prímtényezőinek száma multiplicitással számolva legfeljebb r.^[3] Egy természetes számot akkor nevezünk k-majdnem prímnek, ha pontosan k prímtényezővel rendelkezik, multiplicitással számolva. Formálisabban, egy n természetes szám akkor és csak akkor k-majdnem prím, ha ν(n) = k, ahol ν(n), azaz nű(n) az n prímtényezős felbontásában található prímek száma, multiplicitással számolva:

\nu (n):=\sum a_{i}\qquad {\mbox{ha}}\qquad n=\prod p_{i}^{a_{i}}.

Egy természetes szám tehát akkor prím, ha 1-majdnem prím és akkor félprím, ha 2-majdnem prím. A k-majdnem prímek halmazát általában P_k jelöli. A legkisebb k-majdnem prím mindig 2^k. Az első néhány k-majdnem prím:

k	k-majdnem prímek	OEIS-sorozat
1	2, 3, 5, 7, 11, 13, 17, 19, …	A000040
2	4, 6, 9, 10, 14, 15, 21, 22, …	A001358
3	8, 12, 18, 20, 27, 28, 30, …	A014612
4	16, 24, 36, 40, 54, 56, 60, …	A014613
5	32, 48, 72, 80, 108, 112, …	A014614
6	64, 96, 144, 160, 216, 224, …	A046306
7	128, 192, 288, 320, 432, 448, …	A046308
8	256, 384, 576, 640, 864, 896, …	A046310
9	512, 768, 1152, 1280, 1728, …	A046312
10	1024, 1536, 2304, 2560, …	A046314
11	2048, 3072, 4608, 5120, …	A069272
12	4096, 6144, 9216, 10240, …	A069273
13	8192, 12288, 18432, 20480, …	A069274
14	16384, 24576, 36864, 40960, …	A069275
15	32768, 49152, 73728, 81920, …	A069276
16	65536, 98304, 147456, …	A069277
17	131072, 196608, 294912, …	A069278
18	262144, 393216, 589824, …	A069279
19	524288, 786432, 1179648, …	A069280
20	1048576, 1572864, 2359296, …	A069281

Az n-nél nem nagyobb, legfeljebb k (nem feltétlenül különböző) prímtényezővel rendelkező π_k(n) egész számok száma aszimptotikusan:^[4]

\pi _{k}(n)\sim \left({\frac {n}{\log n}}\right){\frac {(\log \log n)^{k-1}}{(k-1)!}},

ami Landau eredménye. Lásd még: Hardy–Ramanujan-tétel.

Jegyzetek

↑ Handbook of Number Theory I. Springer, 316. o. (2006). ISBN 978-1-4020-4215-7
↑ Rényi, Alfréd A. (1948). „On the representation of an even number as the sum of a single prime and single almost-prime number” (orosz nyelven). Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 12 (1), 57–78. o.
↑ Heath-Brown, D. R. (1978. május 1.). „Almost-primes in arithmetic progressions and short intervals”. Mathematical Proceedings of the Cambridge Philosophical Society 83 (3), 357–375. o. DOI:10.1017/S0305004100054657.
↑ Tenenbaum, Gerald. Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press (1995. november 24.). ISBN 0-521-41261-7

További információk

Weisstein, Eric W.: Almost prime (angol nyelven). Wolfram MathWorld

[1] Handbook of Number Theory I. Springer, 316. o. (2006). ISBN 978-1-4020-4215-7

[2] Rényi, Alfréd A. (1948). „On the representation of an even number as the sum of a single prime and single almost-prime number” (orosz nyelven). Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 12 (1), 57–78. o.

[3] Heath-Brown, D. R. (1978. május 1.). „Almost-primes in arithmetic progressions and short intervals”. Mathematical Proceedings of the Cambridge Philosophical Society 83 (3), 357–375. o. DOI:10.1017/S0305004100054657.

[4] Tenenbaum, Gerald. Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press (1995. november 24.). ISBN 0-521-41261-7

[1]

[2]

[3]

[4]

Sablon:Prímszámok osztályozása m v sz Prímszámok osztályozása
Képlet alapján	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Dupla Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Faktoriális (n! ± 1) Primoriális (p_n# ± 1) Eukleidész (p_n# + 1) Pitagoraszi (4n + 1) Pierpont (2^u·3^v + 1) Kvartikus prímek (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Köbös (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Szábit (3·2ⁿ ± 1) Mills (floor(A^3ⁿ))
Számsorozat alapján	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partíciók Bell Motzkin
Tulajdonság alapján	Wieferich (pár) Wall–Szun–Szun Wolstenholme Wilson Szerencsés Fortunátus Ramanujan Pillai Regular Erős Stern Szuperszinguláris (elliptikus) Szuperszinguláris (holdfény-elmélet) Jó Szuper Higgs Erősen kotóciens
Számrendszerfüggő	Boldog Diéder Palindrom Mírp Repunit (10ⁿ − 1)/9 Permutálható Körkörös Csonkolható Középpontosan tükrös Minimális Gyenge Full reptend Unikális Primeval Önös Smarandache–Wellin
Mintázatok	Iker (p, p + 2) Ikerprímlánc (n − 1, n + 1, 2n − 1, 2n + 1, …) Prímhármas (p, p + 2 vagy p + 4, p + 6) Prímnégyes (p, p + 2, p + 6, p + 8) prím n−es Unokatestvér (p, p + 4) Szexi (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham-lánc (p, 2p ± 1, …) Biztonságos (p, (p − 1)/2) Számtani sorozatban (p + a·n, n = 0, 1, …) Kiegyensúlyozott (egymást követő p − n, p, p + n)
Méret alapján	Titáni (1000+ számjegy) Gigantikus (10 000+) Mega (1 000 000+) Ismert legnagyobb
Komplex számok	Eisenstein-prím Gauss-prím
Összetett számok	Álprím Erős álprím Majdnem prím Félprím Interprím
Kapcsolódó fogalmak	Valószínű prím Ipari szintű prím Illegális prímszám Prímszámképlet Prímhézag
Az első 100 prím	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
Prímszámok listája