Project Euler Forum

Hi, I apologise that my first post here is kind of a complaint, but it's important that I make my point.

I've just solved it (yesterday) and in my opinion, problem 066 doesn't match what Project Euler is all about.

Correct me if I am wrong, since this is the whole premise of my argument, but talking from my hundreds of hours dedicated to this problem and from what I've seen in the forum after I solved it, I got to the conclusion that the only way to solve this problem is through some fairly obscure mathematical procedure, impossible to figure out without searching for it and which most people still didn't even understand why it worked even after implementing it.

Now, of course, the site does encourage searching... but I solved every problem before this one (1-65) and pretty much never had to search the internet for anything but technicalities (and I am just a high school student). Usually when there is a new concept the problem presents it and when the solution requires the use of some unusual math, the problem often times teaches you how to do it. On this one, however, you are clueless of any such thing.

The reason why that's bad is related to what Project Euler also states: "There is a fine line between researching ideas and using the answer you found on another website". Many members, such as myself, take pride in finding the solution 100% on their own, not researching for even the smallest tip, figuring the whole math, the whole logic. Even in though times, we persist, never stop trying until we find the solution and never researching, because the bigger the suffering and the difficulty, the more rewarding it is when you finally find the solution. Then, you can feel that it was completely by your own merit, with the knowledge that you posses and through the endurance of having never given up even when it seemed hopeless and you could have easily let it go and not have experienced this feeling. That's what fuels me and many others.

This problem should ABSOLUTELY either straight up show the necessary math or at least have some warning stating that you can not solve it without researching something.

I took more than a year to solve this problem, having made a lot of attempts. When I said that I spent hundreds of hours on this thing I wasn't joking, I literally did spend hundreds of hours, I truly spent an insane amount of time on this. I tried my best to find something through math, most things leading to nothing, though despite all I was actually even able to do a lot of progress, I sped up the program a lot from my simple first attempt, and was able to find 200-ish solutions. That's also when I finally scraped any doubt that any similar algorithm, no matter how much faster, wasn't enough, but I still kept trying for a long time.

Throughout this process I eventually actually started to lose a bit of self-esteem even, started wondering if I worsened at this or was never as good as I thought, which isn't uncommon among programmers, but for me it was fairly new at such extent, especially with Euler (nothing that worrisome though). I also often lost some of the will to solve programming problems, which I always loved; and by the way, Project Euler's are my favorites, but I got to the point where I was a bit afraid of even opening the site, facing that problem again and getting into the same rabbit hole as always.

To conclude, I would like to point out that I say all of this because I truly love Project Euler, I think it's amazing and it has encouraged and boosted my programming practice and skills since it's very beginning, I have only gratitude for it's existence. I wish to save a lot of similar pointless suffering, which is most certainly going to come, and maintain the sites' standard, by promoting the smallest of changes. It may not seem that important at first, but it is, because my story isn't an isolated case, there are many many people who have gone through similar experiences on this problem, some better, some worse, the problem's forum has a bunch of them.

Here is a recent example that I got from the forum. What happenned to him was the same that happenned to me, if not worse.

From member ikanreed on 23 Jul 2021:

"I have spent years of time and literally filled up notebooks on this problem.

This year, I gave up and read the [can't give tip to the solution here]. There were lots of things I had derived myself there, but the magic of [can't give tip to the solution here] just never crossed my mind.

I knew from so much experimentation that there was a relevant something to get from the [can't give tip to the solution here], but I could never suss out what it was."

If people are stuck, they are supposed to read the thread Clarifications on Project Euler problems here about the problem.
If you've read the thread viewtopic.php?p=3819#p3819 you would have learned there that you are supposed to do some research.
The hint the problem gives is: Quadratic Diophantine Equation.
If you have never met that term you are supposed to research it in a book or on the web.
The reason Project Euler does this is to make you prolific in doing (internet) research on subjects you haven't studied yet.
Stubbornly trying to do it all by yourself without looking for resources is a misunderstanding of the goals of project euler.

hk wrote: Sun Mar 27, 2022 8:48 pm If people are stuck, they are supposed to read the thread Clarifications on Project Euler problems here about the problem.
If you've read the thread viewtopic.php?p=3819#p3819 you would have learned there that you are supposed to do some research.
The hint the problem gives is: Quadratic Diophantine Equation.
If you have never met that term you are supposed to research it in a book or on the web.
The reason Project Euler does this is to make you prolific in doing (internet) research on subjects you haven't studied yet.
Stubbornly trying to do it all by yourself without looking for resources is a misunderstanding of the goals of project euler.

I completely agree that my case derived greatly from my own immense stubbornness, I should have been quicker to follow the site's recommendation and do some research and I think it's good that Project Euler incentivatizes the behaviour of googling and figuring it out for yourself.

My issue with this problem though is that not only it isn't clear that you should google something to solve it (which by itself is kind of okay) but actually more than that, it somewhat unintencionally tricks you into thinking you shouldn't, because at first you think the solution is simply a brute force, but you realise that despite it working it isn't fast enough so you try to optimize it and perhaps find some math trick that can speed the process and all.

And that is the path to be followed in Project Euler in my opinion (or at least a legitimate one), researching only when absolutely necessary, because researching could easily take fun away from the problem if you are not careful, for example: some problems could be solved by using famous algorithms (which would be the easiest way) but I and others didn't know about them at the time and solved them on our own ways with some creativity, or even figured the famous way to solve the problems by ourselves. That's one of the great things about these problems, using logic and creativity. Plus, it's not ever clear at all if you are stuck at a problem because you just didn't have the realization necessary to solve it, or if it's impossible for you to solve it with only the information you posses. I have been stuck at other problems for days, even more than a week, several times and ended up solving them without looking at any aditional information at all, but simply continuing to try.

Of course that I took it too far on this one, but what I've just described of the problem being somewhat misleading on whether you should research for something or not and you ending up losing a lot of time until "giving up" has been said by many people. And unlike other frustrating times, I don't think losing it this way is constructive.

Personally, I strongly believe the statement should make the fact you should research for something on this problem more clear, I think it would make the problem overall better, but I understand your point and it is reasonable to leave it the way it is, so I'm okay if you and the admins don't agree.

Also, thank you for taking your time hk!

I think you've learned a valuable lesson here that will serve you well as you continue your journey through the problems. Research is going to be essential. The fact that you have made it up to problem 66 without needing to research and you're still in high school is an incredible achievement.

But as it says in one of the Q&As on the About page:

Do you have any hints on solving problems?

Read the details of the problem very carefully and make note of any example cases given. Experiment with pencil and paper to get a feel for the ideas behind the problem. If the ideas are new to you, then use the internet or books to get some background; the problem should contain clues as to what to look-up. Try writing a program to generate for simple cases and check that your output agrees with the example cases. This will confirm that you've understood the problem and are heading in the right direction. Based on this try to extrapolate to estimate the time it will take to get the final answer. If it's going to take significantly more than a minute, then rethink your strategy.

In this particular case, searching quadratic Diophantine equations (e.g. Wikipedia) would have have pointed you in the right direction to at least give you the name of the type of equation you are trying to solve.

To get the most out of the problems that lie ahead, I'd recommend a slight change to your mindset. Recognise that the problems have been designed to expose you to new ideas and new learning opportunities. What you already have in abundance is perseverance and a good sense of pride and honour. This means you are going to approach each new problem with the right attitude. You'll know that research is necessary, but you will take the minimum and battle to make the connections yourself. This approach will help you significantly as you work through the problem set because you will have gained the maximum amount of learning from each problem. And in turn, the ideas you learn will help to unlock the secrets of other newer problems.

Good luck!

pmiguelez wrote: Sun Mar 27, 2022 11:37 pm it somewhat unintencionally tricks you into thinking you shouldn't [Google anything], because at first you think the solution is simply a brute force, but you realise that despite it working it isn't fast enough so you try to optimize it and perhaps find some math trick that can speed the process and all.

I would say that it's problem 1 which doesn't match what Project Euler is about, because that one can be solved by brute force. (Obviously I understand why problem 1 uses 1000 instead of 10¹²: there's no need for anyone to explain that).

The vast majority of PE problems have a test value so that you can check that you're on the right lines, and I think that most of those test values are obtainable by brute force; sometimes there's a small test value which can be obtained by brute force, an intermediate one which requires one idea, and the submission value requires a second idea. In general, the role of brute force is to give you enough small examples that you can try to spot patterns. Whenever you find yourself thinking that brute force will work for the actual submission value, it's a sign that you've misunderstood the problem.

As for research: every problem could in principle be solved purely by your own research without standing on the shoulders of anyone, but then you're forcing yourself to rediscover many large chunks of mathematics from the ancient Greeks to the 20th century, work which at the time was worth doctorates.

euler wrote: Mon Mar 28, 2022 6:26 am I think you've learned a valuable lesson here that will serve you well as you continue your journey through the problems. Research is going to be essential. The fact that you have made it up to problem 66 without needing to research and you're still in high school is an incredible achievement.

But as it says in one of the Q&As on the About page:

Do you have any hints on solving problems?

Read the details of the problem very carefully and make note of any example cases given. Experiment with pencil and paper to get a feel for the ideas behind the problem. If the ideas are new to you, then use the internet or books to get some background; the problem should contain clues as to what to look-up. Try writing a program to generate for simple cases and check that your output agrees with the example cases. This will confirm that you've understood the problem and are heading in the right direction. Based on this try to extrapolate to estimate the time it will take to get the final answer. If it's going to take significantly more than a minute, then rethink your strategy.

In this particular case, searching quadratic Diophantine equations (e.g. Wikipedia) would have have pointed you in the right direction to at least give you the name of the type of equation you are trying to solve.

To get the most out of the problems that lie ahead, I'd recommend a slight change to your mindset. Recognise that the problems have been designed to expose you to new ideas and new learning opportunities. What you already have in abundance is perseverance and a good sense of pride and honour. This means you are going to approach each new problem with the right attitude. You'll know that research is necessary, but you will take the minimum and battle to make the connections yourself. This approach will help you significantly as you work through the problem set because you will have gained the maximum amount of learning from each problem. And in turn, the ideas you learn will help to unlock the secrets of other newer problems.

Good luck!

Thanks very much for the advice, what you've said makes a lot of sense. I will certaily approach the problems with a new mindset moving forward and won't be afraid of researching when necessary

I'd like to express my gratitude to the participants of the thread. I was about to spend (likely) hours and hours trying to optimise my code or manually eliminating some solutions. After looking at the thread, I realised how much I was wrong. A sneak pick to Wikipedia has opened my eyes to new knowledge and gave me great satisfaction from utilising it.

Thank you, pmiguelez, for starting the thread, and thank you, hk and euler, for your valuable input.

I think we have been well prepared for this problem by the toolset shown to us in the previous problems. Yes, it was maybe the toughest so far, but I really like how problems 57, 64, 65 gave us the means to tackle this one. Like the OP I have not looked up the term "Diophantine Equations", and it probably took me 6-8 failed attempts to solve problem 66, but I really enjoyed thinking about possible solutions and implementing them, and in the end was able to solve it. I too have learned from this thread that I should maybe research the topic (hinted at by the problem title) when next I struggle with a project Euler problem.