cp's OEIS Frontend

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

%I A329526 #18 Dec 07 2019 17:23:56
%S A329526 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 A329526 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 A329526 8,8,8,7,8,8,8,9
%N A329526 Number of 1's required to build n using +, -, *, ^ and factorial.
%C A329526 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 A329526 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 A329526 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 A329526 (Python)
%o A329526 import math
%o A329526 delta_bound = 10
%o A329526 limit = 8*2**delta_bound
%o A329526 log_limit = math.log(limit)
%o A329526 def factorial(n):
%o A329526   if n <= 1: return 1
%o A329526   return n * factorial(n-1)
%o A329526 def condensings(a, b):
%o A329526   result = []
%o A329526   # Addition
%o A329526   if a+b < limit: result.append(a+b)
%o A329526   # Subtraction
%o A329526   if a > b: result.append(a-b)
%o A329526   # Multiplication
%o A329526   if a*b < limit: result.append(a*b)
%o A329526   # Division
%o A329526   if a % b == 0: result.append(a//b)
%o A329526   # Exponentiation
%o A329526   if b*math.log(a) < log_limit: result.append(a**b)
%o A329526   for n in result:
%o A329526     if 2 < n < 10:
%o A329526       fac = factorial(n)
%o A329526       if fac < limit: result.append(fac)
%o A329526   return result
%o A329526 # Create delta bound.
%o A329526 # "delta(n) = k" means k 1's are required to build up
%o A329526 # n from the operations in the 'condensings' function.
%o A329526 delta = dict()
%o A329526 delta[1] = 1
%o A329526 # Create inverse map.
%o A329526 delta_inv = {i:[] for i in range(1, delta_bound)}
%o A329526 for a in delta: delta_inv[delta[a]].append(a)
%o A329526 # Calculate delta.
%o A329526 for D in range(2, delta_bound):
%o A329526   for A in range(1, D):
%o A329526     B = D - A
%o A329526     for a in delta_inv[A]:
%o A329526       for b in delta_inv[B]:
%o A329526         for c in condensings(a, b):
%o A329526           if c >= limit: continue
%o A329526           if c not in delta:
%o A329526             delta[c] = D
%o A329526             delta_inv[D].append(c)
%o A329526 a = 1
%o A329526 while a < limit:
%o A329526   if not a in delta: break
%o A329526   print(a, delta[a])
%o A329526   a += 1
%Y A329526 Cf. A025280, A306560, A323727, A091334.
%K A329526 nonn
%O A329526 1,2
%A A329526 _Onno M. Cain_, Nov 15 2019