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

[maxal]

Для любителей сложных и неординарных задач. Примите к сведению, что приведенные открытые проблемы не подразумевают чрезмерную сложность и/или глубокую изученность в математическом мире (в противовес всемирно известным гипотезам типа гипотезы Гольдбаха). Возможно, какие-то из них допускают короткие и изящные решения. И у нас есть шанс их найти

Также, нужно учитывать, что эта статья 2004 года и с тех пор, некоторые из представленных гипотез получили свое докательство/опровержение (как, например, самая первая, на поверку довольно простенькая задача).

Итак: Prove or Disprove. 100 Conjectures from the OEIS

[worm2]

Интересный зоопарк.
Навскидку:
Первые две, наверное, следуют из разложений в ряд Тейлора. Хотя точно не скажу --- нет особого интереса. Дальше идут трюки поинтереснее. К некоторым вообще непонятно как подступиться. Но вот 51-я следует из довольно-таки широко известных фактов. А 40-я тривиальна до неприличия.
То есть задачи сильно различаются по степени сложности. Действительно, похоже, что любому найдётся задачка по силам.

[maxal]

Там в конце приводится ссылка на текущее состояние гипотез:
http://www.ark.in-berlin.de/conj.txt

Большинство уже успешно доказаны/опровергнуты, но есть и по-прежнему открытые.

[juna]

Мне из недоказанных показалась интересной проблема 46.
И как только такие гипотезы рождаются?
Наверное, она допускает какие-то обобщения.

[RIP]

Или я что-то не понимаю, или одно из двух. В задаче 113
$a_{54}=0$, но $18=2+(-4)^2$
Что означает фраза "k in base-4 contains only -1,0,1"?

Добавлено спустя 1 час 52 минуты 57 секунд:

Всё, разобрался. Там утверждается наоборот, что если $k$ таково, то $a_{3k}=0$. Но тогда это очень простая задача. Почему я не вижу её в списке решенных?

[RIP]

Точнее там должно так утверждаться, а там задача сформулирована неверно.

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

Задачи 111 и 112 тоже вроде несложные, только сформулированы неправильно. Там походу условия перепутаны.
То-то их нет в списке решенных

[RIP]

Задачка сперта отседова, №113. В ссылочке maxalа напротив задачи - большое жирное ничего, но задачка очень простая, для детского сада. Привожу её в правильной формулировке.
Пусть
$a_0=0,$
$a_{2n+1}=-a_n,\quad n\geqslant0,$
$a_{2n}=1-a_n,\quad n\geqslant1.$
Пусть натуральное число $k$ можно записать в виде $k=\sum\limits_{n=0}^Ne_n4^n$, где $e_n\in\{0;\pm1\}$. Докажите, что $a_{3k}=0$.

Темы объединены.

[juna]

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

Мне из недоказанных показалась интересной проблема 46.
И как только такие гипотезы рождаются?
Наверное, она допускает какие-то обобщения.

Хм…
Достаточность условия доказывается тривиально.
Пусть $A(k)$ - минимальный простой множитель числа $k$. Утверждается, что если взять $L=3^n+3*2^n+6$ и посчитать все такие $k$, что $k<L$ и $k>(A(k))^n$, то их будет больше половины от $L$.
Среди $L$ чисел ровно половина имеет минимальный простой множитель 2, ровно третья часть имеет минимальный простой множитель 3.
1. Считаем $k>2^n$, таких среди $L$: $3^n+3*2^n+6-2^n=3^n+2^{n+1}+6$, среди них надо взять половину: $B=\frac{3^n}{2}+2^n+3$.
2. Считаем $k>3^n$, таких среди $L$: $3^n+3*2^n+6-3^n=3*2^n+6$, берем третью часть: $C=2^n+2$.
Легко видеть, что $B+C-\frac{L}{2}=2^{n-1}>0$ Другие простые множители не доставляют таких чисел, т.к. $\forall n>2 (5^n>L)$ ч.т.д. Т.е. нужно доказать необходимость.

[RIP]

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

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

Мне из недоказанных показалась интересной проблема 46.
И как только такие гипотезы рождаются?
Наверное, она допускает какие-то обобщения.

Хм…
Достаточность условия доказывается тривиально.
Пусть $A(k)$ - минимальный простой множитель числа $k$. Утверждается, что если взять $L=3^n+3*2^n+6$ и посчитать все такие $k$, что $k<L$ и $k>(A(k))^n$, то их будет больше половины от $L$.
Среди $L$ чисел ровно половина имеет минимальный простой множитель 2, ровно третья часть имеет минимальный простой множитель 3.
1. Считаем $k>2^n$, таких среди $L$: $3^n+3*2^n+6-2^n=3^n+2^{n+1}+6$, среди них надо взять половину: $B=\frac{3^n}{2}+2^n+3$.
2. Считаем $k>3^n$, таких среди $L$: $3^n+3*2^n+6-3^n=3*2^n+6$, берем третью часть: $C=2^n+2$.
Легко видеть, что $B+C-\frac{L}{2}=2^{n-1}>0$ Другие простые множители не доставляют таких чисел, т.к. $\forall n>2 (5^n>L)$ ч.т.д. Т.е. нужно доказать необходимость.

Это неверное решение. Вы не учли, что числа могут и на $6$ делиться...

[juna]

Вы правы, я ошибся. Нужно оценивать $\frac{B}{3}+C-\frac{L}{2}$. Но тогда не выходит каменный цветок. А поскольку другие простые не доставляют нам указанных чисел, то и гипотеза неверна.

[RIP]

Там вроде в условии $k\leqslant L$ и гипотеза, скорее всего, верна.

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

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

Нужно оценивать $\frac{B}{3}+C-\frac{L}{2}$.

А это с какой радости

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

Более того скажу, гипотеза верна и очень легко проверяется.

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

Вообще, подозреваю, что решено задач больше, чем отражено в ссылке. По-видимому автор просто забил на это дело.

[juna]

Да, не так разделил, нужно $B+C/2-L/2=1$ - верна.

[RIP]

В связи с этой задачкой у меня возник вопрос. Обозначим

$$K_L=\#\{k\leqslant L\mid k>(A(k))^{n}\}$$

Как себя ведет $K_L$ при $L\to\infty$?

[maxal]

RIP писал(а):

Вообще, подозреваю, что решено задач больше, чем отражено в ссылке. По-видимому автор просто забил на это дело.

Не, автор вполне активен. Можете посылать свои решения ему на мыло:
Ralf Stephan <[e-mail]>

[juna]

А вообще мое решение нельзя считать до конца верным, т.к. нужно учитывать округления, когда нацело не делится. Но это слишком тонко.