Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Calculate Conway's Constant

Tags:

javascript

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?

like image 993
Lexa B. Avatar asked Feb 22 '21 17:02

Lexa B.


People also ask

What is Conways constant?

The number λ ≈ 1. 303577269... is known as Conway's constant. The crucial point in Conway's proof is that each C-number is made up of one or more of 92 “basic” non-interacting strings (subsequences), or audioactive “elements”, called him as the basic 92 chemical elements, from Hydrogen H to Uranium U.

Is there a 4 in the look and say sequence?

No digits other than 1, 2, and 3 appear in the sequence, unless the seed number contains such a digit or a run of more than three of the same digit.

Who made the look and say sequence?

This sequence is also known as the Morris Number Sequence. Robert Morris was a famous cryptographer and he asked a puzzle: “What is the next number in the sequence 1, 11, 21, 1211, 111221?” Can any of you solve this?


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

like image 166
primo Avatar answered Sep 21 '22 12:09

primo