A005245 -id:A005245 - cp's OEIS frontend

A263283 Minimum number of characters required to express n in Peano Arithmetic.

1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 10, 11, 12, 11, 11, 12, 12, 13, 12, 13, 14, 15, 13, 13, 14, 14, 14, 15, 14, 15, 15, 16, 16, 15, 15, 16, 17, 16, 16, 17, 16, 17, 17, 16, 17, 18, 16, 17, 17, 17, 17, 18, 17, 18, 18, 18, 19, 20, 17, 18, 19, 18, 17, 18, 19, 20

Offset: 0

Daniel Hill, Oct 13 2015

This sequence is the minimum number of characters needed in Peano Arithmetic to represent the number, where the characters are (i) '0' naming 0, (ii) 's' expressing the successor operation, (iii) '+' expressing the operation of addition, and (iv) 'x' expressing the operation of multiplication. Brackets are not used; Polish notation is employed instead, in which the operator is written before the terms rather than between them. Although in some cases there are different formulas of the same minimal length that represent the same number, the construction of the formulas is not arbitrary. It is not arbitrary that we start from 0, and it is not arbitrary that the only operations allowed are succession, addition, and multiplication. Finally, it is not arbitrary to use Polish notation to ensure shortness of formulas.
Another way of thinking of it would be: the minimum number of uses of operations necessary to give the number in Peano Arithmetic, where (i) 0 is considered to be a 0-ary operation, (ii) succession is a unary operation, (iii) addition is a binary operation, and (iv) multiplication is a binary operation. This way of thinking has the advantage that it doesn't look fishy not to mention brackets.
For all n > 0, one has 6 * log_4(n) - 1 <= a(n) <= 7 * log_3(n) + 3, with the left inequality being an equality if and only if n is a power of 4 (except for n = 1). One can prove the lower bound by induction, while the upper bound follows from translating the base-3 expansion of n into the language of Peano Arithmetic (using Horner's method and always using 's' symbols rather than additions). - Rémi Peyre, Nov 06 2021
When is addition first used? Specifically: (1) What is the first index n where there is a formula of length a(n) containing the addition operator? and (2) What is the first index n such that all formulas of length a(n) contain at least one addition operator? For n up to 10^5, there are no formulas of length a(n) using addition, only successor, multiplication, and 0. Note that if the answer to (2) is "never", then this sequence is also the minimum number of characters required to express n in Skolem Arithmetic. - Charles R Greathouse IV, Nov 17 2021

			So the name for 0 is simply '0', a formula of length 1. (Equivalently, 0 is formed by one use of the 0-ary operation, 0.)
The name for 1 is 's0', a formula of length 2. (Equivalently, 1 is formed by two uses of operations: the 0-ary operation, 0, and succession applied once to it.)
The name for 2 is 'ss0', a formula of length 3. (Equivalently, 2 is formed by three uses of operations: the 0-ary operation, 0, and succession applied twice to it.)
The name for 3 is 'sss0', a formula of length 4. (Equivalently, 3 is formed by four uses of operations: the 0-ary operation, 0, and succession applied thrice to it.)
The name for 9 is 'xsss0sss0', a formula of length 9. (Equivalently, 9 is formed by nine uses of operations: the 0-ary operation, 0, twice, succession applied thrice to each value of these operations, and multiplication applied to these two new values.)
The name for 10 is 'sxsss0sss0', a formula of length 10. (Equivalently, 10 is formed by ten uses of operations: the 0-ary operation, 0, twice, succession applied thrice to each value of these operations, multiplication applied to these two new values, and then succession applied to this last value.)
The name for 12 is 'xsss0ssss0', a formula of length 10. (Equivalently, 12 is formed by ten uses of operations: the 0-ary operation, 0, twice, succession applied thrice to one value of these operations and four times to the other, and then multiplication applied to these two new values.)
The name for 14 is 'xss0sssssss0', a formula of length 12. (Equivalently, 14 is formed by twelve uses of operations: the 0-ary operation, 0, twice, succession applied twice to one value of these operations and seven times to the other, and then multiplication applied to these two new values.)

Alois P. Heinz, Table of n, a(n) for n = 0..20000
Daniel Hill, Spreadsheet of first 27 terms
Index to sequences related to the complexity of n

Cf. A005245.

first(n)=my(v=vector(n+1)); v[1]=1; for(k=1,n, my(r=v[k],t); for(i=12,k\2, t=v[i+1]+v[k+1-i]; if(tk, break); t=v[d+1]+v[k/d+1]; if(tCharles R Greathouse IV, Nov 11 2021

from functools import cache
@cache
def a(n):
    if n == 0: return 1
    cs = a(n-1)
    ca = min((a(i) + a(n-i) for i in range(1, n)), default=cs)
    cm = min((a(j) + a(n//j) for j in range(2, n) if n%j == 0), default=cs)
    return 1 + min(cs, ca, cm)
print([a(n) for n in range(68)])  # Michael S. Branicky, Nov 05 2021

a(n) = 1 + min {a(n-1), a(i)+a(n-i), a(j)+a(n/j)} where 0 <= i <= n and j|n. - Charlie Neder, Jul 09 2018

More terms from Charlie Neder, Jul 09 2018

More terms from Alois P. Heinz, Jul 09 2018

A293771 Minimum number of steps needed to compute n using a machine that can read, write and add starting with the number 1.

Original entry on oeis.org

0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9, 9, 10, 10, 9, 10, 10, 9, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 12, 11, 12, 12, 11, 12, 12, 12, 12, 13, 11, 12, 12, 12, 13, 13, 12, 13, 13, 12, 12, 13, 13, 14, 13, 13, 13, 14, 12, 13, 13, 13, 13, 14, 13, 14, 13, 12, 13, 14, 13, 14, 14, 14, 14, 15

Offset: 1

Floris P. van Doorn, Oct 15 2017

nonn

The machine has a cache which holds 1 integer and a memory which holds a list of integers.
The machine starts with a number 1 in cache and empty memory.
At every step, the machine can do one of three things:
  (1) write the number from cache to a new position in memory;
  (2) read any number from memory and put it in cache;
  (3) add any number from memory to the number in cache.
a(n) is the minimum number of steps needed to get the number n in cache.
Conjecture: reading from memory (operation 2) is never needed to get to a number in the minimal number of steps.
Additional conjectures and comments by Glen Whitney, Oct 12 2021: (Start)
Conjecture II: For each n, there is a minimal-length program for n that stores numbers in memory in increasing order.
Conjecture III: For each n, there is a minimal-length program such that the difference between successive numbers stored in memory is strictly increasing.
All three conjectures are empirically verified for all programs of length 23 or less, and all values of n up to 2326. However, note that if you are allowed to specify the set of numbers that must be stored in memory, then the first conjecture fails for memory {1,3,9,27,30,54} and conjecture II fails for {1,3,9,27,30,54,60}. (These sequences of numbers in memory are similar to addition chains, see A003313.) Hence, a proof of the first conjecture might need to involve showing that every n has a "good" sequence of numbers that can be stored in memory to produce n, avoiding the need to invoke the read operation. Conjecture III supplies one speculative possibility of a property that might fill the role of "good." A proof of any of these conjectures would tremendously speed up computation of a(n) as compared to brute force. (End)
One can add a useless read instruction after the first operation of writing the initial one in cache to memory. Therefore, there is always a program one step longer than optimal that performs a read. Thus, in a numerical search, the first sign one might observe that read operations can be helpful is a tie for shortest between a program that does read and one that doesn't, for some value of n. However, no such ties occur for program length 21 or less. - Glen Whitney, Oct 23 2021

			For n = 23 we need 10 steps to get 23 in cache:
   1. Write 1 to memory
   2. Add 1 to cache (cache contains 2)
   3. Write 2 to memory
   4. Add 2 to cache (cache contains 4)
   5. Add 2 to cache (cache contains 6)
   6. Add 1 to cache (cache contains 7)
   7. Write 7 to memory
   8. Add 7 to cache (cache contains 14)
   9. Add 7 to cache (cache contains 21)
  10. Add 2 to cache (cache contains 23)
There are several other essentially different 10-step programs that result in 23 in cache, but no 9-step programs. (If a program differs just by the order of a sequence of successive additions, it's not considered essentially different.) Note that for all n < 2326, all of the numbers that have an essentially unique minimal program that puts a maximal set of numbers in memory are of the form 2^k, 1+2^k, 3^k, or 1+3^k, except for 5, 809 and 1609:
For n = 809 we need 21 steps: (1) W1; (2) A1 => 2; (3) A1 => 3; (4) W3; (5) A3 => 6; (6) A3 => 9; (7) A1 => 10; (8) W10; (9) A10 => 20; (10) W20; (11) A20 => 40; (12) W40; (13) A40 => 80; (14) W80; (15) A80 => 160; (16) A80 => 240; (17) A3 => 243; (18) W243; (19) A243 => 486; (20) A243 => 729; (21) A80 => 809.
n = 1609 can be computed most efficiently in 23 steps. The contents of memory when 1609 is reached are {1,3,10,20,40,80,160,483}; the precise steps can be inferred from these memory contents.

Glen Whitney, Table of n, a(n) for n = 1..2326 (Terms 1..340 from Robert G. Wilson v)
Glen Whitney, C program to compute a(n) for small values of a(n)
Glen Whitney, Somewhat more efficient C program to compute a(n)
Index to sequences related to the complexity of n

Cf. A005245, A091333, A172005.

Cf. A003313 (addition chains; similar except read/write are "free").

PossibleNextStates[{n_, l_}] :=
Join[{#, l} & /@ l,
  If[! MemberQ[l, n], {{n, Sort@Append[l, n]}}, {}], {n + #, l} & /@ l]
states = {{1, {}}}; i = 0; c[1] = 0;
Do[states = Union @@ PossibleNextSteps /@ states; i++;
  If[! IntegerQ[c[#[[1]]]], c[#[[1]]] = i] & /@ states, {14}];
c /@ Range[88]

A349983 a(n) is the largest k such A000792(k) <= n.

Original entry on oeis.org

1, 2, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

Offset: 1

Harry Altman, Jan 08 2022

Harry Altman, Integer Complexity: The Integer Defect, Moscow Journal of Combinatorics and Number Theory 8-3 (2019), 193-217.

Harry Altman, Integer Complexity: The Integer Defect, arXiv:1804.07446 [math.NT], 2018.

Cf. A005245, A000792, A007600.

a(n) = max{ 3*floor(log_3(n)), 3*floor(log_3(n/2))+2, 3*floor(log_3(n/4))+4, 1 }.

a(n) = A007600(n)-1 except when n appears in A000792, in which case a(n) = A007600(n).

A361838 a(n) is the number of 2s in the binary hereditary representation of 2n.

Original entry on oeis.org

1, 2, 3, 2, 3, 4, 5, 3, 4, 5, 6, 5, 6, 7, 8, 3, 4, 5, 6, 5, 6, 7, 8, 6, 7, 8, 9, 8, 9, 10, 11, 4, 5, 6, 7, 6, 7, 8, 9, 7, 8, 9, 10, 9, 10, 11, 12, 7, 8, 9, 10, 9, 10, 11, 12, 10, 11, 12, 13, 12, 13, 14, 15, 4, 5, 6, 7, 6, 7, 8, 9, 7, 8, 9, 10, 9, 10, 11, 12, 7

Offset: 1

Jodi Spitz, Mar 26 2023

See comments on A266201 for the definition of hereditary representation.

			A table of n, the binary hereditary representation of 2n, and the number of 2s in the representation:
 n | hereditary rep. of 2n   | number of 2s
---+-------------------------+--------------
 1 | 2                       |      1
 2 | 2^2                     |      2
 3 | 2^2+2                   |      3
 4 | 2^(2+1)                 |      2
 5 | 2^(2+1)+2               |      3
 6 | 2^(2+1)+2^2             |      4
 7 | 2^(2+1)+2^2+2           |      5
 8 | 2^2^2                   |      3
 9 | 2^2^2+2                 |      4
10 | 2^2^2+2^2               |      5
11 | 2^2^2+2^2+2             |      6
12 | 2^2^2+2^(2+1)           |      5
13 | 2^2^2+2^(2+1)+2         |      6
14 | 2^2^2+2^(2+1)+2^2       |      7
15 | 2^2^2+2^(2+1)+2^2+2     |      8
16 | 2^(2^2+1)               |      3
17 | 2^(2^2+1)+2             |      4
18 | 2^(2^2+1)+2^2           |      5
19 | 2^(2^2+1)+2^2+2         |      6
20 | 2^(2^2+1)+2^(2+1)       |      5
21 | 2^(2^2+1)+2^(2+1)+2     |      6
22 | 2^(2^2+1)+2^(2+1)+2^2   |      7
23 | 2^(2^2+1)+2^(2+1)+2^2+2 |      8
24 | 2^(2^2+1)+2^2^2         |      6
25 | 2^(2^2+1)+2^2^2+2       |      7
26 | 2^(2^2+1)+2^2^2+2^2     |      8
27 | 2^(2^2+1)+2^2^2+2^2+2   |      9
28 | 2^(2^2+1)+2^2^2+2^(2+1) |      8

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A005245, A025280.

a(n)=if(n==0, 0, sum(k=0, logint(n,2), if(bittest(n,k), 1 + a((k+1)\2)))) \\ Andrew Howroyd, Apr 07 2023

A378758 Number of 1's required to build n using +, -, and ^.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 6, 5, 5, 6, 7, 8, 9, 8, 7, 6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 7, 6, 7, 8, 9, 8, 7, 8, 9, 9, 8, 9, 10, 11, 12, 12, 13, 12, 13, 12, 11, 10, 9, 8, 9, 10, 11, 12, 12, 12, 12, 13, 13, 12, 11, 10, 9, 8, 7, 8, 9, 10, 11, 12, 13, 13, 12, 12, 13

Offset: 1

Jake Bird, Dec 06 2024

nonn

All intermediate steps in building the number should be integers as well, for consistency with related sequences.

A348262(n) >= a(n) >= A091334(n) for all n, as the available operators in A348262 are a subset of the available operators here, and the available operators here are a subset of the available operators in A091334.

			a(22) = 10 because 22 = (1+1+1+1+1)^(1+1)-(1+1+1), which has 10 occurrences of the symbol "1", and there is no way of making 22 with fewer using these rules.
Note that A348262(22) = 12 because 22 = (1+1)^(1+1)^(1+1)+(1+1)^(1+1)+1+1; subtraction allows for two fewer occurrences of the symbol "1" to be used here. Similarly, A091334(22) = 9 because 22 = ((1+1+1)^(1+1)+1+1)*(1+1); multiplication allows for one fewer occurrence of the symbol "1" to be used there. 22 is the least n such that A348262(n) > a(n) > A091334(n).

Jake Bird, Table of n, a(n) for n = 1..300

Cf. A000027 {1,+}, {1,+,-}
Cf. A005245 {1,+,*}
Cf. A348262 {1,+,^}
Cf. A091333 {1,+,-,*}
Cf. A025280 {1,+,*,^}
Cf. A378759 {1,+,/,^}
Cf. A091334 {1,+,-,*,^}
Cf. A348089 {1,+,-,*,/,^}

A378759 Number of 1's required to build n using +, /, and ^.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 5, 5, 6, 7, 8, 9, 9, 10, 6, 7, 8, 9, 10, 11, 12, 13, 11, 7, 8, 6, 7, 8, 9, 10, 7, 8, 9, 10, 8, 9, 10, 11, 12, 10, 11, 12, 13, 13, 14, 15, 13, 9, 10, 11, 12, 13, 12, 13, 14, 13, 14, 13, 14, 12, 13, 11, 7, 8, 9, 10, 11, 12, 13, 14, 12

Offset: 1

Jake Bird, Dec 06 2024

nonn

All intermediate steps in building the number should also be integers.

A348262(n) >= a(n) >= A348089(n) for all n, as the available operators in A348262 are a subset of the available operators here, and the available operators here are a subset of the available operators in A348089.

			a(14) = 9 because 14 = ((1+1+1)^(1+1+1)+1)/(1+1), which has 9 occurrences of the symbol "1", and there is no way of making 14 with fewer using these rules.
Note that A348262(14) = 10 because 14 = (1+1+1)^(1+1)+(1+1)^(1+1)+1; division allows for one fewer occurrence of the symbol "1" to be used here. Similarly, A348089(14) = 8, because 14 = (1+1)^(1+1)^(1+1)-(1+1); subtraction allows for one fewer occurrence of the symbol "1" to be used there. 14 is the least n such that A348262(n) > a(n) > A348089(n).

Jake Bird, Table of n, a(n) for n = 1..119

Cf. A000027 {1,+}, {1,+,-}
Cf. A005245 {1,+,*}
Cf. A348262 {1,+,^}
Cf. A091333 {1,+,-,*}
Cf. A378758 {1,+,-,^}
Cf. A025280 {1,+,*,^}
Cf. A091334 {1,+,-,*,^}
Cf. A348089 {1,+,-,*,/,^}

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Original entry on oeis.org

1, 2, 2, 3, 4, 2, 3, 4, 4, 3, 4, 4, 5, 6, 4, 5, 6, 6, 7, 6, 2, 3, 4, 4, 5, 6, 4, 3, 4, 5, 5, 6, 6, 5, 6, 4, 5, 6, 6, 7, 8, 4, 5, 6, 4, 5, 6, 6, 5, 6, 6, 7, 8, 8, 3, 4, 5, 5, 6, 7, 5, 6, 6, 7, 6, 4, 5, 6, 6, 7, 8, 6, 7, 8, 8, 5, 6, 4, 5, 6, 6, 7, 6, 6, 7, 8, 6, 7, 8, 8, 5, 6, 7, 7, 8, 9, 7, 8, 6, 7, 8, 8

Offset: 1

Jonathan Vos Post, Apr 08 2006

nonn

This problem has the optimal substructure property.

			a(1) = 1 because "1" has a single 1.
a(2) = 2 because "1+1" has two 1's.
a(3) = 2 because 3 = T(1+1) has two 1's.
a(6) = 2 because 6 = T(T(1+1)).
a(10) = 3 because 10 = T(T(1+1)+1).
a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
a(15) = 4 because 15 = T(T(1+1)+1+1).
a(21) = 2 because 21 = T(T(T(1+1))).
a(28) = 3 because 28 = T(T(T(1+1))+1).
a(55) = 3 because 55 = T(T(T(1+1)+1)).

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, 1971.
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Ed Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Wikipedia, Optimal substructure.

See also A023361 = number of compositions into sums of triangular numbers, A053614 = numbers that are not the sum of triangular numbers. Iterated triangular numbers: A050536, A050542, A050548, A050909, A007501.

Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.

a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
      if n<3 then n
    elif n=m*(m+1)/2 then a(m)
    else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
      fi
    end:
seq (a(n), n=1..110);  # Alois P. Heinz, Jan 05 2011

a[n_] := a[n] = Module[{m = Floor[Sqrt[n*2]]}, If[n < 3, n, If[n == m*(m + 1)/2, a[m], Min[Table[a[i] + a[n - i], {i, 1, Floor[n/2]}]]]]];
Array[a, 110] (* Jean-François Alcover, Jun 02 2018, from Maple *)

I do not know how many of these entries have been proved to be minimal. - N. J. A. Sloane, Apr 15 2006

Corrected and extended by Alois P. Heinz, Jan 05 2011

A118121 Roman numeral complexity of n.

Original entry on oeis.org

1, 2, 3, 2, 1, 2, 3, 4, 2, 1, 2, 3, 4, 3, 2, 3, 4, 4, 3, 2, 3, 4, 5, 4, 3, 4, 5, 5, 4, 3, 4, 5, 5, 5, 4, 4, 5, 5, 5, 2, 3, 4, 5, 4, 3, 4, 5, 6, 4, 1, 2, 3, 4, 3, 2, 3, 4, 5, 3, 2, 3, 4, 5, 4, 3, 4, 5, 6, 4, 3, 4, 5, 6, 5, 4, 5, 5, 6, 5, 4, 4, 5, 6, 5, 5, 6, 6, 6, 6, 2, 3, 4, 5, 4, 3, 4, 5, 6, 4, 1, 2, 3

Offset: 1

Jonathan Vos Post, May 12 2006

The least number of letters {I, V, X, L, C, D, M} needed to represent n by an expression with conventional Roman numerals, addition, multiplication and parentheses. a(n) <= A006968(n) and a(n) <= A005245(n). Conventional Roman numerals are very efficient at reducing complexity from number of letters in "old style" Roman numerals (A092196) and more primitive representations. In all but two examples shown (38, 88) the use of {+,*} reduces the representation by a single symbol (counting + and *); in these two it saves 2 symbols. In an alternate history, complexity theory and minimum description length could have been invented by Gregorius Catin.

			a(n) < A006968(n) for these examples. Here "<" means less in letter count:
a(18) = 4 [IX + IX < XVIII]; a(28) = 5 [XIV * II < XXVIII]; a(33) = 5 [XI * III < XXXIII]; a(36) = 4 [VI * VI < XXXVI]; a(37) = 5 [VI * VI + I < XXXVII]; a(38) = 5 [XIX * II < XXXVIII]; a(77) = 5 [XI * VII < LXXVII]; a(78) = 6 [XIII * VI < LXXVIII]; a(81) = 4 [IX * IX < LXXXI]; a(82) = 5 [XLI * II < LXXXII]; a(83) = 6 [XLI * II + I < LXXXIII]; a(84) = 5 [XX * IV < LXXXIV]; a(87) = 6 [IX * IX + VI < LXXXVII]; a(88) = 6 [XI * VIII < LXXXVIII].

Index to sequences related to the complexity of n

Cf. A005245, A006968, A092196.

A210660 Smallest number m such that A210659(m)=n.

Original entry on oeis.org

1, 2, 6, 7, 14, 23, 86, 179, 538, 1439, 9566, 21383, 122847, 777419, 1965374, 6803099, 19860614, 26489579, 269998838, 477028439

Offset: 0

Janis Iraids, Mar 28 2012

nonn

The sequence was discovered by Martins Opmanis.

J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results. arXiv preprint arXiv:1203.6462, 2012. - From _N. J. A. Sloane_, Sep 22 2012
Index to sequences related to the complexity of n

Cf. A210659, A005245, A005520.

A274061 Number of 1's required to build n using +, * and concatenation of 1's, where the result of concatenation is interpreted as a binary string.

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 3, 4, 4, 5, 6, 5, 6, 5, 4, 5, 6, 6, 7, 7, 5, 6, 7, 6, 7, 8, 6, 6, 7, 6, 5, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 7, 8, 8, 6, 7, 8, 7, 6, 7, 8, 8, 9, 8, 9, 7, 8, 9, 9, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8, 9, 10, 8, 9, 9, 10, 11, 9, 8, 9, 10, 8, 9, 10, 9, 9, 10, 8, 9, 9, 7, 8, 9, 8, 9, 8, 9, 9

Offset: 1

Jeremy Tan, Jun 08 2016

nonn

Like A005245, but concatenation of ones is allowed and their results are treated as binary representations of integers. Hence 3 can be represented as 11, 7 as 111 and so on.

The largest number with complexity n is 2^n-1 (A000225), the concatenation of n 1's. This follows from (2^m-1)(2^n-1) < 2^(m+n)-1 for m, n >= 1.

			n . minimal expression . number of 1's
1...1....................1
2...1+1..................2
3...11...................2
4...11+1.................3
5...11+1+1...............4
6...11*(1+1).............4
7...111..................3
8...111+1................4
9...11*11................4
10..11*11+1..............5
11..11*11+1+1............6
12..11*(11+1)............5
13..11*(11+1)+1..........6
14..111*(1+1)............5
15..1111.................4
16..1111+1...............5
17..1111+1+1.............6
18..11*11*(1+1)..........6
19..11*11*(1+1)+1........7
20..(11+1+1)(11+1).......7
21..111*11...............5

Alois P. Heinz, Table of n, a(n) for n = 1..20000
Jeremy Tan, Python program

Cf. A005245, A133344.

with(numtheory):
a:= proc(n) option remember; (k-> `if`(2^k=n+1, k,
      min(seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
          seq(a(i)+a(n-i), i=1..n/2))))(ilog2(n+1))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jun 09 2016

a[n_] := a[n] = Function[k, If[2^k == n+1, k, Min[Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}], Table[a[i] + a[n-i], {i, 1, n/2}]]]] @ Floor[Log[2, n+1]];
Array[a, 100] (* Jean-François Alcover, Mar 27 2017, after Alois P. Heinz *)

cp's OEIS Frontend

A263283 Minimum number of characters required to express n in Peano Arithmetic.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A293771 Minimum number of steps needed to compute n using a machine that can read, write and add starting with the number 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A349983 a(n) is the largest k such A000792(k) <= n.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A361838 a(n) is the number of 2s in the binary hereditary representation of 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A378758 Number of 1's required to build n using +, -, and ^.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A378759 Number of 1's required to build n using +, /, and ^.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A118121 Roman numeral complexity of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A210660 Smallest number m such that A210659(m)=n.