Followers 0

# Straight Lining

## 19 posts in this topic

Posted · Report post

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.

0

##### Share on other sites

Posted · Report post

1 2 4 8 16 128 136 137

is as small as i can get.

0

##### Share on other sites

Posted (edited) · Report post

oops, another senior moment...

Except I admire the problem and Phil's solution!

Edited by CaptainEd
0

##### Share on other sites

Posted · Report post

Yeah, I can't get better than Phil's.

I can tie it if I am allowed to use division.

0

##### Share on other sites

Posted · Report post

1 2 3 5 9 27 135 137

0

##### Share on other sites

Posted · Report post

1 2 3 5 9 27 135 137

How'd you get from the 5 to the 9 in one move?

0

##### Share on other sites

Posted · Report post

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

0

##### Share on other sites

Posted · Report post

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.

0

##### Share on other sites

Posted · Report post

Nice going, guys! If you'd like to try another, I think that 277 is pretty hard.

0

##### Share on other sites

Posted (edited) · Report post

1 2 4 5 16 256 272 277

Phil taught me all I know...

Edited by CaptainEd
0

##### Share on other sites

Posted · Report post

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.

0

##### Share on other sites

Posted (edited) · Report post

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?

0

##### Share on other sites

Posted · Report post

edit: subtraction is clearly nessicary in some edge cases, such as 1023.

0

##### Share on other sites

Posted · Report post

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.

0

##### Share on other sites

Posted · Report post

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?

0

##### Share on other sites

Posted · Report post

1 2 4 6 24 144 288 312 311

is my personal "best fit".

0

##### Share on other sites

Posted · Report post

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

0

##### Share on other sites

Posted · Report post

I'm pretty sure, I've tried several approaches, including powers of 3, and 5.

0

##### Share on other sites

Posted · Report post

by the way, there is one with 8 if you allow division.

1 2 3 5 25 625 622 311

0

## Create an account

Register a new account