2.1.1 Description

2.1.2 Solution

First, we deparse the op-codes by identifying jumps and loops:

x5=123

<--+

x5=x5&456

   |

x5=(x5==72)?1:0

   |

x1+=x5

---+

jump if x5 != 72

x5=0

<--------------+

x4=x5|65536

               |

x5=3935295

<----------+   |

x2=x4&255

           |   |

x5+=x2

           |   |

x5=x5&16777215

           |   |

x5*=65899

           |   |

x5=x5&16777215

           |   |

x2=x4<256?1:0

           |   |

x1+=x2

           |   |

x1++

---+       |   |

jump if x4 < 256

   |       |   |

x2=0

<--|-------|---|---+

x3=x2+1

   |       |   |   |

x3*=256

   |       |   |   |

x3=(x3>x4)?1:0

   |       |   |   |

x1+=x3

   |       |   |   |

x1++

---|---+   |   |   |

jump if x3 > x4

   |   |   |   |   |

x2++

---|---|---|---|---+

<--|---+   |   |

x4=x2

---|-------+   |

<--+           |

x2=(x5==x0)?1:0

               |

x1+=x2

---------------+

jump if x5 != x0

That is the code boils down to the following logic:

1. Lines 1 - 5 do not do anything useful as x5 is anyways reset in line 6.
2. Lines 9 - 28: in the first iteration x2 is zero and we setup x5 and x4. Then as long as x4 is greater or equal than 256 we will find the largest x2 such that 256 * x2 <= x4 in a loop.
3. We use this x2 to update x5 in the next iteration. x4 is also updated and the iteration starts again.
4. Line 29 is the only possibility to stop the infinite loop. If we set x0 to match (any) generated x5 the program will terminate.

Hence, to solve the first part we have to generate the first x5 and set x0 to this value.

N.B. As we need bit 64 bitwise operations, we include a simple C++ code to avoid the need to work on bit vectors in R for speed reasons.

#include <Rcpp.h>

Rcpp::NumericVector bitwOp64(Rcpp::NumericVector a, Rcpp::NumericVector b, 
                             int64_t(*op)(int64_t, int64_t)) {
  size_t len = a.size();
  std::vector<int64_t> res(len), x(len), y(len);
  // integer64 in R are internally stored as double -> use memcpy to copy bit structure
  // reinterpret_cast would work too but results in a compiler warning
  std::memcpy(&(x[0]), &(a[0]), len * sizeof(double));
  std::memcpy(&(y[0]), &(b[0]), len * sizeof(double));
  for (size_t i = 0; i < len; ++i) {
    res[i] = op(x[i], y[i]);
  }
  Rcpp::NumericVector res_r(len);
  std::memcpy(&(res_r[0]), &(res[0]), len * sizeof(double));
  res_r.attr("class") = "integer64";
  return res_r;
}

// [[Rcpp::export]]
Rcpp::NumericVector bitwAnd64(Rcpp::NumericVector a, Rcpp::NumericVector b) {
  return bitwOp64(a, b, [](int64_t x, int64_t y) { return x & y; });
}

// [[Rcpp::export]]
Rcpp::NumericVector bitwOr64(Rcpp::NumericVector a, Rcpp::NumericVector b) {
  return bitwOp64(a, b, [](int64_t x, int64_t y) { return x | y; });
}

debug_chronal <- function() {
  x4 <- x5 <- as.integer64(0L)
  first_x5 <- NULL
  seen <- new.env(parent = emptyenv())
  while (TRUE) {
    x4 <- bitwOr64(x5, as.integer64(65536L))
    x5 <- as.integer64(3935295)
    while (x4 > 0) {
      x2 <- bitwAnd64(x4, as.integer64(255L))
      x5 <- bitwAnd64(x5 + x2,
                      as.integer64(16777215L)) * 
        as.integer64(65899L)
      x5 <- bitwAnd64(x5, as.integer64(16777215L))
      x4 <- x4 %/% as.integer64(256L)
    }
    if (is.null(first_x5)) {
      first_x5 <- x5
    }
    key <- as.character(x5)
    if (exists(key, seen)) {
      break
    }
    seen[[key]] <- TRUE
    last_x5 <- x5
  }
  list(first_x5 = first_x5,
       last_x5 = last_x5)
}

res <- debug_chronal()
res$first_x5

## integer64
## [1] 16457176

2.2.1 Description

2.2.2 Solution

To solve the second part, we continue producing x5 until we end get an x5 which we have seen already. The x5 produced just before is our solution.

res$last_x5

## integer64
## [1] 13625951