Project Euler/198

From charlesreid1

Problem Statement

A best approximation to a real number x for the denominator bound d is a rational number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac r s} (in reduced form) with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \le d} , so that any rational number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac p q} which is closer to x than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac r s} has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q > d}

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac 9 {40}} has the two best approximations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac 1 4} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac 1 5} for the denominator bound 6. We shall call a real number x ambiguous if there is at least one denominator bound for which x possesses two best approximations. Clearly, an ambiguous number is necessarily rational. How many ambiguous numbers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x=\frac p q, 0 < x < \frac 1 {100}} , are there whose denominator q does not exceed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 10^8} ?

examples

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

conditions

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0 < \frac p q < \frac 1 {100}}

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 some constraints:

  • p and q are coprime, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mbox{gcd}(p,q) = 1}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p \geq 1}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p \leq \frac q {100}}

Technique

Start with a program that won't scale, and generate intermediate solutions (smaller values of q limit) that we can trust.

Introduce optimizations to scale better, use intermediate solutions to verify answers don't change

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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [a_0; a_1, a_2, \dots, a_n]} , 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [0; 4, 2, 4]}

First convergent: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [0;4] = \frac 1 4}

Second convergent: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [0; 4, 2] = \frac 1 {4 + \frac 1 2} = \frac 2 9}

Third (final) convergent: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [0; 4, 2, 4] = \frac 9 {40}}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [0; a_1]} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [0; a_1, 1, 1, \dots, 1]}

Flags



Euler.jpg
Project Euler
project euler notes

Project Euler

Grid 0: Problems 1-99

Problem 1  · Problem 2  · Problem 3  · Problem 4  · Problem 5  · Problem 6  · Problem 7  · Problem 8  · Problem 9  · Problem 10

Problem 11  · Problem 12  · Problem 13  · Problem 14  · Problem 15  · Problem 16  · Problem 17  · Problem 18  · Problem 19  · Problem 20

Problem 21  · Problem 22  · Problem 23  · Problem 24  · Problem 25  · Problem 26  · Problem 27  · Problem 28  · Problem 29  · Problem 30

Problem 31  · Problem 32  · Problem 33  · Problem 34  · Problem 35  · Problem 36  · Problem 37  · Problem 38  · Problem 39  · Problem 40

Problem 41  · Problem 42  · Problem 43  · Problem 44  · Problem 45  · Problem 46  · Problem 47  · Problem 48  · Problem 49  · Problem 50

Problem 51  · Problem 52  · Problem 53  · Problem 54  · Problem 55  · Problem 56  · Problem 57  · Problem 58  · Problem 59  · Problem 60

Problem 61  · Problem 62  · Problem 63  · Problem 64  · Problem 65  · Problem 66  · Problem 67  · Problem 68  · Problem 69  · Problem 70

Problem 71  · Problem 72  · Problem 73  · Problem 74  · Problem 75  · Problem 76  · Problem 77  · Problem 78  · Problem 79  · Problem 80

Grid 1: Problems 100-199

Problem 100  · Problem 101  · Problem 102  · Problem 103  · Problem 104  · Problem 105  · Problem 106  · Problem 107  · Problem 108  · Problem 109

...

Problem 150  · Problem 151  · Problem 152  · Problem 153  · Problem 154  · Problem 155  · Problem 156  · Problem 157  · Problem 158  · Problem 159

...

Problem 170  · Problem 171  · Problem 172  · Problem 173  · Problem 174  · Problem 175  · Problem 176  · Problem 177  · Problem 178  · Problem 179

...


Problem 190  · Problem 191  · Problem 192  · Problem 193  · Problem 194  · Problem 195  · Problem 196  · Problem 197  · Problem 198  · Problem 199


Grid 2: Problems 200-299

Problem 227  · Problem 254


Grid 3: Problems 300-399


Problem 301  · Problem 310

Problem 312  · Problem 319

Problem 323  · Problem 328

Problem 334  · Problem 337

Problem 345  · Problem 346

Problem 355  · Problem 356

Problem 364  · Problem 367

Problem 373  · Problem 378

Problem 382  · Problem 389

Problem 391

Grid 5: Problems 500-599

Problem 400


Grid 5: Problems 500-599

Problem 500  · Problem 501  · Problem 502


Grid 9: Problems 900-999

Problem 932


* = in progress

Flags  · Template:ProjectEulerFlag  · e


Retrieved from "https://charlesreid1.com/w/index.php?title=Project_Euler/198&oldid=29795"