## How Many Distinct Products In A Times Table?

### July 15, 2014

We all learned our times tables in elementary school. For instance, here is the standard 9 by 9 times table:

```1  2  3  4  5  6  7  8  9 2  4  6  8 10 12 14 16 18 3  6  9 12 15 18 21 24 27 4  8 12 16 20 24 28 32 36 5 10 15 20 25 30 35 40 45 6 12 18 24 30 36 42 48 54 7 14 21 28 35 42 49 56 63 8 16 24 32 40 48 56 64 72 9 18 27 36 45 54 63 72 81```

That table has 36 distinct products: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72 and 81.

Your task is to write a program that computes the number of distinct products in an n by n times table. There is an obvious O(n2) algorithm; can you do better? When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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