login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005520 Smallest number of complexity n: smallest number requiring n 1's to build using + and *.
(Formerly M0523)
29
1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, 59, 89, 107, 167, 179, 263, 347, 467, 683, 719, 1223, 1438, 1439, 2879, 3767, 4283, 6299, 10079, 11807, 15287, 21599, 33599, 45197, 56039, 81647, 98999, 163259, 203999, 241883, 371447, 540539, 590399, 907199 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Ed Pegg Jr, www.mathpuzzle.com, Apr 10 2001, notes that all the new terms are -1 mod 120. - That is, this holds at least for all terms from a(45) = 590399 up to the highest known term a(89) given in the b-file at the end of 2015. Comment clarified by Antti Karttunen, Dec 14 2015

Largest number of complexity n is given by A000792. - David W. Wilson, Oct 03 2005

After 1438 = 2 * 719, all elements through 8206559 are primes. Equivalently, except for a(4) = 4, a(7) = 10, a(10) = 22 and a(25) = 1438, we have a(1) through a(53) are all primes. - Jonathan Vos Post, Apr 07 2006

a(54)-a(89) are all primes. - Janis Iraids, Apr 21 2011

Previous observations (primes with property -1 mod 120) still hold. - Martins Opmanis, Oct 16 2009

The prime 353942783 = A189125(1) =  2 * 3 + (1 + 2^2 * 3^2)*(2 + 3^4(1 + 2 * 3^10)) is the smallest counterexample to Guy's first hypothesis on integer complexity. - Jonathan Vos Post, Mar 30 2012

The sequence A265360 (second smallest number of complexity n) seems to have similar properties. - Janis Iraids via Antti Karttunen, Dec 15 2015

REFERENCES

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

R. K. Guy, Unsolved Problems in Number Theory, Sec. F26 (related material).

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

LINKS

Janis Iraids, Table of n, a(n) for n = 1..89

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

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

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.

Ed Pegg Jr., Math Games: Integer Complexity, www.mathpuzzle.com, April 12, 2004.

D. A. Rawsthorne, How many 1's are needed?, Fib. Quart. 27 (1989), 14-17.

Eric Weisstein's World of Mathematics, Integer Complexity

Index to sequences related to the complexity of n

EXAMPLE

Examples from Piotr Fabian:

1=1, 1 "one": first 1, z(1)=1

2=1+1, 2 "ones": first 2, z(2)=2

3=1+1+1, 3 "ones": first 3, z(3)=3

4=1+1+1+1, 4 "ones": first 4, z(4)=4

5=1+1+1+1+1, 5 "ones": first 5, z(5)=5

6=(1+1)*(1+1+1), 5 "ones"

7=1+((1+1)*(1+1+1)), 6 "ones": first 6, z(6)=7

8=(1+1)*(1+1+1+1), 6 "ones"

9=(1+1+1)*(1+1+1), 6 "ones"

10=1+((1+1+1)*(1+1+1)), 7 "ones": first 7, z(7)=10

11=1+(1+(1+1+1)*(1+1+1)), 8 "ones": first 8, z(8)=11

12=(1+1)*((1+1)*(1+1+1)), 7 "ones"

MAPLE

N:= 100000: # to get all terms <= N

R:= Vector(N):

R[1]:= 1: A[1]:= 1:

for n from 2 to N do

  inds:= [seq(n-i, i=1..floor(n/2))];

  m:= min(R[1..floor(n/2)] + R[inds]);

  for d in select(`<=`, numtheory:-divisors(n), floor(sqrt(n))) minus {1} do

    m:= min(m, R[d]+R[n/d])

  od;

  R[n]:= m;

  if not assigned(A[m]) then A[m]:= n fi;

od:

seq(A[m], m=1..max(R)); # Robert Israel, Dec 14 2015

MATHEMATICA

nn = 10000;

R = Table[0, nn];

R[[1]] = 1; Clear[A]; A[1] = 1;

For[n = 2, n <= nn, n++,

  inds = Table[n-i, {i, 1, n/2}];

  m = Min[R[[1 ;; Floor[n/2]]] + R[[inds]]];

  Do[

    m = Min[m, R[[d]] + R[[n/d]]], {d,

    Select[Rest[Divisors[n]], # <= Sqrt[n]&]}

  ];

  R[[n]] = m;

  If[!IntegerQ[A[m]], A[m] = n];

];

Table[A[m], {m, 1, Max[R]}] (* Jean-François Alcover, Aug 05 2018, after Robert Israel *)

PROG

See the Python program by Tim Peters at A005421.

(MATLAB)

N = 10^6;

fact = cell(1, N);

for n = 2:sqrt(N)

  for m = [n^2:n:N]

    fact{m} = [fact{m}, n];

  end

end

R = zeros(1, N);

R(1) = 1;

A(1) = 1;

mmax = 1;

for n = 2:N

  m = min(R(1:floor(n/2)) + R([n-1:-1:ceil(n/2)]));

  if numel(fact{n}) > 0

    m = min(m, min(R(fact{n}) + R(n ./ fact{n})));

  end

  R(n) = m;

  if m > mmax

    A(m) = n;

    mmax = m;

  elseif A(m) == 0

    A(m) = n;

  end

end

A % Robert Israel, Dec 14 2015

CROSSREFS

Cf. A005245, A025280, A003037, A005421, A048183, A181898, A182061, A265360.

Sequence in context: A133493 A265938 A182061 * A048183 A255641 A122975

Adjacent sequences:  A005517 A005518 A005519 * A005521 A005522 A005523

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Corrected and extended by David W. Wilson, May 1997

Extended to terms a(40)=163259 and a(41)=203999 by John W. Layman, Nov 03 1999

Further terms from Piotr Fabian (PCF(AT)who.net), Mar 30 2001

a(68)-a(89) from Janis Iraids, Apr 20 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 20:13 EST 2018. Contains 317324 sequences. (Running on oeis4.)