Re: [math-fun] Can we make fast divisibility tests for binary computers?

Marc's suggestion re GCD is really a bin-packing problem. That is, we have a set of primes. Their "sizes" are their logs to base 2. We wish to pack the primes into as few bins as possible (size of bin is machine wordlength in bits). We then can test N for divisibility by taking the gcd(N, bin-products). One could try the "first fit decreasing" bin packing heuristic... or others...