спираль Улама

Визуализация простых чисел, образованных путем расположения целых чисел в виде спирали

Спираль Улама размером 201×201. Черные точки представляют простые числа. Диагональные, вертикальные и горизонтальные линии с высокой плотностью простых чисел хорошо видны.

Для сравнения, спираль со случайными нечетными числами, окрашенными в черный цвет (при той же плотности простых чисел в спирали 200x200).

Спираль Улама или первичная спираль — это графическое изображение множества простых чисел , придуманное математиком Станиславом Уламом в 1963 году и популяризированное в колонке «Математические игры» Мартина Гарднера в журнале Scientific American некоторое время спустя. ^[1] Она строится путем записи положительных целых чисел в квадратную спираль и специальной маркировки простых чисел.

Улам и Гарднер подчеркнули поразительное появление в спирали заметных диагональных, горизонтальных и вертикальных линий, содержащих большое количество простых чисел. И Улам, и Гарднер отметили, что существование таких заметных линий не является неожиданным, поскольку линии в спирали соответствуют квадратичным многочленам , а некоторые такие многочлены, такие как многочлен Эйлера , генерирующий простые числа x ²  −  x  + 41, как полагают, производят высокую плотность простых чисел. ^{[2] [3]} Тем не менее, спираль Улама связана с основными нерешенными проблемами в теории чисел, такими как проблемы Ландау . В частности, ни один квадратичный многочлен никогда не был доказан в качестве порождающего бесконечно много простых чисел, не говоря уже о том, чтобы иметь высокую асимптотическую плотность их, хотя существует хорошо обоснованная гипотеза относительно того, какой должна быть эта асимптотическая плотность.

В 1932 году, за 31 год до открытия Улама, герпетолог Лоренс Клаубер построил треугольный, неспиральный массив, содержащий вертикальные и диагональные линии, демонстрирующие схожую концентрацию простых чисел. Как и Улам, Клаубер отметил связь с многочленами, генерирующими простые числа, такими как полиномы Эйлера. ^[4]

Строительство

Спираль Улама строится путем записи положительных целых чисел в спиральном расположении на квадратной решетке :

и затем отметим простые числа:

На рисунке простые числа, по-видимому, концентрируются вдоль определенных диагональных линий. В спирали Улама 201×201, показанной выше, диагональные линии четко видны, подтверждая закономерность до этой точки. Горизонтальные и вертикальные линии с высокой плотностью простых чисел, хотя и менее заметные, также очевидны. Чаще всего числовая спираль начинается с числа 1 в центре, но можно начать с любого числа, и наблюдается та же концентрация простых чисел вдоль диагональных, горизонтальных и вертикальных линий. Начиная с 41 в центре, получается диагональ, содержащая непрерывную строку из 40 простых чисел (начиная с 1523 к юго-западу от начала координат, уменьшаясь до 41 в начале координат и увеличиваясь до 1601 к северо-востоку от начала координат), самый длинный пример такого рода. ^[5]

История

По словам Гарднера, Улам открыл спираль в 1963 году, когда рисовал во время презентации «длинной и очень скучной статьи» на научном собрании. ^[1] Эти ручные вычисления составили «несколько сотен точек». Вскоре после этого Улам с соавторами Майроном Стайном и Марком Уэллсом использовали MANIAC II в Лос-Аламосской научной лаборатории, чтобы расширить вычисления до примерно 100 000 точек. Группа также вычислила плотность простых чисел среди чисел до 10 000 000 вдоль некоторых линий, богатых простыми числами, а также вдоль некоторых линий, бедных простыми числами. Изображения спирали до 65 000 точек были показаны на «присоединенном к машине телескопе», а затем сфотографированы. ^[6] Спираль Улама была описана в колонке «Математические игры» Мартина Гарднера в журнале Scientific American за март 1964 года и представлена ​​на обложке этого выпуска. Некоторые фотографии Стайна, Улама и Уэллса были воспроизведены в колонке.

В приложении к колонке Scientific American Гарднер упомянул более раннюю статью Клаубера. ^{[7] [8]} Клаубер описывает свою конструкцию следующим образом: «Целые числа располагаются в треугольном порядке с 1 на вершине, вторая строка содержит числа от 2 до 4, третья — от 5 до 9 и т. д. Когда простые числа указаны, обнаруживается, что в определенных вертикальных и диагональных линиях есть концентрации, и среди них обнаруживаются так называемые последовательности Эйлера с высокими концентрациями простых чисел». ^[4]

Объяснение

Диагональные, горизонтальные и вертикальные линии в числовой спирали соответствуют многочленам вида

${\displaystyle f(n)=4n^{2}+bn+c}$

где b и c — целые константы. Когда b четно, линии диагональны, и либо все числа нечетные, либо все четные, в зависимости от значения c . Поэтому неудивительно, что все простые числа, кроме 2, лежат на чередующихся диагоналях спирали Улама. Некоторые многочлены, такие как , хотя и дают только нечетные значения, факторизуются по целым числам и поэтому никогда не являются простыми, за исключением, возможно, случаев, когда один из множителей равен 1. Такие примеры соответствуют диагоналям, которые лишены простых чисел или почти лишены их. ${\displaystyle 4n^{2}+8n+3}$ ${\displaystyle (4n^{2}+8n+3)=(2n+1)(2n+3)}$

Чтобы понять, почему некоторые из оставшихся нечетных диагоналей могут иметь более высокую концентрацию простых чисел, чем другие, рассмотрим и . Вычислите остатки от деления на 3, когда n принимает последовательные значения 0, 1, 2, .... Для первого из этих многочленов последовательность остатков равна 1, 2, 2, 1, 2, 2, ..., а для второго — 2, 0, 0, 2, 0, 0, .... Это означает, что в последовательности значений, принимаемых вторым многочленом, два из каждых трех делятся на 3 и, следовательно, определенно не являются простыми числами, в то время как в последовательности значений, принимаемых первым многочленом, ни одно не делится на 3. Таким образом, кажется правдоподобным, что первый многочлен будет давать значения с более высокой плотностью простых чисел, чем второй. По крайней мере, это наблюдение дает мало оснований полагать, что соответствующие диагонали будут одинаково плотными с простыми числами. Конечно, следует рассмотреть делимость на простые числа, отличные от 3. Рассматривая также делимость на 5, остатки при делении на 15 повторяются с шаблоном 1, 11, 14, 10, 14, 11, 1, 14, 5, 4, 11, 11, 4, 5, 14 для первого многочлена и с шаблоном 5, 0, 3, 14, 3, 0, 5, 3, 9, 8, 0, 0, 8, 9, 3 для второго, подразумевая, что только три из 15 значений во второй последовательности являются потенциально простыми (не делятся ни на 3, ни на 5), в то время как 12 из 15 значений в первой последовательности являются потенциально простыми (поскольку только три делятся на 5 и ни одно не делится на 3). ${\displaystyle 4n^{2}+6n+1}$ ${\displaystyle 4n^{2}+6n+5}$

Хотя строго доказанных результатов о простых числах в квадратичных последовательностях немного, соображения, подобные приведенным выше, приводят к правдоподобной гипотезе об асимптотической плотности простых чисел в таких последовательностях, которая описана в следующем разделе.

Гипотеза Харди и Литтлвуда F

В своей статье 1923 года о гипотезе Гольдбаха Харди и Литтлвуд высказали ряд гипотез, одна из которых, если она верна, объяснила бы некоторые поразительные особенности спирали Улама. Эта гипотеза, которую Харди и Литтлвуд назвали «Гипотеза F», является частным случаем гипотезы Бейтмана–Хорна и утверждает асимптотическую формулу для числа простых чисел вида ax ²  +  bx  +  c . Лучи, исходящие из центральной области спирали Улама, образующие углы 45° с горизонталью и вертикалью, соответствуют числам вида 4 x ²  +  bx  +  c с четным b ; горизонтальные и вертикальные лучи соответствуют числам того же вида с нечетным b . Гипотеза F дает формулу, которую можно использовать для оценки плотности простых чисел вдоль таких лучей. Она подразумевает, что будет значительная изменчивость плотности вдоль разных лучей. В частности, плотность весьма чувствительна к дискриминанту полинома, b ²  − 16 c .

Простые числа вида 4 x ²  − 2 x  + 41 с x  = 0, 1, 2, ... выделены фиолетовым цветом. Выдающаяся параллельная линия в нижней половине рисунка соответствует 4 x ²  + 2 x  + 41 или, что эквивалентно, отрицательным значениям x .

Гипотеза F касается многочленов вида ax ²  +  bx  +  c, где a , b и c — целые числа, а a — положительное число. Если коэффициенты содержат общий множитель, больший 1, или если дискриминант Δ =  b ²  − 4 ac является полным квадратом , многочлен факторизуется и, следовательно, производит составные числа, поскольку x принимает значения 0, 1, 2, ... (за исключением, возможно, одного или двух значений x , где один из множителей равен 1). Более того, если a  +  b и c оба четные, многочлен производит только четные значения и, следовательно, является составным, за исключением, возможно, значения 2. Харди и Литтлвуд утверждают, что, за исключением этих ситуаций, ax ²  +  bx  +  c принимает простые значения бесконечно часто, поскольку x принимает значения 0, 1, 2, ... Это утверждение является частным случаем более ранней гипотезы Буняковского и остается открытым. Харди и Литтлвуд далее утверждают, что асимптотически число P ( n ) простых чисел вида ax ²  +  bx  +  c и меньших n определяется выражением

${\displaystyle P(n)\sim A{\frac {1}{\sqrt {a}}}{\frac {\sqrt {n}}{\log n}}}$

где A зависит от a , b , и c , но не от n . По теореме о простых числах эта формула с A , равным единице , является асимптотическим числом простых чисел меньших n , ожидаемых в случайном наборе чисел, имеющем ту же плотность, что и набор чисел вида ax ²  +  bx  +  c . Но поскольку A может принимать значения больше или меньше 1, некоторые многочлены, согласно гипотезе, будут особенно богаты простыми числами, а другие — особенно бедны. Необычно богатым многочленом является 4 x ²  − 2 x  + 41 , который образует видимую линию в спирали Улама. Константа A для этого многочлена приблизительно равна 6,6, что означает, что числа, которые он генерирует, почти в семь раз чаще являются простыми, чем случайные числа сопоставимого размера, согласно гипотезе. Этот конкретный многочлен связан с многочленом Эйлера , порождающим простые числа x ²  −  x  + 41, заменой x на 2 x или, что эквивалентно, ограничением x четными числами. Константа A задается произведением, пробегающим все простые числа,

${\displaystyle A=\prod \limits _{p}{\frac {p-\omega (p)}{p-1}}~}$,

в котором — число нулей квадратного многочлена по модулю p и, следовательно, принимает одно из значений 0, 1 или 2. Харди и Литтлвуд разбивают произведение на три множителя следующим образом: ${\displaystyle \omega (p)}$

${\displaystyle A=\varepsilon \prod _{p}{\biggl (}{\frac {p}{p-1}}{\biggr )}\,\prod _{\varpi }{\biggl (}1-{\frac {1}{\varpi -1}}{\Bigl (}{\frac {\Delta }{\varpi }}{\Bigr )}{\biggr )}}$.

Здесь множитель ε, соответствующий простому числу 2, равен 1, если a  +  b нечетно, и 2, если a  +  b четно. Первый индекс произведения p пробегает конечное число нечетных простых чисел, делящих как a, так и b . Для этих простых чисел , поскольку p не может делить c . Второй индекс произведения пробегает бесконечное число нечетных простых чисел, не делящих a . Для этих простых чисел равен 1, 2 или 0 в зависимости от того, является ли дискриминант 0, ненулевым квадратом или неквадратом по модулю p . Это объясняется использованием символа Лежандра , . Когда простое число p делит a, но не b, то есть один корень по модулю p . Следовательно, такие простые числа не вносят вклад в произведение. ${\displaystyle \omega (p)=0}$ ${\displaystyle \varpi }$ ${\displaystyle \omega (p)}$ ${\displaystyle \left({\frac {\Delta }{\varpi }}\right)}$

Квадратичный многочлен с A ≈ 11,3, на данный момент самым высоким известным значением, был обнаружен Якобсоном и Уильямсом. ^{[9] [10]}

Варианты

В статье Клаубера 1932 года описывается треугольник, в котором строка n содержит числа от ( n   − 1) ²  + 1 до n ² . Как и в спирали Улама, квадратичные многочлены генерируют числа, которые лежат на прямых линиях. Вертикальные линии соответствуют числам вида k ²  −  k  +  M . На рисунке видны вертикальные и диагональные линии с высокой плотностью простых чисел.

Роберт Сакс разработал вариант спирали Улама в 1994 году. В спирали Сакса неотрицательные целые числа нанесены на архимедову спираль , а не на квадратную спираль, используемую Уламом, и расположены так, что один полный квадрат появляется на каждом полном обороте. (В спирали Улама два квадрата появляются на каждом обороте.) Многочлен Эйлера, генерирующий простые числа, x ²  −  x  + 41, теперь выглядит как одна кривая, когда x принимает значения 0, 1, 2, ... Эта кривая асимптотически приближается к горизонтальной линии в левой половине рисунка. (В спирали Улама многочлен Эйлера образует две диагональные линии, одну в верхней половине рисунка, соответствующую четным значениям x в последовательности, другую в нижней половине рисунка, соответствующую нечетным значениям x в последовательности.)

Дополнительную структуру можно увидеть, когда в спираль Улама также включены составные числа . Число 1 имеет только один множитель, само себя; каждое простое число имеет два множителя, себя и 1; составные числа делятся по крайней мере на три различных множителя. Используя размер точки, представляющей целое число, для указания количества множителей и раскрашивая простые числа в красный цвет, а составные числа в синий, получаем показанную фигуру.

Спирали, следующие за другими мозаиками плоскости, также порождают линии, богатые простыми числами, например, шестиугольные спирали.

• 
  Выделен треугольник Клаубера с простыми числами, порожденными многочленом Эйлера x ²   −   x   + 41.
• 
  Мешки спиральные.
• 
  Спираль Улама размером 150×150, показывающая как простые, так и составные числа.
• 
  Шестиугольная числовая спираль с простыми числами зеленого цвета и более сложными составными числами темных оттенков синего цвета.
• 
  Числовая спираль с 7503 простыми числами, видимыми на правильном треугольнике.
• 
  Спираль Улама с 10 миллионами простых чисел.

Смотрите также

• Распознавание образов
• Простой k-кортеж

Ссылки

1. Гарднер 1964, стр. 122.
2. Стайн, Улам и Уэллс 1964, стр. 517.
3. Гарднер 1964, стр. 124.
4. Daus 1932, стр. 373.
5. Моллин 1996, стр. 21.
6. Стайн, Улам и Уэллс 1964, стр. 520.
7. Гарднер 1971, стр. 88.
8. Хартвиг, Дэниел (2013), Путеводитель по бумагам Мартина Гарднера, Онлайн-архив Калифорнии, стр. 117.
9. Якобсон-младший, MJ; Уильямс, H. C (2003), «Новые квадратичные многочлены с высокой плотностью простых значений» (PDF) , Математика вычислений , 72 (241): 499–519, Bibcode : 2003MaCom..72..499J, doi : 10.1090/S0025-5718-02-01418-7
10. Гай, Ричард К. (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer, стр. 8, ISBN 978-0-387-20860-2

Библиография

• Даус, PH (1932), «Мартовское заседание секции Южной Калифорнии», American Mathematical Monthly , 39 (7), Математическая ассоциация Америки: 373–374, doi : 10.1080/00029890.1932.11987331, JSTOR  2300380
• Гарднер, М. (март 1964 г.), «Математические игры: замечательные знания о простом числе», Scientific American , 210 : 120–128, doi : 10.1038/scientificamerican0364-120
• Гарднер, М. (1971), Шестая книга математических развлечений Мартина Гарднера из Scientific American , Издательство Чикагского университета, ISBN 978-0-226-28250-3
• Харди, GH; Литтлвуд, Дж. Э. (1923), «Некоторые проблемы 'Partitio Numerorum'; III: О выражении числа как суммы простых чисел», Acta Mathematica , 44 : 1–70, doi : 10.1007/BF02403921
• Хоффман, Пол (1988), Месть Архимеда: Радости и опасности математики , Нью-Йорк: Fawcett Colombine, ISBN 0-449-00089-3
• Mollin, RA (1996), «Квадратичные многочлены, производящие последовательные различные простые числа и группы классов комплексных квадратичных полей» (PDF) , Acta Arithmetica , 74 : 17–30, doi : 10.4064/aa-74-1-17-30
• Pegg, Jr., Ed (17 июля 2006 г.), «Prime generation polynomials», Math Games , Mathematical Association of America , получено 1 января 2019 г.
• Стайн, М. Л.; Улам, С. М.; Уэллс, М. Б. (1964), «Визуальное отображение некоторых свойств распределения простых чисел», American Mathematical Monthly , 71 (5), Математическая ассоциация Америки: 516–520, doi : 10.2307/2312588, JSTOR  2312588
• Стайн, М.; Улам, С.М. (1967), «Наблюдение за распределением простых чисел», American Mathematical Monthly , 74 (1), Математическая ассоциация Америки: 43–44, doi : 10.2307/2314055, JSTOR  2314055