Programming Praxis

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

1. Graham said

   July 15, 2014 at 8:37 PM

   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

   July 16, 2014 at 5:57 PM

   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

   July 21, 2014 at 12:43 PM

   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

   July 21, 2014 at 12:45 PM

   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

   July 22, 2014 at 1:05 PM

   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 Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

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

Cancel

Connecting to %s

Notify me of new comments via email.

Notify me of new posts via email.