Pillai sekvence - Pillai sequence

The Pillai sekvence je posloupnost celých čísel které mají ve svých chamtivých reprezentacích rekordní počet termínů jako součty prvočísla (a jeden). Je pojmenován po Subbayya Sivasankaranarayana Pillai, který ji poprvé definoval v roce 1930.^[1]

Vyplývá to z Goldbachova domněnka že každé celé číslo větší než jedno lze reprezentovat jako součet nejvýše tří prvočísla. Nalezení takového zastoupení by však mohlo zahrnovat řešení případů problém podmnožiny, což je výpočetně obtížné. Místo toho Pillai považoval následující za jednodušší chamtivý algoritmus pro nalezení zastoupení ${ displaystyle n}$ jako součet prvočísel: vyberte první prvočíslo v součtu jako největší prvočíslo ${ displaystyle p}$ to je nanejvýš ${ displaystyle n}$, a poté rekurzivně sestrojte zbývající část rekurzivně pro ${ displaystyle n-p}$Pokud tento proces dosáhne nuly, zastaví se. A pokud dosáhne jedné místo nuly, musí do součtu zahrnout jednu (i když to není prvočíslo), a pak se zastaví. Například tento algoritmus představuje 122 jako 113 + 7 + 2, i když kratší reprezentace 61 + Možné jsou také 61 nebo 109 + 13.

The ${ displaystyle n}$číslo v Pillai sekvenci je nejmenší číslo, jehož chamtivé vyjádření jako součet prvočísel (a jednoho) vyžaduje ${ displaystyle n}$ podmínky. Tato čísla jsou

0, 1, 4, 27, 1354, 401429925999155061, ... (sekvence A066352 v OEIS )

Každé číslo ${ displaystyle a (n)}$ v pořadí je součet předchozího čísla ${ displaystyle a (n-1)}$ s prvočíslem ${ displaystyle p}$, nejmenší prime jehož následování hlavní mezera je větší než ${ displaystyle a (n-1)}$.^[2] Například číslo 27 v sekvenci je 4 + 23, kde první hlavní mezera větší než 4 je ta mezi 23 a 29.

Protože prvočísla se zmenšují, jak se zvětšují (jak je kvantifikováno pomocí věta o prvočísle ), vždy existuje hlavní mezera větší než kterýkoli člen v Pillai sekvenci, takže posloupnost pokračuje v nekonečném počtu termínů. Termíny v sekvenci však rostou velmi rychle. Odhaduje se, že vyjádření dalšího výrazu v pořadí by vyžadovalo „stovky milionů číslic“.^[3]

Reference