Problem of the Week 1073

They Said It Couldn't Be Done

A classic puzzle is to write positive integers as a combination of 1, 2, 3, 4 using the operations of addition, subtraction, multiplication, division, and exponentiation (and as many parentheses as you like), using each of the numbers exactly once. For example, 33 = 1 + 4³/2, or 1 + 4 × 2³. It turns out that 34 is the smallest number having no such representation.

It had been believed that 791 is the smallest number with no representation in terms of 1, 2, 3, 4, 5, and 6. But this is not so, as discovered recently by Bruce Torrence.

Express 791 using the numbers 1, 2, 3, 4, 5, 6 and the five basic operations above.

Extra credit: Do the same for 1, 2, 3, ..., 790. But there must have been something subtle about 791, since that was thought impossible.

Note: Bruce observed that it does not matter whether one insists that each of the numbers be used. For one can combine any unused numbers (other than 1) into a sum S and then either multiply an expression by 1^S (if 1 is not used in it) or replace 1 by 1^S (if 1 is used in it).

Source: Bruce Torrence, "Arithmetic combinations," Mathematica in Education and Research, 12:1 (2007) 47-59. See also sequence A071794, which (prior to Bruce's work) contained the incorrect value 791 in the sequence 2, 4, 11, 34, 178, 791. Bruce's computation shows that it is quite likely that the correct first-missing value for 6 numbers (called a(6)) is 926.

5 March 2007