Problem 233

enderw88 · Post by **enderw88** » Thu Mar 08, 2012 8:12 pm

ffff0 wrote:Same as everyone. As for now, i can't see any difference for even and odd N. And i can't understand why answer for 38000000 is correct and answer for 10^11 is not. I simply don't see any special cases between this numbers.

My code finds 5422051 solutions for 10^11. Is it too big or too small?

Update: Wait a bit, I've got an idea.

Update 2: And hero have won once again without any help!
There are 5422629 solutions in total and there is no difference between even and odd N. It's something else.

I am exactly where you were at the 5422051 solutions...if it wouldn't be too big of a hint can you explain why 38,000,000 is a significant number? If it is too much of a hint, then just ignore...

hk · Post by hk » Thu Mar 08, 2012 9:20 pm

38000000 is significantly less than 10^11.
That's the only significance of 38000000.

enderw88 · Post by **enderw88** » Thu Mar 08, 2012 9:58 pm

hk wrote:38000000 is significantly less than 10^11.
That's the only significance of 38000000.

Thanks! I was beginning to think it was astrological in nature...I will keep thinking.

Marcus_Andrews · Post by **Marcus_Andrews** » Sat Mar 10, 2012 4:58 am

hk wrote:38000000 is significantly less than 10^11.
That's the only significance of 38000000.

XD

enderw88 · Post by **enderw88** » Tue Mar 20, 2012 5:58 pm

Marcus wrote:
hk wrote:38000000 is significantly less than 10^11.
That's the only significance of 38000000.
XD

What is "XD"?

Marcus_Andrews · Post by **Marcus_Andrews** » Tue Mar 20, 2012 7:37 pm

enderw88 wrote:
Marcus wrote:
hk wrote:38000000 is significantly less than 10^11.
That's the only significance of 38000000.
XD
What is "XD"?

It's like a smiley.

For some reason "That's the only significance of 38000000" made me laugh

JMHoekstra · Post by **JMHoekstra** » Thu Jan 03, 2013 9:04 am

The first time I'm asking, but I could really use a hint on problem 233. By studying the properties of f(N) I have generated a list with all 'primitives' N. But I cannot find a way to also sum the right multiples for these, without double counting of common multiples etc, under 1e11, for f(N)=420 without requiring a 'quantum computer' in terms of computing time.

Any hints on how I should proceed?

EDIT: ok, so I was close already. Solved it one day later: fixed a bug. And with some smart aborting and limiting of loops, I could keep the computing time within acceptable limits. Also, sets in Python are great! Still, my solution is way over one minute though. More like 30 minutes. Luckily I saved my data from previous attempts. So the final program, by using two previously generated lists, ran in about 1 minute.

Quite surprising where this question leads you! Would never have guessed that, the first time I read the problem.

Fibonacci award!

Bye,
Jacco Hoekstra

TheEvil · Post by **TheEvil** » Thu Jan 03, 2013 10:47 am

When I was trying to solve this problem, I could find a formula for f(N), but I spent a day with finding that little mistake, like everyone else. If you have something for 'primitive' N-s, you should try to find something for general N-s. And after that you won't have double counting problems.

mdean · Post by **mdean** » Thu Jan 24, 2013 9:52 pm

Ugh... My code is giving the correct answer for 38,000,000 but my answer for 10^11 is apparently wrong. Guessing it's probably a rounding error at this point.

Update: my 10^10 value turned out to be correct and it wasn't a rounding error, but I did manage to find and correct the problem. Looks like I just need 144 for Fibonacci Fever now. That problem and problem 84, which I need for centurion, I'm kind of dreading...

ffff0 · Post by **ffff0** » Fri Jan 25, 2013 1:56 am

You are not the first one. I bet that it's not rounding error. You miss something.

bobjalynch · Post by **bobjalynch** » Sun Jul 14, 2013 4:07 am

I'm missing something on this one. My code is written generically, so should work for any value of N. I get the answer quoted on this forum when I plug in the test case N = 38,000,000. But my solution for N=1^11 is wrong. I know I'm on the right path, as I get the same # of solutions (5422051) as ffff0 mentioned in his original post. So far, I haven't had the same epiphany that ffff0 had, when he got the right # of solutions at 5422629. I'm only off by 578 solutions, out of 5.4 million ! I've scoured my brain and my code for something missing, but I'm coming up blank. Any minor minor hints pointing in the right direction would be greatly appreciated (although my suspicion is that any hint will give it away).... ffff0 - Maybe it would be too big a hint, but would you be willing to give me a value of N that was in your updated correct list (of 5422629 solutions) that wasn't in your list of 5422051 solutions ?

bobjalynch · Post by **bobjalynch** » Sun Jul 14, 2013 4:32 am

Think I just had my epiphany, having to do with the completeness of my 3(mod4) list. Now I just have to figure out to code it, but not tonight. Will get back tomorrow, hopefully with glory...

bobjalynch · Post by **bobjalynch** » Sun Jul 14, 2013 2:14 pm

No glory after a few more hours of troubleshooting... <snip by mpiotte> Number of solutions = 5422051, off by a few hundred, compared to posted correct answer. Any hints possible ?
EDIT by mpiotte: spoiler removed.

rlindley · Post by **rlindley** » Mon Aug 12, 2013 4:09 pm

I don't know why I did not think to look here when I was working on this problem. It sure would have helped me. But I finally got it anyway.

n2sz · Post by **n2sz** » Sun Aug 12, 2018 4:30 pm

I wanted to just drop in and thank everyone who participated in this thread. I like having a 'safe zone' where I can get hints which will not destroy the value of the puzzle. Due to the various points of info given here, I was able to confirm that I was mostly on the right track, which was a great boost for my determination to continue. It turned out to be a number of silly bugs, including, but not limited to, the very same silly bugs others were dealing with (< instead of <= for instance!).

DeKlod · Post by **DeKlod** » Wed Mar 20, 2019 7:51 am

Nothing particularly interesting to say, other than that I'm one of those who get the 'classic but wrong' answer for 10^10 as well even though the answer for 38000000 is correct.
So if, as I rather expect, I end up going completely mad over this one, please come and visit me at the hospital

DeKlod

DeKlod · Post by **DeKlod** » Fri Mar 22, 2019 7:04 am

Blimey, got there in the end - and I can't believe how long I spent looking at the code when it turned out to be basically sound and my mistake was somewhere entirely else...
I know see why so many people seem to be getting the same false result as I did: and to all my bothers and sisters out there who are struggling: don't despair, check your very basic arithmetic and remember that there's more than one way to skin a cat (hope that's not too much of a hint)

llawton · Post by **llawton** » Wed Aug 02, 2023 5:04 pm

OK - thought I had it. I'm blind, so I shy away from a lot of the geometry problems, but I got excited when I started thinking about triangles and factorizations.
But based on earlier posts, I am missing a whole slew of solutions. I can generate 585259 "minimal" solutions - i.e. solutions where any proper divisor is not a solution. Can anyone confirm or tell me by what order of magnitude I am off? When I throw in the relevant multiples, I get nowhere near 5000000 solutions.
Help? Beating my head against a wall . . ..

llawton · Post by **llawton** » Thu Aug 03, 2023 4:26 pm

Yay! I was hoping that posting would jostle something loose and help me find the program or logic bug - got it now. Thanks for letting me post.

Project Euler Forum

Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233

Re: Problem 233