login
This site is supported by donations to The OEIS Foundation.

 

Logo


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[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 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.

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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 20:50 EDT 2019. Contains 326155 sequences. (Running on oeis4.)