Problem 659. How long is the longest prime diagonal?

Created by Ned Gulley

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Stanislaw Ulam once observed that if the counting numbers are</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Ulam_spiral\"><w:r><w:t>arranged in a spiral</w:t></w:r></w:hyperlink><w:r><w:t>, the prime numbers contained in it form a surprising pattern. They appear to cluster along diagonals of the spiral matrix.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given n, return the length of the longest diagonal sequence of primes in spiral(n).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input  n = 7\n Output d = 4]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Since isprime(spiral(n)) is</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[     1     0     0     0     1     0     0\n     0     0     0     1     0     0     0\n     1     0     1     0     0     0     0\n     0     1     0     0     1     1     0\n     0     0     1     0     1     0     1\n     0     1     0     0     0     1     0\n     1     0     0     0     0     0     1]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

901 Solutions
433 Solvers

Last Solution submitted on Jul 28, 2020

Last 200 Solutions

Problem Comments

7 Comments

7 Comments

Show 4 older comments

Jacob on 11 Jun 2012

I agree that the solution is mis-coded. isprime(spiral(4)) gives:
1 0 0 0
0 0 1 1
1 0 1 0
0 0 0 1
which means that d=2 for this case.

Ned Gulley on 11 Jun 2012

Rescoring based on corrected test suite. Sorry about that.

Jonathan Campelli on 11 May 2015

"find the longest diagonal arrangement of primes in spiral(n)" leaves room for misinterpretation.

I would have quickly understood:
"return the length of the longest diagonal sequence of primes in spiral(n)"

David Verrelli on 17 Nov 2017

Like Jonathan Campelli, I still feel the problem statement could be clearer. From the example I eventually figure that reference is being made to the diagonally oriented elements running between elements (1,5) and (4,2) of isprime(spiral(n)). But arguably these are not on a/the "diagonal" of that matrix, per http://mathworld.wolfram.com/Diagonal.html (cf. https://en.wikipedia.org/wiki/Main_diagonal ).

David Verrelli on 17 Nov 2017

Furthermore, there is no mention in the current online MATLAB documentation that "spiral" is actually a function that is already provided with MATLAB — i.e. that the user does not have to write their own function to make the spiral matrix. Apparently, "spiral can be found in the demo folder" [ref: https://stackoverflow.com/questions/29466058/spiral-loop-on-a-matrix-from-a-point].

Tung Nguyen on 29 Oct 2019

hard

Highphi on 24 Jul 2020 at 17:17

eh, I think the problem statement made sense. especially if you just run 'isprime(spiral(n))' in your command window. I liked this problem. Ended up using the technique I almost used on another problem awhile back but it made more sense to use here, so I had the basic framework already started :D

Solution Comments

Solution 2045288

1 Comment

1 Comment

Miles Walker on 4 Dec 2019

Interesting! This error stems from using "Ix" in both function and sub-function. As I test my code in scripts not contained within a function I was missing it.

Why are parameters made available to sub-functions by default?

Solution 1854983

1 Comment

1 Comment

jianrui fan on 21 Jun 2019

this is really awesome and impressive.I do learn something

Solution 1699697

1 Comment

1 Comment

A C on 27 Dec 2018

n = isprime(spiral(n))

Solution 593819

1 Comment

1 Comment

jianrui fan on 21 Jun 2019

thank you very much

Solution 443569

1 Comment

1 Comment

Ramoflaple on 11 Aug 2015

a good precise algorithm

Solution 117430

1 Comment

1 Comment

Jon on 21 Mar 2014

Best solution that doesn't cheat with a lookup or regexp

Solution 102911

1 Comment

1 Comment

Dirk Engel on 26 Jun 2012

max(diff(find(~zeroOneVector)))-1 returns the longest run of ones in a vector of zeros and ones, but it FAILS IN SEVERAL CASES, e.g.:
- all ones: [1 1 1 1 1] returns empty
- just a single zero: [1 1 0 1 1] returns empty
- all zeros at one end: [1 1 1 0 0] returns 0
- longest run at one end: [1 1 0 1 0] returns the longest run between zeros, here 1

As a workaround for all cases, add zeros to both ends of the vector:
max(diff(find(~[0 zeroOneVector 0])))-1

However, this is not necessary for this solution because the matrix is very sparse.

Problem Recent Solvers433

Problem Tags

asee diagonal pattern poor_problem_statement primes spiral

Problem 659. How long is the longest prime diagonal?

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers433

Suggested Problems

More from this Author49

Problem Tags

Problem 659. How long is the longest prime diagonal?

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers433

Suggested Problems

More from this Author49

Problem Tags

Players