11
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ How do you verify that $13$ is minimal? $\endgroup$ – Surb Oct 16 '18 at 19:06
  • $\begingroup$ @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". $\endgroup$ – Hugh Oct 16 '18 at 20:01
  • $\begingroup$ @Surb if you're interested, check out oeis.org/A005245, posted by celtschk. It has some references to existing proofs. $\endgroup$ – Hugh Oct 16 '18 at 20:04
3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – celtschk Oct 16 '18 at 16:20
  • $\begingroup$ Oops, there's a missing open-parenthesis. Copy-and-paste error. Will fix. [EDITED to add:] Fixed now. Sorry about that. $\endgroup$ – Gareth McCaughan Oct 16 '18 at 17:00
  • $\begingroup$ Now the expression makes more sense. Thanks. $\endgroup$ – celtschk Oct 16 '18 at 18:47
  • $\begingroup$ From OEIS, we know that for $n=73$, the minimal number $\ge3\log_373$, or at least $12$. $\endgroup$ – TheSimpliFire Oct 16 '18 at 19:41
  • $\begingroup$ @TheSimpliFire: Actually, from OEIS we know that for $n=73$ the value is exactly 13. $\endgroup$ – celtschk Oct 16 '18 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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