Problem 210

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
miodrag.milenkovic
Posts: 17
Joined: Wed Apr 02, 2008 6:14 pm

Problem 210

Post by miodrag.milenkovic »

I must be crazy but I get a lot more for N(4). Don't know how to show it without giving away too much...

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 210

Post by daniel.is.fischer »

Count again. I get 24, too for r = 4.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

miodrag.milenkovic
Posts: 17
Joined: Wed Apr 02, 2008 6:14 pm

Re: Problem 210

Post by miodrag.milenkovic »

Yes, I was going crazy. Sanity restored, somewhat...

Taifu
Posts: 34
Joined: Sun Jan 13, 2008 8:38 pm

Re: Problem 210

Post by Taifu »

I got a right number for 4 and 8:

4 24
8 100
12 226
100 15648
1000000000 ?

But for 1000000000 it's wrong.

Can somebody tell me if 12 and 100 are right?

Thanks :-)
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 210

Post by daniel.is.fischer »

The number for r = 12 is correct, the one for r = 100 not.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 210

Post by quilan »

Taifu wrote:I got a right number for 4 and 8:

4 24
8 100
12 226
100 15648
1000000000 ?

But for 1000000000 it's wrong.

Can somebody tell me if 12 and 100 are right?

Thanks :-)
Bah, I came out with the same formula as you... looks like I'm gonna have to do r==24 by hand before I can figure this one out.
ex ~100%'er... until the gf came along.
Image

flyee
Posts: 1
Joined: Sat Sep 27, 2008 4:58 am

Re: Problem 210

Post by flyee »

quilan wrote:
Taifu wrote:I got a right number for 4 and 8:

4 24
8 100
12 226
100 15648
1000000000 ?

But for 1000000000 it's wrong.

Can somebody tell me if 12 and 100 are right?

Thanks :-)
Bah, I came out with the same formula as you... looks like I'm gonna have to do r==24 by hand before I can figure this one out.
i got the same formula -___-|||

LarryC
Posts: 66
Joined: Sat Jun 14, 2008 7:33 pm

Re: Problem 210

Post by LarryC »

Me also. This is a little tedious... ;-)

LarryC
Posts: 66
Joined: Sat Jun 14, 2008 7:33 pm

Re: Problem 210

Post by LarryC »

Ha! Found my mistake... Hopefully won't be long now.

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 210

Post by quilan »

lster wrote:Ha! Found my mistake... Hopefully won't be long now.
Yeah, it's a pretty sneaky bit of subtlety... now to finally work a method for solving that missing amount...
ex ~100%'er... until the gf came along.
Image

LarryC
Posts: 66
Joined: Sat Jun 14, 2008 7:33 pm

Re: Problem 210

Post by LarryC »

It is funny how so many of us have fallen into that trap... :)

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 210

Post by quilan »

Ok, this is annoying. So, apparently my algorithm is juuuust subtly off from correctness. I've done a manual check on up to 1000 but it becomes far too slow to calculate further. Is there any chance anyone can confirm/deny these values?

[snip values, not to give too much info to others]
ex ~100%'er... until the gf came along.
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 210

Post by daniel.is.fischer »

I didn't check your value for 100, the others are correct. So if your answer for 109 isn't accepted, you could PM me.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

Jarlax
Posts: 1
Joined: Tue Sep 30, 2008 7:37 am

Re: Problem 210

Post by Jarlax »

I have 2 algos for this problem - first one is O(N), second is bruteforce (for checking first algo on little values of N). I have tested both algos on many values of N (max tested - 10000) and they gived me equal results, but with N=1000000000 I got WA. Here are my results:
4 24
8 100
12 226
100 15944
10000 159814790
500000000 406249999821471154
Can somebody tell me if 500000000 is right?

sker
Posts: 5
Joined: Tue Sep 30, 2008 8:05 am

Re: Problem 210

Post by sker »

Taifu wrote:I got a right number for 4 and 8:

4 24
8 100
12 226
100 15648
1000000000 ?

But for 1000000000 it's wrong.

Can somebody tell me if 12 and 100 are right?

Thanks :-)
I got the same formula too.

User avatar
jaap
Posts: 550
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 210

Post by jaap »

It maybe should be mentioned in this thread that in most computer languages a floating point type with 64 bits (e.g. a 'double') will only have essentially 53 bits to hold an integer value. It is therefore not accurate for integers above 253, or about 9*1015.

User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: Problem 210

Post by Tommy137 »

I read this thread a few days ago (so I knew there was a trap) and just now analyzed the probleme with pen&paper... I walked right into the trap and I've got no idea how to get out of it :D


Edit: Ahh.. I think I found the missing parts :)
Image

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 210

Post by quilan »

Yeah, I should put it out there, that there seems to be many people (myself included) that have run into floating point rounding errors with the very large values in this problem. That being said, there are integer methods to solve this.
Last edited by quilan on Tue Sep 30, 2008 8:57 pm, edited 1 time in total.
ex ~100%'er... until the gf came along.
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 210

Post by daniel.is.fischer »

Jarlax wrote:I have 2 algos for this problem - first one is O(N), second is bruteforce (for checking first algo on little values of N). I have tested both algos on many values of N (max tested - 10000) and they gived me equal results, but with N=1000000000 I got WA. Here are my results:
4 24
8 100
12 226
100 15944
10000 159814790
500000000 406249999821471154
Can somebody tell me if 500000000 is right?
Unfortunately, it's wrong :(
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: Problem 210

Post by Tommy137 »

Yeah, I've got it.... finally :D
Image

Post Reply