Problémy spojené s aritmetickými průběhy - Problems involving arithmetic progressions
Problémy spojené aritmetické průběhy jsou předmětem zájmu teorie čísel,[1] kombinatorika, a počítačová věda, a to jak z teoretického, tak z aplikovaného hlediska.
Největší podmnožiny bez progrese
Najděte mohutnost (označenou Ak(m)) největší podskupiny z {1, 2, ...,m} který neobsahuje žádný průběh k odlišné termíny. Prvky zakázaných postupů nemusí být po sobě následující.
Například, A4(10) = 8, protože {1, 2, 3, 5, 6, 8, 9, 10} nemá žádné aritmetické posloupnosti délky 4, zatímco všechny podskupiny 9 prvků {1, 2, ..., 10} mít jeden. Paul Erdős nastavit cenu 1 000 $ za otázku týkající se tohoto čísla, kterou sbírá Endre Szemerédi protože to, co se stalo známé jako Szemerédiho věta.
Aritmetické průběhy z prvočísel
Szemerédiho věta uvádí, že soubor přirozená čísla nenulové horní asymptotická hustota obsahuje konečné aritmetické průběhy libovolné délky k.
Erdős udělal obecnější domněnka z čehož by to vyplývalo
- Posloupnost čísel prvočísel obsahuje aritmetické průběhy libovolné délky.
Tento výsledek prokázal Ben Green a Terence Tao v roce 2004 a nyní je známá jako Věta o Green-Tao.[2]
Viz také Dirichletova věta o aritmetických postupech.
Od roku 2020[Aktualizace], nejdelší známý aritmetický postup prvočísel má délku 27:[3]
- 224584605939537911 + 81292139·23#·n, pro n = 0 až 26. (23# = 223092870 )
Od roku 2011 je nejdelší známý aritmetický průběh po sobě prvočísla má délku 10. Bylo nalezeno v roce 1998.[4][5] Postup začíná 93místným číslem
- 100 99697 24697 14247 63778 66555 87969 84032 95093 24689
- 19004 18036 03417 75890 43417 03348 88215 90672 29719
a má společný rozdíl 210.
Zdroj o domněnce Erdős-Turán z roku 1936:
- P. Erdős a P. Turán, O některých sekvencích celých čísel, J. London Math. Soc. 11 (1936), 261–264.
Připraví v aritmetických postupech
Věta o prvočísle pro aritmetické posloupnosti se zabývá asymptotické rozdělení prvočísel v aritmetické posloupnosti.
Pokrytí a rozdělení do aritmetických průběhů
- Najít minimální ln taková, že jakákoli sada n zbytky modulo str může být pokryta aritmetickým postupem délky ln.[6]
- Pro danou sadu S celých čísel najít minimální počet aritmetických postupů, které pokrývají S
- Pro danou sadu S celých čísel najít minimální počet nepřekrývajících se aritmetických postupů, které pokrývají S
- Najděte počet způsobů rozdělení oddílů {1, ...,n} do aritmetických průběhů.[7]
- Najděte počet způsobů rozdělení oddílů {1, ...,n} do aritmetických průběhů délky alespoň 2 se stejnou periodou.[8]
- Viz také Krycí systém
Viz také
Poznámky
- ^ Samuel S. Wagstaff, Jr. (1979). "Několik otázek týkajících se aritmetických průběhů". Americký matematický měsíčník. Mathematical Association of America. 86 (7): 579–582. doi:10.2307/2320590. JSTOR 2320590.
- ^ Weisstein, Eric W. „Prime Arithmetic Progression“. MathWorld.
- ^ Jens Kruse Andersen, Připraví se v aritmetických záznamech o postupu. Citováno 2020-08-10.
- ^ H. Dubner; T. Forbes; N. Lygeros; M. Mizony; H. Nelson; P. Zimmermann, „Deset po sobě jdoucích prvočísel v aritmetickém postupu“, Math. Comp. 71 (2002), 1323–1328.
- ^ projekt Devět a deset prvočísel
- ^ Vsevolod F. Lev (2000). "Simultánní aproximace a pokrytí aritmetickým postupem přes Fstr". Journal of Combinatorial Theory, Series A. 92 (2): 103–118. doi:10.1006 / jcta.1999.3034.
- ^ Sloane, N. J. A. (vyd.). "Pořadí A053732 (Počet způsobů rozdělení {1, ..., n} na aritmetické posloupnosti délky> = 1)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.
- ^ Sloane, N. J. A. (vyd.). "Pořadí A072255 (Počet způsobů rozdělení {1,2, ..., n} do aritmetických průběhů ...)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.