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.
Programming Praxis 
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 :adjustable nil))) (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)))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; array.add( new ArrayList<Integer>() ); System.out.println(); for (int j = 0; j<a; j++) { array.get( array.size() -1 ).add((k)*(j+1)); 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)) { n.add(array.get(i).get(j)); } } } System.out.println("\n\nDistinct Products: "+ n.size()); } public static boolean find(int q, HashSet<Integer> v) { return v.contains(q); } }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:
#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); } }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;
}
}