Jānis Iraids: Created page with "Category: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, multi..."

2014-10-13T09:42:34Z

Created page with "Category: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, multi..."

New page

[[Category: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]].

Integer Complexity - Revision history

Jānis Iraids: /* Concerning the best expressions */

Jānis Iraids: Updated the links because GET params are not allowed in internal links. The extension that bypasses this is not available any more.

Jānis Iraids: Created page with "Category: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, multi..."