A091334 -id:A091334 - cp's OEIS frontend

A005245 The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.

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

Offset: 1

N. J. A. Sloane

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
It appears that this sequence is lower than A348262 {1,+,^} only a finite number of times. - Gordon Hamilton and Brad Ballinger, May 23 2022
The second Altman links proves that {a(n) - 3*log_3(n)} is a well-ordered subset of the reals whose intersection with [0,k) has order type omega^k for each positive integer k, so this set itself has order type omega^omega. - Jianing Song, Apr 13 2024

			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)

M. Criton, "Les uns de Germain", Problem No. 4, pp. 13 ; 68 in '7 x 7 Enigmes Et Défis Mathématiques pour tous', vol. 25, Editions POLE, Paris 2001.
R. K. Guy, Unsolved Problems in 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).

M. F. Hasler, Table of n, a(n) for n = 1..10000
Harry Altman, Highest few sums and products of ones, Preprint, undated but before 2013.
Harry Altman, Integer Complexity and Well-Ordering, arXiv:1310.2894v1 [math.NT] , Oct 10, 2013.
Harry Altman and Joshua Zelinsky, Numbers with integer complexity close to the lower bound, arXiv:1207.4841 [math.NT], 2012.
J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250.
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, Complexity of natural numbers, arXiv:2111.03345 [math.NT], 2021.
J. Arias de Reyna and J. van de Lune, The question "How many 1's are needed?" revisited, arXiv preprint arXiv:1404.1850 [math.NT], 2014.
J. Arias de Reyna and J. van de Lune, Algorithms for determining integer complexity, arXiv preprint arXiv:1404.2183 [math.NT], 2014.
Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arxiv:1409.0446 [math.NT], 2014.
Katherine Cordwell, Alyssa Epstein, Anand Hemmady, Steven J. Miller, Eyvindur A. Palsson, Aaditya Sharma, Stefan Steinerberger and Yen Nhi Truong Vu, On algorithms to calculate integer complexity, arXiv:1706.08424 [math.NT], 2017.
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.
Qizheng He, Improved Algorithms for Integer Complexity, arXiv:2308.10301 [cs.DS], 2023.
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, arXiv:1203.6462 [math.NT], 2012.
Daniel A. Rawsthorne, How many 1's are needed?, Fibonacci Quarterly 27 (1989), pp. 14-17.
Srinivas, Vivek V. and Shankar, B. R., Integer Complexity: Breaking the Theta(n^2) barrier, World Academy of Science 41 (2008), pp. 690-691.
Stefan Steinerberger, A Short Note on Integer Complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014).
Stefan Steinerberger, A short note on integer complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014). [Cached copy, with permission.]
Joshua Zelinsky, Upper Bounds on Integer Complexity, arXiv preprint (2022). arXiv:2211.02995 [math.NT]
Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, YouTube video, 2012.
Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, Journal of Number Theory, Volume 133, Issue 2, February 2013, Pages 391-397.
Eric Weisstein's World of Mathematics, Integer Complexity
Dimitri Zucker, The Most Underrated Concept in Number Theory, Combo Class Youtube video that mentions this sequence.
Index to sequences related to the complexity of n

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

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

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

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

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

A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6 && return(n);
if(n<=#A005245, A005245[n]&return(A005245[n]) /* return memoized result if available */,
A005245=vector(n) /* create vector if needed - should better reuse existing data if available */);
for(i=1, n-1, A005245[i] || A005245[i]=A005245(i,lim)); /* compute all previous elements */
A005245[n]=min( vecmin(vector(min(n\2,if(lim>0,lim,n)), k, A005245[k]+A005245[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, A005245[d[i+1]]+A005245[d[ #d-i]]))/* multiplicative possibilities */))}
\\ See also the Python program by Tim Peters at A005421.
\\ M. F. Hasler, Jan 30 2008

from functools import lru_cache
from itertools import takewhile
from sympy import divisors
@lru_cache(maxsize=None)
def A005245(n): return min(min(A005245(a)+A005245(n-a) for a in range(1,(n>>1)+1)),min((A005245(d)+A005245(n//d) for d in takewhile(lambda d:d*d<=n,divisors(n)) if d>1),default=n)) if n>1 else 1 # Chai Wah Wu, Apr 29 2023

It is 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]
It is known from the work of Selfridge and Coppersmith that 3 log_3 n <= a(n) <= 3 log_2 n = 4.754... log_3 n for all n > 1. [Guy, Unsolved Problems in Number Theory, Sect. F26.] - Charles R Greathouse IV, Apr 19 2012 [Comment revised by N. J. A. Sloane, Jul 17 2016]
Zelinsky (2022) improves the upper bound to a(n) <= A*log n where A = 41/log(55296) = 3.754422.... This compares to the constant 2.7307176... of the lower bound. - Charles R Greathouse IV, Dec 11 2022
a(n) >= A007600(n) is a very accurate lower bound. - Mehmet Sarraç, Dec 18 2022

More terms from David W. Wilson, May 15 1997

A025280 Complexity of n: 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, 8, 6, 7, 7, 8, 8, 9, 9, 10, 8, 7, 8, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 10, 11, 11, 12, 11, 10, 11, 12, 9, 8, 9, 10, 10, 11, 8, 9, 9, 10, 10, 11, 11, 12, 12, 11, 7, 8, 9, 10, 11, 12, 12, 13, 9, 10, 10, 10, 11, 12, 11, 12, 11, 7, 8, 9, 10, 11, 12, 11

Offset: 1

N. J. A. Sloane, David W. Wilson

nonn

R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
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. A005245 (variant using + and *), A091333 (using +, -, and *), A091334 (using +, -, *, and ^), A348089 (using +, -, *, /, and ^), A348262 (using + and ^).

Cf. A003037, A005520, A005208.

with(numtheory):
a:= proc(n) option remember; `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(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..100);  # Alois P. Heinz, Mar 08 2013

root[x_, n_] := With[{f = FactorInteger[x]}, Times @@ (f[[All, 1]]^(f[[All, 2]]/n))]; Clear[a]; a[n_] := a[n] = If[n == 1, 1, Min[Table[a[i] + a[n-i], {i, 1, n-1}], Table[a[d] + a[n/d], {d, Divisors[n][[2 ;; -2]]}], Table[a[root[n, p]] + a[p], {p, DeleteCases[Divisors[GCD @@ FactorInteger[n][[All, 2]]], 0|1]}]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Mar 12 2014, after Alois P. Heinz *)

from math import gcd
from sympy import divisors, factorint, integer_nthroot
from functools import cache
@cache
def a(n):
    if n == 1: return 1
    p = min(a(i)+a(n-1) for i in range(1, n//2+1))
    divs, m = divisors(n), n
    if len(divs) > 2:
        m = min(a(d)+a(n//d) for d in divs[1:len(divs)//2+1])
    f = factorint(n)
    edivs, e = divisors(gcd(*f.values())), n
    if len(edivs) > 1:
        e = min(a(integer_nthroot(n, r)[0])+a(r) for r in edivs[1:])
    return min(p, m, e)
print([a(n) for n in range(1, 88)]) # Michael S. Branicky, Mar 24 2024 after Alois P. Heinz

a(n) = A005208(n) + 1.

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

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

Offset: 1

Jens Voß, Dec 30 2003

nonn

Consider an alternate complexity measure b(n) which gives the minimum number of 1's necessary to build n using +, -, *, and / (where this additional operation is strict integer division, defined only for n/d where d|n). It turns out that b(n) coincides with a(n) for all n up to 50221174, see A348069. - Glen Whitney, Sep 23 2021

In respect of the previous comment: when creating A362471, where repunits are allowed, we found a difference if we allowed n/d with noninteger (intermediate) results. So, see also A362626. - Peter Munn, Apr 29 2023

			A091333(23) = 10 because 23 = (1+1+1+1) * (1+1+1) * (1+1) - 1. (Note that 23 is also the smallest index at which A091333 differs from A005245.)

Janis Iraids, Table of n, a(n) for n = 1..10000
Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arXiv:1409.0446 [math.NT], 2014.
Janis Iraids, A C program to compute the sequence
J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results. arXiv preprint arXiv:1203.6462 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 22 2012
Index to sequences related to the complexity of n

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

Cf. A348069, A362471, A362626.

from functools import cache
@cache
def f(m):
    if m == 0: return set()
    if m == 1: return {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])
                if x != y: out.add(abs(x-y))
    return out
def aupton(terms):
    tocover, alst, n = set(range(1, terms+1)), [0 for i in range(terms)], 1
    while len(tocover) > 0:
        for k in f(n) - f(n-1):
            if k <= terms:
                alst[k-1] = n
                tocover.discard(k)
        n += 1
    return alst
print(aupton(77)) # Michael S. Branicky, Sep 28 2021

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.

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

Original entry on oeis.org

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

Offset: 1

Robin Powell, Jan 25 2019

nonn

			a(14) = 7 because 14 = (1+1)^^(1+1+1)-1-1. (Note that 14 is also the smallest index at which this sequence differs from A091334.)

Wikipedia, Tetration
Index to sequences related to the complexity of n

Cf. A091333, A091334, A025280.

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,+,-,*,/,^}

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

Original entry on oeis.org

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

Offset: 1

Onno M. Cain, Nov 15 2019

nonn

A number n may be written from the digits of its binary representation using the 5 aforementioned operations whenever a(n) <= floor(log_2(n))+1.

			a(117) = 7 since 117 = ((1+1+1)!-1)!-1-1-1 is the representation of 117 with the operations +,-,*,^ and factorial requiring the fewest 1's.

O. M. Cain, The Exceptional Selfcondensability of Powers of Five, arXiv:1910.13829 [Math.HO], 2019.

Cf. A025280, A306560, A323727, A091334.

import math
delta_bound = 10
limit = 8*2**delta_bound
log_limit = math.log(limit)
def factorial(n):
  if n <= 1: return 1
  return n * factorial(n-1)
def condensings(a, b):
  result = []
  # Addition
  if a+b < limit: result.append(a+b)
  # Subtraction
  if a > b: result.append(a-b)
  # Multiplication
  if a*b < limit: result.append(a*b)
  # Division
  if a % b == 0: result.append(a//b)
  # Exponentiation
  if b*math.log(a) < log_limit: result.append(a**b)
  for n in result:
    if 2 < n < 10:
      fac = factorial(n)
      if fac < limit: result.append(fac)
  return result
# Create delta bound.
# "delta(n) = k" means k 1's are required to build up
# n from the operations in the 'condensings' function.
delta = dict()
delta[1] = 1
# Create inverse map.
delta_inv = {i:[] for i in range(1, delta_bound)}
for a in delta: delta_inv[delta[a]].append(a)
# Calculate delta.
for D in range(2, delta_bound):
  for A in range(1, D):
    B = D - A
    for a in delta_inv[A]:
      for b in delta_inv[B]:
        for c in condensings(a, b):
          if c >= limit: continue
          if c not in delta:
            delta[c] = D
            delta_inv[D].append(c)
a = 1
while a < limit:
  if not a in delta: break
  print(a, delta[a])
  a += 1

cp's OEIS Frontend

A005245 The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A025280 Complexity of n: number of 1's required to build n using +, *, and ^.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

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

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