problem 210
Posted: Sat Jan 10, 2009 7:55 pm
Can somebody please confirm the answer for N(1000). my answer is 1597548.
thanks in advance.
thanks in advance.
Project Euler Forum
A website dedicated to the puzzling world of mathematics and programming
https://projecteuler.chat/
Problem 210
Page 3 of 4
Re: problem 210
Posted: Sat Jan 10, 2009 8:49 pm
That answer is (I believe) incorrect. We had a thread discussing this problem a while back, if you'd like to search around for it.
Re: problem 210
Posted: Sat Jan 10, 2009 9:17 pm
All the "Problem xxx" threads (except the newest) have been moved because they cluttered up a lot of subfora, they will return concentrated in one place, but there's some merging and editing work to be done before that.
Re: problem 210
Posted: Sat Jan 10, 2009 10:52 pm
Close, but your answer is too low.
Re: problem 210
Posted: Sun Jan 11, 2009 12:38 pm
I have checked my program and I found a small error, but still I am unable to get the correct answer. Can someone please tell me if I am correct this time.
N(1000) = 1597880
N(10000) = 159814790
N(100000) = 15981722482
N(1000000) = 1598174519142
N(1000) = 1597880
N(10000) = 159814790
N(100000) = 15981722482
N(1000000) = 1598174519142
Re: Problem 210
Posted: Sun Jan 11, 2009 9:21 pm
Yep.
Re: Problem 210
Posted: Wed May 06, 2009 1:36 pm
What does |x| + |y| ≤ r mean? It should define a diamond shaped area, right? I don't understand what kind of trap did you fall into? I have found a closed formula that seems to work for small number without writing any code, then what happens? I have a feeling from the messages in this thread that there is a circle thing here but I cannot understand how a diamond shaped area becomes circle??
******* 4
******4 3 4
****4 3 2 3 4
**4 3 2 1 2 3 4
4 3 2 1 0 1 2 3 4
**4 3 2 1 2 3 4
****4 3 2 3 4
******4 3 4
********4
******* 4
******4 3 4
****4 3 2 3 4
**4 3 2 1 2 3 4
4 3 2 1 0 1 2 3 4
**4 3 2 1 2 3 4
****4 3 2 3 4
******4 3 4
********4
Re: Problem 210
Posted: Wed May 06, 2009 3:28 pm
Well, you're absolutely right re: diamond, but you'll see that something subtle happens with regards to forming the triangle. I don't want to take away the joy of discovery from you, but the smallest example that shows the errant behavior starts @ r=24. Do a brute-force of the coordinate space & compare to the correct answer. This problem is quite nice in the way it sneaks that one in there.
Edit: Correct answer is 916 I think... provided my old code still works. And I -think- it was 24 that causes the odd behavior. Might have been 20 or something.
Edit: Correct answer is 916 I think... provided my old code still works. And I -think- it was 24 that causes the odd behavior. Might have been 20 or something.
Re: Problem 210
Posted: Wed May 06, 2009 3:40 pm
r=24. Hmmm. OK I will try to see what happens there.quilan wrote:Well, you're absolutely right re: diamond, but you'll see that something subtle happens with regards to forming the triangle. I don't want to take away the joy of discovery from you, but the smallest example that shows the errant behavior starts @ r=24. Do a brute-force of the coordinate space & compare to the correct answer. This problem is quite nice in the way it sneaks that one in there.
Re: Problem 210
Posted: Wed May 06, 2009 5:05 pm
I get 904 for both. I counted the number of stars in the following.sinan wrote:r=24. Hmmm. OK I will try to see what happens there.quilan wrote:Well, you're absolutely right re: diamond, but you'll see that something subtle happens with regards to forming the triangle. I don't want to take away the joy of discovery from you, but the smallest example that shows the errant behavior starts @ r=24. Do a brute-force of the coordinate space & compare to the correct answer. This problem is quite nice in the way it sneaks that one in there.
Code: Select all
*
***
*****
*******
*********
***********
4************
432************
43210************
4321098************
432109876************
43210987654************
4321098765432***********4
**2109876543212*********2**
****0987654321012*******0****
******8765432109012*****8******
********6543210989012***6********
**********4321098789012*4**********
************2109876*****2************
**************09876*****0*2************
****************8765****8**12************
******************654***6***012************
********************43**4****9012************
**********************2*2*****89012************
************************0*****6789012************
**********************2*2345678901234**********
********************4***4567890123456********
******************6*****6789012345678******
****************8*******8901234567890****
**************0*********0123456789012**
************2***********2345678901234
**********4*************45678901234
********6***************678901234
******8*****************8901234
****0*******************01234
**2*********************234
4***********************4
***********************
*********************
*******************
*****************
***************
*************
***********
*********
*******
*****
***
*
Re: Problem 210
Posted: Sun Oct 25, 2009 1:53 am
Hi,
I just want to assure myself that the circle-like shape is not a circle (which I thought when I looked at - I thought it's just some rounding errors or I don't know what)... But at a bigger numbers it starts to get - and Mathematica probably shouldn't make any rounding errors as long as I'm using the fractional notation. So could anybody just assure me in this? I wasted lots of time making equations for circle, just to see that they don't work...
I just want to assure myself that the circle-like shape is not a circle (which I thought when I looked at
Expand
Expand
Re: Problem 210
Posted: Sun Oct 25, 2009 1:05 am
I suggest you look at Thales' theorem (or its generalisation). That should tell you exactly what shape the figure is.
Re: Problem 210
Posted: Tue Oct 27, 2009 12:32 pm
Thales' theorem somehow helped, thanks. But in the end I found out the shape with simply plotting the N(200). Then one little sqrt(2) and I was ready to analyze further 
ATM my code works, but it's quite slow. And I think I have a nice way to calculate it! But still, the more N, the more loops
I guess I'm not going to reach the 1,000,000,000 this way...
Is there a solution which doesn't require loops? Or at least not so many loops? (for 1000 my code does cca 1650 loops - I can PM my algo if you want)
EDIT: I think I just found a way to make it 4x faster, but I'll have to rewrite it into the code... But even if 4x faster, it'll run for eternity...
ATM my code works, but it's quite slow. And I think I have a nice way to calculate it! But still, the more N, the more loops
Code: Select all
Timing[PE210[1000]]
{0.297, 1597880}
Timing[PE210[2000]]
{1.14, 6392158}
Timing[PE210[3000]]
{2.61, 14382796}Is there a solution which doesn't require loops? Or at least not so many loops? (for 1000 my code does cca 1650 loops - I can PM my algo if you want)
EDIT: I think I just found a way to make it 4x faster, but I'll have to rewrite it into the code... But even if 4x faster, it'll run for eternity...
Re: Problem 210
Posted: Mon Jul 23, 2012 7:53 am
N(10^7)=removed
N(10^8)=removed
Is this correct?
N(10^8)=removed
Is this correct?
Re: Problem 210
Posted: Mon Jul 23, 2012 9:08 am
[mar]don't post intermediate results[/mar]
So please remove your values.
You could as well calculate your answer for 10^9 and use the PE answer box couldn't you?
So please remove your values.
You could as well calculate your answer for 10^9 and use the PE answer box couldn't you?
Re: problem 210
Posted: Mon Jul 23, 2012 10:55 am
I get the same results as this person and daniel.is.fisher confirms them in the next post, but my answer for 10**9 is wrong, which is why I posted my higher results. Could you just double check if the above results are correct? Or could you PM me the answer for 10**7?viv_ban wrote:I have checked my program and I found a small error, but still I am unable to get the correct answer. Can someone please tell me if I am correct this time.
N(1000) = 1597880
N(10000) = 159814790
N(100000) = 15981722482
N(1000000) = 1598174519142
Re: Problem 210
Posted: Mon Jul 23, 2012 1:32 pm
viv_bans values are correct.
BTW daniel.is.fisher was one of the team that were involved in the development of this problem so you should not doubt him on this.
I'm suspecting you have an accuracy problem about which already much has been written in this thread.
BTW daniel.is.fisher was one of the team that were involved in the development of this problem so you should not doubt him on this.
I'm suspecting you have an accuracy problem about which already much has been written in this thread.
Re: Problem 210
Posted: Mon Jul 23, 2012 2:12 pm
Well I'm sure he was, however I just wanted to be absolutely sure, as he might've misread the numbers or something similar, and although I know it's unlikely, I just wanted to be absolutely sure. I also thought that a problem with floating point precision would've come up at 10^6, as it is a pretty large value, but then again I wouldn't know. I'll try some of the methods in this thread to see if I get the correct answer.
Thanks for your help.
EDIT: yep, you were right! I got the answer right. Wow, I thought that floor(sqrt(x)) would give you an accurate floor of the root of x, but apparently not! Thanks again!!
Thanks for your help.
EDIT: yep, you were right! I got the answer right. Wow, I thought that floor(sqrt(x)) would give you an accurate floor of the root of x, but apparently not! Thanks again!!
Re: Problem 210
Posted: Fri Dec 28, 2012 9:12 am
I've been banging my head on my desk all night because of this one. Could somebody confirm that Python isn't plagued with the accuracy and overflow issues discussed here? All of my testing would indicate that the large numbers are properly dealt with, and math.floor(x**0.5) seems to function properly.
My results for values up to r=10^6 were consistently off by 1, which I couldn't justify, but adding 1 to my answer for 10^9 doesn't work
My results for values up to r=10^6 were consistently off by 1, which I couldn't justify, but adding 1 to my answer for 10^9 doesn't work
Re: Problem 210
Posted: Fri Dec 28, 2012 8:01 pm
I don't know that much about Python. I gather that its integers are naturally "big". But how would the interpreter know how much precision you need in an exponentiation?coreyjkelly wrote:All of my testing would indicate that the large numbers are properly dealt with, and math.floor(x**0.5) seems to function properly.