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

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, 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, 8, 8, 8, 7, 8, 8, 8, 9

Offset: 1

Author

Onno M. Cain, Nov 15 2019

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

• O. M. Cain, The Exceptional Selfcondensability of Powers of Five, arXiv:1910.13829 [Math.HO], 2019.

Crossrefs

Cf. A025280, A306560, A323727, A091334.

Programs

Python

import math
delta_bound = 10
limit = 8*2**delta_bound
log_limit = math.log(limit)
def factorial(n):
  if n <= 1: return 1
  return n * factorial(n-1)
def condensings(a, b):
  result = []
  # Addition
  if a+b < limit: result.append(a+b)
  # Subtraction
  if a > b: result.append(a-b)
  # Multiplication
  if a*b < limit: result.append(a*b)
  # Division
  if a % b == 0: result.append(a//b)
  # Exponentiation
  if b*math.log(a) < log_limit: result.append(a**b)
  for n in result:
    if 2 < n < 10:
      fac = factorial(n)
      if fac < limit: result.append(fac)
  return result
# Create delta bound.
# "delta(n) = k" means k 1's are required to build up
# n from the operations in the 'condensings' function.
delta = dict()
delta[1] = 1
# Create inverse map.
delta_inv = {i:[] for i in range(1, delta_bound)}
for a in delta: delta_inv[delta[a]].append(a)
# Calculate delta.
for D in range(2, delta_bound):
  for A in range(1, D):
    B = D - A
    for a in delta_inv[A]:
      for b in delta_inv[B]:
        for c in condensings(a, b):
          if c >= limit: continue
          if c not in delta:
            delta[c] = D
            delta_inv[D].append(c)
a = 1
while a < limit:
  if not a in delta: break
  print(a, delta[a])
  a += 1