38^n+31- составное

[grizzly]

Руст в сообщении #1102723 писал(а):

Пусть $a,b,c,d$ целые, такие, что $cd\ne 0, |ab|>1$. Тогда в последовательности

$$x_n=c*a^n+d*b^n$$

все члены кроме может быть конечного числа составные.

Очень сильное утверждение, которое покрывает сразу несколько открытых проблем теории чисел. Но что-то здесь не так. Например, для случая $a=2, b=d=1, c=3$ вроде бы известно, что последовательность $x_n$ содержит бесконечное число простых. См. также о проблеме Ризеля, числах Прота и Серпинского.

[Sonic86]

Руст в сообщении #1102723 писал(а):

Пусть $a,b,c,d$ целые, такие, что $cd\ne 0, |ab|>1$. Тогда в последовательности

$$x_n=c*a^n+d*b^n$$

все члены кроме может быть конечного числа составные.

Простых Мерсенна и Ферма - конечное число?!

[Руст]

Я упустил исключение $|cd|=1$ из гипотезы. В этом случае нельзя (кроме особых случаев одно из $T_p=1$) покрыть арифметическими прогрессиями $kT_p+y_p$.

В доказательстве этого конкретного случая я проверил только покрытие по модулю для каждого делителя, являющегося степенью простого числа.
Это доказывает утверждение гипотезы для данного случая. Но малые n могут не попасть в покрытие арифметическими последовательностями.
Их надо отдельно проверять. Т.е. надо немного переделать программу так, чтобы
доказать, что и при малых n не будет исключений.

[grizzly]

Руст
Давайте посмотрим на простые числа Прота. Ни на MathWorld'e, ни в энциклопедии последовательностей для первых значений $k$ не сказано ничего определённого о конечности / бесконечности количества этих чисел. Для чисел вида $3\cdot 2^n+1$ я посмотрел с десяток старых статей, посвящённых проблемам факторизации этих чисел Прота, -- тоже ничего -- все просто говорят о довольно общих условиях и выводах. Немного настораживает, не находите

[Руст]

При фиксированном $k$ может быть очень много простых вида $ka^n+1$ (случай, когда k и a степени одного и того же числа исключаем).
Я высказал гипотезу, где не все возможные исключения рассмотрел. У меня к этому есть только вероятностные соображения о возможности
покрытия натуральных чисел арифметическими последовательностями. Я проверял это по модулю степеней простых чисел для исходного примера.
Однако это доказывает только, что для достаточно больших $n$ оно попадает хотя бы в одно из арифметических последовательностей (что соответствует гипотезе).
Достаточно большое может быть действительно большим типа $n>10^{1000000}$, так как общий период покрывающий все n - $M=lcm(p_i^{k_i})=\prod_i p_i^{k_i}$ большое.
А покрытие гарантировано только начиная с $M*\pi(X)$.

[Sonic86]

Руст в сообщении #1102723 писал(а):

Провел доказательство (компьютерное) для данного случая $c=b=1,a=38,d=31$.
Рассмотрим множество простых $P=\{p<N|T_p|M\}$. Где $T_p$ период $x_n$ по модулю $p$ для которых $p|x_{kT_p+m_p} \ \forall k$.
Я взял

$$N=2^{16}, M=\prod_pp^{[\log_p(256)]}.$$

Показал, что для каждой примарной компоненты $M$ вида $p^{\nu_p}$ и для каждого вычета $y_p$ и $n=kp^{\nu_p}+y_p$ существует простое $q$ (зависящее от n),
что $q|x_n$. Все примарные вычеты покрывают все вычеты по модулю $M$.
Так как простые ограничены $q<N$ и все члены $|x_n|<N$ составные, то действительно все $x_n$ составные.

Товарищи, кто-нибудь понял? Я ничего не понял
Прежде всего, если мы доказывает, что для какого-то $p^{\nu_p}$ для всех $y_p:0\leqslant y_p<p$ для любого $k$ $q|x(kp^{\nu_p}+y_p)$, то зачем нам перебирать остальные $p^{\nu_p}$? Этого уже достаточно.
И $M$ явно же взято от балды, значит его можно уменьшить? Можно ли подобрать пример попроще типа $2^n-7$, чтобы можно было руками пощупать?
Как насчет текста программы?