## How Many Distinct Products In A Times Table?

### July 15, 2014

The obvious brute-force algorithm initializes an array of *n*^{2} 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(*n*^{2}). 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;

}

}