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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005245 Complexity of n: number of 1's required to build n using + and *.
(Formerly M0457)
28
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; text; 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.

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

Altman writes: "Define |n| to be the complexity of n, the smallest number of ones needed to write n using an arbitrary combination of addition and multiplication. John Selfridge showed that |n| greater than or equal to 3 log_3 n for all n. Define the defect of n, denoted delta(n), to be |n| - 3 log_3 n. In this paper, we consider the set D := {delta(n): n greater than or equal to 1 of all defects. We show that as a subset of the real numbers, the set D is well-ordered, of order type omega^omega. More specifically, for k greater than or equal to 1 an integer, Dcap[0,k) has order type omega^k. We also consider some other sets related to D, and show that these too are well-ordered and have order type omega^omega." [Jonathan Vos Post, Oct 10 2013]

REFERENCES

M. Criton, "Les uns de Germain", Problem No.4 pp 13 ; 68 in '7 x 7 Enigmes Et Defis Mathematiques pour tous', vol.25 Editions POLE Paris 2001.

J. Arias de Reyna, Complejidad de los numeros naturales, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250.

R. K. Guy, Unsolved Problems 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).

LINKS

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

Harry Altman, Highest few sums and products of ones

Harry Altman and Joshua Zelinsky, Numbers with integer complexity close to the lower bound, arXiv:1207.4841

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

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

J. Arias de Reyna, J. van de Lune, Algorithms for determining integer complexity, arXiv preprint arXiv:1404.2183, 2014

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

Martin N. Fuller, C program

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

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 (2012)

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

J. Arias de Reyna and J. van de Lune, Algorithms for determining integer complexity arXiv 1404.2183, 2014.

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

Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, Journal of Number Theory, submitted. video abstract

Eric Weisstein's World of Mathematics, Integer Complexity

Index to sequences related to the complexity of n

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.

Coppersmith proved that 3 log_3 n <= a(n) <= 3 log_2 n for all n > 1. - Charles R Greathouse IV, Apr 19 2012

EXAMPLE

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

MAPLE

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

MATHEMATICA

a[n_] := a[n] = If[n == 1, 1, Min [Sequence @@ Table [a[i] + a[n-i], {i, 1, n/2}], Sequence @@ 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 *)

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.

(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

CROSSREFS

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

Sequence in context: A007600 A195872 A091333 * A061373 A104135 A046108

Adjacent sequences:  A005242 A005243 A005244 * A005246 A005247 A005248

KEYWORD

nonn,nice,look,changed

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from David W. Wilson, May 15 1997

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 21 16:47 EDT 2014. Contains 248377 sequences.