词条 | Integer complexity |
释义 |
In number theory, the integer complexity of an integer is the smallest number of ones that can be used to represent it using ones and any number of additions, multiplications, and parentheses. It is always within a constant factor of the logarithm of the given integer. ExampleFor instance, the number 11 may be represented using eight ones: 11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1. However, it has no representation using seven or fewer ones. Therefore, its complexity is eight. The complexities of the numbers 1, 2, 3, ... are 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... {{OEIS| A005245}} The smallest numbers with complexity 1, 2, 3, ... are 1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... {{OEIS|A005520}} Upper and lower boundsThe question of expressing integers in this way was originally considered by {{harvtxt|Mahler|Popken|1953}}. They asked for the largest number with a given complexity {{mvar|k}};[1] later, Selfridge showed that this number is For example, when {{math|1=k = 10}}, {{math|1=x = 2}} and the largest integer that can be expressed using ten ones is {{math|1=2{{sup|2}}{{hsp}}3{{sup|2}} = 36}}. Its expression is (1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1). Thus, the complexity of an integer {{mvar|n}} is at least {{math|3{{hsp}}log{{sub|3}}{{hsp}}n}}. The complexity of {{mvar|n}} is at most {{math|3{{hsp}}log{{sub|2}}{{hsp}}n}} (approximately {{math|4.755{{hsp}}log{{sub|3}}{{hsp}}n}}): an expression of this length for {{mvar|n}} can be found by applying Horner's method to the binary representation of {{mvar|n}}.[2] Almost all integers have a representation whose length is bounded by a logarithm with a smaller constant factor, {{math|3.529{{hsp}}log{{sub|3}}{{hsp}}n}}.[3] Algorithms and counterexamplesThe complexities of all integers up to some threshold {{mvar|N}} can be calculated in total time {{math|O(N{{sup|1.222911236}})}}.[4] Algorithms for computing the integer complexity have been used to disprove several conjectures about the complexity. In particular, it is not necessarily the case that the optimal expression for a number {{mvar|n}} is obtained either by subtracting one from {{mvar|n}} or by expressing {{mvar|n}} as the product of two smaller factors. The smallest example of a number whose optimal expression is not of this form is 353942783. It is a prime number, and therefore also disproves a conjecture of Richard K. Guy that the complexity of every prime number {{mvar|p}} is one plus the complexity of {{math|p − 1}}.[5] References1. ^{{citation | last1 = Mahler | first1 = K. | author1-link = Kurt Mahler | last2 = Popken | first2 = J. | journal = Nieuw Archief voor Wiskunde | mr = 0053986 | pages = 1–15 | title = On a maximum problem in arithmetic | volume = 1 | year = 1953}}. 2. ^{{citation | last = Guy | first = Richard K. | authorlink = Richard K. Guy | department = Unsolved Problems | doi = 10.2307/2323338 | issue = 3 | journal = American Mathematical Monthly | mr = 1540817 | pages = 186–190 | title = Some suspiciously simple sequences | volume = 93 | year = 1986}}. 3. ^{{citation|first=Christopher E.|last=Shriver|year=2015|title=Applications of Markov chain analysis to integer complexity|arxiv=1511.07842|bibcode=2015arXiv151107842S}}. 4. ^{{citation|first1=K.|last=Cordwell|first2=A.|last2=Epstein|first3=A.|last3=Hemmady|first4=S.|last4=Miller|first5=E.|last5=Palsson|first6=A.|last6=Sharma|first7=S.|last7=Steinerberger|first8=Y.|last8=Vu|title=On algorithms to calculate integer complexity|year=2017|arxiv=1706.08424|bibcode=2017arXiv170608424C}} 5. ^{{citation|url=https://oeis.org/A005245/a005245.c.txt|title=Program to calculate A005245, A005520, A005421|first=Martin N.|last=Fuller|date=February 1, 2008|publisher=OEIS|accessdate=2015-12-13}}. External links
1 : Integer sequences |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。