две 1000-долларовые задачи от Рона Грэхема

[maxal]

Сегодня общался с Роном Грэхемом (один из авторов "Конкретной Математики"), он предложил по $1000 за решение каждой из следующих задачек:

1) Доказать, что найдется бесконечно много натуральных чисел $m$ таких, что

$$\mathop{\text{НОД}}({2m\choose m}, 3\cdot 5\cdot 7) = 1.$$

2) Доказать, что найдется лишь конечное количество натуральных чисел $m$ таких, что

$$\mathop{\text{НОД}}({2m\choose m}, 3\cdot 5\cdot 7\cdot 11) = 1.$$

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

Замечание 1. Биномиальный коэффициент ${2m\choose m}$ не делится на простое число $p$ тогда и только тогда, когда все цифры в $p$-ичном представлении $m$ не превосходят $\frac{p}{2}.$

Замечание 2. Может оказаться полезной эта статья: On the Prime Factor of ${2n \choose n}$, Math. Comp. 29 (1975), 83-92.

[juna]

1) Немного переиначим. Нужно найти бесконечно много $m$, что
$\sum\limits_{i=1}^{\infty}{\lfloor \frac{2m}{p^i}} \rfloor-2\sum\limits_{i=1}^{\infty}{\lfloor \frac{m}{p^i}} \rfloor=0$ одновременно для $p=3,5,7$.
Отдельно рассмотрим это выражение для $p=3,5,7$.
$p=3$, тогда это выражение выполняется, если $m=3^k$ или $m=3^k+1$ (не все, но только очевидные случаи)
$p=5$, тогда это выражение выполняется, если $m=5^k$ или $m=5^k+1$ или $m=5^k+2$ (не все, но только очевидные случаи)
$p=7$, тогда это выражение выполняется, если $m=7^k$ или $m=7^k+1$ или $m=7^k+2$ или $m=7^k+3$ (не все, но только очевидные случаи).
Можно посмотреть при каких $k$ это будет выполняться одновременно, например, $m=1,10$ - выполняется.
Это, конечно, не решение, а мысли вслух.
Добавлено
Очевидные случаи не помогают, т.к. уравнения типа $A^x-B^y=C$ имеют, как правило, конечное число решений.

[Руст]

С точки зрения вероятностных соображений утверждения справедливы. Думаю, что авторы воспользовались именно этими соображениями. Встречал я эти задачи вссвязи с числами Каталана. Кажется даже здесь обсуждали.
Вероятностные соображения следующие. Количество чисел меньше большого числа N имеет все цифры в p -ичном исчислении меньше p/2 с вероятностью $(\frac{p+1}{2p})^{N_p}, \ N_p=\frac{log(N)}{log p}$. Поэтому, по вероятностным соображениям найдётся бесконечно много натуральных чисел n, что все цифры меньше p/2 для всех нечётных p из некоторого множества тогда и только тогда, когда $\sum_p\frac{\ln(2p)-\ln(p+1)}{\ln(p)}<1$. Всё это верно для множества из p=3,5,7 (сумма равна 0.974...) и для множества p=3,5,7,11 сумма превосходит 1 (примерно 1.2268...).

[juna]

Расчеты показывают, что для п.1 из двух миллионов имеем только такие решения:
1
10
756
757
3160
3186
3187
3250
7560
7561
7651
20007

[Руст]

По вероятностным соображениям n -ое такое число порядка n в степени 38 (0,974/(1-0.974)). Так, что в дальнейшем их должно встретится реже. Вначале, когда количество цифр мало, это немного нарушается и встречается несколько чаще.

[juna]

Мне кажется, что найти бесконечность можно уже среди чисел специального вида - $m=2^{k_1}\cdot 3^{k_2} \cdot 5^{k_3} \cdot 7^{k_4}$.

[Батороев]

Допустим, что число m в 3-чной системе счисления (СС) имеет вид:
$ A = ...a_6 a_5 a_4 a_3 a_2 a_1 a_0 $,
где
$ a_0 = 1$
$ a_1,a_2,a_3,a_4,a_5,a_6,... < 2 $

Мне кажется, что решение этих задач "кроется" в следующих системах неравенств:

$ (a_0*1 + a_1*3 + a_2*4 + a_3*2 + a_4*1 + a_5*3 + a_6*4 + ... )\equiv (< 3)(mod 5) $ (1)
$ (a_0*1 + a_1*3 + a_2*2 + a_3*6 + a_4*4 + a_5*5 + a_1*1 + ...) \equiv (< 4)(mod 7) $


$ (a_0*1 + a_1*3 + a_2*4 + a_3*2 + a_4*1 + a_5*3 + a_6*4 + ... ) \equiv (< 3)(mod 5) $ (2)
$ (a_0*1 + a_1*3 + a_2*2 + a_3*6 + a_4*4 + a_5*5 + a_6*1 +.... ) \equiv (< 4)(mod 7) $
$ (a_0*1 + a_1*3 + a_2*9 + a_3*5 + a_4*4 + a_5*1 + a_6*3 +...) \equiv (< 5)(mod 11)$

Суть по-видимому, в том, что система неравенств (1) выполняется бесконечно, а система неравенств (2) имеет ограничение по величине числа m.

[Батороев]

Допустим, что число m в 1155-чной системе счисления (СС) имеет вид:
$ A = ...a_6 a_5 a_4 a_3 a_2 a_1 a_0 $,
где $ a_0 $ не кратно 3, 5, 7,11

Тогда для 2-й задачи можно записать:

$ (a_0*1 + a_1*0 + a_2*0 + a_3*0 + a_4*0 + a_5*0 + a_6*0 + ... )\equiv (< 2)(mod 3) $ (2)
$ (a_0*1 + a_1*0 + a_2*0 + a_3*0 + a_4*0 + a_5*0 + a_6*0 + ... )\equiv (< 3)(mod 5) $
$ (a_0*1 + a_1*0 + a_2*0 + a_3*0 + a_4*0 + a_5*0 + a_6*0 + ... )\equiv (< 4)(mod 7) $
$ (a_0*1 + a_1*0 + a_2*0 + a_3*0 + a_4*0 + a_5*0 + a_6*0 +...)\equiv (< 5)(mod 11)$

Хотя эти условия и не достаточные, но возникает мысль о том, что может быть, достаточно проверить, имеет ли 2-я задача решение в пределах $ 1< m < 1155 $?

[maxal]

juna в сообщении #54025 писал(а):

Расчеты показывают, что для п.1 из двух миллионов имеем только такие решения:

см. последовательность A030979

[RIP]

Здесь вроде как утверждается, что первая задача решена. Сам пока не смотрел.
Стиль изложения у автора какой-то совершенно отвратительный: много мусора, и невнятно местами.

[Руст]

RIP в сообщении #364298 писал(а):

Здесь вроде как утверждается, что первая задача решена. Сам пока не смотрел.
Стиль изложения у автора какой-то совершенно отвратительный: много мусора, и невнятно местами.

Бегло просмотрел. Там еще ссылки на предыдущие результаты. В принципе идея доказательства этой задачи понятная. Однако, эти методы не могут быть применены к другой задаче. Т.е. такими методами не удастся доказать конечность $(p_i,\frac{p_i-1}{2})$ good чисел для всех i, когда $\sum_i \frac{log (2p_i) -log (p_i+1)}{log p_i} >1.$

[maxal]

RIP в сообщении #364298 писал(а):

Здесь вроде как утверждается, что первая задача решена. Сам пока не смотрел.

Тот же автор в другом препринте доказывает гипотезу Биля: http://arxiv.org/abs/1007.5122
Как-то подозрительно всё это...