cp's OEIS Frontend

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

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

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

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.

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.

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.