How Many Distinct Products In A Times Table?
July 15, 2014
The obvious brute-force algorithm initializes an array of n2 bits to #f
, uses nested loops on i from 1 to n and j from 1 to n to compute the products i · j and marks each of the products as #t
in the bit array, then counts the number of #t
bits to produce the result m:
(define (m n) ; brute force
(let ((bits (make-vector (+ (* n n) 1) #f)))
(do ((i 1 (+ i 1))) ((< n i))
(do ((j i (+ j 1))) ((< n j))
(vector-set! bits (* i j) #t)))
(do ((k 1 (+ k 1))
(c 0 (+ c (if (vector-ref bits k) 1 0))))
((< (* n n) k) c))))
We make the bits
array one element too big because Scheme arrays are indexed from 0 rather than 1.
> (time (m 1000))
(time (m 1000))
1 collection
124 ms elapsed cpu time, including 0 ms collecting
125 ms elapsed real time, including 8 ms collecting
8192848 bytes allocated, including 735696 bytes reclaimed
248083
> (time (m 2000))
(time (m 2000))
1 collection
515 ms elapsed cpu time, including 31 ms collecting
504 ms elapsed real time, including 31 ms collecting
32384656 bytes allocated, including 230944 bytes reclaimed
959759
> (time (m 4000))
(time (m 4000))
1 collection
2028 ms elapsed cpu time, including 109 ms collecting
2022 ms elapsed real time, including 113 ms collecting
128768656 bytes allocated, including 40464784 bytes reclaimed
3723723
> (time (m 8000))
(time (m 8000))
1 collection
8268 ms elapsed cpu time, including 515 ms collecting
8278 ms elapsed real time, including 510 ms collecting
513536656 bytes allocated, including 805920 bytes reclaimed
14509549
Time complexity is clearly quadratic, as time expended quadruples when n doubles. Space complexity is also quadratic, for the n · n array.
There are a couple of ways to improve that. One halves the work by iterating j starting from i instead of 1. Another reduces multiplication to addition in the same was as the Sieve of Eratosthenes:
(define (m n) ; sieve
(let ((bits (make-vector (+ (* n n) 1) #f)))
(do ((i 1 (+ i 1))) ((< n i))
(do ((j (* i i) (+ i j))) ((< (* i n) j))
(vector-set! bits j #t)))
(do ((k 1 (+ k 1))
(c 0 (+ c (if (vector-ref bits k) 1 0))))
((< (* n n) k) c))))
(time (m 1000))
1 collection
219 ms elapsed cpu time, including 125 ms collecting
229 ms elapsed real time, including 123 ms collecting
8192656 bytes allocated, including 1574832 bytes reclaimed
248083
> (time (m 2000))
(time (m 2000))
1 collection
452 ms elapsed cpu time, including 31 ms collecting
455 ms elapsed real time, including 30 ms collecting
32384656 bytes allocated, including 229888 bytes reclaimed
959759
> (time (m 4000))
(time (m 4000))
1 collection
1841 ms elapsed cpu time, including 93 ms collecting
1845 ms elapsed real time, including 97 ms collecting
128768656 bytes allocated, including 552439744 bytes reclaimed
3723723
> (time (m 8000))
(time (m 8000))
1 collection
7613 ms elapsed cpu time, including 374 ms collecting
7629 ms elapsed real time, including 397 ms collecting
513536656 bytes allocated, including 805888 bytes reclaimed
14509549
If n is large the calculation can be segmented, similarly to the Sieve of Eratosthenes. That reduces the space complexity to O(n), because the optimum segment size is n, but leaves the time complexity at O(n2). I don’t know of an O(m) algorithm.
You can run the program at http://programmingpraxis.codepad.org/pvCamAkP. Richard Brent has a good discussion of the problem at http://maths-people.anu.edu.au/~brent/pd/multiplication.pdf., and Sloane has more at A027424.
Trying to jump back on the Lisp/Scheme train. Here’s a Common Lisp version:
How can I improve this?
If we rearrange the loop a little, we can progressively generate the counts for all tables up to n:
#include <vector>
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
int n = atoi(argv[1]);
std::vector<bool> seen(n*n+1);
int count = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= i*i; j+=i) {
count += !seen[j];
seen[j] = true;
}
printf("%d %d\n", i, count);
}
}
That code should be:
Pigeon Hole Principle
import java.util.ArrayList;
public class DistinctProductsForTimesTables {
public static void main(String[] args){
ArrayList distinctProducts = getDistinctProducts(1000);
System.out.println(distinctProducts);
}
public static ArrayList getDistinctProducts(int N){
boolean[] pigeonHole = new boolean[N*N+1];
ArrayList distinctProducts = new ArrayList();
for(int i=1;i<=N;i++){
for(int j=i;j<=N;j++){
pigeonHole[i*j] = true;
}
}
for(int i=0;i<=N*N;i++){
if(pigeonHole[i]){
distinctProducts.add(new Integer(i));
}
}
return distinctProducts;
}
}