Jump to content

Sum of diagonal elements in a prime numbers spiral


LovE-RicH

Recommended Posts

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?:)

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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();
        }
    }
}

Link to comment
Share on other sites

 

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/

Link to comment
Share on other sites

 

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

Link to comment
Share on other sites

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).

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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. ;)

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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).

Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.