Задача про число на компьютере

[rightways]

На экране компьютера горит натуральное число, большее 1 000 000. Каждую минуту из числа на экране вычитается количество его натуральных делителей, отличных от самого числа (например, из числа 28 вычитается 5). Докажите, что рано или поздно на экране будет нечётное простое число.

[TOTAL]

rightways в сообщении #1550715 писал(а):

На экране компьютера горит натуральное число, большее 1 000 000.

Я перепробовал все такие натуральные числа. Всегда оставалась единица. Или вычитал неправильно?

[Dendr]

Так не "останется", а "будет" же.

[rightways]

Можете проверить вот такое решение, оно вроде правильное но кажется где то есть ошибка:

По индукции проверяем базу, начинаем с маленького числа , например 6.
Переход: Пусть для чисел 6, 7, 8, ..., N-1 утверждение верно. Докажем для N.

Так как N>6, то у него есть хотя бы один собственный делитель. Тогда следующее число будет N-m<N. Остается доказать, что N-m>6. что верно для достаточно больших N. (например 12).

Не кажется ли данное решение слишком простым?

[nnosipov]

rightways в сообщении #1550718 писал(а):

но кажется где то есть ошибка

Не вижу. Но надо бы оформить поаккуратней.

[Dendr]

nnosipov в сообщении #1550723 писал(а):

Но надо бы оформить поаккуратней.

У числа $N=n^2$ есть делители, не имеющие пары: 1, $n$, все остальные делители - парные: $\{q, N/q\}$, где $2\le q\le n-1$. То есть, у $N$ самое большее $2+2(n-2)=2n-2$ делителя. (здесь и далее говоря "делитель", я подразумеваю, делитель, меньший $N$). На самом деле, равенство достигается только для $N=4$, в общем случае делителей гораздо меньше.
Во всяком случае, получаем $N-m\ge n^2-2n+2$. При $n\ge4$ это выражение не меньше 6, для $n=3$ можем убедиться, посчитав явно.

Если $N=n^2+\Delta, 0<\Delta<2n+1$, то непарный делитель только единица, а пары собираются из $2\le q\le 2$. В общем, тут $m\le2n-1$.
И тогда $N-m\ge n^2+\Delta-2n+1>(n-1)^2$, и правая часть превысит 6 опять же при $n\ge4$.

Таким образом, при $N\ge16$ мы можем гарантировать, что $N-m>6$. Ну и поскольку единица - всегда делитель, то $m\ge1$ и число на экране всегда уменьшается (уже независимо от $N$ - проблемы возникнут только при $N=1$, но это тривиальный случай).
Если в какой-то момент встретится простое, то все, мы победили. Если нет, то пока оно больше 15, беспокоиться не о чем, продолжаем такой обратный отсчет.
Допустим, на экране показалось составное число, меньшее 16. Из вышесказанного следует, что это число из набора $\{8, 9, 10, 12, 14, 15\}$. Их можно перебрать "руками" и получить, что нечетное простое в самом деле получается:
$8\to5$
$9\to7$
$10\to7$
$12\to7$
$14\to11$
$15\to12\to7$

P.S. На самом деле, что любопытно - их этого списка видно, что на экране должно появиться не вообще нечетное простое, а простое, больше 3. Вообще, если ретроспективно посмотреть на соотношения выше, то возникают сомнения, что числа, большие миллиона таким образом спустятся хотя бы до трехзначных простых... Надо бы программку составить. А может и в OEIS такая последовательность уже есть?

[waxtep]

Dendr в сообщении #1550906 писал(а):

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

У меня возникло аналогичное ощущение, что сильно дальше $N-\sqrt N$ и не уедем; и похоже даже не корень: например, числа в диапазоне $2^{30}\pm2^{16}$ могут "спуститься" на $2^{11}$ (например, $1073688000\rightarrow1073685887$), а вот на $2^{12}$ уже нет (рекордсмен в этом диапазоне $1073729318\rightarrow1073726287$ с дельтой в $3031$). Конечно, наблюдения в отдельных точках не показательны

[tonven]

TOTAL в сообщении #1550716 писал(а):

rightways в сообщении #1550715 писал(а):

На экране компьютера горит натуральное число, большее 1 000 000.

Я перепробовал все такие натуральные числа. Всегда оставалась единица. Или вычитал неправильно?

Неправильно автор употребил свойство "все".
На экране компьютера может загореться столько чисел, > 1 000 000, что их не переберут компьютеры всей Галактики.

[Sender]

Это ограничение легко обойти, осуществляя перебор в уме.

[waxtep]

waxtep в сообщении #1550917 писал(а):

У меня возникло аналогичное ощущение, что сильно дальше $N-\sqrt N$ и не уедем; и похоже даже не корень:

Скорее похоже на $N-k\ln^3N$: смотрел максимальные дельты в каждом из (перекрывающихся) диапазонов $2^n\pm2^{n-1},6\leqslant n\leqslant23$; эти максимумы даже не монотонны, если же точки немонотонности исключить, оставшиеся максимальные дельты похожи на $k\ln^3N$ с $k\approx0,6$; для больших $N$ у меня уже не хватает мощи (использую PARI/GP в браузере...)

[waxtep]

Не поленился поставить PARI/GP на древний ноутбук и догнать вычисления до $2^{28}$. Наверное, еще один-два интервала, и я всё: уже этот интервал считался около 5 часов при 25%-ной загрузке процессора, рост времени расчета примерно линейный, т.е. ожидается около 10 и 20 часов соответственно.

(результаты и пояснения)

$$\begin{tabular}{l|llll} m & N & \Delta & \ln^3N & \Delta/\ln^3N \\ \hline 6 & 51 & 28 & 61 & 0,46 \\ 7 & 144 & 65 & 123 & 0,53 \\ 8 & 253 & 90 & 169 & 0,53 \\ 9 & 660 & 157 & 274 & 0,57 \\ 10 & 660 & 157 & 274 & 0,57 \\ 11 & 2 112 & 301 & 449 & 0,67 \\ 12 & 4 370 & 367 & 589 & 0,62 \\ 13 & 10 758 & 547 & 800 & 0,68 \\ 14 & 10 758 & 547 & 800 & 0,68 \\ 15 & 42 352 & 705 & 1209 & 0,58 \\ 16 & 76 290 & 887 & 1421 & 0,62 \\ 17 & 185 375 & 1494 & 1785 & 0,84 \\ 18 & 185 375 & 1494 & 1785 & 0,84 \\ 19 & 487 872 & 1175 & 2247 & 0,52 \\ 20 & 1 550 867 & 1780 & 2896 & 0,61 \\ 21 & 1 600 218 & 2357 & 2915 & 0,81 \\ 22 & 3 890 432 & 2419 & 3494 & 0,69 \\ 23 & 12 546 819 & 2662 & 4367 & 0,61 \\ 24 & 22 707 852 & 3395 & 4860 & 0,70 \\ 25 & 41 672 646 & 3775 & 5401 & 0,70 \\ 26 & 51 501 850 & 4847 & 5599 & 0,87 \\ 27 & 125 307 360 & 4549 & 6483 & 0,70 \\ 28 & 360 212 028 & 4991 & 7648 & 0,65 \end{tabular}$$

• $m$ - ведется расчет "финального" простого числа $p(n)$ для всех $n:2^m-2^{m-1}\leqslant n\leqslant2^m+2^{m-1}$
• $\Delta, N$ - максимальное на данном промежутке значение $n-p(n)$ и наименьшее $n$, при котором оно достигается
• две последние колонки - округленные значения $\ln^3N$ и $\Delta/\ln^3N$

По мнению экселя, зависимость $\Delta$ от $\ln^3N$ (по точкам из таблицы) похожа на прямую $y=0,7069x-23,73$ с $R^2=0,9726$; при этом, не сказать, что $\Delta$ ведет себя монотонно и не скачет:

Нестрогие рукомахательные соображения в пользу $\Delta\sim\ln^3N$:

• типичное число делителей $\tau(N)\sim\ln N$ (формула Дирихле)
• интервал между соседними простыми $g(N)\sim\ln^2N$ (гипотеза Крамера)
• "из соображений размерности", двигаясь (в среднем) шажками $\tau(N)$ сквозь частокол простых, расставленных через $g(N)$, мы наткнемся на простое на расстоянии $\Delta(N)\sim\tau(N)\cdot g(N)\sim\ln^3N$

[waxtep]

Последние два диапазона без сюрпризов, на чем пожалуй и хватит баловаться:

$$\begin{tabular}{l|llll} m & N & \Delta & \ln^3N & \Delta/\ln^3N \\ \hline 29 & 721 906 968 & 6001 & 8486 & 0,71 \\ 30 & 1 415 774 016 & 7193 & 9355 & 0,77 \end{tabular}$$

[Dendr]

waxtep в сообщении #1551226 писал(а):

хватит баловаться

Смеха ради можно задаться вопросом - а какие простые числа порождаются данной процедурой? И сколько может быть прародителей у каждого?
Проверив вручную числа вплоть до 300, выяснил, что среди простых, меньших $2^8$ 19 "самопорождаемых" (никакое составное к ним не приводит). А больше всего прародителей у 163 - их 28, собранных в 8 сходящихся цепочек.
Следующий кандидат, как будто 271, но ни проверять дальше, ни кодить сбор статистики особо желания нет. Поскольку это все равно курьез, системы здесь никакой не обнаруживается. Хотя Нилу Слоану наверняка понравится.

[waxtep]

Dendr в сообщении #1551416 писал(а):

среди простых, меньших $2^8$ 19 "самопорождаемых" (никакое составное к ним не приводит).

Интересно, конечно ли их множество? Доля простых по мере приближения к концу натурального ряда роста величины рассматриваемых чисел все падает же. А если бесконечно, можно надеяться обнаружить какую-то структуру, наверное, не поленюсь клавиши понажимать

[waxtep]

waxtep в сообщении #1551419 писал(а):

Dendr в сообщении #1551416 писал(а):

среди простых, меньших $2^8$ 19 "самопорождаемых" (никакое составное к ним не приводит).

Интересно, конечно ли их множество? Доля простых по мере приближения к концу натурального ряда роста величины рассматриваемых чисел все падает же. А если бесконечно, можно надеяться обнаружить какую-то структуру, наверное, не поленюсь клавиши понажимать

Похоже, "самопорождаемых" простых довольно много, на числах до 20 миллионов каждое третье такое:

\\numd1.gp
sm(n)={if(n<2, return(0)); while(1-isprime(n), n=n-numdiv(n)+1); return(n)};
sm5(s,f)={p0=primes([1,f]); pp=Set(vector(f-s+1,k,if((g=sm(s+k-1))<s+k-1,g,0))); sgp=setminus(p0,pp); return([matsize(p0)[2],matsize(sgp)[2]])};

parisizemax = 1024000000, primelimit = 20000000
(20:09) gp > \r numd1.gp
(20:09) gp > sm5(1,20000000)
  *** primes: Warning: increasing stack size to 64000000.
  *** vector: Warning: increasing stack size to 128000000.
  *** vector: Warning: increasing stack size to 256000000.
  *** numdiv: Warning: increasing stack size to 512000000.
  *** numdiv: Warning: increasing stack size to 1024000000.
%3 = [1270607, 423743]