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.
viv_ban
Posts: 23
Joined: Mon May 26, 2008 3:09 pm

problem 210

Post by viv_ban »

Can somebody please confirm the answer for N(1000). my answer is 1597548.
thanks in advance.

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

Re: problem 210

Post by quilan »

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.
Last edited by quilan on Sun Jan 11, 2009 5:09 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 11:15 pm
Location: Bremen, Germany

Re: problem 210

Post by daniel.is.fischer »

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.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: problem 210

Post by TripleM »

Close, but your answer is too low.

viv_ban
Posts: 23
Joined: Mon May 26, 2008 3:09 pm

Re: problem 210

Post by viv_ban »

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

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

Re: Problem 210

Post by daniel.is.fischer »

Yep.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

sinan
Posts: 16
Joined: Mon Sep 15, 2008 10:14 am

Re: Problem 210

Post by sinan »

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

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

Re: Problem 210

Post by quilan »

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.
Last edited by quilan on Wed May 06, 2009 4:52 pm, edited 2 times in total.
ex ~100%'er... until the gf came along.
Image

sinan
Posts: 16
Joined: Mon Sep 15, 2008 10:14 am

Re: Problem 210

Post by sinan »

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.
r=24. Hmmm. OK I will try to see what happens there.

sinan
Posts: 16
Joined: Mon Sep 15, 2008 10:14 am

Re: Problem 210

Post by sinan »

sinan wrote:
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.
r=24. Hmmm. OK I will try to see what happens there.
I get 904 for both. I counted the number of stars in the following.

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

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 210

Post by MaJJ »

Hi,

I just want to assure myself that the circle-like shape is not a circle (which I thought when I looked at
Expand
- 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...
Image
Image

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

Re: Problem 210

Post by daniel.is.fischer »

I suggest you look at Thales' theorem (or its generalisation). That should tell you exactly what shape the figure is.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 210

Post by MaJJ »

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 :(

Code: Select all

Timing[PE210[1000]]
{0.297, 1597880}
Timing[PE210[2000]]
{1.14, 6392158}
Timing[PE210[3000]]
{2.61, 14382796}
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...
Image
Image

User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 11:57 am
Location: Sydney, Australia

Re: Problem 210

Post by thedoctar »

N(10^7)=removed
N(10^8)=removed

Is this correct?
Last edited by thedoctar on Mon Jul 23, 2012 10:53 am, edited 1 time in total.
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames

User avatar
hk
Administrator
Posts: 10871
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 210

Post by hk »

[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?
Image

User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 11:57 am
Location: Sydney, Australia

Re: problem 210

Post by thedoctar »

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
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?
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames

User avatar
hk
Administrator
Posts: 10871
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 210

Post by hk »

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

User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 11:57 am
Location: Sydney, Australia

Re: Problem 210

Post by thedoctar »

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!!
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames

coreyjkelly
Posts: 7
Joined: Fri Dec 28, 2012 5:54 am
Location: Canada

Re: Problem 210

Post by coreyjkelly »

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 :(
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 210

Post by thundre »

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

Post Reply