Problem 210

[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...

[daniel.is.fischer]

Count again. I get 24, too for r = 4.

[miodrag.milenkovic]

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

[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

[daniel.is.fischer]

The number for r = 12 is correct, the one for r = 100 not.

[quilan]

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.

[flyee]

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]

Me also. This is a little tedious...

[LarryC]

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

[quilan]

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...

[LarryC]

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

[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]

[daniel.is.fischer]

I didn't check your value for 100, the others are correct. So if your answer for 10⁹ isn't accepted, you could PM me.

[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]

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.

[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 2⁵³, or about 9*10¹⁵.

[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


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

[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.

[daniel.is.fischer]

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

[Tommy137]

Yeah, I've got it.... finally