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

Author

Robin Powell, Feb 23 2019

Keywords

• nonn

Examples

			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
		

Links

• Index to sequences related to the complexity of n

Crossrefs

Cf. A005245, A025280, A323727.

Programs

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

Extensions

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