A306560 Smallest number of 1's required to build n using +, *, ^ and tetration.

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

Offset

1,2

Links

Table of n, a(n) for n=1..87.

Index to sequences related to the complexity of n

Example

a(16) = 5 because 16 = (1+1)^^(1+1+1). (Note that 16 is also the smallest index at which this sequence differs from A025280.)
a(34) = 8 because 34 = ((1+1)^^(1+1+1)+1)*(1+1). - Jens Ahlström, Jan 11 2023

Prog

(Python)
from functools import lru_cache
from sympy import factorint, divisors
tetration = {2**2**2: 5, 2**2**2**2: 6, 3**3: 5, 4**4: 6, 5**5: 7}
@lru_cache(maxsize=None)
def a(n):
    res = n
    if n < 6:
        return res
    if n in tetration:
        return tetration[n]
    for i in range(1, n):
        res = min(res, a(i) + a(n-i))
    for d in [i for i in divisors(n) if i not in {1, n}]:
        res = min(res, a(d) + a(n//d))
    factors = factorint(n)
    exponents = set(factors.values())
    if len(exponents) == 1:
        e = exponents.pop()
        if e > 1:
            res = min(res, a(sum(factors.keys())) + a(e))
    return res
# Jens Ahlström, Jan 11 2023

Crossrefs

Cf. A005245, A025280, A323727.

Sequence in context: A323727 A348089 A091334 * A025280 A365092 A096365

Adjacent sequences: A306557 A306558 A306559 * A306561 A306562 A306563

Keyword

nonn

Author

Robin Powell, Feb 23 2019

Extensions

a(34) onward corrected by Jens Ahlström, Jan 11 2023

Status

approved