|
Search: id:A005245
|
|
|
| A005245 |
|
Complexity of n: number of 1's required to build n using + and *.
(Formerly M0457)
|
|
+0
15
|
|
| 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; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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.
J. Arias de Reyna, Complejidad de los numeros naturales, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250.
|
|
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
|
|
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.
|
|
PROGRAM
|
(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<=#A5245, A5245[n]&return(A5245[n]) /* return memoized result if available */,
A5245=vector(n) /*create vector if needed - should better re-use exiting data if available */);
for(i=1, n-1, A5245[i] | A5245[i]=A005245(i, lim)); /* compute all previous elements */
A5245[n]=min( vecmin(vector(min(n\2, if(lim>0, lim, n)), k, A5245[k]+A5245[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, A5245[d[i+1]]+A5245[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: A096365 A007600 A091333 this_sequence A061373 A104135 A046108
Adjacent sequences: A005242 A005243 A005244 this_sequence A005246 A005247 A005248
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
More terms from David W. Wilson (davidwwilson(AT)comcast.net) May 15 1997
|
|
|
Search completed in 0.002 seconds
|
