Jump to content
BrainDen.com - Brain Teasers
  • 0

Straight Lining


superprismatic
 Share

Question

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.

Link to comment
Share on other sites

18 answers to this question

Recommended Posts

  • 0

question: is division ever faster? the opening post mentioned that it affects the problem, but i think multiplication, addition and subtraction are enough to get any minimum number of steps. I'm not sure if even subtraction is necessary.

No, the article I referred to in the original post was talking about a different aspect of straight line programs.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...