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,2

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.

Links

Table of n, a(n) for n=1..76.

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

Example

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.

Prog

(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

Crossrefs

Cf. A025280, A306560, A323727, A091334.

Sequence in context: A117391 A129456 A030412 * A160371 A059686 A101083

Adjacent sequences: A329523 A329524 A329525 * A329527 A329528 A329529

Keyword

nonn

Author

Onno M. Cain, Nov 15 2019

Status

approved