A323727 -id:A323727 - cp's OEIS frontend

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

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

Offset: 1

Robin Powell, Feb 23 2019

nonn

			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.)
a(34) = 8 because 34 = ((1+1)^^(1+1+1)+1)*(1+1). - _Jens Ahlström_, Jan 11 2023

Index to sequences related to the complexity of n

Cf. A005245, A025280, A323727.

from functools import lru_cache
from sympy import factorint, divisors
tetration = {2**2**2: 5, 2**2**2**2: 6, 3**3: 5, 4**4: 6, 5**5: 7}
@lru_cache(maxsize=None)
def a(n):
    res = n
    if n < 6:
        return res
    if n in tetration:
        return tetration[n]
    for i in range(1, n):
        res = min(res, a(i) + a(n-i))
    for d in [i for i in divisors(n) if i not in {1, n}]:
        res = min(res, a(d) + a(n//d))
    factors = factorint(n)
    exponents = set(factors.values())
    if len(exponents) == 1:
        e = exponents.pop()
        if e > 1:
            res = min(res, a(sum(factors.keys())) + a(e))
    return res
# Jens Ahlström, Jan 11 2023

a(34) onward corrected by Jens Ahlström, Jan 11 2023

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

Original entry on oeis.org

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

Onno M. Cain, Nov 15 2019

nonn

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.

			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. M. Cain, The Exceptional Selfcondensability of Powers of Five, arXiv:1910.13829 [Math.HO], 2019.

Cf. A025280, A306560, A323727, A091334.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions