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.

About these ads

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

    $ ./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[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);
       }
    }
    
  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]){
    distinctProducts.add(new Integer(i));
    }
    }
    return distinctProducts;
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: