IBM Ponder This #270 · October 2020

This month's challenge is dedicated to the memory of Frances Allen, who passed away in August. Among her many accomplishments is the invention of the control-flow graph, in her 1970 paper "Control flow analysis"

The control-flow graph of a program contains a node for each code block that has exactly one entry and one exit point (i.e., there are no jump commands inside the block) and an edge A -> B that indicates a possible transition from the last line of A to the first line of B (due to a jump command or simply B being placed right after A).

We introduce a toy programming "language" with the following limited set of commands:1. "X = Y" where X and Y are either strings indicating variable names, or literal integers. 2. "X = Y OP Z" where X, Y, Z are either strings or literal integers, and "OP" belongs to the set {+, -, *, /, %} with the usual meaning for this operations. 3. "JMP A" where A is an integer, meaning the program jumps to the line denoted by A. 4. "JMP_ZERO X A" where X is a string indicating a variable, and the program jumps to A only if X is 0. 5. "RETURN X" which should be **the last line** in the program, denoting its return value. 6. "CHAOS LINES" which indicates a random jump to one of the lines in LINES, which is a comma-separated list of integers.

A program consists of a sequence of lines, each containing a line number followed by an instruction.

Your goal: Find a program with at most **20** lines that starts with

 10 A = a
 20 B = b

Where "a" and "b" are integers such that a > b, and that returns the greatest common divisor of a and b (for any a, b), such that in the program's control-flow graph, the number of paths from the entry node to the exit node of length $n$ is the sequence

0, 2, 2, 5, 8, 17, 32, 65, 128, 257,...

(https://oeis.org/A052531)

A bonus '*' for finding another program returning the greatest common divisor, such that the sequence of the number of paths from the entry to the exit node contains the number "1970" after at most 20 elements.

Here's a sample program, along with its control-flow graph:

 10 A = 20
 20 B = 20
 30 C = A - B
 40 JMP_ZERO C 70
 50 C = A - 20
 60 CHAOS 30, 40, 80
 70 JMP 90
 80 JMP 30
 90 RETURN A

Solution

Best opened after a real attempt

To be added.