cp's OEIS Frontend

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

%I A306560 #27 Feb 07 2023 15:09:55
%S A306560 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,
%T A306560 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,
%U A306560 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
%N A306560 Smallest number of 1's required to build n using +, *, ^ and tetration.
%H A306560 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A306560 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.)
%e A306560 a(34) = 8 because 34 = ((1+1)^^(1+1+1)+1)*(1+1). - _Jens Ahlström_, Jan 11 2023
%o A306560 (Python)
%o A306560 from functools import lru_cache
%o A306560 from sympy import factorint, divisors
%o A306560 tetration = {2**2**2: 5, 2**2**2**2: 6, 3**3: 5, 4**4: 6, 5**5: 7}
%o A306560 @lru_cache(maxsize=None)
%o A306560 def a(n):
%o A306560     res = n
%o A306560     if n < 6:
%o A306560         return res
%o A306560     if n in tetration:
%o A306560         return tetration[n]
%o A306560     for i in range(1, n):
%o A306560         res = min(res, a(i) + a(n-i))
%o A306560     for d in [i for i in divisors(n) if i not in {1, n}]:
%o A306560         res = min(res, a(d) + a(n//d))
%o A306560     factors = factorint(n)
%o A306560     exponents = set(factors.values())
%o A306560     if len(exponents) == 1:
%o A306560         e = exponents.pop()
%o A306560         if e > 1:
%o A306560             res = min(res, a(sum(factors.keys())) + a(e))
%o A306560     return res
%o A306560 # _Jens Ahlström_, Jan 11 2023
%Y A306560 Cf. A005245, A025280, A323727.
%K A306560 nonn
%O A306560 1,2
%A A306560 _Robin Powell_, Feb 23 2019
%E A306560 a(34) onward corrected by _Jens Ahlström_, Jan 11 2023