A "1-expression" is a formula in which you add ($+$) or multiply ($\times$) the number 1 any number of times to create a natural number. Parentheses are allowed.

For example, you can create $22$ as follows:
$1 + 1 + ((1 + 1 + 1 + 1) × (1 + 1 + 1 + 1 + 1)) = 22$.
This is a 1-expression with 11 times a 1 in it.

You could also have done:
$1 + ((1 + 1 + 1) × (1 + ((1 + 1) × (1 + 1 + 1)))) = 22$.
This is a 1-expression with "1" only used ten times. Therefore, 10 is the minimum "1-value" of 22—that is, there is no 1-expression with which you can make 22 where you use a 1 less than 10 times.

Your task is to determine the minimum 1-value of 73.

  • Is concatenating allowed (e.g. combining 2 1s to form an 11)? – Excited Raichu Oct 16 at 13:39
  • 1
    @ExcitedRaichu I'd assume not or else the minimum 1s for the example with 22 would be 4 instead of 10, (11 +11) – gabbo1092 Oct 16 at 13:42
  • @gabbo1092 oh right lol – Excited Raichu Oct 16 at 13:42
  • See oeis.org/A005245 — the “minimal 1-value” there is called the complexity of the number. – celtschk Oct 16 at 16:05
up vote 8 down vote accepted

I may as well throw this out there:

$((1 + 1)*(1+1)*(1+1)*(1+1+1)*(1+1+1))+1$, for a total of 13 ones.

This was accomplished by multiplying together the prime factors of 72, and adding one.

  • How do you verify that $13$ is minimal? – Surb Oct 16 at 19:06
  • @Surb To be honest — I'm not entirely sure. I kinda guess-and-checked with aimless logic here and there. I guess my only proof is: "nobody has found one for 12". – Hugh Oct 16 at 20:01
  • @Surb if you're interested, check out oeis.org/A005245, posted by celtschk. It has some references to existing proofs. – Hugh Oct 16 at 20:04

I got this:

$$(1+1)\times(1+1)\times(1+1)\times(1+1+1)\times(1+1+1)+1 = 73$$ The minimum 1 value of 73 is 13

  • 1
    Sadly, Hugh was 10 seconds quicker... – Keelhaul Oct 16 at 13:49
  • 1
    Good job though. I guess we both went for the prime-factor-plus-one route. – Hugh Oct 16 at 13:50

Hugh and Keelhaul have already given correct solutions to the specific problem posed. If anyone wants to experiment with this, here's some fairly dumb Python code to find optimal solutions by brute force.

cache = {1: (1, '1')}
def best(n):
  try: return cache[n]
  except:
    cache[n] = best1(n)
    return cache[n]
def best1(n):
  (cost,expr) = (n*n,'fail')
  for m in range(1,n):
    c0,c1 = best(m),best(n-m)
    if c0[0]+c1[0]<cost: cost,expr = c0[0]+c1[0],c0[1]+'+'+c1[1]
    d = round(n/m)
    if m>1 and m*d==n:
      c0,c1 = best(m),best(d)
      if c0[0]+c1[0]<cost: cost,expr = c0[0]+c1[0],'('+c0[1]+')*('+c1[1]+')'
  return (cost,expr)

A few empirical observations: when n is composite the best solution is usually the product of solutions for some factors of n. For n=10, n=22, n=25, n=28, n=33 there are equally good solutions using factorizations of n-1 instead. I think n=46 is the first time it's strictly better not to factorize n: 2*(2+3*(1+2*3)) costs 13, while 1+3*3*5 costs only 12. I bet there are n for which the best solution is of form a*b+c*d, but after a small amount of experimenting I haven't found one yet.

  • For best(14) I get (8, '(1+1)*1+(1+1)*1+1+1))') with your code. While OEIS confirms the 8, the expression seems not quite right. – celtschk Oct 16 at 16:20
  • Oops, there's a missing open-parenthesis. Copy-and-paste error. Will fix. [EDITED to add:] Fixed now. Sorry about that. – Gareth McCaughan Oct 16 at 17:00
  • Now the expression makes more sense. Thanks. – celtschk Oct 16 at 18:47
  • From OEIS, we know that for $n=73$, the minimal number $\ge3\log_373$, or at least $12$. – TheSimpliFire Oct 16 at 19:41
  • @TheSimpliFire: Actually, from OEIS we know that for $n=73$ the value is exactly 13. – celtschk Oct 16 at 20:55

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.