Problem 058

[ricc]

the forum thread from problem 58 has been locked. where can i post queries regarding the validity of the solution?

[daniel.is.fischer]

You can PM me.

[yog.sothothe]

Has anybody noticed that the sample posted is wrong...

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

Code: Select all

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

the spiral should start going left and so should do the branch generating each outer square
it does not change the diagonal values nor the formulas because of some odd simmetry,
but the layout is a bit different

[TripleM]

The spiral in that diagram goes anticlockwise like the problem statement says. Sure, there are other methods of generating anticlockwise spirals, but it says:

and spiralling anticlockwise in the following way

So no, the problem statement is not wrong.

[yog.sothothe]

Yes it is! at least from a logical point of view
it' s just an arbitrary decision of Yours to make right what is wrong.
it would be more correct to say anticklockwise, except the first move which I( the problem poser) arbitrarily and against any logic decide to
make in the wrong direction.
see problem 28 where the 2 is in the same position as this one, and correctly defined as clockwise

[Lord_Farin]

Quit whining. This is not about the problem statement. You are just upset because the problem designers have decided against (your) logic. What rule decides where a layer of the spiral begins? None, that is arbitrary.

[hk]

Hope this helps:
Anticlockwise means: at each TURN you make a left turn (seen from above).
Clockwise means: at each TURN you make a right turn (seen from above).
This means that the first step can be made in ANY direction, as long as you keep taking left turns after that first step.
The problem example clearly defines the direction of the FIRST step. Nothing wrong with doing it the way it is done.

[yog.sothothe]

This means that the first step can be made in ANY direction, as long as you keep taking left turns after that first step.
The problem example clearly defines the direction of the FIRST step. Nothing wrong with doing it the way it is done.

I was only making a comparison with the problem 28 layout and I was expecting also the first move to be different, that' s all
Just trying to understand... I was not complaining, not whining, and I am not upset!
Thank You anyway. I liked Your answer much better than the arrogant(*) reply of Lord_... I forgot his name

It' s not an issue about right or wrong, just about agreeing on the premises and terminology!

(*)with due respect, if that is the tone somebody should expect around here I will not post any longer
is not in my habit to start flames but also is not my habit, and I will not stand, to be disrespected

dropping out of these forums...
my best regards
Yog

[hk]

Dropping out of these forums would be a pity because they can be helpful.
Perhaps you could become a little more careful when stating a problem description is wrong? And certainly when you are kindly corrected in the way TripleM did. We all understand that one can have problems understanding what a problem description says, but coming in stating it is wrong??
You know the problem has been live for over 6 years now. Small chance it actually IS wrong with so many people having gone through it.

[sstein]

I keep getting a wrong answer on this one and its annoying me because it seems to be really simple.

can someone confirm my results below for percentages > 10%

Cor is bottom right corner on that spiral.

First drops below 50% at side length 11. Diagonal count: 21. Prime Count 10. Cor: 121
First drops below 40% at side length 31. Diagonal count: 61. Prime Count 23. Cor: 961
First drops below 30% at side length 49. Diagonal count: 97. Prime Count 28. Cor: 2401
First drops below 20% at side length 309. Diagonal count: 617. Prime Count 123. Cor: 95481
First drops below 15% at side length 981. Diagonal count: 1961. Prime Count 294. Cor: 962361

???

I think my list of primes I generate to check if a number is prime or not is just too small. I generate a list of primes. Then check if each diagonal (top left, top right, bottom left) exist in this list. It generates an answer but I think my prime count ends up wrong due to it all coming out false eventually.

[Mr.Wizard]

I only looked at the "first drops below" numbers, not the counts, but they seem right to me.

[rodegia]

sstein,
I ran into the same problem. I got the same numbers. I figured out what was going wrong. I wasn't generating enough primes. Around 12% there wasn't enough for it.

[olleicua]

I'm having trouble generate the primes fast enough. I'm memoizing the primes in a hash using a sieve algorithm. I'm currently generating all primes below 10,000,000 and my program is taking almost a minute to run. My understanding is that these problems should take much less time. Is there a way to solve this without sieving this far or am I just sieving inefficiently. Could someone look at my ruby code?

[thundre]

I'm having trouble generate the primes fast enough. I'm memoizing the primes in a hash using a sieve algorithm. I'm currently generating all primes below 10,000,000 and my program is taking almost a minute to run. My understanding is that these problems should take much less time. Is there a way to solve this without sieving this far or am I just sieving inefficiently. Could someone look at my ruby code?

You can probably improve your prime sieve by looking at some examples on the web. There are simple algorithms which are fast because they use only addition -- no multiplication or division (and no modulo, which is essentially division that keeps the remainder and throws away the quotient).

There are also other primality tests.

For some of the more advanced problems, one minute in Ruby would be a great victory.

[hk]

We also offer a prime sieve tutorial.
See the overview for problem 10.

[NotMyFault]

I have code that should work but isn't working. It's in C++, definate spoiler to post it so could I PM someone/someone PM me?

A little by the way, Why isn't there irc.projecteuler.net??

[rayfil]

We realize you are new to this forum. Please don't start a new thread for a problem when one already exists. For your information, problem numbers below 100 are padded with 0's to produce all 3-digit numbers for ease of searching. Your question(s) may already have been answered when you search properly.

Also please read the sticky thread entitled "Comments, questions and clarifications about PE problems".

[hk]

A little by the way, Why isn't there irc.projecteuler.net??

Why should there be?

[SekritAlias]

So I've been trying this problem for a while. I'm generating the diagonals, and after every 4, calculating the ratio of primes. Once that is less than .1, I print the side length. The issue seems to be that I run out of primes. I just made a list of all primes below 40,000,000, and the diagonals seem to get bigger than that before I even get under .11. I did check the first couple ratios generated, they were right (IE, for sidelength of 7 I had r~=.615). I just checked, and my prime generating algorithm (which I've used a number of times successfully with smaller numbers), generates the same number of primes as wolframalpha says there should be, so I doubt that is the issue;

[RishadanPort]

--

See next post: