## Problem 198

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers

### Problem 198

I have some difficulty understanding the problem description for 198. At first I thought I understood the problem and I have a program that works alright (at least for my interpretation of the description). But as the answer is wrong, I thought I'd check.

A best approximation to a real number x for the denominator bound d is a rational number r/s (in reduced form) with s ≤ d, so that any rational number p/q which is closer to x than r/s has q > d.

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. 9/40 has the two best approximations 1/4 and 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 x = p/q, 0 < x < 1/100, are there whose denominator q does not exceed 10^8?

Is x = p/q in reduced form? Should q <= 10^8 or q < 10^8? Is the answer 303937 for the simpler case 10^5?

Thanks.
BjornEdstrom

Posts: 37
Joined: Thu Nov 08, 2007 11:16 pm

### Re: "Ambiguous Numbers" is ambiguous

x may or may not be in reduced form, but is counted only once. For the given example, x = 9/40 = 63/280, both denominators do not exceed 108, but (if x were < 1/100) it's only one x, so count only once. Hence it's easiest to assume x is in reduced form, too.
"Does not exceed" is "less than or equal to", hence q 108.
Your value for 105 is much too large.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

daniel.is.fischer

Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: "Ambiguous Numbers" is ambiguous

Is 321 correct?

stijn263

Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

### Re: "Ambiguous Numbers" is ambiguous

stijn263 wrote:Is 321 correct ?

No, but I think I know what your mistake is. Hint: You overlooked the trivial cases. I hope it's ok to post this spoiler. I made the same error at first, too.
Edit: sorry.
Last edited by funktio on Sat Jun 14, 2008 1:18 pm, edited 2 times in total.
for($"=@_=split??,"Jrsk an treP rehlohacteu,";$";$\="\r"){$\.=$.=chr 32+95*rand,$_-$"or$.ne$_[--$"%2?-$"-1:$"]&&$"++for++$|..$";print}<> funktio Posts: 14 Joined: Mon May 19, 2008 5:55 pm Location: Helsinki, Finland ### Re: "Ambiguous Numbers" is ambiguous I changed the spoiler, hopefully it's still helpful enough, but less direct. Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là. daniel.is.fischer Posts: 2400 Joined: Sun Sep 02, 2007 10:15 pm Location: Bremen, Germany ### Re: "Ambiguous Numbers" is ambiguous No need to be sorry, funktio, you didn't tell too much, I just saw a way to tell less which I hope still tells enough. If it doesn't, your original hint will be reinstated Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là. daniel.is.fischer Posts: 2400 Joined: Sun Sep 02, 2007 10:15 pm Location: Bremen, Germany ### Re: "Ambiguous Numbers" is ambiguous Solved it! Thanks a lot funktio It appeared I had an integer overflow as well. I rewrote ( p/q < 1/100) to (p*100 < q), however p*100 doesn't fit into int32 for all possible values of p obviously. So all values of p, where p*100 > 232, were accepted too.. stijn263 Posts: 1505 Joined: Sat Sep 15, 2007 10:57 pm Location: Netherlands ### Re: "Ambiguous Numbers" is ambiguous daniel.is.fischer wrote:No need to be sorry, funktio, you didn't tell too much, I just saw a way to tell less which I hope still tells enough. If it doesn't, your original hint will be reinstated Ahh, good to hear that. It's a very nice problem; it would've been sad if I had ruined it for stijn263 by giving too much away. for($"=@_=split??,"Jrsk an treP rehlohacteu,";$";$\="\r"){$\.=$.=chr
32+95*rand,$_-$"or$.ne$_[--$"%2?-$"-1:$"]&&$"++for++$|..$";print}<>
funktio

Posts: 14
Joined: Mon May 19, 2008 5:55 pm
Location: Helsinki, Finland

### Re: "Ambiguous Numbers" is ambiguous

It must be the football and the warm weather that's making me dull, but I still have problems understanding exactly what's being asked.

For example, are these ambigious numbers?

(5, 12) (7, 12) (9, 20) (11, 20) (7, 24) (17, 24) (13, 28) (15, 28) ?

Because there are well over 321 of them for the x=p/q denominator bound 10^5. I get 19 836 with a new program.
BjornEdstrom

Posts: 37
Joined: Thu Nov 08, 2007 11:16 pm

### Re: "Ambiguous Numbers" is ambiguous

Yes, all are ambiguous. Maybe you missed the 0 < x < 1/100 part?
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

daniel.is.fischer

Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: "Ambiguous Numbers" is ambiguous

BjornEdstrom wrote:For example, are these ambigious numbers?
(5, 12) (7, 12) (9, 20) (11, 20) (7, 24) (17, 24) (13, 28) (15, 28) ?

Yes, 5/12 ... 15/28 are ambiguous numbers. They do not count towards the total in this problem, however, since none of them is smaller than 1/100.

jaap

Posts: 420
Joined: Tue Mar 25, 2008 3:57 pm

### Re: "Ambiguous Numbers" is ambiguous

Because there are well over 321 of them for the x=p/q denominator bound 10^5. I get 19 836 with a new program.
321 isn't correct since I forgot about the trivial cases..

stijn263

Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

### Re: "Ambiguous Numbers" is ambiguous

And including those, there are more than 19836.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

daniel.is.fischer

Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: "Ambiguous Numbers" is ambiguous

I'm also finding it difficult to comprehend.

The thing I don't get is, if x = p/q, then how can we know if it's ambiguous? After all, we are not told what the highest bound placed on the approximate's denominator is.
LarryC

Posts: 66
Joined: Sat Jun 14, 2008 7:33 pm

### Re: "Ambiguous Numbers" is ambiguous

If x = p/q (reduced), then for all denominator bounds d q, the unique best approximation to x is x itself, so the maximal denominator bound to consider, if you have no better idea, is q-1.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

daniel.is.fischer

Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Next