Problem 157

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.
quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Who can I PM for a question on 157?

Post by quilan »

So, I finally figured out the trick to make it easy and I've got a rock solid algorithm for it, but my answer's not going through. Since it would give far too much away to announce it here, is there an admin I could PM to check something with?
ex ~100%'er... until the gf came along.
Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Who can I PM for a question on 157?

Post by daniel.is.fischer »

Sure :)
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
David F
Posts: 23
Joined: Sun Jul 20, 2008 11:03 pm

Problem 157

Post by David F »

I think this has been brought up before, but I don't think it is very obvious what actual answer is expected here. Is the wording intentionally vague, or am I missing something?

(I've got the correct answer so I don't need help, but in the end I only tried it out of desperation. I still don't think it makes sense, to be honest).
User avatar
rayfil
Administrator
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 157 wording/clarification

Post by rayfil »

Is the wording intentionally vague, or am I missing something?
Every effort is always made to provide problem descriptions which are as clear as possible to avoid any ambiguity.

For Problem #157, the number of solutions (and their details) are given when the exponent n = 1 (i.e. p/101 = p/10).

The description clearly asks to report the total number of solutions when the exponent n is varied between 1 and 9 inclusive. Could you expand a bit more on which part may not have been clear enough for you.
When you assume something, you risk being wrong half the time.
David F
Posts: 23
Joined: Sun Jul 20, 2008 11:03 pm

Re: Problem 157 wording/clarification

Post by David F »

OK, in hindsight, and with the benefit of a short break away from the problem, I can see why a strict reading of the question gives the answer that is expected.

However, I think it is very easy (and reading people's responses on the solution thread, I don't think I was alone) not to realise that, for example, 1/1+1/1 = 20/10 is to be treated as a different solution to 1+1+1/1=200/100.

I don't think it would be unreasonable to point that out in the question wording, or, alternatively to simply state that the solution is the number of distinct quadtuples (a,b,p,n).

Again, with hindsight, this is my misreading of the question. But out of the last 50 problems, this is the only one where my main difficulty was a misunderstanding of the wording, rather than the underlying mathematics. It seems to me that ProjectEuler generally tries to avoid such situations even where clarification may not be strictly necessary.
User avatar
GenePeer
Posts: 112
Joined: Sat Apr 03, 2010 1:14 pm
Contact:

Re: Problem 157

Post by GenePeer »

David F wrote:However, I think it is very easy (and reading people's responses on the solution thread, I don't think I was alone) not to realise that, for example, 1/1+1/1 = 20/10 is to be treated as a different solution to 1+1+1/1=200/100.

I don't think it would be unreasonable to point that out in the question wording, or, alternatively to simply state that the solution is the number of distinct quadtuples (a,b,p,n).
Agreed. It would only cost one extra sentence in the description and avoid any confusion whatsoever. Aren't the descriptions supposed to be as clear as possible?
Image
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 157

Post by TripleM »

What other possible interpretation is there? You're not asked for the number of values the sum can take; you're asked for the number of solutions to an equation. If you are asked for the solutions to x^2 - 3x + 2 = 0 you don't need to clarify that two solutions are different if they have different values of x, or that you don't count the solutions as the same because they both give a result of 0. There isn't any difference with this problem - adding it here would just be a bad precedent to require unnecessary wording in lots of other problems.

(I can't see anyone in the problem thread who misunderstood the question in the way you mentioned; just some for whom the above solutions were counted as the same due to a bug in their code).
User avatar
GenePeer
Posts: 112
Joined: Sat Apr 03, 2010 1:14 pm
Contact:

Re: Problem 157

Post by GenePeer »

TripleM wrote:(I can't see anyone in the problem thread who misunderstood the question in the way you mentioned; just some for whom the above solutions were counted as the same due to a bug in their code).
neverforget. That makes it three of us, that have mentioned it. And like David, this is the only problem in the last 59 I've done that I've misunderstood. But if the admins see no reason to change the wording, it's fine.

And can the admins combine tapan's consecutive posts on the second page of the problem's forum?
Image
User avatar
hk
Administrator
Posts: 10975
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 157

Post by hk »

GenePeer wrote: And can the admins combine tapan's consecutive posts on the second page of the problem's forum?
Done.
Image
User avatar
jake223
Posts: 57
Joined: Mon Apr 25, 2011 5:15 am
Location: USA
Contact:

Re: Problem 157

Post by jake223 »

Can anybody validate these results and tell me which ones are wrong? thanks in advance.
for 10^n: (cumulative)

n solutions
1 20
2 *06
3 *86
4 **82
5 **62
6 **60
7 ***86
8 ***64
9 ***38
Image
User avatar
rayfil
Administrator
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 157

Post by rayfil »

102 is wrong already.
When you assume something, you risk being wrong half the time.
User avatar
jake223
Posts: 57
Joined: Mon Apr 25, 2011 5:15 am
Location: USA
Contact:

Re: Problem 157

Post by jake223 »

thanks. i'll look further at my code.
EDIT: I stilll can't find my error. can I PM somebody my method/results for 10^2?
Image
User avatar
jake223
Posts: 57
Joined: Mon Apr 25, 2011 5:15 am
Location: USA
Contact:

Re: Problem 157

Post by jake223 »

I think I figured out my problem, however I am still getting an incorrect answer. Can anybody point out where I start to go wrong? thanks.
[these are cululative]
  1. 20
  2. *22
  3. *78
  4. **36
  5. **28
  6. **84
  7. ***44
  8. ***32
  9. ***90
  10. ***86
Image
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 157

Post by thundre »

jake223 wrote:10. ***86
That's where you're going wrong. From the problem statement:
How many solutions has this equation for 1 ≤ n ≤ 9?
So you shouldn't have an entry for n=10.
Image
User avatar
jake223
Posts: 57
Joined: Mon Apr 25, 2011 5:15 am
Location: USA
Contact:

Re: Problem 157

Post by jake223 »

Oops. Thanks.
Image
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 157

Post by Oliver1978 »

Hmm, back after some time off I seem to have picked a "nice" one...

I've tried to brute-force my way into this and get e.g. 102 fractions for n = 2 and *56 for n = 3. I'm somewhat doubtful that this is correct... :?
49.157.5694.1125
MuthuVeerappanR
Posts: 472
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 157

Post by MuthuVeerappanR »

leghorn wrote:Hmm, back after some time off I seem to have picked a "nice" one...

I've tried to brute-force my way into this and get e.g. 102 fractions for n = 2 and *56 for n = 3. I'm somewhat doubtful that this is correct... :?
It indeed is..
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
scientes
Posts: 8
Joined: Fri Sep 12, 2014 11:54 am

Re: Problem 157

Post by scientes »

It is simple problem after PE 108.
creature
Posts: 1
Joined: Thu Jul 30, 2015 12:41 am

Re: Problem 157

Post by creature »

Registered because I also feel the problem statement is ambiguous and no one has clearly explained the source of the ambiguity.

An earlier comment by euler says we're counting distinct quadruples (a, b, p, n).

But this never specified and one can just as well interpret the wording to mean total number solution pairs (a, b) for which 1/a + 1/b can be written in the form p/10, p/100, p/1000, etc. Especially while comparing with problems 108 and 110 where solution counting is done with a fixed value on the right side of a similar equation. Thus it's not clear there are multiple solutions with the same values of a and b.

Not only does the example for n = 1 convey no information to address this question but the restriction to a value of n reinforces the apparent connection to problems 108 and 110, which suggests we shouldn't concern ourselves with how p and n could be varied for fixed a, b.

In diophantine-like equations there's often a bit ambiguity in what is meant by a solution when specific solutions give rise to trivially related ones. Something like x/(x+1) = (m/n)^2 is conventionally interpreted to mean "find values of x for which x/(x+1) is the square of a rational number", not an invitation to describe an infinite set of trivial solutions by multiplying m and n by arbitrary constants. In problem 157 moving factors between p and the 10^n seems similarly trivial.
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 157

Post by Oliver1978 »

Brute-force aside, I'm positively sure I've found the pattern in this. Alas my numbers seem incorrect. Would anyone mind to hear me about this, and either support or decline my thoughts?
49.157.5694.1125
Post Reply