Project Euler Forum

SekritAlias wrote: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;

If you think everything's working correctly and you've run out of prime numbers, what course of action do you think this suggests?

mdean wrote: If you think everything's working correctly and you've run out of prime numbers, what course of action do you think this suggests?

Generate more primes ?

I'am sorry but I have been stuck on this problem for 3 days generating up to 707081281 sieve matrix and still hitting ~10% ratio
The code takes ~30min to generate that giant spiral and consumes all of my 4GB ram.

Also is the ratio considered a "rounded" or a "floored" double of the average ?

Thanks.

Zvirx wrote:

mdean wrote: If you think everything's working correctly and you've run out of prime numbers, what course of action do you think this suggests?

Generate more primes ?

I'am sorry but I have been stuck on this problem for 3 days generating up to 707081281 sieve matrix and still hitting ~10% ratio
The code takes ~30min to generate that giant spiral and consumes all of my 4GB ram.

So you'll have to think of some other way to check which numbers on the diagonals are prime.

Zvirx wrote:Also is the ratio considered a "rounded" or a "floored" double of the average ?

It's a ratio of two whole numbers - a rational number - which you have to compare to 1/10. There is no flooring or rounding involved in that question. How you get your computer to do this comparison is up to you.

jaap wrote: So you'll have to think of some other way to check which numbers on the diagonals are prime.

This gave me a huge idea, but not about how to generate the primes; i still use the same sieve method but wiped clean my algorithm for generating the spiral and wrote a smarter one, now the solution takes 30 seconds, 29 seconds of those 30 are for generating the sieve and not the spiral

jaap wrote: It's a ratio of two whole numbers - a rational number - which you have to compare to 1/10. There is no flooring or rounding involved in that question. How you get your computer to do this comparison is up to you.

You are right but this exactly where i was thrown off where it said "a ratio of 8/13 ≈ 62%" while that is technically correct its not what it meant when comparing it to 1/10.

Thank you jaap, you made me think of a better algorithm to generate the spiral; i was able to solve the problem.

can someone confirm if the answer is around 32800? because that's what I keep getting, but it's not right. I think i'm just a little off...

sstein wrote:I keep getting a wrong answer on this one and its annoying me because it seems to be really simple.
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'm getting the same diagonal and prime counts for the percentages, but my side lengths are smaller than yers ... still can't get the right answer tho >.<

solarmew wrote:can someone confirm if the answer is around 32800? because that's what I keep getting, but it's not right. I think i'm just a little off...

"... a little off..." is a relative term. I would say that 32800 is not very close - but then, that's relative, also.

Tom

how about 26200-ish? XD I think the way my algorithm output the side length the first time was weird ... this seems closed to what other person here got before, but still no cigar :I ....

Edit:

yep, got it ... stoopid floor function ... tried to mess me up ...

I modified code from Problem 28 (Number spiral diagonals) to go counterclockwise and applied to primes.
I have the answer where a side is below 700 and it is not accepted. Any hints to verify what I am doing wrong in my algorithm?
Thanks.

For debugging these problems in general, it often helps to test smaller cases first. For example, do you get the correct ratio for the spiral of side length 7? If not, investigate why not.

Thank you mdean. My code correctly calculates for 7 but failed for

sstein wrote:
I keep getting a wrong answer on this one and its annoying me because it seems to be really simple.
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 calculated for each side with increment 1. However, it must be increment 2 because based on the problem description the new spiral adds 2 to a side.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed.

Now everything works. My program is now stopping execution on out of memory exception without reaching 10% level.

EDIT:
Fix it. It is now working and the solution below 10% is found !

Hey all!

I write a python code but I cannot see why my answer is wrong so anyone can help me to find it ? I run the code for the 7 lenght case and it works

This problem aroused my curiosity about square spirals, so I made a spreadsheet to find out their properties, and got the following Square Spiral Rules, which I hope will be interesting, at least some of them. I followed the same pattern to create my spirals as the original problem.

Note: These are just my observations, I have not done any research to find out if any or all of the properties I describe here have been already published. But, even if all them are known since many years ago, it was fun for me to find them by myself.

The behaviors of the diagonal (corner) elements of square spirals simply follow the structure mandated by the regular increments, by beginning from the start number, located at the center of the spiral and set at any value, and the repetitive application of the constant step, which is the difference, set also at any value, between consecutive elements along the vertical and horizontal sides of the spiral. So, even if many readers will not find anything interesting in these behaviors, for sake of completeness I listed all that I found, but I think that rule 1.8 is surprising because of the exception it contains, maybe it is even inexplicable. And other rules sound also interesting to me.

1. Regarding the last digit of the elements along each of the four diagonals of a square spiral, for any combination of the start number, odd or even, and the step, odd or even, except when the step is a multiple of 5, the following behaviors are observed:

1.1. The last digit is repeated cyclically.

1.2. The cycle is different for each diagonal.

1.3. The length of all cycles is five.

1.4. Regardless of the step, the last digits have the same parity as the start number.

1.5. The last digit of the cycle, i.e. the fifth one, equals the start number.

To give two examples of the five rules above, for a start number set at 3 and steps set at 3 and 4, the elements of the top-right (T-R) diagonals end with the digits, listed from innermost corner to outermost corner, of 9-9-3-1-3… and 1-1-3-7-3…, respectively.

1.6. Each five-digit cycle has two consecutive numbers repeated. The location of that pair moves one step to the right along the cycle as the diagonal investigated moves one step counterclockwise. For example, for a start number set at 2 and step set at 2, the diagonal cycles, listed from the T-R one to the bottom-right (B-R) one, are 6-6-2-4-2…, 0-4-4-0-2…, 4-2-6-6-2…, and 8-0-8-2-2…, respectively, showing the one-step translation of the pair in the right direction.

1.7. The pair repeated at the T-R cycle and the bottom-left (B-L) are the same. For example, for a start number set at 5 and step set at 2, those cycles are 9-9-5-7-5… (T-R) and 7-5-9-9-5… (B-L).

1.8. Additionally to the last digit of any cycle being the same as the start number, as indicated in rule 1.5, all cycles for any step, except for the T-L diagonal, have that start number repeated: for the T-R cycle, at the third digit position; for the B-L cycle, at the second digit position; and for the B-R cycle, at the fourth digit position (this in agreement with rule 1.6). The start number is never repeated at the T-L diagonal. For example, for a start number set at 6, those cycles for a step set at 2 are: 0-0-6-8-6… (T-R), 4-8-8-4-6… (T-L), 8-6-0-0-6… (B-L), and 2-4-2-6-6… (B-R).

1.9. When comparing the same diagonal and the same step for two consecutive start numbers of the same parity, the ending digits move one step to the right in the corresponding odd or even sequence 1-3-5-7-9-1-3… or 0-2-4-6-8-0-2…. For example, with the step number set at 3, the cycle of the B-L diagonal with the start number set at 5 is 3-5-1-1-5…, each digit is one step higher, i.e. to the right in the odd numbers sequence, than the corresponding digit of the B-L cycle with the start number set at 3, which is 1-3-9-9-3….

2. When the step is set to a multiple of five, there are no cycles, all elements along all diagonals end with the start number.

3. For any start number, the cycles repeat in the same order before and after the step set at 5 or its multiples so, for example, the last digits of each of the four diagonals for step set at 1 are equal to those for step set at 6, last digits with step set at 2 and 7 are equal, and so on. A more specific example is that the cycle for the top-left (T-L) diagonal for a start number set at 4 is 6-2-2-6-4… when the step is set at 3, 8, 13, 18….

4. When the sixteen cycles, for any start number, for steps set in the range from 1 to 4, which are identical as those for steps 6 to 9, as indicated in rule 3, are written grouped vertically by diagonal, that is, all four cycles for the same diagonal appear in the same column, the following behaviors are observed, which are the same as when the steps that are compared are the four steps smaller or larger than any multiple of five:

4.1. Comparing consecutive steps, the differences along the corresponding odd or even numbers sequences, between corresponding cycle digits are: 1-1-0-3-0 (T-R), 2-3-3-2-0 (T-L), 3-0-1-1-0 (B-L), and 4-2-4-0-0 (B-R). For example, the T-R cycle for a start number set to 1 and a step set to 4, which is 9-9-1-5-1…, can be obtained by adding to the T-R cycle for a start number set to 1 and a step set to 3, which is 7-7-1-9-1… the applicable difference indicated in this rule, which is 1-1-0-3-0, applied digit-by-digit. To give the example of one specific calculation of this comparison, if to the fourth digit of the cycle for step 3, which is 9, the required number of steps along the odd-number sequence 9-1-3-5-7-9-1…, which is 3, is added, the obtained result is correctly 5 for the fourth digit of the cycle for step 4 (that is, 9 to 1 to 3 to 5 are three steps). A zero in this context means that both digits are identical.

4.2. Comparing consecutive diagonals in counterclockwise direction, for the same start number and step, the differences in steps along the corresponding odd or even numbers sequences, between corresponding cycle digits are: 1-2-3-4-0 (for step set at 1), 2-4-1-3-0 (step 2), 3-1-4-2-0 (step 3), and 4-3-2-1-0 (step 4). These are the differences when making three moves between consecutive diagonals, the exception is when moving from B-R diagonal to T-R diagonal, which completes the travel around the diagonals, in this case the differences are 2-4-1-3-0 (for step set at 1), 4-3-2-1-0 (step 2), 1-2-3-4-0 (step 3), and 3-1-4-2-0 (step 4). So the pattern here is that those differences are sorted, such that if the set of four differences between any diagonal except B-R and T-R is considered, each of the odd or even numbers sequences differences of 1, 2, 3, and 4 steps appears in each of the four possible positions and without repetition; and the same happens with the other set, the one that exists between B-R and T-R diagonals, with the 1, 2, 3, and 4 steps. For example, for a start number set to 4 and step set to 3, to move from the B-L cycle, which is 2-4-0-0-4..., to the B-R cycle, which is 8-6-8-4-4..., the applicable difference is 3-1-4-2-0. To verify just one digit of this example, the first one, which is 2, plus three steps as indicated in this rule along the even numbers sequence 0-2-4-6-8-0-2…, gives correctly the result first digit of 8 for the next diagonal. But, to move from the B-R cycle to the T-L cycle, the applicable differences are now 1-2-3-4-0 to arrive to 0-0-4-2-4....

5. The digit cycles repeat themselves with a period of 10 respect to the start number. For example, the cycles for same step and diagonal position for the following start numbers are identical: 1, 11, and 21; 4, 14, and 24.