Problem 268

[elendiastarman]

Well, all that I can say is that this problem difficulty grade was set to 4 out of 9 where 1-3 are easy, 4-6 are medium and 7-9 are hard problems. Being voted 4 means that the problem is easy with a bit of spice, something tricky to understand.

Where can you see those difficulty grades? On the website if I sort on difficulty it just sorts on number of people who have solved it.

This "grade" is really a reflection of how hard the site's problem-makers think it is. Every (I think) feasible PE problem suggestion is tested by a few select people, like daniel.is.fischer, hk, euler, etc... They figure out the problem limits that make it possible, but difficult (usually) to solve it within a minute. If #273 is a 2 and #274 is an 8, that doesn't mean that one is easy and the other is hard...it means that one is relatively easy and the other is relatively hard.
I think I've described the situation accurately; if not, feel free to correct me.

[TripleM]

I understood that note as meaning "don't contact *US* about it". Not "don't talk about it with anyone". Isn't the point of project euler to learn something? Googling for the answer won't teach you anything, but never being able to solve a problem won't teach you anything either. Sometimes a small hint at the right time is the best way forward.

Believe me, you will learn immeasurably more by spending days, weeks, months continuously failing / working on different approaches to the same problem than you ever will by getting a hint from someone else. It is definitely worth the perseverance.

[Diadem]

I think I respectfully disagree. You probably do learn a lot more from working on something for months, than you would if you solved it in a few hours after some hints. But in those few months you could solve a few dozen problems with the latter approach, and learn a lot more in total. People learn more if don't have to learn everything by themselves, but occasionally get help. You know, that's why we have schools! But I think I just totally managed to derail this thread. My apologies.

Anyway I think I'm close to solving it now

[stijn263]

If it were me, I'd just let this problem rest for a while, and solve that few dozen other problems, and maybe one of them (or something else) will give you the insight that helps solve this problem, (or, if you have already solved all the other problems, perhaps you should try to do one of them in a more efficient way )

If #273 is a 2 and #274 is an 8, that doesn't mean that one is easy and the other is hard...it means that one is relatively easy and the other is relatively hard.

It means the development team members think a problem is relatively easy/hard. But they/we ( ) aren't representative solvers; sometimes a problem is thought to be easy because they all know a certain theorem, but that same problem might be a much bigger challenge when you need to come up with that theorem yourself. (in this particular case the title of the problem proposal kind of gave away the problem ) Or sometimes we all miss an (easy) insight and rate the problem harder than the average PE solver would rate it. So the rating isn't really accurate and that's exactly why it's not published . (Only problems 203 - 207 were announced to be easy problems)

[genious999]

Only problems 203 - 207 were announced to be easy problems

I still managed to find difficulty in at least one of those, despite them being announced "easy"

[Ted]

Again, I mean no personal disrespect, Diadem. Your viewpoint is at least as valid as (greater than than or equal to) mine. I personally agree more with stijn263/henk263 and TripleM, and joined this great Project with that in mind. I certainly appreciate the more direct approach of coursework and asking questions, and in my working years would have required it had this level math been involved. But as a leisure pursuit, this is my comfort area, as slow-to-find-a-way as I am.

To sfabriz -- I appreciated your comments as well. If I conveyed a feeling of complaint originally, I did not so intend. Perversely, I enjoy being stuck and floundering, as subsequent victory when/if it comes, feels so good! And 99% of what I now know (not much still!) of number theory I have learned by finding my way through PE problems, including some I've not yet solved. In fact, I'm finding it easier to absorb with these problems as applications (sorry, G.Hardy!)

And as you're the author of this particular one, I want you to know I'm enjoying it already, even though I've not solved it, as I am working through what may or may not be a promising approach. And to echo my previous point, I don't NEED to know whether my approach will work yet, as even incorrect approaches based on new items learned may be useful elsewhere.

[sfabriz]

[...]To sfabriz -- I appreciated your comments as well. If I conveyed a feeling of complaint originally, I did not so intend. [...]

I didn't get any "complaint feeling", really, so, no harm.
Enjoy the solving!

sfab

[Bo102010]

I'm a bit confused by problem 268.

I devised a method that I think scales to a limit of 10^16, but it delivers the wrong answer. I checked this forum to find that the answer given for some lower limits doesn't match what I would expect. I'm pretty sure I'm misunderstanding the problem somehow, but I'm not sure where. To check my "clever" method, I also have a "brute force" method.

Both methods yield a result of 8963 a limit of 10^5, but this disagrees with the 9280 posted earlier. I can't figure out which numbers I'm missing.

Am I understanding the problem correctly? I don't think it's too much to give the details of this brute force method, which couldn't hope to get to 10^16:

• Compute and store the prime factorization of all numbers from 2 to the limit, excluding duplicates. For example, 1050 = 2 * 3 * 5 * 5 * 7, so store {2, 3, 5, 7} .
• Add 1 to the running total if this length of the set of prime factors is >= 4 and the largest prime in the set is < 100 .

If I were to PM someone a list of my 8963 numbers for 10^5, could someone respond with the 317 numbers I'm missing?

[Bo102010]

Never mind, I figured it out!

The phrase "divisible by at least four distinct primes less than 100" means that each valid number is divisible by four primes less than 100, but the 5th, 6th, 7th, etc. primes can be larger than 100.