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

[rightways]

Почему $38^n+31$ всегда составное?

[sergei1961]

при нечётных делится на три...

[NSKuber]

При чётных подобной халявы не наблюдается. Например, наименьший простой делитель $38^{24}+31$ - $10141$.

[venco]

В добавок, если $n=2\mod 4$, то делится на 5.
Если $n=4\mod 12$, то делится на 7.
А вот с $n=0\mod 12$ и $n=8\mod 12$ облом, никакой регулярной структуры не вижу.
Разложение для плохих $n$:
$38^{8}+31 = 577\cdot 12277\cdot 613763$
$38^{12}+31 = 322249\cdot 338431\cdot 83126873$
$38^{20}+31 = 5861\cdot 93377\cdot 72021190193664628182131$
$38^{24}+31 = 10141\cdot 235951\cdot 34348178707619446764774037637$
$38^{32}+31 = 181246145664079\cdot 12573651361301249\cdot 156799580994082357297$
$38^{36}+31 = 419\cdot 6124795085316907739\cdot 290338007428229189705366218753645967$
Пока везде по три простых множителя, но не видно никакой регулярной структуры.

[grizzly]

venco в сообщении #1098906 писал(а):

Пока везде по три простых множителя, но не видно никакой регулярной структуры.

Количество сомножителей пляшет дальше как угодно. Если бы привели ещё одно разложение, то нетрудно было бы заметить, что при $n=8 \bmod 36$ число делится на 577

[Naf2000]

$38^{48}+31=1723 \cdot 3920372735102239198932309911848148888285405714255716808096690131227475949$ имеет только два простых делителя

[Sonic86]

А далеко не факт, что все значения составные. Либо Вы подбираете конечное число модулей, по которым $38^n+11\equiv 0$ (это возможно: https://ru.wikipedia.org/wiki/%D0%A7%D0 ... 0%B3%D0%BE), либо Вы будете страдать до Большого разрыва.
Напоминаю, что предполагается, что число простых вида $2^n-1$ бесконечно.

[Sonic86]

Я тупым брутфорсом на PARI/GP дошел до $n=6500$ - там все числа составные.
Вообще да - с функциями типа $f(n)=ka^n+b$ ситуация поинтереснее. Когда все значения $f(n)$ - составные? Данный пример - это исключение или таких много? Как много? Какой пример минимальный?

upd: ссылки:
http://math.stackexchange.com/questions ... form-38n31
тут мужик утверждает, что $38^n+31$ составное аж для всех $n<185000$
Приводится стандартный вероятностный аргумент, оценивающий первое такое $n$ - порядка миллиона.
еще: http://math.stackexchange.com/questions ... -composite
тут - до $220000$

[ET]

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

Вообще да - с функциями типа $f(n)=ka^n+b$ ситуация поинтереснее. Когда все значения $f(n)$ - составные? Данный пример - это исключение или таких много? Как много? Какой пример минимальный?

Таких, очевидно, много. Один из самых простых - $3^n+1$

[Lia]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Математика (общие вопросы)»

[Sonic86]

ET в сообщении #1100330 писал(а):

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

Вообще да - с функциями типа $f(n)=ka^n+b$ ситуация поинтереснее. Когда все значения $f(n)$ - составные? Данный пример - это исключение или таких много? Как много? Какой пример минимальный?

Таких, очевидно, много. Один из самых простых - $3^n+1$

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

[Sonic86]

Я пока потыкался ручками, нашел несколько примеров, но они до исходного сильно не дотягивают:
$2^n-7$
$2^n-337$

upd: добрался до калькулятора. Я довольно хорошо посчитал ручками.
Скрипт для $a<10^3$ выдал, что у последовательности $2^n-a$ при $a=221$ 1-е простое число имеет номер $n=714$, а для $a=337$ - $n=791$. Остальные результаты послабже: для $a=809$ - $n=636$.
Распределение 1-го простого числа в последовательности $2^n-a$ смахивает на экспоненциальное (не считал), хотя в хвостах выбросы сильные.
В общем, я думаю, что $38^n+31$ - это что-то типа сильно запущенного случая $2^n-337$. Автор, наверное, на это рассчитывал.
Надо бы еще попробовать распределение сравнить с распределением, которое получается из вероятностных соображений. Если дадут...

[Sinoid]

(Оффтоп)

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

Скрипт для $a<10^3$

я вот, когда вижу подобные слова, думаю: это что, для каждой такой задачи пишется и затем устанавливается специальный файл .exe? Или как?

[Sonic86]

(Оффтоп)

Sinoid в сообщении #1102085 писал(а):

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

Скрипт для $a<10^3$

я вот, когда вижу подобные слова, думаю: это что, для каждой такой задачи пишется и затем устанавливается специальный файл .exe? Или как?

Я использовал PARI/GP (http://dxdy.ru/topic14229.html)
Ну вообще да: каждый раз пишу и запускаю.

[Руст]

Здесь действительно все члены составные.

Мои вероятностные соображения говорят, что верна следующая гипотеза:

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

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

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

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

Программа работает для любого набора $a,b,c,d$, надо только корректировать $N$ и максимальные начальные примарные компоненты порядка $\sqrt{N}$.