Problem 268

[Cerium]

Hi all,

Problem 268 (View Problem)

I get a wrong answer for 10¹⁶ and primes below 100, so can someone tell me if I get the right answer for 10⁸ and primes below 25 for instance, I get : 5229364 is it too low, too high or maybe near the right answer ?

Thanks in advance.

[ac336]

My solution isn't correct yet but I get:

For 10^8 and primes below 25 i get 3301377

For primes up to 100 i get:
10^6: 77579
10^7: 768778
10^8: 7881475

Am I anywhere near correct?

[ac336]

Scratch that, solved it now - those numbers should be correct.

[Cerium]

Ok thanks

[Jochen_P]

Scratch that, solved it now - those numbers should be correct.

Yep, those numbers are correct...

# 10^4:_____811
# 10^5:____9280
# 10^6:___77579
# 10^7:__768778
# 10^8: _7881475

Can't tell for 10^9 of course, as this is where memory ends
If I'd split up the dictionary in 10^16/10^8 parts the code would run for a bit over 15 years

[hisoka-san]

This problem reminds the very first problem...

[zwuupeape]

Can't tell for 10^9 of course, as this is where memory ends
If I'd split up the dictionary in 10^16/10^8 parts the code would run for a bit over 15 years

I will definitely not be giving too much away if I tell you there are other means to solve this problem than directly counting.
Start by asking yourself how many numbers less than 1000 have at least 1 prime factor less than 4, and how many have at least 2 prime factors less than 6, and continue from there.

[Jochen_P]

Start by asking yourself how many numbers less than 1000 have at least 1 prime factor less than 4...

The result for this first question gives a hint on who 'really' designed that problem

[stijn263]

What do you mean? As far as I know, this was a problem proposal from sfabriz

[zwuupeape]

What do you mean? As far as I know, this was a problem proposal from sfabriz

It's a bit cryptic. The answer is 666, so he means the devil

[elendiastarman]

What do you mean? As far as I know, this was a problem proposal from sfabriz

It's a bit cryptic. The answer is 666, so he means the devil

Psshhhh....it's NOT 666. It's OBVIOUSLY 42...



Well... maybe 424242.

[zwuupeape]

I don't mean the answer to the problem, but the answer to the simpler question - how many numbers below 1000 are divisible by 2 or 3. The answer is, indeed, 666

[elendiastarman]

...I bet I could take 10 minutes and use numerology and this fact to prove that sfabriz IS the devil....

[sfabriz]

...I bet I could take 10 minutes and use numerology and this fact to prove that sfabriz IS the devil....

[Diadem]

I've recently discovered this website. I did a lot of the easier ones, but I decided I wanted to do a really hard one.

But wow, this one is hard!

I found a 'smart' algoritm that is independent on the upper bound of 10^16. But it goes as the factorial of the number of primes you need to test. There are 25 below 100, and 25! computations is a bit too much for my computer to handle.

If A is a set of primes and B is a set of primes I need to figure out how many numbers are divided by any number in A but are not divided by any number in B. I can't do that in less than factorial time though.

[sfabriz]

I've recently discovered this website. I did a lot of the easier ones, but I decided I wanted to do a really hard one.
But wow, this one is hard!
I found a 'smart' algoritm that is independent on the upper bound of 10^16. But it goes as the factorial of the number of primes you need to test. There are 25 below 100, and 25! computations is a bit too much for my computer to handle.
If A is a set of primes and B is a set of primes I need to figure out how many numbers are divided by any number in A but are not divided by any number in B. I can't do that in less than factorial time though.

This one is not that hard, actually.
When you figure out what to do is just a matter of doing it.
If you're stuck with an algorithm that is clearly not the right choice for this problem, try working on the problem from another point of view.
This is why i find that problem threads are so useful, because you learn from what others have done and discover sometimes very different points of view for the same problem.
To solve this one anyway, I guess 100% of those who did it used the same principle.
So, good luck!
sfabriz

[Diadem]

I'm been racking my brain for days now over my problem (well, it's not like I've been working full-time on it. But it's been at the back of my mind for days now). And I just can't find a solution.

I suppose I can't really go into detail about what I'm trying without potentionally giving away stuff. Is there anyone I can PM what I'm trying to do, who can let me know if I'm on the right track, or if what I'm doing is complete BS.

I just had a new idea of how to do it, but it turns out I'll need 5172478382359200 computations for that. Jikes. So far none of my smart algoritms are faster than direct brute force computation.

[Ted]

I would be disappointed, actually, to see Diadem's question answered here. One of the original attractions to Project Euler, for me at least, is at the bottom of the Problems page: NOTE: Please do not contact Project Euler if you are unable to solve a particular problem. If you can't solve it, then you can't solve it!

This is not directed personally at Diadem. I'm agnostic about the interim test results posted here. I resist asking such things, but can't always resist peeking at interim results, although I do feel guilty about it. But I would hate to have the approach to a problem laid out before joining the pantheon of solvers.

I post this because I want to weigh in as a citizen in support of the able administrators, who (I hope) would say the same. i men no disrespect, but as a long-time, not terribly able solver, I have spent weeks attacking problem 268 among 80 others, and wouldn't care much for loosening the rules at this point. (Maybe I'll feel different on my deathbed!)

Of course, as a citizen and not administrator, I can be safely ignored! Carry on!

[sfabriz]

...I have spent weeks attacking problem 268 among 80 others, and wouldn't care much for loosening the rules at this point. (Maybe I'll feel different on my deathbed!)...

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.
And it's not that hard, really, otherwise it would have made to a much higher number.

I'm not going to give out hints (sry) because that's not the spirit of this website, but I tell you what I do when I'm stuck (and it happens a lot!). I scratch the problem as much as I can, putting on paper every relation/equation/concept I think is important. Then, being stuck, I start searching (google, wikipedia, mathworld, ...) for related arguments to what I've written. Most of the times I discover that some guy 80 years ago was analyzing a similar problem and made a theorem that (oh, finally) cuts out 99% of my calculations and the problem becomes magically solvable.
You do that, and you add another brick to your knowledge, which is the ultimate point for being here working on math problems instead of being out having another kind of fun.

Also, I'd like to remind you one advice I've seen many times in these threads: "If you can't solve it, try to do first some other problems with smaller id, since many times happens that they will give you that sparkle you need to attack this one."
And I tell you, I am 100% sure that you've already done the one you need to get to this one.

This is as far as I can go helping you, I hope it's enough!
Cheers,
sfabriz

[Diadem]

I would be disappointed, actually, to see Diadem's question answered here. One of the original attractions to Project Euler, for me at least, is at the bottom of the Problems page: NOTE: Please do not contact Project Euler if you are unable to solve a particular problem. If you can't solve it, then you can't solve it!

This is not directed personally at Diadem. I'm agnostic about the interim test results posted here. I resist asking such things, but can't always resist peeking at interim results, although I do feel guilty about it. But I would hate to have the approach to a problem laid out before joining the pantheon of solvers.

I did not actually use the interim test results posted here. I generated my own ages ago with a brute force attack.

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.

Anyway I wasn't asking for hints per se. I merely want to know if my idea is anywhere feasible, or if I should redo from start.

I'm pretty new to this site. If such questions are inappropriate I'd like to hear it and I'll retract the question.

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.

And I tell you, I am 100% sure that you've already done the one you need to get to this one.

Yeah it's related to some problem with a ridiculously low number. I know I'm probably making this much more complex than it is by missing something simple. It's like that for all problems. Some of them I did in under 10 minutes with a very simple solution while others post horribly complex solutions that took them hours. Others take me hours, and once I've solved them I read on the acompanying forum thread: "I just realized x and y and so I did z and it took me 10 minutes". Such is life.

In the meantime I'm steadily working my way up through the other problems. Life won't end if I can't solve this one