{"id":1154,"date":"2015-01-05T12:00:51","date_gmt":"2015-01-05T17:00:51","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=1154"},"modified":"2016-12-05T14:02:57","modified_gmt":"2016-12-05T19:02:57","slug":"prime-spiral","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2015\/01\/05\/prime-spiral\/","title":{"rendered":"Prime Spiral"},"content":{"rendered":"<div class=\"content\">\r\n\r\n<!--introduction-->The prime spiral was discovered by Stanislaw Ulam in 1963, and featured on the cover of Scientific American in March, 1964.\r\n\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n \t<li><a href=\"#ca6ecc6e-3824-4f03-85e5-68d4d918c6d2\">Stanislaw Ulam<\/a><\/li>\r\n \t<li><a href=\"#664e1de8-c27a-4d21-82ab-a0744e2d83ab\">The Prime Spiral<\/a><\/li>\r\n \t<li><a href=\"#d5f074b6-6e81-4efe-b401-09ce5534ed6c\">10-by-10<\/a><\/li>\r\n \t<li><a href=\"#544b5cfa-0eac-41e2-91ea-4c2a171919a9\">Piecewise Quadratics<\/a><\/li>\r\n \t<li><a href=\"#f01fe3a5-5579-4526-9bb3-0e5ac1cf093f\">Improved Spiral Function<\/a><\/li>\r\n \t<li><a href=\"#ba402e60-e323-4cfe-a695-eb60c12b13f0\">Prime Spiral Is Spy<\/a><\/li>\r\n \t<li><a href=\"#15b44afe-2a79-4b55-8b68-14697f6c6a46\">Increasing Sizes<\/a><\/li>\r\n \t<li><a href=\"#13348b03-6e97-46b8-b521-e8bd94110bdf\">Animated Prime Spiral<\/a><\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Stanislaw Ulam<a name=\"ca6ecc6e-3824-4f03-85e5-68d4d918c6d2\"><\/a><\/h4>\r\nStanislaw Ulam (1909-1984) was an eminent Polish-American mathematician who spent most of his career at Los Alamos, but who also had connections with several American universities, especially the University of Colorado. His many illustrious colleagues included von Neumann, Teller, Metropolis, Erdos, Richtmyer, Rota, and Kac.\r\n\r\nUlam had a wide range of mathematical interests. He was deeply involved in the early development of computers at Los Alamos. He is one of the primary developers of the Monte Carlo method. Later in his career he made contributions to mathematical biology and medicine. He wrote popular books, including \"Adventures of a Mathematician\" and \"Analogies Between Analogies\".\r\n<h4>The Prime Spiral<a name=\"664e1de8-c27a-4d21-82ab-a0744e2d83ab\"><\/a><\/h4>\r\nAs the story goes, Ulam was bored during a seminar in 1963 and began to doodle in his notebook. He numbered the integer lattice points in the plane in a spiral fashion and then highlighted the prime numbers. He was surprised to see that with this numbering the primes were not distributed randomly throughout the plane, but appeared to fall on diagonal segments.\r\n<h4>10-by-10<a name=\"d5f074b6-6e81-4efe-b401-09ce5534ed6c\"><\/a><\/h4>\r\nHere is the 10-by-10 prime spiral, showing the spiral numbering and the 25 primes among the first 100 integers. The most prominent diagonal segment includes the primes 19, 7, 23, 47, and 79.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/primespiral_10.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n<h4>Piecewise Quadratics<a name=\"544b5cfa-0eac-41e2-91ea-4c2a171919a9\"><\/a><\/h4>\r\nUlam's numbering at any point $(i,j)$ in the plane is a piecewise quadratic function of $i$ and $j$. For example, the values along the upper and lower halves of the antidiagonal, or their offsets by one, (depending upon whether the size is odd or even), are perfect squares. So there are certainly not any primes along these diagonals.\r\n\r\nThis reminds me of the quadratics that generate primes. The most famous is <i>Euler's polynomial<\/i>,\r\n\r\n$$ p(n) = n^2-n+41 $$\r\n\r\nThis generates primes for $n$ from 1 through 40, but, obviously, not for $n$ equal to 41.\r\n<pre class=\"codeinput\">   n = 1:41;\r\n   p = n.^2-n+41;\r\n   isprime(p)\r\n<\/pre>\r\n<pre class=\"codeoutput\">ans =\r\n  Columns 1 through 13\r\n     1     1     1     1     1     1     1     1     1     1     1     1     1\r\n  Columns 14 through 26\r\n     1     1     1     1     1     1     1     1     1     1     1     1     1\r\n  Columns 27 through 39\r\n     1     1     1     1     1     1     1     1     1     1     1     1     1\r\n  Columns 40 through 41\r\n     1     0\r\n<\/pre>\r\nThe Euler primes themselves don't show up in the Ulam prime spiral. But each of the diagonal segments corresponds to a quadratic polynomial, although probably one that generates fewer than 40 primes.\r\n<h4>Improved Spiral Function<a name=\"f01fe3a5-5579-4526-9bb3-0e5ac1cf093f\"><\/a><\/h4>\r\nThe MATLAB <tt>demos<\/tt> directory has a <tt>spiral<\/tt> function that generates Ulam's numbering. I'm afraid that the code is ancient, and pretty bad. It's not too hard to write better code. This generates successively larger spirals by rotating one of a given size 180 degrees and then appending another column at the right and another row at the bottom to produce the next larger size.\r\n<pre class=\"codeinput\">   type <span class=\"string\">improved_spiral<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">   function S = improved_spiral(n)\r\n   % SPIRAL SPIRAL(n) is an n-by-n matrix with elements ranging\r\n   % from 1 to n^2 in a rectangular spiral pattern.\r\n   S = [];\r\n   for m = 1:n\r\n      S = rot90(S,2);\r\n      S(m,m) = 0;\r\n      p = m^2-m+1;\r\n      v = (m-1:-1:0);\r\n      S(:,m) = p-v';\r\n      S(m,:) = p+v;\r\n   end\r\n<\/pre>\r\n<h4>Prime Spiral Is Spy<a name=\"ba402e60-e323-4cfe-a695-eb60c12b13f0\"><\/a><\/h4>\r\nOnce we have the spiral numbering, the prime spiral is our old friend, the <tt>spy<\/tt> plot.\r\n<pre class=\"codeinput\">   type <span class=\"string\">primespiral_core.m<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">   function primespiral(n)\r\n   % PRIMESPIRAL PRIMESPIRAL(n) is Ulam's prime spiral.\r\n   P = zeros(n,n);\r\n   P(primes(n^2)) = 1;\r\n   S = improved_spiral(n);\r\n   P = P(S);\r\n   spy(P)\r\n<\/pre>\r\n<h4>Increasing Sizes<a name=\"15b44afe-2a79-4b55-8b68-14697f6c6a46\"><\/a><\/h4>\r\nHere are prime spirals of three different sizes.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/primespiral_200.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/primespiral_400.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/primespiral_600.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n<h4>Animated Prime Spiral<a name=\"13348b03-6e97-46b8-b521-e8bd94110bdf\"><\/a><\/h4>\r\nThe <a href=\"https:\/\/www.mathworks.com\/content\/dam\/mathworks\/mathworks-dot-com\/moler\/ncm\/primespiral.m\">function primespiral<\/a> in my textbook <a href=\"https:\/\/www.mathworks.com\/moler\/chapters.html\">Numerical Computing with MATLAB<\/a> includes a provision for starting the numbering at a value larger than one. Animating this feature emphasizes the diagonal nature of the prime locations. The title on this plot is the starting value of the numbering.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/primespiral_animated.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\n<script>\/\/ <![CDATA[\r\nfunction grabCode_04aeeaa652eb491cb275fa57dcfc8fdf() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='04aeeaa652eb491cb275fa57dcfc8fdf ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 04aeeaa652eb491cb275fa57dcfc8fdf';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2015 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('\r\n\r\n\r\n\r\n<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\r\n\r\n\r\n\r\n\r\n\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }\r\n\/\/ ]]><\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;\"><a><span style=\"font-size: x-small; font-style: italic;\">Get\r\nthe MATLAB code<noscript>(requires JavaScript)<\/noscript><\/span><\/a><\/p>\r\nPublished with MATLAB\u00ae R2014b\r\n\r\n<\/div>\r\n<!--\r\n04aeeaa652eb491cb275fa57dcfc8fdf ##### SOURCE BEGIN #####\r\n%% Prime Spiral\r\n% The prime spiral was discovered by Stanislaw Ulam in 1963, and featured\r\n% on the cover of Scientific American in March, 1964.\r\n\r\n%% Stanislaw Ulam\r\n% Stanislaw Ulam (1909-1984) was an eminent Polish-American mathematician\r\n% who spent most of his career at Los Alamos, but who also had connections\r\n% with several American universities, especially the University of Colorado.\r\n% His many illustrious colleagues included von Neumann, Teller, Metropolis,\r\n% Erdos, Richtmyer, Rota, and Kac.\r\n\r\n%%\r\n% Ulam had a wide range of mathematical interests.  He was deeply involved\r\n% in the early development of computers at Los Alamos. He is one of the\r\n% primary developers of the Monte Carlo method.  Later in his career he\r\n% made contributions to mathematical biology and medicine.  He wrote popular\r\n% books, including \"Adventures of a Mathematician\" and \"Analogies Between\r\n% Analogies\".\r\n\r\n%% The Prime Spiral\r\n% As the story goes, Ulam was bored during a seminar in 1963 and began to\r\n% doodle in his notebook.  He numbered the integer lattice points in the plane\r\n% in a spiral fashion and then highlighted the prime numbers.  He was\r\n% surprised to see that with this numbering the primes were not distributed\r\n% randomly throughout the plane, but appeared to fall on diagonal segments.\r\n\r\n%% 10-by-10\r\n% Here is the 10-by-10 prime spiral, showing the spiral numbering and the\r\n% 25 primes among the first 100 integers.  The most prominent diagonal segment\r\n% includes the primes 19, 7, 23, 47, and 79.\r\n%\r\n% <<primespiral_10.png>>\r\n%\r\n\r\n%% Piecewise Quadratics\r\n% Ulam's numbering at any point $(i,j)$ in the plane is a piecewise quadratic\r\n% function of $i$ and $j$.  For example, the values along the upper and\r\n% lower halves of the antidiagonal, or their offsets by one, (depending\r\n% upon whether the size is odd or even), are perfect squares.\r\n% So there are certainly not any primes along these diagonals.\r\n\r\n%%\r\n% This reminds me of the quadratics that generate primes.  The most famous\r\n% is _Euler's polynomial_,\r\n%\r\n% $$ p(n) = n^2-n+41 $$\r\n%\r\n% This generates primes for $n$ from 1 through 40, but, obviously, not for\r\n% $n$ equal to 41.\r\n\r\nn = 1:41;\r\np = n.^2-n+41;\r\nisprime(p)\r\n\r\n%%\r\n% The Euler primes themselves don't show up in the Ulam prime spiral.\r\n% But each of the diagonal segments corresponds to a quadratic polynomial,\r\n% although probably one that generates fewer than 40 primes.\r\n\r\n%% Improved Spiral Function\r\n% The MATLAB |demos| directory has a |spiral| function that generates Ulam's\r\n% numbering.  I'm afraid that the code is ancient, and pretty bad.\r\n% It's not too hard to write better code.  This generates successively\r\n% larger spirals by rotating one of a given size 180 degrees and then\r\n% appending another column at the right and another row at the bottom to\r\n% produce the next larger size.\r\n\r\ntype improved_spiral\r\n\r\n%% Prime Spiral Is Spy\r\n% Once we have the spiral numbering, the prime spiral is our old friend,\r\n% the |spy| plot.\r\n\r\ntype primespiral_core.m\r\n\r\n%% Increasing Sizes\r\n% Here are prime spirals of three different sizes.\r\n%\r\n% <<primespiral_200.png>>\r\n%\r\n%\r\n% <<primespiral_400.png>>\r\n%\r\n%\r\n% <<primespiral_600.png>>\r\n%\r\n\r\n%% Animated Prime Spiral\r\n% The <https:\/\/www.mathworks.com\/moler.htmlncm\/primespiral.m function primespiral>\r\n% in my textbook <https:\/\/www.mathworks.com\/moler.htmlncmfilelist.html % Numerical Computing with MATLAB> includes a provision for starting the\r\n% numbering at a value larger than one.  Animating this feature emphasizes\r\n% the diagonal nature of the prime locations.  The title on this plot is\r\n% the starting value of the numbering.\r\n%\r\n% <<primespiral_animated.gif>>\r\n%\r\n\r\n##### SOURCE END ##### 04aeeaa652eb491cb275fa57dcfc8fdf\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/primespiral_10.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction-->The prime spiral was discovered by Stanislaw Ulam in 1963, and featured on the cover of Scientific American in March, 1964.\r\n\r\n<!--\/introduction-->... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2015\/01\/05\/prime-spiral\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,4,8],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1154"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=1154"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1154\/revisions"}],"predecessor-version":[{"id":2188,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1154\/revisions\/2188"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=1154"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=1154"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=1154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}