A005245 -id:A005245 - cp's OEIS frontend

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

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

Offset: 1

Jens Voß, Dec 30 2003

nonn

One strategy for computing integer complexities like a(n) is to proceed in rounds, successively determining all n for which a(n) = 2, 3, 4, 5, and so on. In each round one takes all operations of pairs of numbers whose already known lesser complexities sum to the current value. The difficulty with this particular a(n) is that exponentiation quickly produces very large values, which conceivably could be near each other and yield a value of a(n) for small n by taking their difference in a later round. However, one can safely compute small values up to 19 by ignoring intermediate results larger than 2^65: this doesn't ignore anything except 2^81, 2^256, and 2^512 in the ninth round, and those values will not become involved in differences that could affect arguments n less than 2^65 until at least round 19, so all small values up to 19 produced in this way will be correct. Doing so gives values for all n from a(1)=1 up to a(3305)=19. It is possible based on the above that a(3306) might be 19, if some large result from round 10 differs from one of the three ignored values in round 9 by exactly 3306. That just about surely doesn't happen, but more careful reasoning would be needed to prove the correct value a(3306) = 20. - Glen Whitney, Sep 22 2021

			A091334(15) = 7 because 15 = (1+1+1+1)^(1+1) - 1. (Note that 15 is also the smallest index at which A091334 differs from A025280.)

Glen Whitney, Table of n, a(n) for n = 1..3305
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
Glen Whitney, Python3.8 program computing up to a(3305)

Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091333 (using +, -, and *), A348089 (using +, -, *, /, and ^), A348262 (using + and ^).

A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

Original entry on oeis.org

2, 2, 1, 10, 13, 22, 38, 91, 195, 443, 634, 1121, 3448, 6793, 17692

Offset: 1

Ali Dasdan, Apr 05 2012

			a(2) = 2 because two 2's can produce 0 = 2-2, 1 = 2/2, 4 = 2+2 = 2*2, so the smallest positive integer that cannot be computed is 2.
a(3) = 1 because no expression with three 3's gives 1.

Cf. A005245, A005520, A003313, A076142, A076091, A061373, A005421, A064097, A025280, A003037, A117618.

Cf. A171826, A171827, A171828, A171829, A258068, A258069, A258070, A258071.

f:= proc(n,b) option remember;
      `if`(n=1, {b}, {seq(seq(seq([k+m, k-m, k*m,
      `if`(m=0, NULL, k/m)][], m=f(n-i, b)), k=f(i, b)), i=1..n-1)})
    end:
a:= proc(n) local i, l;
      l:= sort([infinity, select(x-> is(x, integer) and x>0, f(n, n))[]]);
      for i do if l[i]<>i then return i fi od
    end:
seq(a(n), n=1..8); # Alois P. Heinz, Apr 13 2012

from fractions import Fraction
from functools import lru_cache
def a(n):
    @lru_cache()
    def f(m):
        if m == 1: return {Fraction(n, 1)}
        out = set()
        for j in range(1, m//2+1):
            for x in f(j):
                for y in f(m-j):
                    out.update([x + y, x - y, y - x, x * y])
                    if y: out.add(Fraction(x, y))
                    if x: out.add(Fraction(y, x))
        return out
    k, s = 1, f(n)
    while k in s: k += 1
    return k
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Jul 29 2022

a(11)-a(12) from Alois P. Heinz, Apr 22 2012
a(13)-a(14) from Michael S. Branicky, Jul 29 2022
a(15) from Michael S. Branicky, Jul 27 2023

A061373 "Natural" logarithm, defined inductively by a(1)=1, a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if n, m>1.

Original entry on oeis.org

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, 13, 14, 11, 12, 12, 12, 12, 13, 11, 13, 12, 12, 13, 14, 12, 13, 13, 12, 12, 13, 13, 14, 13, 14, 13, 14, 12, 13, 13, 13, 13, 14

Offset: 1

Juan Arias-de-Reyna, Jun 08 2001

Related to A005245, the complexity of n, which is <= this sequence. They are equal up to term a(46) and for 771 values out of the first 1000 terms. A061373 is easier to compute.

a(A182061(n)) = n and a(m) < n for m < A182061(n). [Reinhard Zumkeller, Apr 09 2012]

T. D. Noe, Table of n, a(n) for n = 1..10000
J. Arias de Reyna, Complejidad de los numeros naturales, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250. (In Spanish.)
J. Arias de Reyna, Complejidad de los numeros naturales, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250. (In Spanish.) [Cached copy, with permission]
J. Arias de Reyna, Complexity of natural numbers, arXiv:2111.03345 [math.NT], 2021.

Cf. A005245.

Cf. A020639.

import Data.List (genericIndex)
a061373 1 = 1
a061373 n = genericIndex a061373_list (n-1)
a061373_list = 1 : f 2 where
   f x | x == spf  = 1 + a061373 (spf - 1) : f (x + 1)
       | otherwise = a061373 spf + a061373 (x `div` spf) : f (x + 1)
       where spf = a020639 x
-- Reinhard Zumkeller, Apr 09 2012

a[1]=1; a[p_?PrimeQ] := 1+a[p-1]; a[n_] := a[n] = With[{d=Divisors[n][[2]] }, a[d] + a[n/d]]; Array[a, 100] (* Jean-François Alcover, Feb 26 2016 *)

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

Original entry on oeis.org

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

Offset: 1

Glen Whitney, Sep 28 2021

nonn

Here division is taken to be strict integer division, i.e., j/k is defined only if k|j.

Because of the presence of exponentiation, division reduces the value of a(n) as compared with A091334(n) (which allows the same operations except division) far more often than adding division to A091333 does; see A348069.

			Because 41 = ((1+1+1)^(1+1+1+1) + 1)/(1+1), and there is no expression with these operators and fewer ones that evaluates to 41, a(41) = 10. Note that 41 is the least n such that a(n) < A091334(n).

Glen Whitney, Table of n, a(n) for n = 1..3802
Glen Whitney, Python3.8 program to compute a(n) for some values of n

Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091333 (using +, -, and *), A091334 (using +, -, *, and ^), A348262 (using + and ^).

Cf. A348069.

A348262 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, 10, 11, 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, 12, 13, 12, 13, 13, 14, 15, 13, 9, 10, 11, 12, 13, 12, 13, 14, 14, 14, 13, 14, 15, 16, 14, 7, 8, 9, 10, 11, 12, 13, 14, 12, 12, 13, 14, 15, 16, 17

Offset: 1

Glen Whitney, Oct 09 2021

nonn

			11+111++^ is a minimal-length RPN formula with value 8, using just these operators. It contains five occurrences of the symbol "1". Hence, a(8) = 5.

Glen Whitney, Table of n, a(n) for n = 1..10000
Edinah K. Ghang and Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013.
Glen Whitney, Python3.8 program to compute a(n)
Index to sequences related to the complexity of n

Cf. A213924 (expression-length complexity with the same set {1,+,^}).

Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091333 (using +, -, and *), A091334 (using +, -, *, and ^), A348089 (using +, -, *, /, and ^).

a(n) = (A213924(n) + 1)/2.

A230697 Length of shortest addition-multiplication chain for n.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 3, 4, 4, 4, 5, 5, 4, 3, 4, 4, 5, 4, 5, 5, 6, 4, 4, 5, 4, 5, 5, 5, 6, 4, 5, 5, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 5, 6, 6, 6, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 5, 6, 6, 6, 7, 5, 4, 5, 5, 5, 6, 6, 6, 6

Offset: 1

Harry Altman, Oct 27 2013

			A shortest addition-multiplication chain for 16 is (1,2,4,16), of length a(16) = 3.
A shortest addition-multiplication chain for 281 is (1,2,4,5,16,25,256,281), of length a(281) = 7. This is the first case where not all terms in some shortest chain are the sum or product of the immediately preceding term and one more preceding term. In other words, 281 is the smallest of the analog of non-Brauer numbers (A349044) for addition-multiplication chains. The next ones are 913, 941, 996, 997, 998, 1012, 1077, 1079, 1542, 1572, 1575, 1589, 1706, 1792, 1795, 1816, 1864, ... . - _Pontus von Brömssen_, May 02 2025

Jinyuan Wang, Table of n, a(n) for n = 1..10000
H. M. Bahig, On a generalization of addition chains: Addition-multiplication chains, Discrete Mathematics 308 (2008), 611-616.
Gleb Ivanov, Python program.

Cf. A003313, A005245, A128998, A173419, A349044, A354914, A383001, A383002.

A133344 Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation.

Original entry on oeis.org

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

Offset: 1

Jonathan Vos Post, Oct 20 2007

The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications, exponentiation and parentheses. This allows juxtaposition of numbers to form larger integers, so for example, 2 = 1+1 has complexity 2, but unlike A003037, so does 11 = 1#1 (concatenating two numbers is an allowed operation). Similarly a(111) = 3. The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.

			An example (usually nonunique) of the derivation of the first 22 values.
a(1) = 1, the number of 1's in "1."
a(2) = 2, the number of 1's in "1+1 = 2."
a(3) = 3, the number of 1's in "1+1+1 = 3."
a(4) = 4, the number of 1's in "1+1+1+1 = 4."
a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."
a(6) = 5, since there are 5 1's in "((1+1)*(1+1+1)) = 6."
a(7) = 6, since there are 6 1's in "1+(((1+1)*(1+1+1))) = 7."
a(8) = 5, since there are 5 1's in "(1+1)^(1+1+1) = 8."
a(9) = 5, since there are 5 1's in "(1+1+1)^(1+1) = 9."
a(10) = 6 since there are 6 1's in "1+((1+1+1)^(1+1)) = ten.
a(11) = 2 since there are 2 1's in "1#1 = eleven."
a(12) = 3 since there are 3 1's in "1+(1#1) = twelve."
a(13) = 4 since there are 4 1's in "1+1+(1#1) = thirteen."
a(14) = 5 since there are 5 1's in "1+1+1+(1#1) = fourteen."
a(16) = 6 since there are 6 1's in "(1+1+1+1)^(1+1)."
a(17) = 7 since there are 7 1's in "1+((1+1+1+1)^(1+1))."
a(18) = 6 since there are 6 1's in "1#((1+1)^(1+1+1))."
a(19) = 6 since there are 6 1's in "1#((1+1+1)^(1+1))."
a(20) = 7 since there are 7 1's in "(1#1)+((1+1+1)^(1+1))."
a(21) = 3 since there are 3 1's in "(1+1)#1."
a(22) = 4 since 22 = (1+1)*(1#1) = (1#1)+(1#1) = (1+1)#(1+1).

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Index to sequences related to the complexity of n

Cf. A003037, A025280, A005520, A005245, A005421, A117618.

with(numtheory):
a:= proc(n) option remember; local r; `if`(n=1, 1, min(
       seq(a(i)+a(n-i), i=1..n-1),
       seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
       seq(`if`(cat("", n)[i+1]<>"0", a(iquo(n, 10^(length(n)-i),
           'r'))+a(r), NULL), i=1..length(n)-1),
       seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
           i=ifactors(n)[2]))) minus {0, 1})))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Nov 06 2013

A213923 Minimal lengths of formulas representing n only using addition, multiplication and the constant 1.

Original entry on oeis.org

1, 3, 5, 7, 9, 9, 11, 11, 11, 13, 15, 13, 15, 15, 15, 15, 17, 15, 17, 17, 17, 19, 21, 17, 19, 19, 17, 19, 21, 19, 21, 19, 21, 21, 21, 19, 21, 21, 21, 21, 23, 21, 23, 23, 21, 23, 25, 21, 23, 23, 23, 23, 25, 21, 23, 23, 23, 25, 27, 23, 25, 25, 23, 23, 25, 25, 27, 25, 27, 25, 27, 23, 25, 25, 25, 25, 27, 25

Offset: 1

Jonathan Vos Post, Mar 06 2013

nonn

			a(3) = 5 because for n = 3, the minimum is length = 5, formula = "11+1+" or "111++".

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Multiplication for integers from 1 to 8000.
Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013

Cf. A005245, A214833.

with(numtheory):
a:= proc(n) option remember;
       1+ `if`(n=1, 0, 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, Mar 07 2013

a[n_] := a[n] = 1 + If[n == 1, 0, Min[Join[Table[a[i] + a[n-i], {i, 1, n/2}], Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 01 2017, after Alois P. Heinz *)

a(n) = 2*A005245(n)-1.

A252739 a(n) = A252738(n) / n.

Original entry on oeis.org

2, 6, 720, 612360000, 1697781042840960000000000, 504261397867001013813789115612253942400000000000000000000000000

Offset: 1

Antti Karttunen, Dec 21 2014

nonn

Note how 6, 720 and 612360000 occur in A244743 as its 0th, 4th and 8th term, from which my bold conjecture that A244743(12) or A244743(16) = 1697781042840960000000000.

According to preliminary results from Janis Iraids, the value of A005245(a(5)) = ||1697781042840960000000000|| = 160, while ||1697781042840960000000000 - 1|| = 169, which lays to rest my naive conjecture above, as 169 - 160 is neither 12 nor 16. Note also how 5, 719 and 612359999 are all primes, while a(5)-1 factorizes as 1697781042840959999999999 = 13 * 89443 * 908669 * 1606890407869. - Antti Karttunen, Dec 20 2015

Cf. A005245, A005940, A163511, A244743, A252738, A252740, A252741.

Scheme
```
(define (A252739 n) (/ (A252738 n) n))
```

a(n) = A252738(n) / n.

A348069 Numbers that may be built from fewer ones by using / in addition to +, -, and *.

Original entry on oeis.org

50221174, 251105873, 346765253, 387421583, 394594943, 526392311, 645706283, 657658237, 689544697, 689544698, 695921989, 774842071, 780158669, 782015431

Offset: 1

Glen Whitney, Sep 27 2021

Consider an integer complexity measure b(n) which is the number of ones required to build n using +, -, *, and /, where the latter operation is strict integer division, i.e., n/d is defined only when d|n. In other words, b(n) is defined identically to A091333(n) except that division is also allowed. Clearly for all n, b(n) <= A091333(n). This sequence lists the integers k for which b(k) < A091333(k).
Both b(n) and A091333(n) are also often equal to A005245(n), the number of ones required to build n using just + and *.
For the first 14 values of a, b(a(i)) = A091333(a(i)) - 1; it seems likely, however, that this difference will increase for larger values.
Computing all n such that b(n) <= 64 reveals the following numbers that must appear in this sequence, with their b-values in brackets: 1011597943 [63], 1032855583 [63], 1035512789 [63], 1038141563 [64], 1040295757 [63], 1040295759 [63], 1162264748 [63], 1162264749 [63], 1183784827 [63], 1183784828 [63], 1183784829 [63], 1292730233 [64], 1370320619 [64], 1376697911 [64], 1377760793 [64], 1378292233 [64], 1379886557 [64], 1542507503 [64], 1556856409 [64], 1571205317 [64].  However, because the least n for which b(n) = 65 is A255641(65) = 913230103 < 1011597943, it's not necessarily the case that the next entry in a after 782015431 is 1011597943, although it's likely; and given the examples where the b-values decrease for successive terms of a, these listed numbers are quite likely not all consecutive terms of a.

			The smallest n for which b(n) as defined in the Comments is strictly less than A091333(n) is 50221174, because 50221174 = (7*3^15 - 1)/2, which requires b(7) + 15*b(3) + 1 + 2 = 6 + 15*3 + 1 + 2 = 54 ones to express with these operations, whereas A091333(a(1)) = A005245(a(1)) = 55 by virtue of the minimal expression 50221174 = 3(2*3*5(2*2*3(3*2+1)(3^4(3^4+1)+1)+1)+1)+1 requiring 3+2+3+5+2+2+3+3+2+1+3*4+3*4+1+1+1+1+1 = 55 ones. Thus the first element of the sequence a is 50221174.
The next smallest n with b(n) < A091333(n) is 251105873 = (5*7*3^15 + 1)/2, requiring 59 ones, as compared with the minimal expression 2^2(3^2(3*2^2+1)(2*3(2^3*3^5(3^2*5+1)+1)+1)+1)+1 showing A091333(a(2)) = A005245(a(1)) = 60, so the second term of a is 251105873.
The next three values with their respective minimal expressions:
346765253 = (3^14(2^4*3^2 + 1) + 1)/2 [60 ones] = 2((2^2*3^4+1)(2*3^2(2^3*3^2+1)(3^4*5+1)+1)+1)+1 [61 ones].
387421583 = (3^7(2*3^11+1)+1)/2 [60 ones] = 2(2*5*7(2^2*3+1)(2^2*3^6(2^3*3^2+1)+1)+1)+1 [61 ones].
394594943 = (3^15(2*3^3 + 1) + 1)/2 [60 ones] = 2*7(2*3^3(5(2^4*3^2-1)(3^6+1)+1)-1)+1 [61 ones] = 3(2^2*3+1)(2*3^2(2*7(2*3^3+1)(3^6+1)+1)+1)+2 [62 ones]. Thus n=394594943 is the least n such that b(n) < A091333(n) < A005245(n).
Additional known values with their respective complexities:
     a(i)   b(a(i)) A091333(a(i)) A005245(a(i))
  --------- ------- ------------- -------------
  526392311    62         63            63
  645706283    62         63            63
  657658237    62         63            64
  689544697    62         63            63
  689544698    62         63            63
  695921989    62         63            63
  774842071    62         63            63
  780158669    63         64            64
  782015431    62         63            63
Thus 782015431 is the smallest value in this sequence at which b decreases from one entry to the next.

Glen Whitney, C program to discover numbers in this sequence

Cf. A253177.

Cf. A091333 and A005245 (other integer complexity measures).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Python

Extensions

A061373 "Natural" logarithm, defined inductively by a(1)=1, a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if n, m>1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A348262 Number of 1's required to build n using + and ^.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A230697 Length of shortest addition-multiplication chain for n.

Views

Author

Keywords

Examples

Links

Crossrefs

A133344 Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A213923 Minimal lengths of formulas representing n only using addition, multiplication and the constant 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A252739 a(n) = A252738(n) / n.

Views

Author

Keywords

Comments

Crossrefs

Programs