Factoring an Integer in JavaScript with a Wheel

Update: bugfix in code


For such series of numbers the first address to go is OEIS of course, so lets do a copy&paste of the first couple of numbers and give it try.
So, these numbers are the differences between the prime numbers. A fact you might have guessed already, didn’t you? 😉
One thing to know about OEIS that it might be a better idea to search for a segment out of the middle of the sequence but it won’t help in this case here, sorry.
The length of the sequence is 485. The number of gaps between a 2310-wheel constructed from the primes 2, 3, 5, 7, and 11 is the number of primes minus one which is 342. Quite a large difference but the number of gaps in a 210-wheel (primes 2, 3, 5, and 7) is 45 and in a 30030-wheel (primes 2, 3, 5, 7, 11, and 13) is 3247.
So where does this large difference between the number of gaps in a 2310-wheel (which we assume it must be because its neighbours are way to much off) come from?
A bit of nomenclature: a list of numbers that are not divisible by any of a consecutive number of primes starting with 2 is called after the successor prime of the list of primes and the suffix “-rough”. Examples: a list of numbers that are not divisible by any of the primes 2, 3, and 5 are called 7-rough numbers because the next prime in the list of 2,3, and 5 would be 7. That allows us to search for another term at OEIS: 13-rough numbers. Not much to find there but the number 2310 which might be familiar to some of my readers.
Another hint: if we write a function with a 30-wheel or with a 210-wheel the second and all further rounds start at index 3. The GNU implementation with the (probably) 2310-wheel starts all further rounds at wheel-index 5, so it might be a matter of periodicity.

But why not just try it?

Building the wheel. A bit more complicated than necessary to include some logging:

Array.prototype.prod = function () {
  var prod = 1;
    prod *= this[i];
  return prod;
Array.prototype.memset = function (x) {
  if (arguments.length == 0) {
    x = 0;
    this[i] = x;
function mkwheel() {
    var primes = [
        2, 3, 5, 7, 11
    // gaps between seeding primes + next prime
    var lead = [
        1, 2, 2, 4, 2, 4
    var gaps;
    var product = primes.prod();
    var wheel = new Array(product);
    var i,
    var rough13;
    // fill with numbers for loggin
    for (i = 0; i < wheel.length; i++) {
        wheel[i] = i;
    // go along the spokes of the wheel and strike out
    for (i = 0; i < primes.length; i++) {
        var p = primes[i];
        var q = product / p;
        for (j = 0; j <= q; j++) {
            wheel[p * j] = 0;
    gaps = new Array(wheel.length);
    rough13 = new Array(wheel.length);
    // we need one-based distance measures
    // BUGFIX: had i = 0
    for (i = primes.length, j = i - 1; i < wheel.length; i++) {
        if (wheel[i] == 0) {
            gaps[j] ++;
        } else {
            rough13[j] = wheel[i];
    gaps.length = j;
    rough13.length = j;
    console.log("13-rough numbers? " + rough13);
    // fill the gap bteween zero and 13 manually
    for (i = 0; i < lead.length; i++) {
        gaps[i] = lead[i];
    console.log("gaps = " + gaps);
    return gaps;

If we put a sequence of the primes up to 2310 under the wheel sequence we can easily spot the problem: it is a wheel. It sieves, by definition, not every composite number out. The first composite here is 169:


But this still leaves us with a difference of five between the 2310-wheel and the GNU-implementation. So it will not work with the computetd sieve? Let’s try:

function factor(n) {
    // checks and balances
    var wheel = mkwheel();
    var length = wheel.length;
    // length of lead of wheel/start of cycle
    var roundstart = 3;
    // first prime
    var factor = 2;
    // cycling index into the wheel
    var next = 0;
    var result = [];
    while (factor * factor <= n) {
        while (n % factor == 0) {
            n /= factor;
        factor += wheel[next];
        if (next == length) {
            next = roundstart;
    if (n > 1) {
    return result;

Some numbers to try (the last three might need some more time. About half a minute each on my old 1 GHz Duron):

// Just a random number
console.log("123123123123123"  + factor(123123123123123));
// 3,31,41,41,271,2906161
// 2^53
console.log("9007199254740992" + factor(9007199254740992));
// 2,2,2,[...],2,2,2
// UPDATE: primorial(41) which pointed me to a bug in my code
console.log("304250263527210" + factor(304250263527210));
// 2,3,5,7,11,13,17,19,23,29,31,37,41
// Semiprime with largest factors possible with JavaScript
console.log("9007195909437503" + factor(9007195909437503));
// 94906247,94906249
// Largest factor possible with JavaScript (input not prime)
console.log("9007199254740898" + factor(9007199254740898));
// 2,4503599627370449
// Largest prime possible with JavaScript
console.log("9007199254740881" + factor(9007199254740881));

Seems to work. Even though I changed the start index from 5 to 3 (works with 5, too, btw. because it is a wheel and a wheel is round, y´know 😉 ).
We could try the GNU version with the last five terms stripped, and it still works. So, why the extra five terms? I honestly don’t know.
Do you?
UPDATE: with the fixed bug I got 483 terms and a start at 3, they have 485 and a start at 5, which should explain the differenc of two but it doesn’t really do it very well because I still don’t get it.
Do you?


One thought on “Factoring an Integer in JavaScript with a Wheel

Leave a Reply


WordPress.com Logo


Google+ photo


Twitter picture


Facebook photo



Connecting to %s
