

where
is the kth prime number.
I thought of this sequence today...
Numbers I calculated before it take up way to much time...



In fact it is A007097.
Nice.
If you remember my prime spiral generator, you would remember it cost over 1 hour to generate a 2000*2000 prime spiral.
But after I did the simple diffusion limited aggregation script1, prime spirals' speed seems impossibly long.
Thx to Edd for pointing out array_shift() is über slow, after I slightly changed the code from
while($n<=$size){ if($prime[0]<=$sn){ $p = array_shift($prime);
$i = 0; while($n<=$size){ if($prime[$i]<=$sn){ $p = $prime[$i++];
$array= range(1,10000); $timeparts = explode(' ',microtime()); $starttime = $timeparts[1].substr($timeparts[0],1); while($i<10000){ $array[$i]; ++$i; } $timeparts = explode(' ',microtime()); $endtime = $timeparts[1].substr($timeparts[0],1); echo 'Native array loop:',bcsub($endtime,$starttime,6),'<br />'; $timeparts = explode(' ',microtime()); $starttime = $timeparts[1].substr($timeparts[0],1); $i= 0; while($i<10000){ array_shift($array); ++$i; } $timeparts = explode(' ',microtime()); $endtime = $timeparts[1].substr($timeparts[0],1); echo 'array_shift():',bcsub($endtime,$starttime,6);
The result:
Native array loop:0.003198 array_shift():2.128530
The native loop is over 650 times faster, don't you think it's too much? What could possibly turn array_shift so inefficient? array_splice($array,0,1) is 7 times slower than array_shift().
So, don't use those functions unless you absolutely have to2.
I used 1 hour 26 minute and 48 seconds to generate this image, and I haven't find anyone online made one this big yet. If anyone found this useful, just download though the attachment.
UPDATE: Also include a 5000*5000 prime spiral created in 78.825353 seconds with my small optimization that make it 650 times faster.
Note: there is a new update make it 650 times faster
A HUGE success from Mgccl the great 
500*500 prime spiral can easily use more than 60 seconds with the previous code about spiral generation, but this one, only 12!
As a tradition, I have to introduce to you the "how" did I make it so fast so it produce the picture below:

1. Find all the primes with the PHP implementation of sieve of Eratosthenes
2. For each prime number, find where the a number locates1
3. Draw the point.
one and three are simple, 2 is HELL lot of work.
I first use some of my precious spear time2 on checking how to divide the spiral into pieces that I can operate on. Soon, I got it where all the perfect squares are going to locate, and the number's relationship to it.

So now I successfully divide the board into small half rings.
Then, I further break the half rings into two smaller pieces, one with the same x position, the other with the same y position. To find the difference, which is where the number lay related to the origin (0,0) point (where 1 is). I have to find each piece's point that lay on either x axis or y axis, so I can use simple add and subtraction to get the relative coordinates, which is the location we wanted
$size = 500; $x_adj = ~ $size & 1; $prime = esprime($size*$size+1); $image = imagecreate($size,$size); imagecolorallocate($image,255,255,255); $color = imagecolorallocate($image,0,0,0); $size2=$size/2; $n = 2;$t = true;$sn=4; $midu=2;$midl=4;$midd=6;$midr=8; while($n<=$size){ if($prime[0]<=$sn){ $p = array_shift($prime); if($t){//even if($p <= $sn-$n){ $x = $n/2; $y = $midu - $p; }else{ $x = $midl -$p; $y = -$n/2; } }else{//odd if($p <= $sn-$n){ $x = (-$n/2)+0.5; $y = $p - $midd; }else{ $x = $p - $midr; $y = ($n/2)-0.5; } } imagesetpixel($image,$x+$size2-$x_adj,$y+$size2,$color); }else{ ++$n; $sn = $n * $n; $t = !$t; if($t){ $midu = $sn-$n*1.5+1; $midl = $sn-$n*0.5+1; }else{ $midd = $sn-$n*1.5+1.5; $midr = $sn-$n*0.5+0.5; } } } header("Content-type: image/png"); imagepng($image);
Note: There is something even faster.
I promised in my last post about make something faster for create the basic prime spiral graph, and I finally made it. 
I modified Christopher David Lane's spiral generator class by adding a method of jump though primeless gaps1.Although I made one myself but it is too confusing to read.

Behold, this generates a prime number spiral in 2.5 seconds on my machine!
$n = 200; $image = imagecreate($n,$n); imagecolorallocate($image, 255,255,255); $color = imagecolorallocate($image, 0,0,0); $sn=$n*$n; $prime = esprime($sn); $y=$x=$n/2; $color2 = imagecolorallocate($image, 255,0,0); imagesetpixel($image,$x,$y,$color2); $remain = 2; $distance = 1; $direction = 1; for ($count = 2; $count <= $sn; ++$count) { if (--$remain == 0) { switch ($direction) { case 0: $distance++; $direction = 3; break; case 2: $distance++; default: $direction--; break; } $remain = $distance; } switch ($direction) { case 3: --$x; break; case 1: ++$x; break; case 0: --$y; break; case 2: ++$y; break; } if($prime[0] == $count){ array_splice($prime, 0, 1); imagesetpixel($image,$x,$y,$color); } if(isset($prime[0])){ if($prime[0]-$count+1<$remain){ switch ($direction) { case 3: $x-=$prime[0]-$count-1; break; case 1: $x+=$prime[0]-$count-1; break; case 0: $y-=$prime[0]-$count-1; break; case 2: $y+=$prime[0]-$count-1; break; } $remain -= $prime[0]-$count-1; $count +=$prime[0]-$count-1; }elseif($prime[0]-$count+1>=$remain){ switch ($direction) { case 3: $x-=$remain-1; break; case 1: $x+=$remain-1; break; case 0: $y-=$remain-1; break; case 2: $y+=$remain-1; break; } $count +=$remain-1; $remain = 1; } } } header("Content-type: image/png"); imagepng($image);
Recent comments
2 days 4 hours ago
6 days 14 hours ago
1 week 20 hours ago
1 week 3 days ago
1 week 3 days ago
1 week 3 days ago
1 week 3 days ago
1 week 5 days ago
2 weeks 1 day ago
2 weeks 1 day ago