|
| |
|
|
A005245
|
|
Complexity of n: number of 1's required to build n using + and *.
(Formerly M0457)
|
|
20
| |
|
|
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, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 12, 11, 12, 13, 11, 12, 12, 12, 12, 13, 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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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.
|
|
|
REFERENCES
| R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
M. Criton, "Les uns de Germain", Problem No.4 pp 13 ; 68 in '7 x 7 Enigmes Et Defis Mathematques pour tous', vol.25 Editions POLE Paris 2001. [From Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 04 2009]
J. Arias de Reyna, Complejidad de los numeros naturales, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| M. F. Hasler, Table of n, a(n) for n = 1..10000
Martin N. Fuller, C program
Eric Weisstein's World of Mathematics, Integer Complexity
Janis Iraids, Online calculator of a(n) for n < 10^12
|
|
|
FORMULA
| It's 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.
|
|
|
EXAMPLE
| Contribution from Lekraj Beedassy (blekraj(AT)yahoo.com), 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)..........11
34...{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)........11
................................................
(End)
|
|
|
PROG
| (PARI, from M. F. Hasler, Jan 30 2008) A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6&return(n);
if(n<=#A05245, A05245[n]&return(A05245[n]) /* return memoized result if available */,
A05245=vector(n) /*create vector if needed - should better re-use exiting data if available */);
for(i=1, n-1, A05245[i] | A05245[i]=A005245(i, lim)); /* compute all previous elements */
A05245[n]=min( vecmin(vector(min(n\2, if(lim>0, lim, n)), k, A05245[k]+A05245[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, A05245[d[i+1]]+A05245[d[ #d-i]]))/* multiplicative possibilities */))}
See also the Python program by Tim Peters at A005421.
|
|
|
CROSSREFS
| Cf. A000792 (largest integer of given complexity).
Cf. A003313, A076142, A076091, A061373, A005421, A064097.
Cf. A005520, A025280, A003037.
Sequence in context: A007600 A195872 A091333 * A061373 A104135 A046108
Adjacent sequences: A005242 A005243 A005244 * A005246 A005247 A005248
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from David W. Wilson (davidwwilson(AT)comcast.net) May 15 1997
|
| |
|
|
