I recently read an article in the American Mathematical Monthly,
August-September 2012, about straight line programs. The article,
by Peter Borwein and Joe Hobart, was about how these things would be
affected by allowing the division operation. But a rather simple idea
for a puzzle formed in my head after reading it. So, here it is:
A straight line program is a sequence of integers p1,p2,p3,....,pn
such that p1=1 and pi is the sum, difference, or product of pk and pl
where k and l are both less than i. It is OK if k=l. So, for example,
one possible straight line program which ends in 12 is 1,2,4,3,12. To be
explicit, p1=1, p2=p1+p1, p3=p2+p2, p4=p3-p1, p5=p4*p3.
Find a shortest straight line program ending in 137.