Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
superprismatic

Straight Lining

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.

Share this post


Link to post
Share on other sites

18 answers to this question

  • 0
CaptainEd    19

My "senior moment" above was doubly erroneous. I thought I was wrong, but I was mistaken. 1 2 3 9 8 (=9-1) 64 128 137(=128+9) is also 7 steps after the 1.

Share this post


Link to post
Share on other sites
  • 0
phil1882    13

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.

Share this post


Link to post
Share on other sites
  • 0
TheChad08    14

3*3 = 9, you're allowed to use any combination of previous values to get the next one.

I assumed that we always had to use the most previous value when determining the next.

EDIT:

Is it really linear if we aren't forced to use the previous value?

Edited by TheChad08

Share this post


Link to post
Share on other sites
  • 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.

Share this post


Link to post
Share on other sites
  • 0

You guys are much better than me at doing this. I fooled around with

311 for some time, and I can't do it with an 8-long program (including

the first 1). But eventually I got a 9-long which ended in 311. Can

you guys do it in an 8-long, like you did with the previous numbers?

Share this post


Link to post
Share on other sites
  • 0

1 2 4 6 24 144 288 312 311

is my personal "best fit".

Nice, but do you have any reason to believe there is no 8-long?

If you look at the end of my 9-long, you'll see that it ends in what

are almost "wasted" moves:

1 2 3 9 18 324 315 312 311

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×