|
|
| (One intermediate revision by the same user not shown) |
| Line 1: |
Line 1: |
| − | [[Category:Complexity]] | + | #REDIRECT [[Integer_Complexity]] |
| − | The complexity of a natural number ''n'' is the minimum number of ones required to write an arithmetic expression for ''n'' using ones, addition, multiplication and parentheses. It is denoted by <math>\left\| n \right\|</math>. The integer complexity has a corresponding sequence in The On-Line Encyclopedia of Integer Sequences: [http://oeis.org/A005245 A005245]. Jānis Iraids has calculated the sequence up to <math>n=10^{12}</math> and the data is available in an [[Special:Complexity|interactive form]].
| |
| − | | |
| − | Equivalently,
| |
| − | :<math>\left\| n \right\| = \min_{a+b = n \vee a\cdot b = n} {(\left\| a \right\| + \left\| b \right\|)}</math>.
| |
| − | | |
| − | ==Logarithmic complexity==
| |
| − | Since the integer complexity of ''n'' is bounded by <math>c\cdot\log_3{n}</math>, the logarithmic complexity <math>\left\| n \right\|_{log} = \frac{\left\| n \right\|}{\log_3 {n}}</math> is of interest as a sort of efficiency measure of ''n''.
| |
| − | | |
| − | ==Distribution of logarithmic complexity==
| |
| − | [[File:Distribution plots.gif|right|thumb|200px|alt=Graphs of distribution of logarithmic complexity.|Logarithmic complexity distribution for numbers of equal complexity.]]
| |
| − | | |
| − | ===The "best" numbers===
| |
| − | The numbers on the left side of the logarithmic complexity distribution curves are simple and their expressions are known. These numbers are also known as sequence [http://oeis.org/A000792 A000792] on The On-Line Encyclopedia of Integer Sequences.
| |
| − | | |
| − | ===The "worst" numbers===
| |
| − | The numbers represented on the right side of the logarithmic complexity distribution curves are more complex. The number represented by the rightmost nonzero column is the smallest number of the given complexity. These numbers are also known as sequence [http://oeis.org/A005520 A005520] on The On-Line Encyclopedia of Integer Sequences.
| |
| − | | |
| − | It has been conjectured that starting from the 26th all these numbers are primes.
| |
| − | | |
| − | ==Some numerical data==
| |
| − | | |
| − | This table summarizes what is known about the "best" and "worst" numbers as well as the distribution of numbers of equal complexity.
| |
| − | | |
| − | {| class="wikitable sortable" style="width:70%"
| |
| − | |-
| |
| − | !<math>n</math>||[http://oeis.org/A005520 A005520](n)||<math>\left\|A005520(n)\right\|_{\log}</math>||PrimeQ[A005520(n)]||<math>\underset{m}{\operatorname{max}} \, \{m | A005520(n) \equiv -1 \pmod{m!}\}</math>||[http://oeis.org/A000792 A000792](n)||[http://oeis.org/A133374 A133374](n)||[http://oeis.org/A005421 A005421](n)
| |
| − | |-
| |
| − | |1||[[Special:Complexity?n=1|1]]||-||False||2||[[Special:Complexity?n=1|1]]||0||1
| |
| − | |-
| |
| − | |2||[[Special:Complexity?n=2|2]]||3.17||True||0||[[Special:Complexity?n=2|2]]||0||1
| |
| − | |-
| |
| − | |3||[[Special:Complexity?n=3|3]]||3.00||True||2||[[Special:Complexity?n=3|3]]||0||1
| |
| − | |-
| |
| − | |4||[[Special:Complexity?n=4|4]]||3.17||False||0||[[Special:Complexity?n=4|4]]||0||1
| |
| − | |-
| |
| − | |5||[[Special:Complexity?n=5|5]]||3.41||True||3||[[Special:Complexity?n=6|6]]||1||2
| |
| − | |-
| |
| − | |6||[[Special:Complexity?n=7|7]]||3.39||True||2||[[Special:Complexity?n=9|9]]||2||3
| |
| − | |-
| |
| − | |7||[[Special:Complexity?n=10|10]]||3.34||False||0||[[Special:Complexity?n=12|12]]||2||2
| |
| − | |-
| |
| − | |8||[[Special:Complexity?n=11|11]]||3.67||True||3||[[Special:Complexity?n=18|18]]||7||6
| |
| − | |-
| |
| − | |9||[[Special:Complexity?n=17|17]]||3.49||True||3||[[Special:Complexity?n=27|27]]||10||6
| |
| − | |-
| |
| − | |10||[[Special:Complexity?n=22|22]]||3.55||False||0||[[Special:Complexity?n=36|36]]||14||7
| |
| − | |-
| |
| − | |11||[[Special:Complexity?n=23|23]]||3.85||True||4||[[Special:Complexity?n=54|54]]||31||14
| |
| − | |-
| |
| − | |12||[[Special:Complexity?n=41|41]]||3.55||True||3||[[Special:Complexity?n=81|81]]||40||16
| |
| − | |-
| |
| − | |13||[[Special:Complexity?n=47|47]]||3.71||True||4||[[Special:Complexity?n=108|108]]||61||20
| |
| − | |-
| |
| − | |14||[[Special:Complexity?n=59|59]]||3.77||True||3||[[Special:Complexity?n=162|162]]||103||34
| |
| − | |-
| |
| − | |15||[[Special:Complexity?n=89|89]]||3.67||True||3||[[Special:Complexity?n=243|243]]||154||42
| |
| − | |-
| |
| − | |16||[[Special:Complexity?n=107|107]]||3.76||True||3||[[Special:Complexity?n=324|324]]||217||56
| |
| − | |-
| |
| − | |17||[[Special:Complexity?n=167|167]]||3.65||True||4||[[Special:Complexity?n=486|486]]||319||84
| |
| − | |-
| |
| − | |18||[[Special:Complexity?n=179|179]]||3.81||True||3||[[Special:Complexity?n=729|729]]||550||108
| |
| − | |-
| |
| − | |19||[[Special:Complexity?n=263|263]]||3.75||True||4||[[Special:Complexity?n=972|972]]||709||152
| |
| − | |-
| |
| − | |20||[[Special:Complexity?n=347|347]]||3.76||True||3||[[Special:Complexity?n=1458|1458]]||1111||214
| |
| − | |-
| |
| − | |21||[[Special:Complexity?n=467|467]]||3.75||True||3||[[Special:Complexity?n=2187|2187]]||1720||295
| |
| − | |-
| |
| − | |22||[[Special:Complexity?n=683|683]]||3.70||True||3||[[Special:Complexity?n=2916|2916]]||2233||398
| |
| − | |-
| |
| − | |23||[[Special:Complexity?n=719|719]]||3.84||True||6||[[Special:Complexity?n=4374|4374]]||3655||569
| |
| − | |-
| |
| − | |24||[[Special:Complexity?n=1223|1223]]||3.71||True||4||[[Special:Complexity?n=6561|6561]]||5338||763
| |
| − | |-
| |
| − | |25||[[Special:Complexity?n=1438|1438]]||3.78||False||0||[[Special:Complexity?n=8748|8748]]||7310||1094
| |
| − | |-
| |
| − | |26||[[Special:Complexity?n=1439|1439]]||3.93||True||6||[[Special:Complexity?n=13122|13122]]||11683||1475
| |
| − | |-
| |
| − | |27||[[Special:Complexity?n=2879|2879]]||3.72||True||6||[[Special:Complexity?n=19683|19683]]||16804||2058
| |
| − | |-
| |
| − | |28||[[Special:Complexity?n=3767|3767]]||3.74||True||4||[[Special:Complexity?n=26244|26244]]||22477||2878
| |
| − | |-
| |
| − | |29||[[Special:Complexity?n=4283|4283]]||3.81||True||3||[[Special:Complexity?n=39366|39366]]||35083||3929
| |
| − | |-
| |
| − | |30||[[Special:Complexity?n=6299|6299]]||3.77||True||3||[[Special:Complexity?n=59049|59049]]||52750||5493
| |
| − | |-
| |
| − | |31||[[Special:Complexity?n=10079|10079]]||3.69||True||7||[[Special:Complexity?n=78732|78732]]||68653||7669
| |
| − | |-
| |
| − | |32||[[Special:Complexity?n=11807|11807]]||3.75||True||4||[[Special:Complexity?n=118098|118098]]||106291||10501
| |
| − | |-
| |
| − | |33||[[Special:Complexity?n=15287|15287]]||3.76||True||4||[[Special:Complexity?n=177147|177147]]||161860||14707
| |
| − | |-
| |
| − | |34||[[Special:Complexity?n=21599|21599]]||3.74||True||6||[[Special:Complexity?n=236196|236196]]||214597||20476
| |
| − | |-
| |
| − | |35||[[Special:Complexity?n=33599|33599]]||3.69||True||5||[[Special:Complexity?n=354294|354294]]||320695||28226
| |
| − | |-
| |
| − | |36||[[Special:Complexity?n=45197|45197]]||3.69||True||3||[[Special:Complexity?n=531441|531441]]||486244||39287
| |
| − | |-
| |
| − | |37||[[Special:Complexity?n=56039|56039]]||3.72||True||5||[[Special:Complexity?n=708588|708588]]||652549||54817
| |
| − | |-
| |
| − | |38||[[Special:Complexity?n=81647|81647]]||3.69||True||4||[[Special:Complexity?n=1062882|1062882]]||981235||75619
| |
| − | |-
| |
| − | |39||[[Special:Complexity?n=98999|98999]]||3.72||True||5||[[Special:Complexity?n=1594323|1594323]]||1495324||105584
| |
| − | |-
| |
| − | |40||[[Special:Complexity?n=163259|163259]]||3.66||True||3||[[Special:Complexity?n=2125764|2125764]]||1962505||146910
| |
| − | |-
| |
| − | |41||[[Special:Complexity?n=203999|203999]]||3.68||True||5||[[Special:Complexity?n=3188646|3188646]]||2984647||203294
| |
| − | |-
| |
| − | |42||[[Special:Complexity?n=241883|241883]]||3.72||True||3||[[Special:Complexity?n=4782969|4782969]]||4541086||283764
| |
| − | |-
| |
| − | |43||[[Special:Complexity?n=371447|371447]]||3.68||True||4||[[Special:Complexity?n=6377292|6377292]]||6005845||394437
| |
| − | |-
| |
| − | |44||[[Special:Complexity?n=540539|540539]]||3.66||True||3||[[Special:Complexity?n=9565938|9565938]]||9025399||547485
| |
| − | |-
| |
| − | |45||[[Special:Complexity?n=590399|590399]]||3.72||True||6||[[Special:Complexity?n=14348907|14348907]]||13758508||763821
| |
| − | |-
| |
| − | |46||[[Special:Complexity?n=907199|907199]]||3.68||True||7||[[Special:Complexity?n=19131876|19131876]]||18224677||1061367
| |
| − | |-
| |
| − | |47||[[Special:Complexity?n=1081079|1081079]]||3.72||True||5||[[Special:Complexity?n=28697814|28697814]]||27616735||1476067
| |
| − | |-
| |
| − | |48||[[Special:Complexity?n=1851119|1851119]]||3.65||True||6||[[Special:Complexity?n=43046721|43046721]]||41195602||2057708
| |
| − | |-
| |
| − | |49||[[Special:Complexity?n=2041199|2041199]]||3.71||True||7||[[Special:Complexity?n=57395628|57395628]]||55354429||2861449
| |
| − | |-
| |
| − | |50||[[Special:Complexity?n=3243239|3243239]]||3.66||True||5||[[Special:Complexity?n=86093442|86093442]]||82850203||3982054
| |
| − | |-
| |
| − | |51||[[Special:Complexity?n=3840479|3840479]]||3.70||True||7||[[Special:Complexity?n=129140163|129140163]]||125299684||5552628
| |
| − | |-
| |
| − | |52||[[Special:Complexity?n=6562079|6562079]]||3.64||True||7||[[Special:Complexity?n=172186884|172186884]]||165624805||7721319
| |
| − | |-
| |
| − | |53||[[Special:Complexity?n=8206559|8206559]]||3.66||True||6||[[Special:Complexity?n=258280326|258280326]]||250073767||10758388
| |
| − | |-
| |
| − | |54||[[Special:Complexity?n=11696759|11696759]]||3.65||True||5||[[Special:Complexity?n=387420489|387420489]]||375723730||14994291
| |
| − | |-
| |
| − | |55||[[Special:Complexity?n=14648759|14648759]]||3.66||True||5||[[Special:Complexity?n=516560652|516560652]]||501911893||20866891
| |
| − | |-
| |
| − | |56||[[Special:Complexity?n=22312799|22312799]]||3.64||True||6||[[Special:Complexity?n=774840978|774840978]]||752528179||29079672
| |
| − | |-
| |
| − | |57||[[Special:Complexity?n=27494879|27494879]]||3.66||True||5||[[Special:Complexity?n=1162261467|1162261467]]||1134766588||40534895
| |
| − | |-
| |
| − | |58||[[Special:Complexity?n=41746319|41746319]]||3.63||True||7||[[Special:Complexity?n=1549681956|1549681956]]||1507935637||56439467
| |
| − | |-
| |
| − | |59||[[Special:Complexity?n=52252199|52252199]]||3.65||True||5||[[Special:Complexity?n=2324522934|2324522934]]||2272270735||78684930
| |
| − | |-
| |
| − | |60||[[Special:Complexity?n=78331679|78331679]]||3.63||True||7||[[Special:Complexity?n=3486784401|3486784401]]||3408452722||109675955
| |
| − | |-
| |
| − | |61||[[Special:Complexity?n=108606959|108606959]]||3.62||True||7||[[Special:Complexity?n=4649045868|4649045868]]||4540438909||152788554
| |
| − | |-
| |
| − | |62||[[Special:Complexity?n=142990559|142990559]]||3.63||True||6||[[Special:Complexity?n=6973568802|6973568802]]||6830578243||213072724
| |
| − | |-
| |
| − | |63||[[Special:Complexity?n=203098319|203098319]]||3.62||True||6||[[Special:Complexity?n=10460353203|10460353203]]||10257254884||297002458
| |
| − | |-
| |
| − | |64||[[Special:Complexity?n=273985919|273985919]]||3.62||True||6||[[Special:Complexity?n=13947137604|13947137604]]||13673151685||413944635
| |
| − | |-
| |
| − | |65||[[Special:Complexity?n=382021919|382021919]]||3.61||True||7||[[Special:Complexity?n=20920706406|20920706406]]||20538684487||577354385
| |
| − | |-
| |
| − | |66||[[Special:Complexity?n=495437039|495437039]]||3.62||True||7||[[Special:Complexity?n=31381059609|31381059609]]||30885622570||804919055
| |
| − | |-
| |
| − | |67||[[Special:Complexity?n=681327359|681327359]]||3.62||True||8||[[Special:Complexity?n=41841412812|41841412812]]||41160085453||1122274894
| |
| − | |-
| |
| − | |68||[[Special:Complexity?n=1006290359|1006290359]]||3.60||True||5||[[Special:Complexity?n=62762119218|62762119218]]||61755828859||1565492145
| |
| − | |-
| |
| − | |69||[[Special:Complexity?n=1406394359|1406394359]]||3.60||True||5||[[Special:Complexity?n=94143178827|94143178827]]||92736784468||2182968270
| |
| − | |-
| |
| − | |70||[[Special:Complexity?n=1857794399|1857794399]]||3.60||True||7||[[Special:Complexity?n=125524238436|125524238436]]||123666444037||3044509482
| |
| − | |-
| |
| − | |71||[[Special:Complexity?n=2728424159|2728424159]]||3.59||True||7||[[Special:Complexity?n=188286357654|188286357654]]||185557933495||4247469161
| |
| − | |-
| |
| − | |72||[[Special:Complexity?n=3743197919|3743197919]]||3.59||True||7||[[Special:Complexity?n=282429536481|282429536481]]||278686338562||5923889964
| |
| − | |-
| |
| − | |73||[[Special:Complexity?n=5008227839|5008227839]]||3.59||True||8||[[Special:Complexity?n=376572715308|376572715308]]||371564487469||8263996299
| |
| − | |-
| |
| − | |74||[[Special:Complexity?n=6872690159|6872690159]]||3.59||True||7||[[Special:Complexity?n=564859072962|564859072962]]||557986382803||11530495182
| |
| − | |-
| |
| − | |75||[[Special:Complexity?n=9839491199|9839491199]]||3.58||True||9||[[Special:Complexity?n=847288609443|847288609443]]||837449118244||16084845369
| |
| − | |-
| |
| − | |76||[[Special:Complexity?n=13485479039|13485479039]]||3.58||True||6||[[Special:Complexity?n=1129718145924|1129718145924]]||1116232666885||-
| |
| − | |-
| |
| − | |77||[[Special:Complexity?n=16724776319|16724776319]]||3.59||True||9||[[Special:Complexity?n=1694577218886|1694577218886]]||1677852442567||-
| |
| − | |-
| |
| − | |78||[[Special:Complexity?n=24679458719|24679458719]]||3.58||True||7||[[Special:Complexity?n=2541865828329|2541865828329]]||2517186369610||-
| |
| − | |-
| |
| − | |79||[[Special:Complexity?n=35524698479|35524698479]]||3.57||True||6||[[Special:Complexity?n=3389154437772|3389154437772]]||3353629739293||-
| |
| − | |-
| |
| − | |80||[[Special:Complexity?n=44211625919|44211625919]]||3.59||True||7||[[Special:Complexity?n=5083731656658|5083731656658]]||5039520030739||-
| |
| − | |-
| |
| − | |81||[[Special:Complexity?n=62391692159|62391692159]]||3.58||True||8||[[Special:Complexity?n=7625597484987|7625597484987]]||7563205792828||-
| |
| − | |-
| |
| − | |82||[[Special:Complexity?n=93753213119|93753213119]]||3.57||True||7||[[Special:Complexity?n=10167463313316|10167463313316]]||10073710100197||-
| |
| − | |-
| |
| − | |83||[[Special:Complexity?n=121551917759|121551917759]]||3.57||True||7||[[Special:Complexity?n=15251194969974|15251194969974]]||15129643052215||-
| |
| − | |-
| |
| − | |84||[[Special:Complexity?n=163539961199|163539961199]]||3.57||True||7||[[Special:Complexity?n=22876792454961|22876792454961]]||22713252493762||-
| |
| − | |-
| |
| − | |85||[[Special:Complexity?n=250585241759|250585241759]]||3.56||True||7||[[Special:Complexity?n=30502389939948|30502389939948]]||30251804698189||-
| |
| − | |-
| |
| − | |86||[[Special:Complexity?n=320429329919|320429329919]]||3.57||True||8||[[Special:Complexity?n=45753584909922|45753584909922]]||45433155580003||-
| |
| − | |-
| |
| − | |87||[[Special:Complexity?n=424847520719|424847520719]]||3.57||True||7||[[Special:Complexity?n=68630377364883|68630377364883]]||68205529844164||-
| |
| − | |-
| |
| − | |88||[[Special:Complexity?n=630371064959|630371064959]]||3.56||True||8||[[Special:Complexity?n=91507169819844|91507169819844]]||90876798754885||-
| |
| − | |-
| |
| − | |89||[[Special:Complexity?n=872573642639|872573642639]]||3.56||True||7||[[Special:Complexity?n=137260754729766|137260754729766]]||136388181087127||-
| |
| − | |}
| |
| − | | |
| − | ==Concerning the best expressions==
| |
| − | | |
| − | There have been conjectures as to what can be the best expression of a number. Notably, it was conjectured, that for prime numbers
| |
| − | :<math>\left\|p\right\| = 1+\left\|p-1\right\|</math>
| |
| − | and
| |
| − | :<math>\left\|2p\right\| = \min{\{2+\left\|p\right\|, 1+\left\|2p-1\right\|\}}</math>.
| |
| − | | |
| − | Even though the intuition behind the hypotheses is very natural - if the number is written as a sum, one of the addends should be very small, i.e. 1, since "expected contribution" to the other addend (as an addend to one of its multipliers) is so much more greater - both of these hypotheses have been shown to be false. However, the smallest offending numbers are quite large: [[Special:Complexity?n=353942783|353942783]] and [[Special:Complexity?n=10278600694|5139300347]], respectively.
| |
| − | | |
| − | Some more counterexamples are listed in this table:
| |
| − | {| class="wikitable sortable"
| |
| − | |-
| |
| − | !<math>n</math>||[http://oeis.org/A189124 A189124](n)||PrimeQ[A189124(n)]
| |
| − | |-
| |
| − | |1||[[Special:Complexity?n=353942783|353942783]]||True
| |
| − | |-
| |
| − | |2||[[Special:Complexity?n=516743639|516743639]]||False
| |
| − | |-
| |
| − | |3||[[Special:Complexity?n=1163385647|1163385647]]||True
| |
| − | |-
| |
| − | |4||[[Special:Complexity?n=1542243239|1542243239]]||False
| |
| − | |-
| |
| − | |5||[[Special:Complexity?n=1932319583|1932319583]]||True
| |
| − | |-
| |
| − | |6||[[Special:Complexity?n=2336924879|2336924879]]||True
| |
| − | |-
| |
| − | |7||[[Special:Complexity?n=3113713259|3113713259]]||False
| |
| − | |-
| |
| − | |8||[[Special:Complexity?n=3444631199|3444631199]]||False
| |
| − | |-
| |
| − | |9||[[Special:Complexity?n=3878989487|3878989487]]||False
| |
| − | |-
| |
| − | |10||[[Special:Complexity?n=4103787551|4103787551]]||False
| |
| − | |-
| |
| − | |11||[[Special:Complexity?n=4166809919|4166809919]]||True
| |
| − | |-
| |
| − | |12||[[Special:Complexity?n=4937621453|4937621453]]||True
| |
| − | |-
| |
| − | |13||[[Special:Complexity?n=5123340683|5123340683]]||True
| |
| − | |-
| |
| − | |14||[[Special:Complexity?n=5170931639|5170931639]]||False
| |
| − | |-
| |
| − | |15||[[Special:Complexity?n=5184740299|5184740299]]||True
| |
| − | |-
| |
| − | |16||[[Special:Complexity?n=5200683263|5200683263]]||False
| |
| − | |-
| |
| − | |17||[[Special:Complexity?n=5390865059|5390865059]]||True
| |
| − | |-
| |
| − | |18||[[Special:Complexity?n=5455982879|5455982879]]||True
| |
| − | |-
| |
| − | |19||[[Special:Complexity?n=5467766947|5467766947]]||True
| |
| − | |-
| |
| − | |20||[[Special:Complexity?n=5570566315|5570566315]]||False
| |
| − | |-
| |
| − | |21||[[Special:Complexity?n=5876676427|5876676427]]||False
| |
| − | |-
| |
| − | |22||[[Special:Complexity?n=6020880739|6020880739]]||False
| |
| − | |-
| |
| − | |23||[[Special:Complexity?n=6213081067|6213081067]]||False
| |
| − | |-
| |
| − | |24||[[Special:Complexity?n=6432033887|6432033887]]||True
| |
| − | |-
| |
| − | |25||[[Special:Complexity?n=6459553799|6459553799]]||True
| |
| − | |-
| |
| − | |26||[[Special:Complexity?n=6545574839|6545574839]]||True
| |
| − | |-
| |
| − | |27||[[Special:Complexity?n=6714582263|6714582263]]||True
| |
| − | |-
| |
| − | |28||[[Special:Complexity?n=6888368878|6888368878]]||False
| |
| − | |-
| |
| − | |29||[[Special:Complexity?n=6988649399|6988649399]]||True
| |
| − | |-
| |
| − | |30||[[Special:Complexity?n=7349349419|7349349419]]||False
| |
| − | |-
| |
| − | |31||[[Special:Complexity?n=7354261907|7354261907]]||False
| |
| − | |-
| |
| − | |32||[[Special:Complexity?n=7378517519|7378517519]]||True
| |
| − | |-
| |
| − | |33||[[Special:Complexity?n=7515851039|7515851039]]||True
| |
| − | |-
| |
| − | |34||[[Special:Complexity?n=7657182539|7657182539]]||True
| |
| − | |-
| |
| − | |35||[[Special:Complexity?n=7756383347|7756383347]]||True
| |
| − | |-
| |
| − | |36||[[Special:Complexity?n=8219266919|8219266919]]||True
| |
| − | |-
| |
| − | |37||[[Special:Complexity?n=8265240899|8265240899]]||False
| |
| − | |-
| |
| − | |38||[[Special:Complexity?n=8267366687|8267366687]]||False
| |
| − | |-
| |
| − | |39||[[Special:Complexity?n=8312800997|8312800997]]||True
| |
| − | |-
| |
| − | |40||[[Special:Complexity?n=8319180029|8319180029]]||False
| |
| − | |-
| |
| − | |41||[[Special:Complexity?n=9299744395|9299744395]]||False
| |
| − | |-
| |
| − | |42||[[Special:Complexity?n=9307738439|9307738439]]||False
| |
| − | |-
| |
| − | |43||[[Special:Complexity?n=9312441947|9312441947]]||True
| |
| − | |-
| |
| − | |44||[[Special:Complexity?n=9417418919|9417418919]]||True
| |
| − | |-
| |
| − | |45||[[Special:Complexity?n=9649914763|9649914763]]||False
| |
| − | |-
| |
| − | |46||[[Special:Complexity?n=9687112847|9687112847]]||True
| |
| − | |-
| |
| − | |47||[[Special:Complexity?n=9796592617|9796592617]]||False
| |
| − | |-
| |
| − | |48||[[Special:Complexity?n=9797579279|9797579279]]||True
| |
| − | |-
| |
| − | |49||[[Special:Complexity?n=9810679247|9810679247]]||True
| |
| − | |-
| |
| − | |50||[[Special:Complexity?n=9816022007|9816022007]]||False
| |
| − | |-
| |
| − | |51||[[Special:Complexity?n=9819417887|9819417887]]||True
| |
| − | |-
| |
| − | |52||[[Special:Complexity?n=10009162939|10009162939]]||False
| |
| − | |-
| |
| − | |53||[[Special:Complexity?n=10251400499|10251400499]]||True
| |
| − | |-
| |
| − | |54||[[Special:Complexity?n=10278600694|10278600694]]||False
| |
| − | |-
| |
| − | |55||[[Special:Complexity?n=10752114599|10752114599]]||False
| |
| − | |-
| |
| − | |56||[[Special:Complexity?n=10795928723|10795928723]]||True
| |
| − | |-
| |
| − | |57||[[Special:Complexity?n=10858961203|10858961203]]||False
| |
| − | |-
| |
| − | |58||[[Special:Complexity?n=10870190159|10870190159]]||False
| |
| − | |-
| |
| − | |59||[[Special:Complexity?n=10900918439|10900918439]]||False
| |
| − | |-
| |
| − | |60||[[Special:Complexity?n=10948216919|10948216919]]||False
| |
| − | |-
| |
| − | |61||[[Special:Complexity?n=10948217573|10948217573]]||False
| |
| − | |-
| |
| − | |62||[[Special:Complexity?n=10982945399|10982945399]]||True
| |
| − | |-
| |
| − | |63||[[Special:Complexity?n=11030276879|11030276879]]||True
| |
| − | |-
| |
| − | |64||[[Special:Complexity?n=11430539819|11430539819]]||True
| |
| − | |-
| |
| − | |65||[[Special:Complexity?n=11520231839|11520231839]]||False
| |
| − | |-
| |
| − | |66||[[Special:Complexity?n=11879689919|11879689919]]||True
| |
| − | |-
| |
| − | |67||[[Special:Complexity?n=12279593759|12279593759]]||True
| |
| − | |-
| |
| − | |68||[[Special:Complexity?n=12402781733|12402781733]]||True
| |
| − | |-
| |
| − | |69||[[Special:Complexity?n=12440572891|12440572891]]||True
| |
| − | |-
| |
| − | |70||[[Special:Complexity?n=12464418523|12464418523]]||False
| |
| − | |-
| |
| − | |71||[[Special:Complexity?n=12483890999|12483890999]]||True
| |
| − | |-
| |
| − | |72||[[Special:Complexity?n=12506394959|12506394959]]||False
| |
| − | |-
| |
| − | |73||[[Special:Complexity?n=12571726823|12571726823]]||True
| |
| − | |-
| |
| − | |74||[[Special:Complexity?n=12580039259|12580039259]]||True
| |
| − | |-
| |
| − | |75||[[Special:Complexity?n=12686036183|12686036183]]||True
| |
| − | |}
| |
| − | | |
| − | Up to <math>5*10^{11}</math> there are 283 counterexamples (all in [[File:2pCounter.txt]]) to the second conjecture. The first 50 are:
| |
| − | {| class="wikitable sortable"
| |
| − | |-
| |
| − | !<math>n</math>||<math>p_n</math>
| |
| − | |-
| |
| − | |1||[[Special:Complexity?n=10278600694|5139300347]]
| |
| − | |-
| |
| − | |2||[[Special:Complexity?n=15497722798|7748861399]]
| |
| − | |-
| |
| − | |3||[[Special:Complexity?n=17048096134|8524048067]]
| |
| − | |-
| |
| − | |4||[[Special:Complexity?n=20726927638|10363463819]]
| |
| − | |-
| |
| − | |5||[[Special:Complexity?n=21760403254|10880201627]]
| |
| − | |-
| |
| − | |6||[[Special:Complexity?n=25899777502|12949888751]]
| |
| − | |-
| |
| − | |7||[[Special:Complexity?n=31329368062|15664684031]]
| |
| − | |-
| |
| − | |8||[[Special:Complexity?n=32062787998|16031393999]]
| |
| − | |-
| |
| − | |9||[[Special:Complexity?n=32801694118|16400847059]]
| |
| − | |-
| |
| − | |10||[[Special:Complexity?n=32869094542|16434547271]]
| |
| − | |-
| |
| − | |11||[[Special:Complexity?n=33096145534|16548072767]]
| |
| − | |-
| |
| − | |12||[[Special:Complexity?n=45557779858|22778889929]]
| |
| − | |-
| |
| − | |13||[[Special:Complexity?n=46507340158|23253670079]]
| |
| − | |-
| |
| − | |14||[[Special:Complexity?n=46539226654|23269613327]]
| |
| − | |-
| |
| − | |15||[[Special:Complexity?n=49550857198|24775428599]]
| |
| − | |-
| |
| − | |16||[[Special:Complexity?n=84744886894|42372443447]]
| |
| − | |-
| |
| − | |17||[[Special:Complexity?n=88995291622|44497645811]]
| |
| − | |-
| |
| − | |18||[[Special:Complexity?n=93431048254|46715524127]]
| |
| − | |-
| |
| − | |19||[[Special:Complexity?n=93497874046|46748937023]]
| |
| − | |-
| |
| − | |20||[[Special:Complexity?n=99509671438|49754835719]]
| |
| − | |-
| |
| − | |21||[[Special:Complexity?n=111750707734|55875353867]]
| |
| − | |-
| |
| − | |22||[[Special:Complexity?n=113050749334|56525374667]]
| |
| − | |-
| |
| − | |23||[[Special:Complexity?n=114773208694|57386604347]]
| |
| − | |-
| |
| − | |24||[[Special:Complexity?n=116657631358|58328815679]]
| |
| − | |-
| |
| − | |25||[[Special:Complexity?n=116873841598|58436920799]]
| |
| − | |-
| |
| − | |26||[[Special:Complexity?n=122110222174|61055111087]]
| |
| − | |-
| |
| − | |27||[[Special:Complexity?n=139615908478|69807954239]]
| |
| − | |-
| |
| − | |28||[[Special:Complexity?n=140017166494|70008583247]]
| |
| − | |-
| |
| − | |29||[[Special:Complexity?n=141054542998|70527271499]]
| |
| − | |-
| |
| − | |30||[[Special:Complexity?n=141121365118|70560682559]]
| |
| − | |-
| |
| − | |31||[[Special:Complexity?n=144638031598|72319015799]]
| |
| − | |-
| |
| − | |32||[[Special:Complexity?n=144655590778|72327795389]]
| |
| − | |-
| |
| − | |33||[[Special:Complexity?n=145797393958|72898696979]]
| |
| − | |-
| |
| − | |34||[[Special:Complexity?n=149190546634|74595273317]]
| |
| − | |-
| |
| − | |35||[[Special:Complexity?n=149286208174|74643104087]]
| |
| − | |-
| |
| − | |36||[[Special:Complexity?n=159497138734|79748569367]]
| |
| − | |-
| |
| − | |37||[[Special:Complexity?n=161540046106|80770023053]]
| |
| − | |-
| |
| − | |38||[[Special:Complexity?n=170485334638|85242667319]]
| |
| − | |-
| |
| − | |39||[[Special:Complexity?n=170536762078|85268381039]]
| |
| − | |-
| |
| − | |40||[[Special:Complexity?n=171785274334|85892637167]]
| |
| − | |-
| |
| − | |41||[[Special:Complexity?n=171786551542|85893275771]]
| |
| − | |-
| |
| − | |42||[[Special:Complexity?n=186119672822|93059836411]]
| |
| − | |-
| |
| − | |43||[[Special:Complexity?n=186603284734|93301642367]]
| |
| − | |-
| |
| − | |44||[[Special:Complexity?n=188076442354|94038221177]]
| |
| − | |-
| |
| − | |45||[[Special:Complexity?n=198433351294|99216675647]]
| |
| − | |-
| |
| − | |46||[[Special:Complexity?n=209236359742|104618179871]]
| |
| − | |-
| |
| − | |47||[[Special:Complexity?n=220007539582|110003769791]]
| |
| − | |-
| |
| − | |48||[[Special:Complexity?n=223183537198|111591768599]]
| |
| − | |-
| |
| − | |49||[[Special:Complexity?n=223671709726|111835854863]]
| |
| − | |-
| |
| − | |50||[[Special:Complexity?n=225394226782|112697113391]]
| |
| − | |}
| |
| − | | |
| − | ==Programs==
| |
| − | A program to calculate complexity in base {1,+,-,*} is found here: [[File:Minus.txt|Minus.txt]].
| |
