|
%I #17 Aug 04 2018 14:38:54
%S 1,2,3,5,8,12,18,27,41,62,93,140,210,315,473,710,1065,1598,2397,3596,
%T 5394,8091,12137,18206,27309,40964,61446,92169,138254
%N 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]}
%C 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 k-th register. The instruction pointer then moves to the next instruction. d[k,l] means decrement the k-th 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.
%C Is this the same as A061419? - _R. J. Mathar_, Feb 19 2009
%C 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 1-4 is only entered at 4, we apply two small program transformations and then collapse instructions 1-3: 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*(b-1) 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
%D Wolfram, S., A New Kind of Science. Champaign, IL: Wolfram Media, pp. 97-102, 2002.
%F a(n) = A061419(n), as shown in the comments.
%Y Cf. A156622, the corresponding sequence for the first register of this machine.
%K nonn
%O 1,2
%A _Jack W Grahl_, Feb 11 2009
%E Mathar's suggested identity of this sequence verified by _Glen Whitney_, Aug 03 2018
|
