Ulama Spiral (Prime Number Spiral)
I am looking for ideas / code (preferably C #, but other languages work too) to make Ulam Spiral infinitely large (limited program runtime or until it stops).
Now numbers are all prime numbers, so the code doesn't matter to them. The interesting part is how to code the location in an endless spiral, what data structure is good to support it, and maybe ideas for output (graphic file, text file?).
How would you do it?
source to share
Consider the lengths of each side: 1, 1, 2, 2, 3, 3, 4, 4, ...
The simplest thing is to iterate over each side while doing this side. You can use LOGO style rendering primitives:
Angle = 0;
x=0; y = 0;
int number = 1;
int sideLength = 1;
StartLine();
for (int side = 1; side < maxSize; side++) {
for (int k = 0; k < sideLength; k++) {
Forward(1);
number++;
if (isPrime(number)) {
StopLine();
Ouput(number);
StartLine();
}
}
TurnLeft();
if (side % 2 == 0) sideLength++;
}
You can improve this by only iterating over the primes on the side:
source to share
The following program works by directly calculating the coordinates of a number. The method NumberToPoint()
performs the following mapping.
0 => (x0 , y0 )
1 => (x0 + 1, y0 )
2 => (x0 + 1, y0 - 1)
3 => (x0 , y0 - 1)
4 => (x0 - 1, y0 - 1)
5 => (x0 - 1, y0 )
6 => ...
The rest is a very simple prime number test and a small console application.
To save the image, I would consider two solutions. If you can create a buffer for the entire image, you can simply use the program below to fill the buffer.
If the buffer is large, I would create a method PointToNumber()
and invert the calculation - the method takes two coordinates and returns the number at that point. With this method, you can iterate from top to bottom and left to right and calculate the number at that point, check if it is simple, and output the pixel as you go without a buffer. But for both solutions, the image size must be known before you start, because adding pixels at the top and left is quite expensive (but possible).
Questions
- Any good ideas for converting finding coefficients in
NumberToPoint()
to hard mathematics in rock without using modular, integer division and sign a thousand times? - Any good ideas to shorten or speed up a numeric test?
code
using System;
using System.Drawing;
using System.Linq;
using System.Threading;
namespace UlamsSpiral
{
public static class Program
{
public static void Main()
{
Int32 width = 60;
Int32 height = 60;
Console.SetWindowSize(Math.Min(width, 120), Math.Min(height, 60));
Console.SetBufferSize(width, height);
Console.CursorVisible = false;
Int32 limit = (Int32)Math.Pow(Math.Min(width, height) - 2, 2);
for (Int32 n = 1; n <= limit; n++)
{
Point point = NumberToPoint(n - 1, width / 2 - 1, height / 2);
Console.ForegroundColor = n.IsPrime() ? ConsoleColor.DarkBlue : ConsoleColor.DarkGray;
Console.SetCursorPosition(point.X, point.Y);
Console.Write('\u25A0');
Console.SetCursorPosition(0, 0);
Console.Write(n);
Thread.Sleep(10);
}
Console.ReadLine();
}
private static Point NumberToPoint(Int32 n, Int32 x0, Int32 y0)
{
Int32[,] c = { { -1, 0, 0, -1, 1, 0 }, { -1, 1, 1, 1, 0, 0 }, { 1, 0, 1, 1, -1, -1 }, { 1, -1, 0, -1, 0, -1 } };
Int32 square = (Int32)Math.Floor(Math.Sqrt(n / 4));
Int32 index;
Int32 side = (Int32)Math.DivRem(n - 4 * square * square, 2 * square + 1, out index);
Int32 x = c[side, 0] * square + c[side, 1] * index + c[side, 2];
Int32 y = c[side, 3] * square + c[side, 4] * index + c[side, 5];
return new Point(x + x0, y + y0);
}
private static Boolean IsPrime(this Int32 n)
{
if (n < 3) return (n == 2);
return Enumerable.Range(2, (Int32)Math.Sqrt(n)).All(m => n % m != 0);
}
}
}
source to share
Why not create a "generator" process / thread that creates numbers and a "read / display" process / thread that displays them, then you can decouple the creation from the display and then the program will really be limited how much data the reader / display is consuming ... As I assumed the "generator" requires a fairly constant data size to work.
source to share