Can a line be constructed that ends in any positive integer whatsoever?

[BicycleTree]

I had this idea this morning and was going to make another "figure-out-the-sequence" out of it, until it occurred to me that it was slightly more interesting than that.

Consider the following procedure: start a line with 0 2, and add on additional numbers as you please so long as the following condition is met for each additional number: label the preceding two numbers from the one you are adding on a and b (in order) and the new number must be a - b, a + b, a / b, or a * b.

Here are lines made by that procedure that end in the numbers 1-4 respectively:
0 2 2 1
(0 + 2 = 2, 2 / 2 = 1)
0 2
(no additional numbers added)
0 2 2 1 3
(0 + 2 = 3, 2 / 2 = 1, 2 + 1 = 3)
0 2 2 4
(0 + 2 = 2, 2 * 2 = 4)

I ended it here because 5 is the first one that's a little bit harder.


Puzzlers:
1. Find lines ending in numbers as high as you can (say, shoot for 20; I just did 11).

2. Given that the last number so far on a line is x, how can you append numbers so that the number -x is the last on the line?

3. Given that the last two numbers in a line are arbitrary x y, can you append numbers until the line ends in y x? (note: if the last two numbers are x y, you can append x - y but not y - x)

4. Given that the last number on a line is arbitrary x, can you append numbers until the line ends in x 1 or in 1 x?

5. Can a line be constructed that ends in any positive integer whatsoever?


I do not know the answers to 3 and 4 at present. If, in thinking about this, you come up with other puzzlers about this type of sequence, feel free to add them to the thread.

 

[BicycleTree]

Here's some more idea of what I mean, in the form of lines ending in numbers from 1 to 9. Complete these up to 30:

0 2 2 1
0 2
0 2 2 1 3
0 2 2 4
0 2 2 1 3 -2 5 (slightly tricky)
0 2 2 4 6
0 2 2 1 3 4 7
0 2 2 4 8
0 2 2 1 3 3 9


---------------------
To be clear, this is how you can make 5:
0 2
(start of line) Now the next number can be 2 (= 0 + 2), -2 (=0 - 2), 0 (=0 * 2), or 0 (= 0 / 2). In this case I chose 2.
0 2 2
Now the next number can be 4 (= 2 + 2), 0 (= 2 - 2), 4 (= 2 * 2), or 1 (= 2 / 2). In this case I chose 1.
0 2 2 1
Now the next number can be 3 (= 2 + 1), 1 (= 2 - 1), 2 (= 2 * 1), or 2 (= 2 / 1). In this case I chose 3.
0 2 2 1 3
Now the next number can be 4 (= 1 + 3), -2 (= 1 - 3), 3 (= 1 * 3), or 1/3 (= 1 / 3). In this case I chose -2.
0 2 2 1 3 -2
Now the next number can be 1 (= 3 + (-2)), 5 (= 3 - (-2)), -6 (= 3 * (-2)), or -1.5 (= 3 / (-2)). In this case I chose 5.
0 2 2 1 3 -2 5

 

[ssj5harsh]

Thanks for the clarification bicycletree. I've gotten pretty high numbers, obviously, there isn't a limit to the series. Those number with a lot of factors are particularly easy. I can't seem to get any of the higher primes(like 17, 31, 53, etc.). I can also get quite a large number of fractions. I'm still working on it though.

 

[BicycleTree]

Well, any integer can be constructed--in fact I figured out a general method that will do so, although the line it makes for a given number n is somewhat longer than n is large. Doing 17 (without that method) was a little tricky:
0 2 2 1 3 4 7 11 -4 7 3 10 -7 17

You can get 31 from 17:
0 2 2 1 3 4 7 11 -4 7 3 10 -7 17 -24 -7 -31 22 -7 31

And you can get 53 from 31:
0 2 2 1 3 4 7 11 -4 7 3 10 -7 17 -24 -7 -31 22 -7 31 22 53

 

[BicycleTree]

I have 4 procedures for negating a number. Here's one of them, the second one I discovered:

a b (a+b) (a+2b) -b

What are the other 3?

 

[BicycleTree]

I did some more thinking about this last night and discovered that yes, it is possible to create a line ending in x 1 or 1 x from a line ending in x.

So the only question of the original five that I don't know the answer to is whether you can create a line ending in y x from a line ending in x y. My feeling at the moment is no; in fact, I know that you can't do it in a straightforward manner using addition and subtraction only. Looking at each new appended number algebraically as (nx+my), you can't get y x explicitly. Puzzle: how do you prove that?

Also, here is an additional question: can you create any rational number whatsoever? Or, more broadly, can you create a line ending in any two integers whatsoever?

 

[AKG]

Getting 20:
0 2
0 2 2 +
0 2 2 1 /
0 2 2 1 3 +
0 2 2 1 3 4 +
0 2 2 1 3 4 12 x
0 2 2 1 3 4 12 16 +
0 2 2 1 3 4 12 16 -4 -
0 2 2 1 3 4 12 16 -4 20 -

 

[gerben]

I have 4 procedures for negating a number. Here's one of them, the second one I discovered:

a b (a+b) (a+2b) -b

What are the other 3?

(+, +, -) a b a+b a+2b -b
(-, +, -) a b a-b a -b
(*, +, -) a b ab b+ab -b
(/, +, -) a b a/b b+a/b -b

(*, /, *, +, +, -) a b ab 1/a b (1/a)+b (1/a)+2b -b
(*, /, *, -, +, -) a b ab 1/a b (1/a)-b 1/a -b
(*, /, *, *, +, -) a b ab 1/a b b/a b+b/a -b
(*, /, *, /, +, -) a b ab 1/a b 1/(ab) b+1/(ab) -b

(/, /, *, *, +, +, -) a b a/b bb/a b b+bb/a 2b+bb/a -b
(/, /, *, *, -, +, -) a b a/b bb/a b b-b/a 2b-b/a -b
(/, /, *, *, *, +, -) a b a/b bb/a b bbb/a b+bbb/a -b
(/, /, *, *, /, +, -) a b a/b bb/a b b/a b+b/a -b


(*, *, /, *, *, -, +, -, /) a b ab abb 1/b ab a ab-a ab -a -b

[/color]

 

[BicycleTree]

Yep, Gerben--the first four of those are what I had in mind. The next eight are just variations on the first four (you just did some operations to get b again, and then applied one of the first four) but the last one is interesting.

Here's my sequence for all the integers:
+ + - - - + + + - ...
a b a+b a+2b -b a+3b -a-4b -b -a-5b -a-6b b ...
When a = 0 and b = 1, which you can get from 0 2 2 1 1 0 1, this creates every integer or the negation of that integer. Although it does take a long time for larger integers. Anyone know a shorter way (besides brute force)?

 

[BicycleTree]

I have figured out the remaining puzzles. So here is the remaining list of questions, which I have the answer to:

1. Given that the last two numbers in a line are arbitrary x y, can you append numbers until the line ends in y x? (note: if the last two numbers are x y, you can append x - y but not y - x) (yes)

2. Given that the last number on a line is arbitrary x, can you append numbers until the line ends in x 1 or in 1 x? (yes)

3. Can a line be constructed that ends in any positive integer whatsoever? (yes--I have answered this one though a quicker answer may exist, and it's necessary in order to solve the other questions)

4. Can any rational number be constructed? (yes)

5. Can a line be constructed that ends in any two integers whatsoever? (yes)

6. Given that a line ends in x y, does there exist a single sequence of operations involving only addition and subtraction that can always be applied to make the line end in y x? (no)

And here is a puzzle I have not solved:
7. Given that a line ends in x y, does there exist a single sequence of operations that can always be applied to make the line end in y x?

 

[Alkatran]

Trivial answer:

0 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1

0+2
2/2
2/1
1*2
2/2
2/1
1*2
...repeat