The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A156623 Values of register b when register a becomes 0 for the two register machine {i, i, i, d[2,1], d[1,6], i, 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 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, i, i, d[2,1], d[1,6], i, 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 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 REFERENCES Wolfram, S., A New Kind of Science. Champaign, IL: Wolfram Media, pp. 97-102, 2002. LINKS 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 1 07:45 EDT 2021. Contains 346384 sequences. (Running on oeis4.)