Codingame Solution: Number of letters in a number - Binary

Original Problem


Find the nth term in the sequence starting with \(S(0) = \text{start}\) and defined by the rule:

Given a term in the sequence, \(S(i)\), the next term, \(S(i+1)\) can be found by counting the letters (ignoring whitespace) in the spelled-out binary representation of \(S(i)\).

As an example, starting from 5 (\(S(0) = 5\)), we convert to the binary representation, 101, then spell it out as an English string "one zero one", and count the letters which yields 10 (\(S(1) = 10\)).
Line 1: integers start and n, separated by a space
Line 1: the nth term in the sequence, expressed as an integer
\(1 \leq n \leq 10^{18}\)
\(1 \leq \text{start} \leq 10^{18}\)


To pass all tests, we work with BigInt the whole time. Since we need to count the number of digits of the binary representation, we write a count function for that job:

function count(x) {
  let r = 0n;
  while (x) {
    r+= 4n - (x & 1n);
    x>>= 1n;
  return r;

First I got impressed by the range of the input value \(n\), but the series converges pretty fast so that a naive implementation works perfectly well

let [start, n] = readline().split` `.map(x => BigInt(x));
for (var i = 0; i < n; i++) {
  var next = count(start);
  if (start == next) {
  start = next;

« Back to problem overview