2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача про число на компьютере
Сообщение19.03.2022, 11:11 


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

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение19.03.2022, 11:38 
Заслуженный участник
Аватара пользователя


23/08/07
5487
Нов-ск
rightways в сообщении #1550715 писал(а):
На экране компьютера горит натуральное число, большее 1 000 000.
Я перепробовал все такие натуральные числа. Всегда оставалась единица. Или вычитал неправильно?

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение19.03.2022, 11:53 


02/04/18
240
Так не "останется", а "будет" же.

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение19.03.2022, 11:59 


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

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

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

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

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение19.03.2022, 13:07 
Заслуженный участник


20/12/10
9055
rightways в сообщении #1550718 писал(а):
но кажется где то есть ошибка
Не вижу. Но надо бы оформить поаккуратней.

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение22.03.2022, 10:18 


02/04/18
240
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 такая последовательность уже есть?

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение22.03.2022, 15:43 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение25.03.2022, 17:47 
Аватара пользователя


06/04/21
138
TOTAL в сообщении #1550716 писал(а):
rightways в сообщении #1550715 писал(а):
На экране компьютера горит натуральное число, большее 1 000 000.
Я перепробовал все такие натуральные числа. Всегда оставалась единица. Или вычитал неправильно?

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

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение25.03.2022, 18:06 


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

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение26.03.2022, 16:49 
Аватара пользователя


07/01/16
1607
Аязьма
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 в браузере...)

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение27.03.2022, 05:09 
Аватара пользователя


07/01/16
1607
Аязьма
Не поленился поставить 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$

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение28.03.2022, 11:12 
Аватара пользователя


07/01/16
1607
Аязьма
Последние два диапазона без сюрпризов, на чем пожалуй и хватит баловаться:
$$\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}$$

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение30.03.2022, 12:15 


02/04/18
240
waxtep в сообщении #1551226 писал(а):
хватит баловаться

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

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение30.03.2022, 14:36 
Аватара пользователя


07/01/16
1607
Аязьма
Dendr в сообщении #1551416 писал(а):
среди простых, меньших $2^8$ 19 "самопорождаемых" (никакое составное к ним не приводит).
Интересно, конечно ли их множество? Доля простых по мере приближения к концу натурального ряда роста величины рассматриваемых чисел все падает же. А если бесконечно, можно надеяться обнаружить какую-то структуру, наверное, не поленюсь клавиши понажимать

 Профиль  
                  
 
 Re: Задача про число на компьютере
Сообщение30.03.2022, 20:44 
Аватара пользователя


07/01/16
1607
Аязьма
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]

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group