Calculate Conway's Constant

user_15261413 0
Viewed 570

I found a code golf challenge that requires you to calculate Conway's Constant to the first 1000 digits. The problem is I couldn't find any place that tells how to calculate this, just websites showing polynomials with a variable x that I do not know what is. I calculated the first 30 numbers in the Look-and-say sequence with this code:

const nums = ["1"],

  trailingSequences = seq => {
    const num = seq[0];
    let counter = 1;
    let idx = 0;
    for (let i = 1; i < seq; i++) {
      if (num == seq[i]) {
        counter++
        idx = i;
      } else {
        break
      };
    }
    return [`${counter}${num}`, idx + 1];
  },

  getNext = previous => {
    let next = "";
    while (true) {
      if (previous == "") {
        break
      };
      const part = trailingSequences(previous);
      next += part[0];
      previous = previous.slice(part[1]);
    }
    return next;
  }


for (let i = 0; i < 30; i++)
  nums.push(getNext(nums[nums.length - 1]))
  
console.log(nums.join("\n\n\n"));

But I still do not know how to extract Conway's constant regardless.

So, how to calculate Conway's Constant to a modifiable precision in JavaScript?

javascript
2 Answers

Conway's Constant is the unique real positive root of an order-71 polynomial. As you might expect it is irrational1, and cannot be expressed as a finite continued fraction.

One of the easiest, and generally speaking most efficient methods to compute polynomial roots is with Newton's method:

Newton's method

where xn is the current guess and f(xn) is a function that evaluates the target polynomial at xn.

In the case that arbitrary precision reals/rationals are not available, the result can instead be scaled by a large power of 10 to compute the desired precision. The implementation below uses V8's BigInts to compute Conway's Constant to 1000 places.

/**
 * Evaluates a polynomial given by coeffs at x,
 * or the derivative thereof, scaled by a factor.
 */
function evalpoly(x, coeffs, scale, deriv) {
  let ret = 0n;
  const d = deriv ? 1 : 0;
  for(let i = coeffs.length - 1; i >= d; i--) {
    ret = x*ret / scale + BigInt(coeffs[i] * [1, i][d]) * scale;
  }
  return ret;
}


const poly = [
  -6, 3, -6, 12, -4, 7, -7, 1, 0, 5, -2, -4, -12, 2, 7, 12, -7, -10,
  -4, 3, 9, -7, 0, -8, 14, -3, 9, 2, -3, -10, -2, -6, 1, 10, -3, 1,
  7, -7, 7, -12, -5, 8, 6, 10, -8, -8, -7, -3, 9, 1, 6, 6, -2, -3,
  -10, -2, 3, 5, 2, -1, -1, -1, -1, -1, 1, 2, 2, -1, -2, -1, 0, 1]

const scale = 10n**1000n

// initial guess 1.333333...
let x = scale * 4n / 3n

for(let i = 0; i < 14; i++) {
  x -= evalpoly(x, poly, scale, 0) * scale / evalpoly(x, poly, scale, 1)
}

x

1 Finch, Steven R., Mathematical Constants, pp. 642, Cambridge University Press, 2003.

user_14413980

The Conway Constant is the ratio between the length of digits of n and n-1 as n approaches inf.

const nums = ["1"],

  trailingSequences = seq => {
    const num = seq[0];
    let counter = 1;
    let idx = 0;
    for (let i = 1; i < seq; i++) {
      if (num == seq[i]) {
        counter++
        idx = i;
      } else {
        break
      };
    }
    return [`${counter}${num}`, idx + 1];
  },

  getNext = previous => {
    let next = "";
    while (true) {
      if (previous == "") {
        break
      };
      const part = trailingSequences(previous);
      next += part[0];
      previous = previous.slice(part[1]);
    }
    return next;
  }


for (let i = 0; i < 30; i++){
  let prev = (nums[nums.length - 1] + '').length;
  let current = (getNext(nums[nums.length - 1]) + '').length; 
  nums.push(getNext(nums[nums.length - 1]))
  // ratio of n / n-1, this is the approx of Conway's Constant
  console.log(current / prev);
}
//console.log(nums.join("\n\n\n"));

user_30465480
Related