Problem 044

[zeycus]

In problem 44 we are required to find "the smallest pair" for which something is true. But what is the order assumed for pairs? I think it should be specified: the pair with minimal sum, the pair with the lowest maximum, the minimal pair in lexicographic order... whatever was in the mind of the problem poster.

[euler]

Thank you for pointing that out. It's a valid point, and reading through the forum it seems that members have mentioned it before; I wish they'd take the time like you did to post it here.

Anyway I've changed the wording to remove ambiguity, but I suspect that now it's made it into a more difficult problem than it should be. As GraemeMcRae pointed out on page 5 of the forum, members were previously arriving at the solution by simply finding the "smallest pair" and superimposing the intended interpretation (either minimal sum or difference), or no interpretation and arriving at it by chance! However, it was ambiguous as there could exist a pair P_j and P_k for which minimal j is less than the intended solution; there is simply no way to check this.
http://projecteuler.net/index.php?secti ... lems&id=44

[zeycus]

Thank you for your prompt and possitive answer. I agree the problem seems a bit more complex now, but I prefer it like this.

Cheers!

[Frisker]

I've been trying to solve this problem for some days now, im using a method where I loop through the differences and then pick out the P(k) and P(j) that match the difference. I get a solution but the number I get isnt low enough I suppose, but I cant see what I am doing wrong.

The solution my program gives me:

Expand

4620347250

If I for example try to get the numbers that produce my difference for p(15000) I get:

Expand

1, p(4687384) and p(4687384) + p(15000)
2, p(299806) and p(299806) + p(15000)
3, p(87596) and p(87596) + p(15000)
4, p(54126) and p(54126) + p(15000)

For p(14321) I get:

Expand

Nothing

I then check if the sum of the two numbers are pentagonal.

I suppose there is something wrong with the algoritm that gives me the pentagonal numbers that got the specified difference. Anyone got any hints of what im doing wrong?.

I wish I could post some code but I suppose that it isnt allowed.

[Tommy137]

Hi,

I used a similar method and got the correct answer, although it was awful slow. I still think it's the only way to ensure that the difference is minimized (many used faster algorithms that did not really minimize D, but nevertheless got the solution).

So I've no idea why your method doesn't work, but it's hard to say anything without seeing the code.

I can only tell you that you are far away from the correct answer


Thomas

[Frisker]

Thanks for your reply!.

Can't you say if my examples above are correct or not? and I suppose that my answer is way too high?. I'll post the code for my method that filters out the pentagonal numbers that form the specified difference

Expand

[code] // returns all P(n)'s that can form the specified difference.
static long[] GetNumbers(double diff)
{
List<long> k = new List<long>();
double x = 0, t = 1.1d; // 1.1 is just to enter the loop

while (t >= 1)
{
x++;

if ((long)t == t) // Does t got decimals?
k.Add((long)t); // if not, put it in the collection

/* the difference between P(n) and P(n+1) is
* 3n + 1, you can with that formula describe any
* number above n that is pentagonal, lets say P(n+x):
* 3n+1 + 3(n+1)+1 + 3(n+2)... + 3(n+x)+1. I can
* write this as x + 3/2 (-x + x^2) + 3xn, this must be
* equal to the difference, x + 3/2 (-x + x^2) + 3xn = diff
* you can from there pull out n to the left side
* (x + 3/2 (-x + x^2) - diff) / -3x = n*/
t = (x + 1.5 * (x * x - x) - diff) / (-3 * x);
}

return k.ToArray();
}[/code]

[quilan]

Can't you say if my examples above are correct or not? and I suppose that my answer is way too high?. I'll post the code for my method that filters out the pentagonal numbers that form the specified difference

I may be slightly confused by your wording... but I'll give it a shot

Expand

[code]p(4687384) + p(15000) = p(4687408)
p(299806) + p(15000) = p(300181)
p(87596) + p(15000) = p(88871)
p(54126) + p(15000) = p(56166)
[/code]
So yes, these are all examples of p(j)+p(k) == p(c)
However, only the first satisfies the condition that p(j)-p(k) == p(d)

So, considering the problem, your first example has a D=|p(4687384)-p(15000)| == p(4687360) == 32957013308992... and that's overshooting the answer by quite a bit.

Keep in mind, the question is asking for the lowest p(d) such that:
p(j)+p(k) == p(c) and p(j)-p(k) == p(d) (for integers j,k,c,d)

[daniel.is.fischer]

Seems you're missing some:
*Penta> indices (penta 15000)
[7499826,4687384,2205808,299806,187196,87596,54126]
*Penta> indices (penta 14321)
[51271566]

Can't say what went wrong, though.

quilan, you must have a bug in your code:
p(4687360) = 32957013310720 [ne] 32957013308992 (which is not pentagonal)

[quilan]

quilan, you must have a bug in your code:
p(4687360) = 32957013310720 [ne] 32957013308992 (which is not pentagonal)

Silly me, I was using Excel, and it came to p(4687360.99987) so err... my bad as they say. No code there.

[Frisker]

I've been pulling hairs to the point of baldness these last days but I finally solved it (never felt this good). The thing was that my method that checked if a number was pentagonal was flawed at big numbers (damn you Math.sqrt!), I should have figured that our earlier though, but I will never make that mistake again!.

Thanks for the help, I probably never would have seen it without that complete list. (I was double checking all the numbers from the GetNumbers method with my "IsPentagonal" function, so that's why my list did differ from the correct one)

[incandenza]

I used a similar method and got the correct answer, although it was awful slow. I still think it's the only way to ensure that the difference is minimized (many used faster algorithms that did not really minimize D, but nevertheless got the solution).

I wonder if it would be better to modify this question so that it is specifically asking for the value of D corresponding to the lowest pair j,k (or the lowest sum j+k or whatever), instead of the lowest D period.

It wouldn't change the actual answer, but it seems that most people are calculating the former and just hitting the answer "by accident". If this is supposed to be one of the easier problems, might as well make it clear that the easy solution is actually valid.

Something just seems wrong about being so easily able to "get away" without checking all the possibilities.

[Erasmus Darwin]

It wouldn't change the actual answer, but it seems that most people are calculating the former and just hitting the answer "by accident". If this is supposed to be one of the easier problems, might as well make it clear that the easy solution is actually valid.

Something just seems wrong about being so easily able to "get away" without checking all the possibilities.

You raise a good point, but I think the slightly harder wording helps in the sense that doing it properly will better prepare people for harder problems.

I noticed that there's some similar but not quite identical "cheating" that can be used for other problems such as 30 and 34. In those cases, the problems require you to find all numbers with a certain property, and no upper bound is provided. As such, you can either find a way to calculate an upper bound, or you can just keep raising the hardcoded upper bound until the answer form accepts your result. Since you'd be relying on the answer form to determine initial correctness rather than as a double-check on your own work, it obviously falls outside the spirit of the rules.

So there are at least a couple easy problems that you can get away with doing it the wrong way, but that doesn't negate the value someone derives from doing them correctly.

[daniel.is.fischer]

About the wording of Problem 44: until last fall it read

Find the smallest pair of pentagonal numbers for which their sum and difference is pentagonal; what is their difference?

and it has been argued that that is ambiguous (though, for all reasonable notions of 'smallest pair', the answer is the same). It was changed to disambiguate the question. Any answer before that change is thus completely excused from not checking whether a smaller difference might exist. Answers after that change would be incomplete without that check indeed. But for many problems you can have an algorithm which gives the right answer without being able to prove that it does. And although it would be interesting to see proofs of correctness for some algorithms, I'd hate to read one for every submitted answer So I think if you come up with an algorithm that very probably gives the correct answer, it's good enough, then you should check the thread if somebody proved the correctness.

[incandenza]

So I think if you come up with an algorithm that very probably gives the correct answer, it's good enough, then you should check the thread if somebody proved the correctness.

Yes, I'm getting more used to the idea that it's OK to just submit any answer you think has even a chance of being correct, since that seems to be more in the spirit of how things are done here.

Originally my attitude was that it was pretty important to be sure your algorithm was correct before submitting, and that you should probably feel pretty bad if you submit an answer and it's wrong.

[euler]

Just to re-iterate those sentiments...

You will know from the phrase at the bottom of the About page: "Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics." To new members it might seem a little circular the idea of restricting access to a full discussion of the solution until you've solved it, in that once you've solved it, would you need to discuss the solution? However, for many people they have an almost workable method, but it may, for example, always give one more than the intended answer. Long standing members have become accustomed to trying one either side of their answer. To have got to that point means you have engaged the problem sufficiently enough to want to know how it works and so you will value the experience of seeing how it should be done properly, or even how it could be done with breath-taking efficiency, all the more. Simply providing problems with full access to answers and a forum at the click of a mouse would only cheapen the experience of learning; in fact, I would go as far to say that no real learning takes place.

[incandenza]

Simply providing problems with full access to answers and a forum at the click of a mouse would only cheapen the experience of learning; in fact, I would go as far to say that no real learning takes place.

Hmm, maybe I missed your point; I don't think anyone was arguing that the answers should be given away.

To me the issue was more, how OK is it to guess? I kind of dislike the idea of guessing because in most real world situations you don't have someone just telling you whether you got the right answer; you have to know your solution is correct. So when it's possible to get the answer right with a semi-guess, I find that kind of disappointing from a problem design point of view. But that's just me.

I do see your point, though, that if you even come up with a decent guess, you've understood the problem enough that it's OK if you luck out and get to see the solutions.

[daniel.is.fischer]

To me the issue was more, how OK is it to guess? I kind of dislike the idea of guessing because in most real world situations you don't have someone just telling you whether you got the right answer; you have to know your solution is correct.

Those feelings honour you. However, in my experience, in most real world situations you don't know whether your solution is correct. Fortunately, often it doesn't matter if it is, it's only important (very important) that your solution is close enough to the correct solution. Of course, you'd better be sure about that, but often you don't have the time to be. Then, if you know enough about the matter, it's perfectly reasonable to make an educated guess. Here, if you understood the problem well enough to see that it should have that structure, but are not able to prove that no freak cases can exist, in my opinion it is legitimate to guess that they don't exist and try out what your structure gives you.

So when it's possible to get the answer right with a semi-guess, I find that kind of disappointing from a problem design point of view. But that's just me.

Not quite just you. But it's terribly hard to come up with problems where a talented pattern-spotter couldn't spot a successful pattern.

[JPGargoyle]

Hi.

Can someone please explain to me what is meant by "D = |Pk - Pj| is minimised"?

Does |Pk - Pj| means the absolute value? or distance?, or something else?

Thanks a lot.

Best regards.

[Georg]

|Pk - Pj| does mean the absolut value

|Pk - Pj| = Pk - Pj, if Pk - Pj ≥ 0
|Pk - Pj| = Pj - Pk, if Pk - Pj < 0

[jaap]

Does |Pk - Pj| means the absolute value?

Yes, the absolute value of the difference between the two numbers.

or distance?

This is exactly how distance is usually defined on real numbers.