Открытые проблемы из OEIS

[RIP]

На самом деле искомых чисел $k$ ровно $\frac{L+1}2$

Добавлено спустя 57 минут 19 секунд:

Короче, вот решение этой задачи. Рассказываю в обозначениях господина Артамонова Ю.Н..
Допустим, что $L\leqslant 3^n$. Тогда для искомых $k$ возможно только $A(k)=2$, поэтому надо посчитать число решений неравенства $2^n<2k\leqslant L$, т.е. $2^{n-1}<k\leqslant\lfloor\frac L2\rfloor$. Ровно $\lfloor\frac L2\rfloor-2^{n-1}$ штук. Недолет.
Пусть теперь $3^n<L\leqslant5^n+4$. Тогда надо еще учесть нечетные $k$, делящиеся на 3, т.е. посчитать число решений нер-ва
$3^n<6k+3\leqslant L$. Их ровно $\lfloor\frac{L-3}6\rfloor-\frac{3^{n-1}-1}2$ штук. Мы хотим, чтобы

$$\left\lfloor\frac{L-3}6\right\rfloor-\frac{3^{n-1}-1}2+\left\lfloor\frac L2\right\rfloor-2^{n-1}>\frac L2$$

Это равносильно

$$\left\lfloor\frac{L-3}6\right\rfloor\geqslant \frac{3^{n-1}+1}2+2^{n-1}$$

Отсюда $L\geqslant3+6\left(\frac{3^{n-1}+1}2+2^{n-1}\right)=3^n+3\cdot2^n+6$.
Это меньше $5^n+4$ при $n\geqslant2$. Случай $n=1$ проверяется непосредственно.

[juna]

Зачем усложнять. После того, как получили $B+C/2-L/2=1$ и так ясно, что это нижнее ограничение для $L$ (тем самым доказана и достаточность и необходимость) – можно предполагать произвольную $L_1$ и проделать с ней то же самое $\frac{L_1-2^n}{2}+\frac{L_1-3^n}{3*2}-\frac{L_1}{2}>=1$, получим искомое.
Впрочем, Ваше решение строгое и полное.
Одно непонятно мне в этой задаче - как рождаются такие гипотезы. По-моему, получить это ограничение, можно решив задачу, а так, чтобы эмпирически – непонятны исходные посылки. Отсюда еще одна гипотеза OEIS: Ralf Stephan отчасти водит нас за нос и предлагает в качестве гипотез уже решенные задачи.

[juna]

Мне показалась интересной проблема 28, и кажется действительно трудной. Переформулирую ее здесь: для любого заданного $n$ найдутся такие $i,j$, что $0<i<j<n, n>3$ и $2^n+2^i+2^j+1 \text{ - простое число}$.
Добавлено
Проверено $\forall n<1000$ - гипотеза верна.

[RIP]

Задачи 111-112 абсолютно неверны и условия не представляется возможным поправить. Например,
$a_3=a_{63}=0,a_{21}=a_{5247}=3,$
однако
$63,5247\in\{n\mid n=3k,k=3i\text{ и }e_1(k)\equiv1\pmod2\}$
$3,21\in\{n\mid n=3k,k\notin\{k\mid k=3i\text{ и }e_1(k)\equiv1\pmod2\}\}$

[juna]

Артамонов Ю.Н. писал(а):

Мне показалась интересной проблема 28, и кажется действительно трудной. Переформулирую ее здесь: для любого заданного $n$ найдутся такие $i,j$, что $0<i<j<n, n>3$ и $2^n+2^i+2^j+1 \text{ - простое число}$.
Добавлено
Проверено $\forall n<1000$ - гипотеза верна.

Гипотеза эта может иметь большое практическое значение, например, для получения очень больших простых чисел по схеме шифрования RSA.
Действительно, например, при поиске простого числа по его номеру необходимо $n$ переборов при порядке простого числа $O(nln(n))$, при поиске в арифметических прогрессиях при $n$ переборах получаем простое число порядка $O(n^2)$.
В этом смысле указанная гипотеза просто сказочная - при $\frac{n(n-1)}{2}$ переборах обеспечивается порядок простого числа $O(2^n)$.
В этой связи данная гипотеза, если она верна, нелегче гипотезы Римана, Гольдбаха и т.д.

[maxal]

Артамонов Ю.Н. писал(а):

Гипотеза эта может иметь большое практическое значение, например, для получения очень больших простых чисел по схеме шифрования RSA.

Совсем даже наоборот. Такие простые будут "слабыми", в том смысле, что их легко перебрать и проверить. В RSA их использовать нельзя.

Артамонов Ю.Н. писал(а):

Действительно, например, при поиске простого числа по его номеру необходимо $n$ переборов

Если мы хотим найти простое большее числа $m,$ то перебирать в среднем придется около $\ln m$ чисел.

Артамонов Ю.Н. писал(а):

В этом смысле указанная гипотеза просто сказочная - при $\frac{n(n-1)}{2}$ переборах обеспечивается порядок простого числа $O(2^n)$.

Ничего сказочного в ней нет. Сказочно было бы, если бы она оказалась неверна для бесконечного числа значений $n$.

[juna]

maxal писал(а):

Артамонов Ю.Н. писал(а):

Гипотеза эта может иметь большое практическое значение, например, для получения очень больших простых чисел по схеме шифрования RSA.

Совсем даже наоборот. Такие простые будут "слабыми", в том смысле, что их легко перебрать и проверить. В RSA их использовать нельзя.

Если не ошибаюсь, большие простые числа специального вида никто в RSA непосредственно не использует. Из них получают еще большие простые числа специальным смешиванием, например, если $a=2^n+2^i+2^j+1$ - большое простое число, то выбирают некоторое случайное четное $b$ из заданного диапазона, чтобы число $ab+1$ было простым, что становится сделать много проще.
А по-поводу сказочности - это вопрос субъективный.

[maxal]

Артамонов Ю.Н. писал(а):

maxal писал(а):

Артамонов Ю.Н. писал(а):

Гипотеза эта может иметь большое практическое значение, например, для получения очень больших простых чисел по схеме шифрования RSA.

Совсем даже наоборот. Такие простые будут "слабыми", в том смысле, что их легко перебрать и проверить. В RSA их использовать нельзя.

Если не ошибаюсь, большие простые числа специального вида никто в RSA непосредственно не использует.

Учитывая, что генерирование ключа - нечастая процедура, то можно просто брать случайное число нужного размера и дальше перебирать числа большие его, проверяя их на простоту каким-нибудь быстрым алгоритмом (типа Миллера-Рабина).

Артамонов Ю.Н. писал(а):

Из них получают еще большие простые числа специальным смешиванием, например, если $a=2^n+2^i+2^j+1$ - большое простое число, то выбирают некоторое случайное четное $b$ из заданного диапазона, чтобы число $ab+1$ было простым, что становится сделать много проще.

Видимо, вы имеете в виду эту процедуру. Ну и как там поможет простое число указанного специального вида? Кроме того, его особенность нарушится уже после первой итерации (а если итерация только одна, то это заведомое ослабление параметров, как я уже писал).
В общем, такие простые в RSA не нужны никаким боком: ни особого ускорения, ни секьюрности они не привносят.

[juna]

Да, процедура похоже эта и итерация предполагалась одна. Не думаю, что это сильное ослабление параметров - в загаданном четном случайном $b$ может быть почти произвольный порядок двоек и выделить степени в выбранных числах специального вида не представляется возможным. Можно попробовать - я загадаю, а Вы факторизуете.
Ладно, с большой практической значимостью палку я перегнул.
В связи с этой проблемой столкнулся с более частной, но тоже интересной гипотезой:
$\forall {k}\in N: {0}\leqslant l\leqslant \lfloor{\frac{3\cdot 2^{k+1}-1}{2}}\rfloor\Rightarrow 4096^{2^k}+4^{2l+1}+3 - \text {составное}$

[maxal]

RIP писал(а):

Задачи 111-112 абсолютно неверны и условия не представляется возможным поправить.

Похоже, что правые части условий задач 111 и 112 должны быть поправлены так:

для 111:

$$n\in\left\{k\,\big|\;k=3i\,\wedge\,e_1(k)\equiv1\pmod2\right\}.$$

для 112:

$$n\in\left\{k\,\big|\;k=3i\,\wedge\,e_1(k)\equiv0\pmod2\right\}.$$

[RIP]

maxal писал(а):

RIP писал(а):

Задачи 111-112 абсолютно неверны и условия не представляется возможным поправить.

Похоже, что правые части условий задач 111 и 112 должны быть поправлены так:

для 111:

$$n\in\left\{k\,\big|\;k=3i\,\wedge\,e_1(k)\equiv1\pmod2\right\}.$$

для 112:

$$n\in\left\{k\,\big|\;k=3i\,\wedge\,e_1(k)\equiv0\pmod2\right\}.$$

Возможно, но тогда это вообще устные задачи.

[maxal]

Да, и причем вместо $\Rightarrow$ там должно быть $\Leftrightarrow$. Тогда это будет в точности соответствовать гипотезе (того же автора) в описании A065359:
Conjectures: a(n) = 3 or -3 iff n in 3*A036556; a(n) = 0 iff n=3k with k not in A036556. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Mar 07 2003

[Sonic86]

Общая формула
$a_n = (1- n \mod 2) - a_{[n/2]}$
Отсюда
$a_n = (1- n \mod 2) - (1- \left[ \frac{n}{2^1}\right] \mod 2) + ... + (1- \left[ \frac{n}{2^{2N-1}}\right] \mod 2) - (1- \left[ \frac{n}{2^{2N}}\right] \mod 2)$
$a_n = - n \mod 2 + \left[ \frac{n}{2^1}\right] \mod 2 - ... - \left[ \frac{n}{2^{2N-1}}\right] \mod 2 + \left[ \frac{n}{2^{2N}}\right] \mod 2$.
$e_N=1$ всегда. Предположим, что есть хотя бы еще одно $a:e_{a-1}=1$, то есть $n=4^an_1+n_2, n_2>0$. Тогда из формулы выше для $a_n$ следует, что $a_{3n}=a_{3n_1}+a_{3n_2}$. Тогда достаточно доказать $a_{3n}=0$ только для $n$, у которых только $e_N=1$, а остальные $e_j \in \{ 0;-1\}.$
Обозначим $s_1 = \sum\limits_{j \geq 0} \left[ \frac{3n}{4^j}\right] \mod 2$, $s_2 = \sum\limits_{j \geq 0} \left[ \frac{3n}{2 \cdot 4^j}\right] \mod 2$ и докажем, что $s_1=s_2.$
$3n=(4-1)n=\sum\limits_j(e_{j-1}-e_j)4^j = \sum\limits_j d_j4^j$
$\left[\frac{3n}{4^k}\right]=\sum\limits_{j \geq k}d_j4^{j-k} + [\epsilon _{k-1}]$
$\left[\frac{3n}{2\cdot 4^k}\right]=\sum\limits_{j \geq k+1}2d_j4^{j-k-1} + [\epsilon _k]$,
где $\epsilon _k = \sum\limits_{j<k} d_j4^{j-k}$.
И тогда $s_1 = \sum\limits_j (d_j +[\epsilon _{j-1}]) \mod 2$, $s_2 = \sum\limits_j [\epsilon _j] \mod 2$. Вычислим обе суммы, сначала $s_2$, потом $s_1$.
Последовательность "цифр" $e_j$ имеет вид: $1,...,0,-1,...,-1,0,...,0,-1,...,-1,0,...,0,-1$. Каждая "горка" $-1,0,...,0,-1$ переводится оператором $d_j=e_{j-1}-e_j$ в $0,1,0,...,0,-1,0,...$, поэтому в сумме $s_2$ для "цифр" $0,...,0,-1$ будет всегда $\epsilon _j <0$ (каждому слагаемому $s_2$ соответствует "цифра" $d_j$), поэтому $s_2$ равно числу нулей в последовательности "цифр" $e_j$ + константа. Константа эта равна 1 - ее находим из рассмотрения начала последовательности $e_j$, начинающейся на 1 (номер $j=N$). Для $s_1$ каждое слагаемое равно $(d_j +[\epsilon _{j-1}]) \mod 2$, "цифра" $d_j$ принимает 2 раза значение 1 на краях "горки", а $\epsilon _j<0$ для всех нулей "горки" и для ее левого края (ему соответствует число 1), так что "горка" из $r$ нулей дает вклад из $r$ единиц в сумму. Значит $s_1$ тоже равна числу нулей в последовательности + постоянная, а постоянная равна 1, что находим из рассмотрения слагаемого с номером $j=0$.
Таким образом, обе суммы равны 1 + число нулей в последовательности "цифр" $e_j$ числа $n$, а значит равны.

Что-то для меня это не совсем детсадовское. Может быть есть решение проще?

[deep blue]

У меня тоже получилось немного громоздкое доказательство, но в принципе лобовое и без хитростей.
Множество чисел $k=k_n=3\sum\limits_{r=0}^ne_r4^r$ можно задать рекуррентно.
Видно, что произвольное число $k_{n+1}$ представляется через некоторое число $k_n$ при помощи одной из трех формул:
$k_{n+1}=4k_n+3$ или $k_{n+1}=4k_n$ или $k_{n+1}=4k_n-3$
Проверкой убеждаемся, что для произвольного числа $k_1$ выполняется $a(k_1)=0$ и $a(k_1-1)=1$
Пусть мы доказали, что для всех $k_n$ выполняются равенства $a(k_n)=0$ и $a(k_n-1)=1$
Докажем тогда, что выполняется и $a(k_{n+1})=0$ и $a(k_{n+1}-1)=1$
Если $k_{n+1}=4k_n+3$, то
$a(k_{n+1})=a(4k_n+3)=a(2(2k_n+1)+1)=a(k_n)=0$ и $a(k_{n+1}-1)=a(4k_n+2)=1+a(4k_n+3)=1$
Если $k_{n+1}=4k_n$, то
$a(k_{n+1})=a(4k_n)=a(k_n)=0$ и $a(k_{n+1}-1)=a(4k_n-1)=a(2(2(k_n-1)+1)+1)=a(k_n-1)=1$
Если $k_{n+1}=4k_n-3$, то
$a(k_{n+1})=a(4k_n-3)=a(4(k_n-1)+1)=-a(2(k_n-1))=-1+a(k_n-1)=0$ и $a(k_{n+1}-1)=a(4k_n-4)=a(k_n-1)=1$
При выводах использовались простейшие тождества:
$a(4k_{n})=a(k_n)$, $a(2k_{n}+1)=-a(k_n)$, $a(2(2k_{n}+1)+1)=a(k_n)$, $a(2k_n)=1-a(k_n)=1+a(2k_{n}+1)$
Наверное можно сделать его более концептуальным и ясным, надеюсь не ошибся при оформлении.