A329526 - OEIS

%I #18 Dec 07 2019 17:23:56

%S 1,2,3,4,4,3,4,5,5,6,6,5,6,6,7,6,7,6,7,7,7,6,5,4,5,6,6,7,8,7,7,6,7,7,

%T 6,5,6,7,8,7,8,7,8,8,8,7,7,6,6,7,8,8,9,8,9,9,9,8,7,6,7,7,6,5,6,7,8,9,

%U 8,8,8,7,8,8,8,9

%N Number of 1's required to build n using +, -, *, ^ and factorial.

%C A number n may be written from the digits of its binary representation using the 5 aforementioned operations whenever a(n) <= floor(log_2(n))+1.

%H O. M. Cain, <a href="https://arxiv.org/abs/1910.13829">The Exceptional Selfcondensability of Powers of Five</a>, arXiv:1910.13829 [Math.HO], 2019.

%e a(117) = 7 since 117 = ((1+1+1)!-1)!-1-1-1 is the representation of 117 with the operations +,-,*,^ and factorial requiring the fewest 1's.

%o (Python)

%o import math

%o delta_bound = 10

%o limit = 8*2**delta_bound

%o log_limit = math.log(limit)

%o def factorial(n):

%o   if n <= 1: return 1

%o   return n * factorial(n-1)

%o def condensings(a, b):

%o   result = []

%o   # Addition

%o   if a+b < limit: result.append(a+b)

%o   # Subtraction

%o   if a > b: result.append(a-b)

%o   # Multiplication

%o   if a*b < limit: result.append(a*b)

%o   # Division

%o   if a % b == 0: result.append(a//b)

%o   # Exponentiation

%o   if b*math.log(a) < log_limit: result.append(a**b)

%o   for n in result:

%o     if 2 < n < 10:

%o       fac = factorial(n)

%o       if fac < limit: result.append(fac)

%o   return result

%o # Create delta bound.

%o # "delta(n) = k" means k 1's are required to build up

%o # n from the operations in the 'condensings' function.

%o delta = dict()

%o delta[1] = 1

%o # Create inverse map.

%o delta_inv = {i:[] for i in range(1, delta_bound)}

%o for a in delta: delta_inv[delta[a]].append(a)

%o # Calculate delta.

%o for D in range(2, delta_bound):

%o   for A in range(1, D):

%o     B = D - A

%o     for a in delta_inv[A]:

%o       for b in delta_inv[B]:

%o         for c in condensings(a, b):

%o           if c >= limit: continue

%o           if c not in delta:

%o             delta[c] = D

%o             delta_inv[D].append(c)

%o a = 1

%o while a < limit:

%o   if not a in delta: break

%o   print(a, delta[a])

%o   a += 1

%Y Cf. A025280, A306560, A323727, A091334.

%K nonn

%O 1,2

%A _Onno M. Cain_, Nov 15 2019