Golombova sekvence - Golomb sequence

V matematice je Golombova sekvence, pojmenoval podle Solomon W. Golomb (ale také volal Silvermanova sekvence), je neklesající celočíselná sekvence kde A_n je počet opakování n se vyskytuje v pořadí počínaje A₁ = 1, a s vlastností, která pro n > Každý 1 A_n je nejmenší jedinečné celé číslo, které umožňuje splnit podmínku. Například, A₁ = 1 říká, že 1 se vyskytuje pouze jednou v pořadí, takže A₂ nemůže být také 1, ale může být, a proto musí být, 2. Prvních několik hodnot je

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12 (sekvence A001462 v OEIS ).

Příklady

A₁ = 1
Proto se 1 v této sekvenci vyskytuje přesně jednou.

A₂ > 1
A₂ = 2

2 se vyskytuje přesně dvakrát v této sekvenci.
A₃ = 2

3 se vyskytuje přesně dvakrát v této sekvenci.

A₄ = A₅ = 3

4 se vyskytuje přesně 3krát v tomto pořadí.
5 se vyskytuje přesně 3krát v tomto pořadí.

A₆ = A₇ = A₈ = 4
A₉ = A₁₀ = A₁₁ = 5

atd.

Opakování

Colin Mallows uvedl výslovně relace opakování ${ displaystyle a (1) = 1; a (n + 1) = 1 + a (n + 1-a (a (n)))}$. An asymptotický výraz pro A_n je

${ displaystyle varphi ^ {2- varphi} n ^ { varphi -1},}$

kde ${ displaystyle varphi}$ je Zlatý řez (přibližně 1,618034).

Reference

• Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Sekvence opakování. Matematické průzkumy a monografie. 104. Providence, RI: Americká matematická společnost. 10, 256. ISBN  0-8218-3387-1. Zbl  1033.11006.
• Guy, Richard K. (2004). Nevyřešené problémy v teorii čísel (3. vyd.). Springer-Verlag. Sekce E25. ISBN  0-387-20860-7. Zbl  1058.11001.

externí odkazy

• Pythonský kód pro Golomb Sequence