|
%I M0457 #206 May 06 2024 07:22:55
%S 1,2,3,4,5,5,6,6,6,7,8,7,8,8,8,8,9,8,9,9,9,10,11,9,10,10,9,10,11,10,
%T 11,10,11,11,11,10,11,11,11,11,12,11,12,12,11,12,13,11,12,12,12,12,13,
%U 11,12,12,12,13,14,12,13,13,12,12,13,13,14,13,14,13,14,12,13,13,13,13,14,13,14
%N The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.
%C The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications and parentheses. This does not allow juxtaposition of 1's to form larger integers, so for example, 2 = 1+1 has complexity 2, but 11 does not ("pasting together" two 1's is not an allowed operation).
%C The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.
%C Guy asks if a(p) = a(p-1) + 1 for prime p. Martin Fuller found the least counterexample p = 353942783 in 2008, see Fuller link. - _Charles R Greathouse IV_, Oct 04 2012
%C It appears that this sequence is lower than A348262 {1,+,^} only a finite number of times. - _Gordon Hamilton_ and Brad Ballinger, May 23 2022
%C The second Altman links proves that {a(n) - 3*log_3(n)} is a well-ordered subset of the reals whose intersection with [0,k) has order type omega^k for each positive integer k, so this set itself has order type omega^omega. - _Jianing Song_, Apr 13 2024
%D M. Criton, "Les uns de Germain", Problem No. 4, pp. 13 ; 68 in '7 x 7 Enigmes Et Défis Mathématiques pour tous', vol. 25, Editions POLE, Paris 2001.
%D R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.
%D K. Mahler and J. Popken, Over een Maximumprobleem uit de Rekenkunde (Dutch: On a maximum problem in arithmetic), Nieuw Arch. Wiskunde, (3) 1 (1953), pp. 1-15.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H M. F. Hasler, <a href="/A005245/b005245.txt">Table of n, a(n) for n = 1..10000</a>
%H Harry Altman, <a href="http://www-personal.umich.edu/~haltman/stdalone.pdf">Highest few sums and products of ones</a>, Preprint, undated but before 2013.
%H Harry Altman, <a href="http://arxiv.org/abs/1310.2894">Integer Complexity and Well-Ordering</a>, arXiv:1310.2894v1 [math.NT] , Oct 10, 2013.
%H Harry Altman and Joshua Zelinsky, <a href="http://arxiv.org/abs/1207.4841">Numbers with integer complexity close to the lower bound</a>, arXiv:1207.4841 [math.NT], 2012.
%H J. Arias de Reyna, <a href="http://hdl.handle.net/11441/40419">Complejidad de los números naturales</a>, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250.
%H J. Arias de Reyna, <a href="/A005245/a005245_1.pdf">Complejidad de los números naturales</a>, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. [Cached copy, with permission]
%H J. Arias de Reyna, <a href="https://arxiv.org/abs/2111.03345">Complexity of natural numbers</a>, arXiv:2111.03345 [math.NT], 2021.
%H J. Arias de Reyna and J. van de Lune, <a href="http://arxiv.org/abs/1404.1850">The question "How many 1's are needed?" revisited</a>, arXiv preprint arXiv:1404.1850 [math.NT], 2014.
%H J. Arias de Reyna and J. van de Lune, <a href="http://arxiv.org/abs/1404.2183">Algorithms for determining integer complexity</a>, arXiv preprint arXiv:1404.2183 [math.NT], 2014.
%H Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, <a href="http://arxiv.org/abs/1409.0446">Integer Complexity: Experimental and Analytical Results II</a>, arxiv:1409.0446 [math.NT], 2014.
%H Katherine Cordwell, Alyssa Epstein, Anand Hemmady, Steven J. Miller, Eyvindur A. Palsson, Aaditya Sharma, Stefan Steinerberger and Yen Nhi Truong Vu, <a href="https://arxiv.org/abs/1706.08424">On algorithms to calculate integer complexity</a>, arXiv:1706.08424 [math.NT], 2017.
%H Martin N. Fuller, <a href="/A005245/a005245.c.txt">C program</a>
%H R. K. Guy, <a href="http://www.jstor.org/stable/2323338">Some suspiciously simple sequences</a>, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
%H Qizheng He, <a href="https://arxiv.org/abs/2308.10301">Improved Algorithms for Integer Complexity</a>, arXiv:2308.10301 [cs.DS], 2023.
%H Janis Iraids, <a href="http://expmath.lumii.lv/wiki/index.php/Special:Complexity">Online calculator of a(n) for n < 10^12</a>
%H Jānis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, <a href="http://arxiv.org/abs/1203.6462">Integer complexity: experimental and analytical results</a>, arXiv:1203.6462 [math.NT], 2012.
%H Daniel A. Rawsthorne, <a href="http://www.fq.math.ca/Scanned/27-1/rawsthorne.pdf">How many 1's are needed?</a>, Fibonacci Quarterly 27 (1989), pp. 14-17.
%H Srinivas, Vivek V. and Shankar, B. R., <a href="http://www.waset.org/journals/waset/v17/v17-119.pdf">Integer Complexity: Breaking the Theta(n^2) barrier</a>, World Academy of Science 41 (2008), pp. 690-691.
%H Stefan Steinerberger, <a href="http://hdl.handle.net/10515/sy5sj1b71">A Short Note on Integer Complexity</a>, Contributions to Discrete Mathematics, Vol. 9.1 (2014).
%H Stefan Steinerberger, <a href="/A005245/a005245.pdf">A short note on integer complexity</a>, Contributions to Discrete Mathematics, Vol. 9.1 (2014). [Cached copy, with permission.]
%H Joshua Zelinsky, <a href="https://arxiv.org/abs/2211.02995">Upper Bounds on Integer Complexity</a>, arXiv preprint (2022). arXiv:2211.02995 [math.NT]
%H Venecia Wang, <a href="http://www.youtube.com/watch?v=R8IQI_dwaJE">A counterexample to the prime conjecture of expressing numbers using just ones</a>, YouTube video, 2012.
%H Venecia Wang, <a href="https://doi.org/10.1016/j.jnt.2012.08.003">A counterexample to the prime conjecture of expressing numbers using just ones</a>, Journal of Number Theory, Volume 133, Issue 2, February 2013, Pages 391-397.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IntegerComplexity.html">Integer Complexity</a>
%H Dimitri Zucker, <a href="https://www.youtube.com/watch?v=RdnTi-2gahs">The Most Underrated Concept in Number Theory</a>, Combo Class Youtube video that mentions this sequence.
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F It is known that a(n) <= A061373(n) but I think 0 <= A061373(n) - a(n) <= 1 also holds. - _Benoit Cloitre_, Nov 23 2003 [That's false: the numbers {46, 235, 649, 1081, 7849, 31669, 61993} require {1, 2, 3, 4, 5, 6, 7} fewer 1's in A005245 than in A061373. - _Ed Pegg Jr_, Apr 13 2004]
%F It is known from the work of Selfridge and Coppersmith that 3 log_3 n <= a(n) <= 3 log_2 n = 4.754... log_3 n for all n > 1. [Guy, Unsolved Problems in Number Theory, Sect. F26.] - _Charles R Greathouse IV_, Apr 19 2012 [Comment revised by _N. J. A. Sloane_, Jul 17 2016]
%F Zelinsky (2022) improves the upper bound to a(n) <= A*log n where A = 41/log(55296) = 3.754422.... This compares to the constant 2.7307176... of the lower bound. - _Charles R Greathouse IV_, Dec 11 2022
%F a(n) >= A007600(n) is a very accurate lower bound. - _Mehmet Sarraç_, Dec 18 2022
%e From _Lekraj Beedassy_, Jul 04 2009: (Start)
%e n.........minimal expression........ a(n) = number of 1's
%e 1..................1...................1
%e 2.................1+1..................2
%e 3................1+1+1.................3
%e 4.............(1+1)*(1+1)..............4
%e 5............(1+1)*(1+1)+1.............5
%e 6............(1+1)*(1+1+1).............5
%e 7...........(1+1)*(1+1+1)+1............6
%e 8..........(1+1)*(1+1)*(1+1)...........6
%e 9...........(1+1+1)*(1+1+1)............6
%e 10..........(1+1+1)*(1+1+1)+1...........7
%e 11.........(1+1+1)*(1+1+1)+1+1..........8
%e 12.........(1+1)*(1+1)*(1+1+1)..........7
%e 13........(1+1)*(1+1)*(1+1+1)+1.........8
%e 14.......{(1+1)*(1+1+1)+1}*(1+1)........8
%e 15.......{(1+1)*(1+1)+1}*(1+1+1)........8
%e 16.......(1+1)*(1+1)*(1+1)*(1+1)........8
%e 17......(1+1)*(1+1)*(1+1)*(1+1)+1.......9
%e 18........(1+1)*(1+1+1)*(1+1+1).........8
%e 19.......(1+1)*(1+1+1)*(1+1+1)+1........9
%e 20......{(1+1+1)*(1+1+1)+1}*(1+1).......9
%e 21......{(1+1)*(1+1+1)+1}*(1+1+1).......9
%e 22.....{(1+1)*(1+1+1)+1}*(1+1+1)+1.....10
%e 23....{(1+1)*(1+1+1)+1}*(1+1+1)+1+1....11
%e 24......(1+1)*(1+1)*(1+1)*(1+1+1).......9
%e 25.....(1+1)*(1+1)*(1+1)*(1+1+1)+1.....10
%e 26....{(1+1)*(1+1)*(1+1+1)+1}*(1+1)....10
%e 27.......(1+1+1)*(1+1+1)*(1+1+1)........9
%e 28......(1+1+1)*(1+1+1)*(1+1+1)+1......10
%e 29.....(1+1+1)*(1+1+1)*(1+1+1)+1+1.....11
%e 30.....{(1+1+1)*(1+1+1)+1}*(1+1+1).....10
%e 31....{(1+1+1)*(1+1+1)+1}*(1+1+1)+1....11
%e 32....(1+1)*(1+1)*(1+1)*(1+1)*(1+1)....10
%e 33...(1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1...11
%e 34..{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)..11
%e .........................................
%e (End)
%p with(numtheory):
%p a:= proc(n) option remember;
%p `if`(n=1, 1, min(seq(a(i)+a(n-i), i=1..n/2),
%p seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))
%p end:
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Apr 18 2012
%t a[n_] := a[n] = If[n == 1, 1,
%t Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~
%t Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]];
%t Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Dec 12 2013, after _Alois P. Heinz_ *)
%o (PARI) A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6 && return(n);
%o if(n<=#A005245, A005245[n]&return(A005245[n]) /* return memoized result if available */,
%o A005245=vector(n) /* create vector if needed - should better reuse existing data if available */);
%o for(i=1, n-1, A005245[i] || A005245[i]=A005245(i,lim)); /* compute all previous elements */
%o A005245[n]=min( vecmin(vector(min(n\2,if(lim>0,lim,n)), k, A005245[k]+A005245[n-k])) /* additive possibilities - if lim>0 is given, consider a(k)+a(n-k) only for k<=lim - we know it is save to use lim=1 up to n=2e7 */, if( isprime(n), n, vecmin(vector((-1+#d=divisors(n))\2, i, A005245[d[i+1]]+A005245[d[ #d-i]]))/* multiplicative possibilities */))}
%o \\ See also the Python program by Tim Peters at A005421.
%o \\ _M. F. Hasler_, Jan 30 2008
%o (Haskell)
%o import Data.List (genericIndex)
%o a005245 n = a005245_list `genericIndex` (n-1)
%o a005245_list = 1 : f 2 [1] where
%o f x ys = y : f (x + 1) (y : ys) where
%o y = minimum $
%o (zipWith (+) (take (x `div` 2) ys) (reverse ys)) ++
%o (zipWith (+) (map a005245 $ tail $ a161906_row x)
%o (map a005245 $ reverse $ init $ a161908_row x))
%o -- _Reinhard Zumkeller_, Mar 08 2013
%o (Python)
%o from functools import lru_cache
%o from itertools import takewhile
%o from sympy import divisors
%o @lru_cache(maxsize=None)
%o def A005245(n): return min(min(A005245(a)+A005245(n-a) for a in range(1,(n>>1)+1)),min((A005245(d)+A005245(n//d) for d in takewhile(lambda d:d*d<=n,divisors(n)) if d>1),default=n)) if n>1 else 1 # _Chai Wah Wu_, Apr 29 2023
%Y Cf. A000792 (largest integer of given complexity), A003313, A076142, A076091, A061373, A005421, A064097, A005520, A025280, A003037, A161906, A161908, A244743.
%K nonn,nice,look,changed
%O 1,2
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_, May 15 1997.
| 