простые числа вида n^2+1

[ИСН]

Ну, не совсем. 3 делит $3^2+6^2$, однако - - -

[yk2ru]

Нужна добавка про взаимную простоту чисел в суммах.

[Sonic86]

yk2ru писал(а):

Если число делит сумму двух квадратов, то оно само сумма двух квадратов. Пример выше с числом $13$.

А это к чему? Ну, независимо от этого это легко доказать...

[Батороев]

Sonic86 в сообщении #422895 писал(а):

(Оффтоп)

Батороев, искренне желаю удачи, вот только боюсь, что алгоритм Евклида там не прокатит. И формула включений-исключений тоже, если что (это чтоб Вы зря не мучились).

Насчет алгоритма Евклида Вы правы. А вот относительно формул включения-выключения я бы не был столь категоричным.

Любое нечетное число можно разложить на разность квадратов двух последовательных чисел:
$ k=\left ( \dfrac {k+1}{2}\right)^2-\left ( \dfrac {k-1}{2}\right)^2$
В отношении рассматриваемых чисел это выглядит следующим образом:
$ n^2+1=\left ( \dfrac {n^2+2}{2}\right)^2-\left ( \dfrac {n^2}{2}\right)^2 $
Поэтому в отношении рассматриваемых чисел можно утверждать, что каждое простое или составное число $n^2+1$ при перестановке членов равенства дает большее число такого же вида:
$ \left ( \dfrac {n^2}{2}\right)^2+1 = \left ( \dfrac {n^2+2}{2}\right)^2 - n^2$
но уже гарантированно составное (т.к. $\dfrac {n^2+2}{2}$ и $n$ - не два последовательных числа).
Количество таких чисел до $n$: $N_1=\sqrt {n}$ (1)

Исходное число условно назовем "прародителем".


Любое составное нечетное число кроме того раскладывается на разность квадратов:
$ k_1\cdot k_2=\left ( \dfrac {k_1+k_2}{2}\right)^2-\left ( \dfrac {k_1-k_2}{2}\right)^2$

Аналогично раскладывая составные числа вида $n^2+1$, а затем переставляя члены равенства, будем получать другие составные числа. Величина вновь получаемых чисел по сравнению с исходным числом зависит от величины меньших множителей данных чисел.

Например,
$325=18^2+1=65\cdot 5= 35^2-30^2$
Получаем: $30^2+1=35^2-18^2=53\cdot 17= 901$
$325<901$, т.к. ${5}<{17}$.

$18^2+1=25\cdot 13=19^2-6^2$
Получаем: $6^2+1=19^2-18^2=37\cdot 1= 37$
$325>37$, т.к. ${13}>{1}$

Из примера видно, что одним из полученных из составного числа является меньшее число (в данном случае $6^2+1=37$), которое является для числа $325$ "прародителем".
Таким образом, составные числа $n^2+1$, имеющие $2$ простых множителя, могут в свою очередь быть "прародителем" всего одного числа, т.к. из двух получаемых чисел одно является "прародителем" самого числа.

Как считать количество других получаемых чисел $N_2$ (в примере - число $30^2+1=901$)? Пока не знаю. По-видимому, используя каким-то образом формулы включений-выключений.
Но почти уверен, что

$N-N_1-N_2\ne 0$
(где $N=\dfrac{n}{2}$ - число всех чисел вида $n^2+1$, непревосходящих $n$).

Попутно отмечу, что существуют "самородящиеся" составные числа, например:
$12^2+1= 145= 29\cdot 5 = 17^2-12^2$
Каждое из них уменьшает на единицу выражение (1). Интересно, много ли таких?

[DVN]

А почему только числа $n^2+1$ ? ИМХО, числа вида $n^2+a$, где a любое и числа вида $n^2-a$, где a не квадрат тоже содержат бесконечное число простых. Пусть кто попробует опровергнуть!

[Батороев]

DVN в сообщении #423518 писал(а):

А почему только числа $n^2+1$ ? ИМХО, числа вида $n^2+a$, где a любое и числа вида $n^2-a$, где a не квадрат тоже содержат бесконечное число простых. Пусть кто попробует опровергнуть!

Под Ваше определение подпадают все простые числа, бесконечность которых доказана.

-- 16 мар 2011 18:19 --

DVN
Извините, не сразу въехал в Ваше условие и поспешил с ответом.

[DVN]

Батороев в сообщении #423520 писал(а):

Извините, не сразу въехал в Ваше условие и поспешил с ответом.

Бывает. См. в личку.

[Батороев]

DVN в сообщении #423859 писал(а):

См. в личку.

Посмотрел. Ваш подход отличается от моего.

Батороев в сообщении #423493 писал(а):

Попутно отмечу, что существуют "самородящиеся" составные числа, например:
$12^2+1= 145= 29\cdot 5 = 17^2-12^2$
Каждое из них уменьшает на единицу выражение (1). Интересно, много ли таких?

Разобрался. Таких чисел немного.
Все составные "самородящиеся" числа (за исключением простого $5$) являются произведением двух соседних чисел из ряда: $a_1=1; a_2=5; a_3;a_4; ... a_i $,
где $a_i=6a_{i-1}-a_{i-2}$
(т.е. в этом ряду каждый член равен шестой части суммы двух соседних членов ).

Таким образом, количество "самородящихся" составных чисел до $n$ не более $(\log_6 n -1)$.

[Droog_Andrey]

Есть гипотеза о том, что простых чисел вида $n^{2^k}+1$ бесконечно для любого наперёд заданного целого положительного $k$, и даже есть гипотеза об их распределении:
http://yves.gallot.pagesperso-orange.fr ... cdgfpn.pdf

[Sonic86]

Droog_Andrey в сообщении #472576 писал(а):

Есть гипотеза о том, что простых чисел вида $n^{2^k}+1$ бесконечно для любого наперёд заданного целого положительного $k$, и даже есть гипотеза об их распределении:
http://yves.gallot.pagesperso-orange.fr ... cdgfpn.pdf

Хорошая статья!
Есть еще одна статья, немного более древняя:
http://www.ams.org/journals/mcom/1962-1 ... 8632-7.pdf
Вообще формула для плотности распределения строится очень просто

[Droog_Andrey]

Ну там ещё фишка в дзета-функции Дедекинда