Problem 210

[viv_ban]

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

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

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

[TripleM]

Close, but your answer is too low.

[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

[daniel.is.fischer]

Yep.

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

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.

[sinan]

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]

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]

Hi,

I just want to assure myself that the circle-like shape is not a circle (which I thought when I looked at

Expand

this

- I thought it's just some rounding errors or I don't know what)... But at a bigger numbers it starts to get

Expand

pretty linear and out of the circle radius

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

[daniel.is.fischer]

I suggest you look at Thales' theorem (or its generalisation). That should tell you exactly what shape the figure is.

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

[thedoctar]

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

Is this correct?

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

[thedoctar]

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?

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

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

[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

[thundre]

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?