Операции с натуральными числами

[Ktina]

С натуральным числом разрешается проводить следующую операцию: прибавлять натуральное число, взаимно простое с ним.

Найти наименьшее натуральное $n>1$, для которого найдётся такое натуральное $k$, из которого нельзя получить $k+n$ ровно за две такие операции. Или доказать, что такого $n$ нет.

[Anton_Peplov]

Напомните: единица считается взаимно простой с чем-либо? Или у нее как всегда особый статус?

[grizzly]

Считается взаимно простой с любым числом.

[ИСН]

Ktina, если так махать мыслью в произвольном направлении, можно попасть в открытую проблему и сломать ум. Ладно себе, а если ещё кому? Доказывал, доказывал невозможность...
Наименьший пример, который мне попался - $n=2184,k=16$.

[Cash]

Наоборот только.
$n=16, k=2184$

(что-то типа решения)

Из невозможности $k+1+(n-1)$ и $k+(n-1)+1$
следует, что $n-1$ имеет в своем разложении, как минимум, 2 различных простых множителя.
$n=7, 11, 13, 16 \dots$

Если спросонья ничего не напутал, то
1. $n=7$
а) $k \equiv 0 \pmod 2$
$k+1+6 \to k \equiv -1 \pmod 3$
$k+3+4$ - увы
б) $k \equiv 1 \pmod 2$
$k+6+1 \to k \equiv 0 \pmod 3$
$k+4+3$ - ...

2.$n=11$
а) $k \equiv 0 \pmod 2$
$k+1+10 \to k \equiv -1 \pmod 5$
$k+3+8 \to k \equiv 0 \pmod3$
$k+5+6$ - ...
б) $k \equiv 1 \pmod 2$
$k+10+1 \to k \equiv 0 \pmod 5$
$k+6+5 \to k \equiv 0 \pmod3 $
$k+8+3$ - ...

3. $n=13$
а) $k \equiv 0 \pmod 2$
$k+1+12 \to k \equiv -1 \pmod 3$
$k+9+4$ - ...
б) $k \equiv 1 \pmod 2$
$k+12+1 \to k \equiv 0 \pmod 3$
$k+4+9$- ...

4. $n=16$
$k+15+1$
а) $k\equiv 0 \pmod3$
$k+7+9 \to k \equiv 0 \pmod 7$
$k+2+14 \to k \equiv 0 \pmod 2$
$k+1+15 \to k \equiv 4 \pmod 5$
$k+13+3 \to k \equiv 0 \pmod{13}$
$k+5+11 \to k \equiv 6 \pmod {11}$
Решение: $k \equiv 2184 \pmod {30030}$

б) $k\equiv 0 \pmod5$
$k+1+15 \to k \equiv 2 \pmod 3$
$k+6+10 \to k \equiv 0 \pmod 2$
$k+11+5 \to k \equiv 0 \pmod {11}$
$k+13+3 \to k \equiv 0 \pmod{13}$
$k+9+7, \to k\equiv 5 \pmod 7$
Решение: $k \equiv 18590 \pmod {30030}$

Интересно, есть ли такие $n=2p+1$, $p$ - простое?

[VAL]

A059756 .

[grizzly]

Cash в сообщении #1062880 писал(а):

$n-1$ имеет в своем разложении, как минимум, 2 различных простых множителя.
$n=7, 11, 13, 16 \dots$

Учёт (пропущенного?) $n=15$ немного удлиняет решение.

[Cash]

(to grizzly)

grizzly в сообщении #1062917 писал(а):

Учёт (пропущенного?) $n=15$ немного удлиняет решение.

Это, наверное, подсознательно побыстрее избавиться хотел

В A059756 нет нечетных чисел. Можно ли как-то элементарно это доказать?

[grizzly]

Cash в сообщении #1063010 писал(а):

В последовательности нет нечетных чисел. Можно ли как-то элементарно это доказать?

Здесь сказано, что нечётных чисел в этой последовательности бесконечно много.

Надеюсь, что я правильно интерпретирую все связи между понятиями и сами понятия, но лучше бы кто-то глянул независимо. Если так, то судя по другим результатам (более свежим) в этой последовательности есть все натуральные числа от 16.

maxal мог бы с ходу точно подтвердить.

[VAL]

grizzly в сообщении #1063036 писал(а):

Cash в сообщении #1063010 писал(а):

В последовательности нет нечетных чисел. Можно ли как-то элементарно это доказать?

Здесь сказано, что нечётных чисел в этой последовательности бесконечно много.

Надеюсь, что я правильно интерпретирую все связи между понятиями и сами понятия, но лучше бы кто-то глянул независимо.

Я понял из той же самой аннотации прямо противоположное
(То, что авторы называют свойством (A), означает отсутствие в A059756.)

Цитата:

Если так, то судя по другим результатам (более свежим) в этой последовательности есть все натуральные числа от 16.

Это совсем странное предположение
Для каждого конкретного $n$ легко проверяется его принадлежность к A059756.
Так что, начало последовательности в OEIS идет без пропусков.

Я немного рассматривал числа Эрдёша-Вудса несколько лет назад. У меня есть смутное ощущение, что отсутствие среди них четных как-то удавалось доказать. Впрочем, я не уверен

[grizzly]

VAL в сообщении #1063064 писал(а):

Я понял из той же самой аннотации прямо противоположное

Вы правы, конечно. Спасибо! Зарапортовался я между "удовлетворяет свойству (A)" и "является контрпримером".

(Оффтоп)

Пожалуй, применю к себе автобан в мат.разделах на пару дней по совокупности оплошностей :)