Project Euler/53 - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:48:00Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:48, 9 October 2019
Line 44:		Line 44:
	=Solution Code=		=Solution Code=

	Link: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round2_050-070/053/CombinatoricSelections.java		Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/053/CombinatoricSelections.java

	<pre>		<pre>

Admin: /* Solution Explanation */

2018-01-08T09:28:40Z

Solution Explanation

← Older revision		Revision as of 09:28, 8 January 2018
Line 15:		Line 15:
	<math>		<math>
	\log \left( \dfrac{n!}{k! (n-k)!} \right)		\log \left( \dfrac{n!}{k! (n-k)!} \right)
	= \log \left( \dfrac{n \times (n-1) \times \dots \times 1 }{ ( k \times (k-1) \times \dots \times 1 )( (n-k) \times (n-k-1) \times \dots \times 1 )} \right)		= \log \left[ \dfrac{n \times (n-1) \times \dots \times 1 }{ ( k \times (k-1) \times \dots \times 1 )( (n-k) \times (n-k-1) \times \dots \times 1 )} \right]
	</math>		</math>

Line 22:		Line 22:
	<math>		<math>
	\log \left( \dfrac{n!}{k! (n-k)!} \right)		\log \left( \dfrac{n!}{k! (n-k)!} \right)
	= \log \left( n \times (n-1) \times \dots \times 1 \right) - \log \left( k \times (k-1) \times \dots \times 1 \right) - \log \left( (n-k) \times (n-k-1) \times \dots \times 1 \right)		= \log \left[ n \times (n-1) \times \dots \times 1 \right] - \log \left[ k \times (k-1) \times \dots \times 1 \right] - \log \left[ (n-k) \times (n-k-1) \times \dots \times 1 \right]
	</math>		</math>

			Further simplifying turns this into a trivial sum:

			<math>
			\log \left( \dfrac{n!}{k! (n-k)!} \right)
			= \sum_{p=1}^{n} \log p - \sum_{q=1}^{n-k} \log q - \sum_{r=1}^{k} \log r
			</math>

			thus reducing the problem of marking a "square" on our 100 x 100 n vs. k grid reduces to adding numbers that are O(10), instead of multiplying numbers that are O(100000000...)

			The final comparison being done is:

			<math>
			\sum_{p=1}^{n} \log p - \sum_{q=1}^{n-k} \log q - \sum_{r=1}^{k} \log r < \log(10000)
			</math>

			If this is true, n-choose-k is less than 1 million; if it is false, n-choose-k is greater than 1 million.

	=Solution Code=		=Solution Code=

Admin: /* Solution Explanation */

2018-01-08T09:24:07Z

Solution Explanation

← Older revision		Revision as of 09:24, 8 January 2018
Line 15:		Line 15:
	<math>		<math>
	\log \left( \dfrac{n!}{k! (n-k)!} \right)		\log \left( \dfrac{n!}{k! (n-k)!} \right)
	= \log \left( \dfrac{n \times (n-1) \times \dots \times 1 }{ ( k \times (k-1) \times \dots \times 1 )( (n-k) \times (n-k-1) \times \dots \times 1 )}		= \log \left( \dfrac{n \times (n-1) \times \dots \times 1 }{ ( k \times (k-1) \times \dots \times 1 )( (n-k) \times (n-k-1) \times \dots \times 1 )} \right)
	</math>		</math>

Admin at 09:23, 8 January 2018

2018-01-08T09:23:38Z

@@ Line 1: / Line 1: @@
-https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/053
+=Problem Statement=
-=Code=
+Problem 53 asks about values of the binomial coefficient, a.k.a. n-choose-k. For some values of n and k, the resulting n-choose-k value can exceed 1 million. This question asks how many binomial coefficients n-choose-k exceed 1 million, for n = 1 to 100.
 <pre>

Admin at 08:12, 8 January 2018

2018-01-08T08:12:30Z

← Older revision		Revision as of 08:12, 8 January 2018
Line 1:		Line 1:
	https://charlesreid1.com:3000/cs/euler/src/master/053/		https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/053

			=Code=

			<pre>
			public class CombinatoricSelections {
			public static void main(String[] args) {
			doit();
			}

			/** Nice easy test. This should be bigger than 1 million - should return true. */
			public static void test() {
			System.out.println("isBigger(23,10) = "+isBigger(23,10));
			}

			/** Solve the problem. */
			public static void doit() {
			int MAX = 100;
			int count = 0;
			boolean[][] isBig = new boolean[MAX][MAX];
			for(int nm1=0; nm1<MAX; nm1++) {
			for(int rm1=0; rm1<MAX; rm1++) {
			// determine if n C r > 1M
			int n = nm1+1;
			int r = rm1+1;
			boolean big = isBigger(n,r);
			isBig[nm1][rm1] = big;
			if(big) count++;
			}
			}
			System.out.println("Total number of n Choose r values that are greater than 1M: "+count);
			}

			/** Boolean: is n choose r bigger than 1 million? */
			public static boolean isBigger(int n, int r) {
			int d = (n-r);
			double LHS = 0.0;
			for(int j=0; j<d; j++) {
			LHS += Math.log(r+d-j) - Math.log(d-j);
			}
			double RHS = Math.log(1000000);
			return LHS > RHS;
			}
			}

			</pre>

	=Flags=		=Flags=

Admin at 08:11, 8 January 2018

2018-01-08T08:11:46Z

← Older revision		Revision as of 08:11, 8 January 2018
Line 1:		Line 1:
			https://charlesreid1.com:3000/cs/euler/src/master/053/

			=Flags=

			{{ProjectEulerFlag}}

	[[Category:Combinatorics]]		[[Category:Combinatorics]]
	[[Category:Permutations]]		[[Category:Permutations]]

Admin: Created page with "Category:Combinatorics Category:Permutations"

2017-07-18T12:10:38Z

Created page with "Category:Combinatorics Category:Permutations"

New page

[[Category:Combinatorics]]
[[Category:Permutations]]