Spiral (Prime Number Spiral) Ulam

Question

Je suis à la recherche d'idées / code (de préférence en C #, mais d'autres langues trop de travail) pour créer Ulam de Spiral infiniment grand (limité par la durée de l'exécution du programme, ou jusqu'à ce que l'arrêt).

Maintenant, les chiffres sont tous les nombres premiers donc le code pour ceux qui est plutôt hors de propos. La partie intéressante est de savoir comment coder l'arrangement dans le sans cesse croissante (infini) spirale, quel type de structure de données est bon pour le soutenir, et peut-être des idées pour la sortie (fichier graphique, fichier texte?).

Comment iriez-vous à ce sujet?

Answer 1

Considérons les longueurs de chaque côté:  1, 1, 2, 2, 3, 3, 4, 4, ...

La chose est simple à itérer sur chaque côté, ce qui rend ce côté. Vous pouvez utiliser les primitives de rendu de style LOGO:

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++;
}

Vous pouvez améliorer ce que par itérer sur les nombres premiers d'un côté:

Answer 2

Le programme suivant fonctionne en calculant directement les coordonnées d'un nombre. Le procédé NumberToPoint() effectue le mappage suivant.

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

Le reste est un test de nombre premier très simple et une petite application de la console.

Pour enregistrer une image que je considère deux solutions. Si vous pouvez créer un tampon pour l'image entière, vous pouvez simplement utiliser le programme ci-dessous pour remplir le tampon.

Si la mémoire tampon serait grande, je voudrais créer un procédé PointToNumber() et inverser le calcul - la méthode prend deux coordonnées et renvoie le nombre à ce stade. Avec cette méthode, vous pouvez itérer de haut en bas et de gauche à droite et de calculer le nombre à ce stade, vérifier si elle est premier, et la sortie du pixel que vous allez sans tampon. Mais pour les deux solutions de la taille de l'image doit être connu avant de commencer, car l'ajout de pixels en haut et à gauche est assez cher (mais la cause possible).

Questions

1. Toutes les bonnes idées pour convertir la recherche de coefficient en NumberToPoint() en mathématiques de roche solide sans utiliser modulo, division entière, et signer mille fois?
2. Toutes les bonnes idées pour raccourcir ou accélérer le test des nombres premiers?

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

Answer 3

Une façon possible de le faire est de créer un réseau linéaire ou une liste pour stocker les numéros et utiliser une formule pour déterminer le moment où la direction doit changer. En ce qui concerne la production, j'ai aimé l'exemple sur wikipedia de dessiner un pixel noir pour un premier et un pixel blanc pour tous les autres numéros.

Answer 4

Pourquoi ne pas avoir un processus « générateur » / thread qui crée les chiffres et un processus / thread « lecteur / affichage » qui les affiche, vous pouvez séparer la création de l'affichage et le programme ne sera réellement limité par la quantité de données du « lecteur / écran » consomme. Depuis que je suppose que le « générateur » a besoin d'un ensemble de données de taille assez constante pour travailler avec.