Computing right-truncatable primes by brute force

right-truncatables.es6

function * multiplesOf (startingWith, n) {
  let number = startingWith;
  
  while (true) {
    yield number;
    number = number + n;
  }
}

function destructure (iterable) {
  const iterator = iterable[Symbol.iterator]();
  const { done, value } = iterator.next();

  if (!done) {
    return { first: value, rest: iterator }
  }
}

class HashSieve {
  constructor () {
    this._hash = Object.create(null);
  }

  addAll (iterable) {
    const { first, rest } = destructure(iterable);

    if (this._hash[first]) {
      this._hash[first].push(rest);
    }
    else this._hash[first] = [rest];

    return this;
  }

  has (number) {
    if (this._hash[number]) {
      this._remove(number);
      return true;
    }
    else return false;
  }

  _remove (number) {
    const iterables = this._hash[number];

    if (iterables == null) return false;

    delete this._hash[number];
    iterables.forEach((iterable) => this.addAll(iterable));

    return number;
  }
}

function * Primes () {
  let prime = 2;
  const composites = new HashSieve();

  while (true) {
    yield prime;
    composites.addAll(multiplesOf(prime * prime, prime));

    while (composites.has(++prime)) {
      // do nothing
    }
  }
}

function memoize (generator) {
  const memos = {},
        iterators = {};

  return function * (...args) {
    const key = JSON.stringify(args);
    let i = 0;

    if (memos[key] == null) {
      memos[key] = [];
      iterators[key] = generator(...args);
    }

    while (true) {
      if (i < memos[key].length) {
        yield memos[key][i++];
      }
      else {
        const { done, value } = iterators[key].next();

        if (done) {
          return;
        } else {
          yield memos[key][i++] = value;
        }
      }
    }
  }
}

const factors = memoize(Primes);

function isPrime(n) {
  const squareRoot = Math.floor(Math.sqrt(n));

  for (const factor of factors()) {
    if (n % factor === 0) {
      return false;
    } else if (factor > squareRoot) {
      return true;
    }
  }
}

function * truncatables(...bases) {
  for (const base of bases) {
    yield base;
    
    const baseTimesTen = base * 10;
  
    for (const digit of [1, 3, 7, 9]) {
      const candidate = baseTimesTen + digit;
    
      if (isPrime(candidate)) {
        yield * truncatables(candidate);
      }
    }
  }
}

for (const truncatable of truncatables(2, 3, 5, 7)) {
  console.log(truncatable);
}

console.log('there are a finite number of truncatables');