superprismatic Posted August 25, 2012 Report Share Posted August 25, 2012 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. Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 26, 2012 Report Share Posted August 26, 2012 1 2 4 8 16 128 136 137 is as small as i can get. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 27, 2012 Report Share Posted August 27, 2012 (edited) oops, another senior moment... Except I admire the problem and Phil's solution! Edited August 27, 2012 by CaptainEd Quote Link to comment Share on other sites More sharing options...
0 TheChad08 Posted August 27, 2012 Report Share Posted August 27, 2012 Yeah, I can't get better than Phil's. I can tie it if I am allowed to use division. Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 27, 2012 Report Share Posted August 27, 2012 how about this tie sequence... 1 2 3 5 9 27 135 137 Quote Link to comment Share on other sites More sharing options...
0 TheChad08 Posted August 27, 2012 Report Share Posted August 27, 2012 how about this tie sequence... 1 2 3 5 9 27 135 137 How'd you get from the 5 to the 9 in one move? Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 27, 2012 Report Share Posted August 27, 2012 3*3 = 9, you're allowed to use any combination of previous values to get the next one. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 27, 2012 Report Share Posted August 27, 2012 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. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 28, 2012 Author Report Share Posted August 28, 2012 Nice going, guys! If you'd like to try another, I think that 277 is pretty hard. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 28, 2012 Report Share Posted August 28, 2012 (edited) 1 2 4 5 16 256 272 277 Phil taught me all I know... Edited August 28, 2012 by CaptainEd Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 28, 2012 Report Share Posted August 28, 2012 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. Quote Link to comment Share on other sites More sharing options...
0 TheChad08 Posted August 28, 2012 Report Share Posted August 28, 2012 (edited) 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 August 28, 2012 by TheChad08 Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 28, 2012 Report Share Posted August 28, 2012 edit: subtraction is clearly nessicary in some edge cases, such as 1023. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 28, 2012 Author Report Share Posted August 28, 2012 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. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 29, 2012 Author Report Share Posted August 29, 2012 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? Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 29, 2012 Report Share Posted August 29, 2012 1 2 4 6 24 144 288 312 311 is my personal "best fit". Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 29, 2012 Author Report Share Posted August 29, 2012 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 Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 30, 2012 Report Share Posted August 30, 2012 I'm pretty sure, I've tried several approaches, including powers of 3, and 5. Quote Link to comment Share on other sites More sharing options...
0 phil1882 Posted August 30, 2012 Report Share Posted August 30, 2012 by the way, there is one with 8 if you allow division. 1 2 3 5 25 625 622 311 Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
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
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.