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




See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.

Problem 198

Postby BjornEdstrom » Sat Jun 14, 2008 11:03 am

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

Postby daniel.is.fischer » Sat Jun 14, 2008 11:31 am

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à.
User avatar
daniel.is.fischer
 
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: "Ambiguous Numbers" is ambiguous

Postby stijn263 » Sat Jun 14, 2008 12:32 pm

Is 321 correct?
User avatar
stijn263
 
Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

Re: "Ambiguous Numbers" is ambiguous

Postby funktio » Sat Jun 14, 2008 12:44 pm

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. :oops:
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

Postby daniel.is.fischer » Sat Jun 14, 2008 1:08 pm

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à.
User avatar
daniel.is.fischer
 
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: "Ambiguous Numbers" is ambiguous

Postby daniel.is.fischer » Sat Jun 14, 2008 1:30 pm

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à.
User avatar
daniel.is.fischer
 
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: "Ambiguous Numbers" is ambiguous

Postby stijn263 » Sat Jun 14, 2008 1:31 pm

Solved it! Thanks a lot funktio :D

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..
User avatar
stijn263
 
Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

Re: "Ambiguous Numbers" is ambiguous

Postby funktio » Sat Jun 14, 2008 4:46 pm

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

Postby BjornEdstrom » Sat Jun 14, 2008 6:57 pm

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

Postby daniel.is.fischer » Sat Jun 14, 2008 7:10 pm

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à.
User avatar
daniel.is.fischer
 
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: "Ambiguous Numbers" is ambiguous

Postby jaap » Sat Jun 14, 2008 7:13 pm

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.
User avatar
jaap
 
Posts: 433
Joined: Tue Mar 25, 2008 3:57 pm

Re: "Ambiguous Numbers" is ambiguous

Postby stijn263 » Sat Jun 14, 2008 7:26 pm

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..
User avatar
stijn263
 
Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

Re: "Ambiguous Numbers" is ambiguous

Postby daniel.is.fischer » Sat Jun 14, 2008 7:30 pm

And including those, there are more than 19836.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
User avatar
daniel.is.fischer
 
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: "Ambiguous Numbers" is ambiguous

Postby LarryC » Sat Jun 14, 2008 7:54 pm

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

Postby daniel.is.fischer » Sat Jun 14, 2008 8:01 pm

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à.
User avatar
daniel.is.fischer
 
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Next

Return to Clarifications on Project Euler Problems

Who is online

Users browsing this forum: No registered users and 1 guest