Složitost celého čísla - Integer complexity - Wikipedia

v teorie čísel, celočíselná složitost z celé číslo je nejmenší počet ty které lze použít k reprezentaci pomocí jednotek a libovolného počtu dodatky, násobení a závorky. Je to vždy v konstantním faktoru logaritmus daného celého čísla.

Příklad

Například číslo 11 může být reprezentováno pomocí osmi:

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

Nemá však žádné zastoupení pomocí sedmi nebo méně. Proto je jeho složitost osm.

Složitost čísel 1, 2, 3, ... je

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... (sekvence A005245 v OEIS )

Nejmenší čísla se složitostí 1, 2, 3, ... jsou

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (sekvence A005520 v OEIS )

Horní a dolní mez

Otázku vyjádření celých čísel tímto způsobem původně zvažoval Mahler & Popken (1953). Požádali o největší počet s danou složitostí $k$ ;^[1] později Selfridge ukázal, že toto číslo je

{ displaystyle 2 ^ {x} 3 ^ {(k-2x) / 3} { text {kde}} x = -k { bmod {3}}.}

Například když $k = 10$ , $X = 2$ a největší celé číslo, které lze vyjádřit pomocí deseti, je $2232 = 36$ . Jeho výraz je

(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).

Složitost celého čísla $n$ je alespoň $3 log 3 n$ . Složitost $n$ je nanejvýš $3 log 2 n$ (přibližně $4,755 log 3 n$ ): výraz této délky pro $n$ lze nalézt přihlášením Hornerova metoda do binární reprezentace z $n$ .^[2] Téměř všechna celá čísla mají reprezentaci, jejíž délka je omezena logaritmem s menším konstantním faktorem, $3,529 log 3 n$ .^[3]

Algoritmy a protipříklady

Složitost všech celých čísel až do určité prahové hodnoty $N$ lze vypočítat za celkový čas $Ó (N 1.222911236)$ .^[4]

Algoritmy pro výpočet celočíselné složitosti byly použity k vyvrácení několika domněnek o složitosti. Zejména nemusí nutně platit, že optimální výraz pro číslo $n$ se získá buď odečtením jednoho z $n$ nebo vyjádřením $n$ jako produkt dvou menších faktorů. Nejmenší příklad čísla, jehož optimální výraz nemá tento tvar, je 353942783. Je to a prvočíslo, a proto také vyvrací domněnku o Richard K. Guy že složitost každého prvočísla $p$ je jedna plus složitost $p - 1$ .^[5]

Reference

^ Mahler, K.; Popken, J. (1953), „O maximálním problému v aritmetice“, Nieuw Archief voor Wiskunde, 1: 1–15, PAN 0053986.
^ Guy, Richard K. (1986), „Některé podezřele jednoduché sekvence“, Nevyřešené problémy, Americký matematický měsíčník, 93 (3): 186–190, doi:10.2307/2323338, PAN 1540817.
^ Shriver, Christopher E. (2015), Aplikace Markovovy řetězové analýzy na celočíselnou složitost, arXiv:1511.07842, Bibcode:2015arXiv151107842S.
^ Cordwell, K .; Epstein, A .; Hemmady, A .; Miller, S .; Palsson, E .; Sharma, A .; Steinerberger, S .; Vu, Y. (2017), Na algoritmech pro výpočet složitosti celého čísla, arXiv:1706.08424, Bibcode:2017arXiv170608424C
^ Fuller, Martin N. (1. února 2008), Program pro výpočet A005245, A005520, A005421, OEIS, vyvoláno 2015-12-13.

externí odkazy

Weisstein, Eric W. „Složitost celého čísla“. MathWorld.

[1] Mahler, K.; Popken, J. (1953), „O maximálním problému v aritmetice“, Nieuw Archief voor Wiskunde, 1: 1–15, PAN 0053986.

[guy-2] Guy, Richard K. (1986), „Některé podezřele jednoduché sekvence“, Nevyřešené problémy, Americký matematický měsíčník, 93 (3): 186–190, doi:10.2307/2323338, PAN 1540817.

[3] Shriver, Christopher E. (2015), Aplikace Markovovy řetězové analýzy na celočíselnou složitost, arXiv:1511.07842, Bibcode:2015arXiv151107842S.

[4] Cordwell, K .; Epstein, A .; Hemmady, A .; Miller, S .; Palsson, E .; Sharma, A .; Steinerberger, S .; Vu, Y. (2017), Na algoritmech pro výpočet složitosti celého čísla, arXiv:1706.08424, Bibcode:2017arXiv170608424C

[5] Fuller, Martin N. (1. února 2008), Program pro výpočet A005245, A005520, A005421, OEIS, vyvoláno 2015-12-13.

[1]

[2]

[3]

[4]

[5]