## 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(*n*^{2}) 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.

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;

}

}