?

Log in

No account? Create an account

Как заработать $1000 - Общество дровосеков Бердичева по изучению Мишны

Jun. 5th, 2017

10:18 am - Как заработать $1000

Previous Entry Share Next Entry

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

Одну из задач (пятую) недавно решили:

Пусть n - целое положительное число. Запишем его разложение на простые множители обычным образом, например, 60 = 22·3·5, где простые числа записаны в порядке возрастания, а показатель степени 1 не пишется. Опустим показатели степени в строку и удалим знаки умножения, получив число f(n). Повторим.

Таким образом, f(60) = f(22·3·5) = 2235. Далее, т. к. 2235 = 3·5·149, его образ 35149, а т. к. 35149 - простое, его образ - оно само. Следовательно, 60 → 2235 → 35149 → 35149 → ..., мы долезли до простого числа и остановились на нём.

Предполагается, что с любого числа можно долезть до простого, хотя для числа 20 это не было показано. Заметим, что 20 → 225 → 3252 → 223271 → ..., достигая числа из более чем 100 цифр, но всё ещё не простого.


Был найден контрпример:
13532385396179 = 13·532·3853·96179.

Почти по $22.73 за бит.

This entry was originally posted at http://spamsink.dreamwidth.org/1052082.html. Please comment there using OpenID.

Comments:

[User Picture]
From:febb
Date:June 5th, 2017 06:11 pm (UTC)
(Link)
А где его страница с е-маилом и этими задачками? :)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 5th, 2017 06:34 pm (UTC)
(Link)
Чем PDF не устраивает? Там, правда, сказано "If you solve one of these, you can reach him by sending snail mail (only) in care of the Department of Mathematics at Princeton University."


(Reply) (Parent) (Thread)
[User Picture]
From:febb
Date:June 5th, 2017 06:40 pm (UTC)
(Link)
Т.е. бумажной почтой? :)
Ок. ПО-моему решение Problem 3. The Thrackle Problem
очевидно. :)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 5th, 2017 07:01 pm (UTC)
(Link)
Под snail mail принято понимать бумажную почту, да. :)

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


(Reply) (Parent) (Thread)
[User Picture]
From:alexanderr
Date:June 6th, 2017 03:46 am (UTC)
(Link)
я убедился, что контрпример правильный, но все равно немного озадачен, что это работает. 52*52 должно сдвигать на две позиции, т.к. 52 это почти 100. а 2 сдвигает только на одну. однако числа равны. видимо, как-то компенсируется тем, что 13 это почти 10, а сдвигает на две позиции. ну и 3853 это не совсем 10,000
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 6th, 2017 03:59 am (UTC)
(Link)
Работает это так:

13*53*53*3853 = 140700001
1407*96179=135323853

т. е. более или менее понятно, как программировать поиск.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:June 6th, 2017 01:16 pm (UTC)
(Link)
Есть другой вопрос - можно ли найти число, для которого эта последовательность неограничена? Ну, вот то же 20, например...
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 6th, 2017 03:43 pm (UTC)
(Link)
Чтобы его "найти", потребуется или бесконечное время, или надо доказать, что она неограничена для данного конкретного числа (например, образуется регулярный узор из цифр, который через несколько шагов повторяется в увеличенном виде; что маловероятно).
Проще :) будет доказать, что такие числа в принципе существвуют, но, как говорил Эрдёш, "Mathematics may not be ready for such problems." Пусть лучше сначала Collatz conjecture решат.
(Reply) (Parent) (Thread)
[User Picture]
From:jazator
Date:June 22nd, 2017 03:49 am (UTC)
(Link)
Это может быть из разряда "проблема 196".
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 22nd, 2017 03:52 am (UTC)
(Link)
Конечно.
(Reply) (Parent) (Thread)