Sum of diagonal elements in a prime numbers spiral

[LovE-RicH]

I don't mean Ulam's spiral, I mean a spiral like in the example below!

 

I found this problem on a site and I'd really like to know how to solve it in PHP (even though it's probably not ment for PHP). I'm a beginner, so I need help...

 

For a spiral of prime numbers sized n × n, what is the sum of diagonals if n=2007?

 

Example (3x3) --> n = 3:

23-19-17
      |
3--2  13
|     |
5--7--11

Sum = 23+2+11 + 5+2+17 = 60

 

How should I even start? Should I make a 2-D array for the spiral? If so, how to place the primes into the array in the right order? Once that's done, it would be easy to add the diagonals - for example the sum of the first diagonal is:

$array[0][0]+$array[1][1]+$array[2][2]+...+$array[d][d]

where d=n*sqrt(2)

 

Or should I make a 1-D array of primes from the 1st to (2007^2)th and add together elements which would be on the diagonals (the interval between 2 diagonal elements increases by 2 after each full circle in the spiral --> can use ID keys)?

So:

                  2+5+11+17+23+43+61+79+101+...+(?)

or with ID keys

      [0]+[2]+[4]+[6]+[8]+[12]+[16]+[20]+[24]+[30]...+[2007^2]
DIFF:    2   2   2   2   4    4    4    4    6

 

Or should I do something completely different?

[ddrudik]

Maybe someone can fix the performance issue with the code to allow it to return the result for 2007 (the function times out for me after somewhere after 75):

<pre>
<?php
function check_prime($num) 
{ 
    if($num == 2 || $num == 3) 
        return true; 
    if($num > 4 && $num & 0x01) 
    {     
        $sq = sqrt($num);             
        if(floor($sq) != $sq) 
        { 
            for($a = 5; $a <= ($num >> 1); $a += 2)         
                if($num % $a == 0) 
                    return false; 
            return true; 
        }
    }
    return false;         
}
function sumdiagprimes($n){
  $r=0;$c=0;$i=2;$p=0;$q=0;$iter=0;
  while($c<pow($n,2)) {
  if(check_prime($i)){
	  $c++;
	  $primes[$c]=$i;
    $r=$r+$i;
	}
	$i++;
}
$primes=array_reverse($primes);
$p=$n-1;
while(isset($primes[$q]) && $p>0){
    for($i=1; $i<=5; $i++){
		$iter++;
    if(isset($primes[$q])){
    	  $result[$q]=$primes[$q];
  		  $q=$q+$p;
  		} else {
		  break;
		}
  }
  $q=$q-$p;
  $p=$p-2;
  }
if(($n/2)!=intval($n/2)){
  $result[$q+1]=$result[$q];
}
  return "after $iter iterations, the sum of diagonals for $n: ".array_sum($result)."\r\n";
}
echo sumdiagprimes(3);
echo sumdiagprimes(4);
echo sumdiagprimes(5);
echo sumdiagprimes(75);
//echo sumdiagprimes(2007);
?>

 

Returns:

after 5 iterations, the sum of diagonals for 3: 60

after 10 iterations, the sum of diagonals for 4: 157

after 10 iterations, the sum of diagonals for 5: 330

after 185 iterations, the sum of diagonals for 75: 2588028

[ddrudik]

I converted that code to C#.NET, I will let you know the result of 2007 if/when it completes processing on my test server.

using System;
using System.Collections;
using System.Text;

namespace sumdiagprimes
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(sumdiagprimes(3));
            Console.WriteLine(sumdiagprimes(4));
            Console.WriteLine(sumdiagprimes(5));
            Console.WriteLine(sumdiagprimes(75));
            Console.WriteLine(sumdiagprimes(2007));
        }
        public static string sumdiagprimes(int size)
        {
            long startTime = DateTime.Now.Ticks;
            int j = 2;
            ArrayList primes = new ArrayList();
            while (primes.Count < Math.Pow(size, 2))
            {
                if (isprime(j))
                {
                    primes.Add(j);
                }
                j++;
            }
            primes.Reverse();
            int p = size - 1;
            int q = 0;
            int iter = 0;
            ArrayList result = new ArrayList();
            while(q<=primes.Count-1 && p>0)
            {
                for(int i=1; i<=5; i++)
                {
                    iter++;
                    if (q <= primes.Count - 1)
                    {
                        //Console.WriteLine("p="+p+" q="+q);
                        if (result.Count==0 || (result[result.Count - 1] != primes[q]))
                        {
                            result.Add(primes[q]);
                        }
                        q = q + p;
                    }
                    else
                    {
                        break;
                    }
                }
                //Console.WriteLine("old q=" + q);
                q = q - p;
                //Console.WriteLine("new q="+q);
                p=p-2;
            }
            if((size % 2) != 0)
            {
                result.Add(result[result.Count-1]);
            }
            Int64 resultsum = 0;
            for (int i = 0; i <= result.Count-1; i++)
            {
                resultsum = resultsum + Convert.ToInt64(result[i]);
            }
            //PrintValues(result);
            long endTime = DateTime.Now.Ticks;
            TimeSpan timeTaken = new TimeSpan(endTime - startTime);
            return "size: "+size+"\r\niter: "+iter+"\r\ntime: "+timeTaken.ToString()+"\r\n sum: "+resultsum+"\r\n\r\n";
        }
        public static bool isprime(int number)
        {
            int i = 0;
            if (number < 2)
            {
                return false;
            }
            else
            {
                for (i = 2; i <= (number / 2); i++)
                {
                    if (number % i == 0)
                    {
                        return false;
                    }
                }
                return true;
            }
        }
        public static void PrintValues(IEnumerable myList)
        {
            foreach (Object obj in myList)
                Console.Write("{0},", obj);
            Console.WriteLine();
        }
    }
}

[GingerRobot]

I'm not convinced that it's necessarily an inefficiency in your code that is the problem. If n=2007, then it's necessary to generate 4028049 primes (2007^2). That's not really a trivial task.

[ddrudik]

GingerRobot, I appreciate that vote of confidence in my code, I will wait for the C#.NET code to complete the task.

[Mchl]

 

Or should I make a 1-D array of primes from the 1st to (2007^2)th and add together elements which would be on the diagonals (the interval between 2 diagonal elements increases by 2 after each full circle in the spiral --> can use ID keys)?

So:

                  2+5+11+17+23+43+61+79+101+...+(?)

or with ID keys

      [0]+[2]+[4]+[6]+[8]+[12]+[16]+[20]+[24]+[30]...+[2007^2]
DIFF:    2   2   2   2   4    4    4    4    6

 

 

That's actually a pretty good idea. Now if you only could find a table containing 4 028 049 first primes, so that you don't have to calculate them by yourself

 

 

http://www.rsok.com/~jrm/printprimes.html maybe?

 

Or

 

http://www.mrteverett.com/primes/

[GingerRobot]

 

Or should I make a 1-D array of primes from the 1st to (2007^2)th and add together elements which would be on the diagonals (the interval between 2 diagonal elements increases by 2 after each full circle in the spiral --> can use ID keys)?

So:

                  2+5+11+17+23+43+61+79+101+...+(?)

or with ID keys

      [0]+[2]+[4]+[6]+[8]+[12]+[16]+[20]+[24]+[30]...+[2007^2]
DIFF:    2   2   2   2   4    4    4    4    6

 

 

That's actually a pretty good idea.

 

That's how i approached it too:

 

<?php
$start = time();
function generate_primes($num){
$generated = 1;
$x = 3;
$primes = array();
$primes[0] = 2;
for($x=3;;$x+=2){
	$prime = TRUE;
	for($y=2;$y<=sqrt($x);$y++){
		if($x % $y == 0){
			$prime = FALSE;
			break;
		}
	}
	if($prime===TRUE){
		$primes[$generated++] = $x;
		if($generated>=$num){
			break;
		}
	}
}
return $primes;
}
function calc_sum($n){
$sum = 0;
$primes = generate_primes($n*$n);
$squares = ceil($n/2);
if($n % 2==0){
	$sum = array_sum(array_slice($primes,0,4));
	$index = 3;
	for($x=2;$x<=$squares;$x++){
		for($y=0;$y<4;$y++){
			$index += 2*$x-1;
			$sum += $primes[$index];
		}
	}
}else{
	$sum = 4; /* 2 is the center of the spiral; count it for both diagonals */
	$index = 0;
	for($x=1;$x<$squares;$x++){
		for($y=0;$y<4;$y++){
			$index += 2*$x;
			$sum += $primes[$index];
		}
	}		
}
return $sum;	
}
echo 'Sum of diagonals for n=500: '.calc_sum(500);
$time = time() - $start;
echo '<br />Time taken: '.$time.' seconds';
?>

 

The prime number generation is slightly more efficient than yours ddrudik. To check if x is prime, it's only necessarily to check if it is divisible by numbers up to sqrt(x), not x/2. I managed to run this for n=500, though it did take almost 3 minutes.

 

Sum of diagonals for n=500: 1107323275
Time taken: 174 seconds

[corbin]

Hrmmm if it were written in something besides PHP (more specifically something with thread support), a thread could be spawned for each core/processor, and it could be done a little more quickly (although the complexity of coding it would invalidate the curiosity of this lol).

[ddrudik]

That's a much more efficient function than mine, I'll admit I stumbled across the question while waiting to answer regex questions elsewhere, I just recognized a pattern in the prime array for diagonals so I took a shot.  In any case it was an interesting question and rather interesting to see that I started from the outside of the spiral and worked in while others started from the inside out.

 

If anyone's interested in the 33.8MB file with the 2007*2007 primes array text file, here it is:

http://www.4shared.com/file/69220338/12b559e2/primesphp.html

 

I created it with this C#.NET code converted from the PHP post by GingerRobot (I understand that it could all be done in C#.NET faster than PHP but this really isn't an exercise in performance).

using System;
using System.Collections;
using System.Text;
using System.IO;

namespace generateprimes
{
    class Program
    {
        static void Main(string[] args)
        {
            genprimes(2007);
        }
        public static void genprimes(double num)
        {
            num = Math.Pow(num, 2);
            int generated = 1;
            int x = 3;
            FileStream fs = new FileStream("primes.txt", FileMode.Create, FileAccess.Write, FileShare.None);
            StreamWriter swFromFileStream = new StreamWriter(fs);
            swFromFileStream.Write("<?php\r\n$primes=array(2,");
            for(x=3;;x+=2)
            {
                bool prime = true;
                int y = 0;
                for (y = 2; y <= Math.Sqrt(x); y++)
                {
                    if (x % y == 0)
                    {
                        prime = false;
                        break;
                    }
                }
                if (prime == true)
                {
                    generated++;
                    Console.WriteLine(generated+"..."+x);
                    swFromFileStream.Write(x+",");
                    if (generated >= num)
                    {
                        break;
                    }
                }
            }
            swFromFileStream.Write(");\r\n?>");
            swFromFileStream.Flush();
            swFromFileStream.Close();
        }
    }
}

 

It wasn't usable for me as an include until I disabled the memory_limit in PHP:

<?php
ini_set("memory_limit","-1");
include 'primes.php';
echo count($primes);
?>

 

Note that rn above in my C#.NET code should be \r\n that is being munged by the post.

[ddrudik]

BTW, for the curious, with the include file and replacing '$primes = generate_primes($n*$n);' with 'global $primes;' in the fine PHP code by GingerRobot (time shown using microtime function):

Sum of diagonals for n=2007: 87676673138

Time taken: 0.002 seconds

[ddrudik]

My 'reverse' function arrived at the same result with the included primes array, albeit a bit slower.

 

after 5015 iterations, the sum of diagonals for 2007: 87676673138

elapsed time: 1.449 seconds

[Mchl]

BTW, for the curious, with the include file and replacing '$primes = generate_primes($n*$n);' with 'global $primes;' in the fine PHP code by GingerRobot (time shown using microtime function):

Sum of diagonals for n=2007: 87676673138

Time taken: 0.002 seconds

 

And that's why lookup tables are so often used

 

A friend of mine won a programming contest this way (a part of it actually). The task was: for given n return n'th element of series defined as {wicked definition} where 1<n<4000. So while others' programs where calculating this series, my friend's program used lookup table with precalculated values.

[corbin]

lol the other ones were probably like "LAME!"

 

 

 

Although it was pretty clever.

[Mchl]

The goal was to return correct result in the shortest time using given tools. I think that's what these contests are about: think out of the box

[corbin]

Eh yeah, pretty clever then.

[.josh]

The goal was to return correct result in the shortest time using given tools. I think that's what these contests are about: think out of the box

 

With a vague goal like that and lookup tables being acceptable, why not just run your code ahead of time, get the results, and then submit a program that simply echoes the string of results.  WIN!

[Mchl]

Not all of the task would be possible to be solved this way. First of all, contestants did not know the exact entry data their programs would have to process. While a lookup table is a perfectly valid solution to a task like "return n-th number from the series", it is not for different problems (think 'travelling salesman' for example).