Problem 351

[elr]

how exactly "hidden from the center" is defined ?
why the points that are circled in red in this picture:

are not hidden from the center ?

[jaap]

how exactly "hidden from the center" is defined ?
why the points that are circled in red in this picture:

are not hidden from the center ?

Because there is a straight line from the centre to any of those points which does not hit any of the other points of the grid.

[Marcus_Andrews]

There is a new PDF for this problem, which should come in handy for certain types of problems that solvers may be having difficulty with lately.

[pimspelier]

Argh... I've spent hours working on this problem, and finally I've got a good, fast algorithm: it gives the answer for 100000 in 0.13 seconds (while doing nothing takes 0.08 seconds).
But when I try 1000000, the program completely stops working and it gives an error: ProjectEuler.exe (the name) has stopped working. It returns -1073741571 (0xC00000FD). I've tried using unsigned long long ints instead of long long ints, but to no prevail. Does anyone know what the problem might be?

EDIT: Thanks mdean and Marcus, solved .

[mdean]

Argh... I've spent hours working on this problem, and finally I've got a good, fast algorithm: it gives the answer for 100000 in 0.13 seconds (while doing nothing takes 0.08 seconds).
But when I try 1000000, the program completely stops working and it gives an error: ProjectEuler.exe (the name) has stopped working. It returns -1073741571 (0xC00000FD). I've tried using unsigned long long ints instead of long long ints, but to no prevail. Does anyone know what the problem might be?

Impossible to guess without seeing the code (don't post that here, I have solved the problem so you can pm me if it's C/C++ and you want me to take a peek) . First figure out where the program is crashing, then figure out why the program is crashing.

[Marcus_Andrews]

Sounds like it may be a stack overflow, based on the error code (in this case, possibly a recursive algorithm that is trying to nest too deeply).

[dchaudh]

Hmm, I was confident I had the right answer, based on (i) a proof and (ii) the fact that my answers for small values of n matched those in the problem text...but the little man gave me a red cross!

Any chance someone could let me know if I have the correct values for H(million) and H(ten million)?
[(5,30),(10,138),(1000,1177848),(1000000,1176221685648),(10000000,117621891442704)]

Thanks!

[dchaudh]

Silly me, I was using Float when I should have been using Double. Sometimes, it's easy to get lulled into complacency when using a language with native big integers...

[DeKlod]

Hello all,
Maybe someone could enlighten me on this one: the PDF solution sheet for this problem describes several possible algorithms of varying efficiency, yet they mainly seem to rely on an array containing all the required integer values, i.e. 10^8 numbers in this case.
On my system and using C/C++, defining an array this size immediately causes a 'Segmentation fault' - and the number spaces required only get larger on some of the more difficult problems on PE.
Am I missing something?
Thanks in advance for any input!
Claude

[jaap]

On my system and using C/C++, defining an array this size immediately causes a 'Segmentation fault' - and the number spaces required only get larger on some of the more difficult problems on PE.
Am I missing something?

Do you know the difference between the stack and heap memory? Do you know how to use standard library containers such as std::vector?

[DeKlod]

Cheers Jaap,
I'm afraid I'll have to confess my ignorance on the first question (I'll google that though). I do use vectors, yes, but I would have thought it would pose problems of efficiency too as it will take up a lot of memory.
I'll try that approach over the weekend though and see what happens
Claude

[jaap]

Cheers Jaap,
I'm afraid I'll have to confess my ignorance on the first question (I'll google that though). I do use vectors, yes, but I would have thought it would pose problems of efficiency too as it will take up a lot of memory.
I'll try that approach over the weekend though and see what happens
Claude

I hope that is where your trouble lies. Basically, if you need to use lots of memory (more than the stack provides), you have to allocate it yourself from the heap. You can do it the old-fashioned C way with malloc/free, or the slightly more C++ way with new[]/delete[], or just use containers like std::vector. Use the smallest integer type you need. For example, with 32-bit integers allocating 10^8 of them takes 4*10^8 bytes, or about 400 Mb. This should be fine on any modern PC.

[DeKlod]

Thanks for that, jaap!
Just one last question, if I may: is there any other obvious technique if you really need large quantities of data? Imagine a sieve for primes up to - say - 10^12. Vectors of type bool seem to be fine up to about 10^10 but not further. So I guess that's where you need to change tack and do something completely different, right?
Not asking for hints, as such, just wanting to avoid long barking sessions up the wrong tree...
Cheers,
Claude

[jaap]

If you ever need more than, say, 600MB of data, then you are probably doing it wrong. You are either using the wrong solving method, or maybe you just don't need to have all of that data in memory at the same time.

[RishadanPort]

Let the middle orchard represent (0, 0).

if I have say an orchard that is on the X-Axis shifted (100 000 000 - 1) away but shifted up or below by 1, -- do I assume I can see this orchard even tho the line is extremely close to just horizontal line?

I am guessing all orchards are points with no width.

[RobertStanforth]

Let the middle orchard represent (0, 0).

if I have say an orchard that is on the X-Axis shifted (100 000 000 - 1) away but shifted up or below by 1, -- do I assume I can see this orchard even tho the line is extremely close to just horizontal line?

I am guessing all orchards are points with no width.

I have moved your post to the existing topic for this problem.
You are correct: we are considering points with no width.

[RishadanPort]

ok I solved this problem...

I am really wondering tho, why H(1000), H(1 000 000), and H(100 000 000) all look so similar... Can anyone explain? feel free to send me private message.

[RobertStanforth]

ok I solved this problem...

I am really wondering tho, why H(1000), H(1 000 000), and H(100 000 000) all look so similar... Can anyone explain? feel free to send me private message.

This question would be better asked in the solutions thread for this problem on the main site.

[Junglemath]

Why is the given example a hexagonal orchard of order 5 and not of order 6?

[hk]

Because the side of it has length 5.