## 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.

Pages: 1 2

### 5 Responses to “How Many Distinct Products In A Times Table?”

1. Graham said

Trying to jump back on the Lisp/Scheme train. Here’s a Common Lisp version:

```(defun m (n)
"ProgPraxis's sieve solution to
'How Many Distinct Products in a Time Table?'"
(let ((bits (make-array (1+ (* n n))
:element-type 'bit
(loop for i from 1 to n do
(loop for j from (* i i) to (* i n) by i
do (setf (elt bits j) 1)))
(loop for b across bits summing b)))
```
2. Nick said

How can I improve this?

```import java.util.*;

public class ft {

/**
* @param args
*/
public static void main(String[] args) {
int a=0,e=0; //e by a times table
Scanner input = new Scanner(System.in);

while(true) {
try {
System.out.print("Enter # of columns: ");
String consoleInput = input.nextLine();
e = Integer.parseInt(consoleInput);
break;
}
catch (Exception ex) {
System.out.println("#s Only!");

}
}
while(true) {
try {
System.out.print("Enter # of rows: ");
String consoleInput = input.nextLine();
a =Integer.parseInt(consoleInput);
break;
}
catch (Exception ex) {
System.out.println("#s Only!");

}
}

ArrayList<ArrayList<Integer>> array = new ArrayList<ArrayList<Integer>>(); //the table
HashSet<Integer> n = new HashSet<Integer>(); //list of distinct products
int k;

for (int i = 0; i<e; i++) {
k=i+1;
System.out.println();
for (int j = 0; j<a; j++) {
System.out.printf("%- 10d", array.get(i).get(j)); //print times table
}
}

int j;
for (int i = 0; i<e; i++) {
for (j = 0; j<a; j++) {
if (!find(array.get(i).get(j), n)) {
}
}
}

System.out.println("\n\nDistinct Products: "+ n.size());

}

public static boolean find(int q, HashSet<Integer> v) {

return v.contains(q);
}
}
```
3. matthew said

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);
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);
}
}

```\$ ./timescount 9
1 1
2 3
3 6
4 9
5 14
6 18
7 25
8 30
9 36
```
4. matthew said

That code should be:

```#include <vector>
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
int n = atoi(argv);
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);
}
}
```
5. ScottW said

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]){