1,2

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).

The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.

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

It appears that this sequence is lower than A348262 {1,+,^} only a finite number of times. - Gordon Hamilton and Brad Ballinger, May 23 2022

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

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.

R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.

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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. F. Hasler, Table of n, a(n) for n = 1..10000

Harry Altman, Highest few sums and products of ones, Preprint, undated but before 2013.

Harry Altman, Integer Complexity and Well-Ordering, arXiv:1310.2894v1 [math.NT] , Oct 10, 2013.

Harry Altman and Joshua Zelinsky, Numbers with integer complexity close to the lower bound, arXiv:1207.4841 [math.NT], 2012.

Juan Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250.

Juan Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. [Cached copy, with permission]

Juan Arias de Reyna, Complexity of natural numbers, arXiv:2111.03345 [math.NT], 2021.

Juan Arias de Reyna and Jan van de Lune, The question "How many 1's are needed?" revisited, arXiv preprint arXiv:1404.1850 [math.NT], 2014.

Juan Arias de Reyna and Jan van de Lune, Algorithms for determining integer complexity, arXiv preprint arXiv:1404.2183 [math.NT], 2014.

Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arxiv:1409.0446 [math.NT], 2014.

Katherine Cordwell, Alyssa Epstein, Anand Hemmady, Steven J. Miller, Eyvindur A. Palsson, Aaditya Sharma, Stefan Steinerberger and Yen Nhi Truong Vu, On algorithms to calculate integer complexity, arXiv:1706.08424 [math.NT], 2017.

Martin N. Fuller, C program

Richard K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.

Qizheng He, Improved Algorithms for Integer Complexity, arXiv:2308.10301 [cs.DS], 2023.

Janis Iraids, Online calculator of a(n) for n < 10^12

Jānis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, Integer complexity: experimental and analytical results, arXiv:1203.6462 [math.NT], 2012.

Sergei Konyagin and Kristina Oganesyan, Upper and lower estimates for integer complexity, arXiv:2603.20876 [math.NT], 2026. See pp. 1, 7, references.

Daniel A. Rawsthorne, How many 1's are needed?, Fibonacci Quarterly 27 (1989), pp. 14-17.

Vivek V. Srinivas and B. R. Shankar, Integer Complexity: Breaking the Theta(n^2) barrier, World Acad. Sci. 41 (2008), 690-691.

Stefan Steinerberger, A Short Note on Integer Complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014).

Stefan Steinerberger, A short note on integer complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014). [Cached copy, with permission.]

Joshua Zelinsky, Upper Bounds on Integer Complexity, arXiv preprint (2022). arXiv:2211.02995 [math.NT]

Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, YouTube video, 2012.

Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, Journal of Number Theory, Volume 133, Issue 2, February 2013, Pages 391-397.

Eric Weisstein's World of Mathematics, Integer Complexity

Dimitri Zucker, The Most Underrated Concept in Number Theory, Combo Class Youtube video that mentions this sequence.

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]

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]

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

a(n) >= A007600(n) is a very accurate lower bound. - Mehmet Sarraç, Dec 18 2022

From Lekraj Beedassy, Jul 04 2009: (Start)

n.........minimal expression........ a(n) = number of 1's

1..................1...................1

2.................1+1..................2

3................1+1+1.................3

4.............(1+1)*(1+1)..............4

5............(1+1)*(1+1)+1.............5

6............(1+1)*(1+1+1).............5

7...........(1+1)*(1+1+1)+1............6

8..........(1+1)*(1+1)*(1+1)...........6

9...........(1+1+1)*(1+1+1)............6

10..........(1+1+1)*(1+1+1)+1...........7

11.........(1+1+1)*(1+1+1)+1+1..........8

12.........(1+1)*(1+1)*(1+1+1)..........7

13........(1+1)*(1+1)*(1+1+1)+1.........8

14.......{(1+1)*(1+1+1)+1}*(1+1)........8

15.......{(1+1)*(1+1)+1}*(1+1+1)........8

16.......(1+1)*(1+1)*(1+1)*(1+1)........8

17......(1+1)*(1+1)*(1+1)*(1+1)+1.......9

18........(1+1)*(1+1+1)*(1+1+1).........8

19.......(1+1)*(1+1+1)*(1+1+1)+1........9

20......{(1+1+1)*(1+1+1)+1}*(1+1).......9

21......{(1+1)*(1+1+1)+1}*(1+1+1).......9

22.....{(1+1)*(1+1+1)+1}*(1+1+1)+1.....10

23....{(1+1)*(1+1+1)+1}*(1+1+1)+1+1....11

24......(1+1)*(1+1)*(1+1)*(1+1+1).......9

25.....(1+1)*(1+1)*(1+1)*(1+1+1)+1.....10

26....{(1+1)*(1+1)*(1+1+1)+1}*(1+1)....10

27.......(1+1+1)*(1+1+1)*(1+1+1)........9

28......(1+1+1)*(1+1+1)*(1+1+1)+1......10

29.....(1+1+1)*(1+1+1)*(1+1+1)+1+1.....11

30.....{(1+1+1)*(1+1+1)+1}*(1+1+1).....10

31....{(1+1+1)*(1+1+1)+1}*(1+1+1)+1....11

32....(1+1)*(1+1)*(1+1)*(1+1)*(1+1)....10

33...(1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1...11

34..{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)..11

.........................................

(End)

with(numtheory):

a:= proc(n) option remember;

`if`(n=1, 1, min(seq(a(i)+a(n-i), i=1..n/2),

seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))

end:

seq(a(n), n=1..100); # Alois P. Heinz, Apr 18 2012

a[n_] := a[n] = If[n == 1, 1,

Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~

Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]];

Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Dec 12 2013, after Alois P. Heinz *)

(PARI) A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6 && return(n);

if(n<=#A005245, A005245[n]&return(A005245[n]) /* return memoized result if available */,

A005245=vector(n) /* create vector if needed - should better reuse existing data if available */);

for(i=1, n-1, A005245[i] || A005245[i]=A005245(i, lim)); /* compute all previous elements */

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 */))}

\\ See also the Python program by Tim Peters at A005421.

\\ M. F. Hasler, Jan 30 2008

(Haskell)

import Data.List (genericIndex)

a005245 n = a005245_list `genericIndex` (n-1)

a005245_list = 1 : f 2 [1] where

f x ys = y : f (x + 1) (y : ys) where

y = minimum $

(zipWith (+) (take (x `div` 2) ys) (reverse ys)) ++

(zipWith (+) (map a005245 $ tail $ a161906_row x)

(map a005245 $ reverse $ init $ a161908_row x))

-- Reinhard Zumkeller, Mar 08 2013

(Python)

from functools import lru_cache

from itertools import takewhile

from sympy import divisors

@lru_cache(maxsize=None)

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

Cf. A025280 (variant using +, *, and ^), A091333 (using +, -, and *), A091334 (using +, -, *, and ^), A348089 (using +, -, *, / and ^), A348262 (using + and ^).

Cf. A000792 (largest integer of given complexity), A003313, A076142, A076091, A061373, A005421, A064097, A005520, A003037, A161906, A161908, A244743.

Sequence in context: A195872 A091333 A293771 * A061373 A372306 A327705

Adjacent sequences: A005242 A005243 A005244 * A005246 A005247 A005248

nonn,nice,look,changed

More terms from David W. Wilson, May 15 1997

approved