Factoring an Integer in JavaScript with a Wheel

Update: bugfix in code

Factoring an integer with a wheel is a known algorithm for which many examples exist for many programming languages. Google might be of some help to find them.
Most of them are either way too simple or way too complicated; I would even say that all of them fall into one of these two categories but I do not know all of them.
One example that could fit both categories at once is the program factor from the GNU-coreutils which uses a wheel to do its work. I did a JavaScript version of it if that language suits you more. The program itself is quite simple yet hard to understand.
For example: what are these numbers at the start and where do they come from?

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;
  for (var i = 0; i < this.length; i++) {
    prod *= this[i];
  }
  return prod;
};
Array.prototype.memset = function (x) {
  if (arguments.length == 0) {
    x = 0;
  }
  for (var i = 0; i < this.length; i++) {
    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,
        j;
    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
    gaps.memset(1);
    // 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];
            j++;
        }
    }
    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:

[...]103,107,109,113,127,131,137,139,149,151,157,163,167,169,173[...]
[...]103,107,109,113,127,131,137,139,149,151,157,163,167,173,179[...]

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) {
            result.push(factor);
            n /= factor;
        }
        factor += wheel[next];
        next++;
        if (next == length) {
            next = roundstart;
        }
    }
    if (n > 1) {
        result.push(n);
    }
    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));
//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?

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s