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

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.

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.

Until n = 10 the terms are equal to A005520(n) where subtraction is not allowed.

Here, fractions are not allowed as intermediate results.

See A362626 for the variant that allows such fractions. The sequences differ first at a(74) and its immediate neighbors, since a(74) = 8 > 7 = A362626(74). See the example in A362626. - Peter Munn, Apr 28 2023

Numbers n such that A005245(n) > A091333(n). Is it true that a(n) ~ n?

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