

A156623


Values of register b when register a becomes 0 for the two register machine {i[1], i[1], i[1], d[2,1], d[1,6], i[2], d[1,5], d[2,3]}


1



1, 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, 140, 210, 315, 473, 710, 1065, 1598, 2397, 3596, 5394, 8091, 12137, 18206, 27309, 40964, 61446, 92169, 138254
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The instructions of this two register counting machine are to be interpreted as follows: Two registers are initialized to zero, and the instruction pointer starts on the first instruction. i[k] means increment the kth register. The instruction pointer then moves to the next instruction. d[k,l] means decrement the kth register if it is nonzero, and then change the instruction pointer to l. Otherwise move the instruction pointer to the next instruction. The following set of 8 instructions is given in the book 'A New Kind of Science' by Stephen Wolfram as one of the simplest register machines which has complex behavior. {i[1], i[1], i[1], d[2,1], d[1,6], i[2], d[1,5], d[2,3]} This sequence distills information about the states of the register machine by including only the values of the 2nd register, at those times when the first register has just been decremented to zero.
Is this the same as A061419?  R. J. Mathar, Feb 19 2009
Indeed, this sequence is identical to A061419: To see this, we will create a sequence of programs each equivalent to the register machine. First, rewrite the instructions in "C" programming language notation, with unsigned integers a and b for the first and second registers: P1~{0: a=0,b=0; 1: a++; 2: a++; 3: a++; 4: if (b) goto 1; 5: a; 6: b++; 7: if (a) goto 5; 8: b,goto 3;}. Note that the condition on a is omitted in instruction 5 because control goes to 6 in any case, and the condition on b is omitted in instruction 8 because b was just incremented in 6, so b > 0 whenever instruction 8 is reached. Next, to ensure that the loop in instructions 14 is only entered at 4, we apply two small program transformations and then collapse instructions 13: P2~{0: a=3,b=0,goto 4; 1: a+=3; 4: if (b) goto 1; 5: a; 6: b++; 7: if (a) goto 5; 8: b,a++,goto 4;}. Now note we cannot proceed past instruction 4 unless b is zero, and we cannot proceed past instruction 7 unless a is zero. Hence we can rewrite the program with explicit loops: P3~{0: a=3,b=0; 4: while (b) a+=3; 7: do {a,b++} while (a); 8: b,a++,goto 4;}. But now the effect of the two loops is clear, so we may rewrite: P4~{0: a=3,b=0; 4: a+=3*b, b=0; 7: b=floor(a/2)+1,a=0; 8: b,a++,goto 4;}. We can now collapse 7 and 8: P5~{0: a=3,b=0; 4: a+=3*b, b=0; 7: b=floor(a/2),a=1,goto 4;} And now we can discard the instruction numbering altogether and see that the equivalent "C" program is P6 ~ a=3; b=0; while (true) {b=floor(a/2); a=3*b+1;}. Finally, we can eliminate a to get that the effect on register b is P7 ~ b=1; while (true) {b = floor((3*b+1)/2);}. Looking back at the loop at instruction 7 in P3, we see that a reaches zero just before the final increment to b, at which point b has the value floor(a/2), for the value of a at the entry to that loop. Hence, the successive values of b in P7 are precisely the successive values of this sequence. Moreover, for b a natural number, floor((3b+1)/2) = ceiling(3b/2). Hence, this sequence is precisely b(1) = 1, b(n+1) = ceiling(3b(n)/2), which is exactly the definition of A061419. Further, we can see that the register b reaches 0 just before the final increment to a in the loop at statement 4 of P3, so when a is 1 + 3*(b1) for the value of b at the entry to that loop. This last observation is to verify the formula for A156622.  Glen Whitney, Aug 03 2018


REFERENCES

Wolfram, S., A New Kind of Science. Champaign, IL: Wolfram Media, pp. 97102, 2002.


LINKS

Table of n, a(n) for n=1..29.


FORMULA

a(n) = A061419(n), as shown in the comments.


CROSSREFS

Cf. A156622, the corresponding sequence for the first register of this machine.
Sequence in context: A077868 A109537 A081226 * A061419 A130732 A018135
Adjacent sequences: A156620 A156621 A156622 * A156624 A156625 A156626


KEYWORD

nonn


AUTHOR

Jack W Grahl, Feb 11 2009


EXTENSIONS

Mathar's suggested identity of this sequence verified by Glen Whitney, Aug 03 2018


STATUS

approved



