Problem 659. How long is the longest prime diagonal?

Created by Ned Gulley

Stanislaw Ulam once observed that if the counting numbers are arranged in a spiral, the prime numbers contained in it form a surprising pattern. They appear to cluster along diagonals of the spiral matrix.

Given n, find the longest diagonal arrangement of primes in spiral(n).

Example:

 Input  n = 7
 Output d = 4

Since isprime(spiral(n)) is

     1     0     0     0     1     0     0
     0     0     0     1     0     0     0
     1     0     1     0     0     0     0
     0     1     0     0     1     1     0
     0     0     1     0     1     0     1
     0     1     0     0     0     1     0
     1     0     0     0     0     0     1

Problem Group

ASEE Challenge

Solve This Now!

57 solvers submitted 132 solutions (2.32 solutions/solver).

Solution Map Solution List Solvers

Problem Comments

3 Comments

Richard Zapor on 10 Jun 2012

I believe the first test case is in error. n=4 should have d=2. 1 is not a prime per the wiki link or provided example. [10 9 8 7;11 2 1 6; 12 3 4 5;13 14 15 16] has only a diagonal of 2 (13-3). If 1 was a prime then d would be 4 [13-3-1-7].

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.

Solution Comments

Solution 102911

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 659. How long is the longest prime diagonal?

Tags

Problem Group

57 solvers submitted 132 solutions (2.32 solutions/solver).

Problem Comments

Solution Comments