Project Euler/198 - Revision history

Unknown user: /* Technique */

2025-04-16T03:09:52Z

Technique

← Older revision		Revision as of 03:09, 16 April 2025
Line 31:		Line 31:

	Develop insights about ambiguous numbers in the process		Develop insights about ambiguous numbers in the process

			===Introducing continued fractions===

			Best approximations relate to continued fractions in that the continued fraction expansion is a best approximation in some sense

			For a rational number, the continued fraction expansion is finite. We also know the fractions we're considering are rational. So we don't have to worry about a continued fraction expansion getting into an infinite loop.

			(However, from past experience with continued fraction expansions, they CAN get reeeeeally long)

			===Crux of the problem===

			For a rational number, continued fraction expansion terminates, and best approximations are convergents

			But problem mentions case of two best approximations for a given denominator bound

			That happens when continue fraction expansion has coeff greater than 1,

			then there are intermediate fractions that can also be best approximations fro certain bounds

			For continued fraction, <math>[a_0; a_1, a_2, \dots, a_n]</math>, convergents are fractions obtained by truncating expansion at each step

			There exists a denominator bound d such that there are two different fractions with denominators <= d equally close to x

			Continued fraction of 9/40 is <math>[0; 4, 2, 4]</math>

			First convergent: <math>[0;4] = \frac 1 4</math>

			Second convergent: <math>[0; 4, 2] = \frac 1 {4 + \frac 1 2} = \frac 2 9</math>

			Third (final) convergent: <math>[0; 4, 2, 4] = \frac 9 {40}</math>

	===Counting ambiguous fractions===		===Counting ambiguous fractions===

Unknown user: /* Technique */

2025-04-16T02:57:14Z

Technique

← Older revision		Revision as of 02:57, 16 April 2025
Line 28:		Line 28:
	Start with a program that won't scale, and generate intermediate solutions (smaller values of q limit) that we can trust.		Start with a program that won't scale, and generate intermediate solutions (smaller values of q limit) that we can trust.

	~~Then, introduce~~ optimizations to scale ~~further~~, ~~and~~ use intermediate solutions to verify ~~optimizations aren~~'t ~~changing answers.~~		Introduce optimizations to scale better, use intermediate solutions to verify answers don't change

	Develop insights about ambiguous numbers in the process.		Develop insights about ambiguous numbers in the process

	~~q < 10,000 is very fast~~ to ~~compute~~, ~~but~~ q < 1,~~000~~,~~000 can take way~~, ~~way longer.~~		===Counting ambiguous fractions===

			Want to count the number of ambiguous fractions

			(Note: can also try counting total number of fractions, then subtracting total number of non-ambiguous fractions)

			We know a fraction p/q is not ambiguous if the continued fraction is <math>[0; a_1]</math> or <math>[0; a_1, 1, 1, \dots, 1]</math>

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* conditions */

2025-04-16T02:34:24Z

conditions

← Older revision		Revision as of 02:34, 16 April 2025
Line 20:		Line 20:

	For a given denom q, poss num p must satisfy some constraints:		For a given denom q, poss num p must satisfy some constraints:
	* p and q are coprime		* p and q are coprime, so <math>\mbox{gcd}(p,q) = 1</math>
	* <math>p \geq 1</math>		* <math>p \geq 1</math>
	* <math>p \leq \frac q {100}</math>		* <math>p \leq \frac q {100}</math>

Unknown user: /* conditions */

2025-04-16T01:35:22Z

conditions

← Older revision		Revision as of 01:35, 16 April 2025
Line 19:		Line 19:
	The smallest possible value of p is 1, implying q > 100. We also know q < 1e8, from the problem statement. This provides an absolute range for q.		The smallest possible value of p is 1, implying q > 100. We also know q < 1e8, from the problem statement. This provides an absolute range for q.

	For a given denom q, poss num p must satisfy <math>p \geq 1</math> ~~and~~ <math>p \leq \frac q {100}</math>		For a given denom q, poss num p must satisfy some constraints:
			* p and q are coprime
			* <math>p \geq 1</math>
			* <math>p \leq \frac q {100}</math>

	==Technique==		==Technique==

Unknown user: /* conditions */

2025-04-16T01:32:54Z

conditions

← Older revision		Revision as of 01:32, 16 April 2025
Line 19:		Line 19:
	The smallest possible value of p is 1, implying q > 100. We also know q < 1e8, from the problem statement. This provides an absolute range for q.		The smallest possible value of p is 1, implying q > 100. We also know q < 1e8, from the problem statement. This provides an absolute range for q.

	For a given denom q, poss num p must satisfy <math>p \geq 1</math> and <math>p \leq \frac q 100</math>		For a given denom q, poss num p must satisfy <math>p \geq 1</math> and <math>p \leq \frac q {100}</math>

	==Technique==		==Technique==

Unknown user: /* conditions */

2025-04-16T01:32:38Z

conditions

← Older revision		Revision as of 01:32, 16 April 2025
Line 15:		Line 15:
	===conditions===		===conditions===

	~~we know~~ <math>0 < \frac p q < \frac 1 {100}~~</math>, which implies <math>q > 100p~~</math>		<math>0 < \frac p q < \frac 1 {100}</math>

	~~together with~~ the ~~upper bound~~ for q~~, this provides~~ a ~~range of values of~~ q: <math>~~100p~~ < q ~~< 10^8~~</math>		The smallest possible value of p is 1, implying q > 100. We also know q < 1e8, from the problem statement. This provides an absolute range for q.

			For a given denom q, poss num p must satisfy <math>p \geq 1</math> and <math>p \leq \frac q 100</math>

	==Technique==		==Technique==

Unknown user: /* conditions */

2025-04-16T01:27:27Z

conditions

← Older revision		Revision as of 01:27, 16 April 2025
Line 15:		Line 15:
	===conditions===		===conditions===

	we know <math>0 < \frac p q < \frac 1 {100}</math>		we know <math>0 < \frac p q < \frac 1 {100}</math>, which implies <math>q > 100p</math>

	which implies <math>q > 100p</math>

	together with the upper bound for q, this provides a range of values of q: <math>100p < q < 10^8</math>		together with the upper bound for q, this provides a range of values of q: <math>100p < q < 10^8</math>

Unknown user: /* examples */

2025-04-16T01:27:04Z

examples

← Older revision		Revision as of 01:27, 16 April 2025
Line 11:		Line 11:
	===examples===		===examples===

	9/40 is ambiguous, with two best approximations 1/4 and 1/5, for a denominator bound of 6 (q < 6)		9/40 is an ambiguous number, with two best approximations 1/4 and 1/5, for a denominator bound of 6 (q < 6)

	===conditions===		===conditions===

Unknown user: /* Problem Statement */

2025-04-16T01:26:40Z

Problem Statement

← Older revision		Revision as of 01:26, 16 April 2025
Line 8:		Line 8:

	How many ambiguous numbers <math>x=\frac p q, 0 < x < \frac 1 {100}</math>, are there whose denominator q does not exceed <math>10^8</math>?</p>		How many ambiguous numbers <math>x=\frac p q, 0 < x < \frac 1 {100}</math>, are there whose denominator q does not exceed <math>10^8</math>?</p>

			===examples===

			9/40 is ambiguous, with two best approximations 1/4 and 1/5, for a denominator bound of 6 (q < 6)

			===conditions===

			we know <math>0 < \frac p q < \frac 1 {100}</math>

			which implies <math>q > 100p</math>

			together with the upper bound for q, this provides a range of values of q: <math>100p < q < 10^8</math>

	==Technique==		==Technique==

Unknown user: /* Technique */

2025-04-16T01:15:05Z

Technique

← Older revision		Revision as of 01:15, 16 April 2025
Line 14:		Line 14:

	Then, introduce optimizations to scale further, and use intermediate solutions to verify optimizations aren't changing answers.		Then, introduce optimizations to scale further, and use intermediate solutions to verify optimizations aren't changing answers.

			Develop insights about ambiguous numbers in the process.

	q < 10,000 is very fast to compute, but q < 1,000,000 can take way, way longer.		q < 10,000 is very fast to compute, but q < 1,000,000 can take way, way longer.