unsigned long int128 (jerom) wrote,
unsigned long int128
jerom

Category:

Мега-червяк

Программист-математик подкинул еще задачку похожую на червяка месячной давности, решения я еще не знаю:

Сформулирую сначала частный случай (в оригинале задача не совсем про червяка):

Червяк сидит в 10 см от финиша. Начинаем с k=2. На каждом шаге делаем: номером k происходит вот что:

1. червяк проползает 1 см к началу, ему остаётся X см
2. мы раскладываем X на сумму степеней числа k с минимальным числом слагаемых, степени тоже раскладываем аналогичным образом, пока не остануться в записи только числа k и 0. После чего заменяем в этой записи k на k+1, вычисляем новую сумму и отодвигаем червяка на это расстояние
3. k = k+1

Вопрос: доползёт ли червяк до финиша, мы его будем отодвигать всё дальше и дальше в бесконечность или он стабилизируется на каком-то расстоянии?

Несколько разложений:
1 по двойкам 20
3 по двойкам 220+20
18 по тройкам 330+30+330+30


Расстояние 10, k = 2.


Шаг 1:
X = 10 - 1 = 9

9 = 2220+20+20, 2 меняем на 3, 3330+30+30 = 82

k = 2 + 1 = 3


Шаг 2:
X = 82 - 1 = 81

81 = 3330+30, 3 меняем на 4,
4440+40 = 1024

k = 4


Шаг 3:
X = 1024 - 1 = 1023

1023 =
44+44+44+440+40+40+440+40+40+440+40+40+440+40+440+40+440+40+440+440+440+40+40+40,
4 меняем на 5,
55+55+55+550+50+50+550+50+50+550+50+50+550+50+550+50+550+50+550+550+550+50+50+50 = 9843

k = 5


Шаг 4:
X = 9843 - 1 = 9842

9842 = (я пропускаю разложение), 5 меняем на 6, получаем 140744

k = 6


Шаг 5:
X = 140744 - 1 = 140743




Итого в середине 5го шага мы на расстоянии 140743 см от финиша…

Каков же ответ?

update: хм, похоже, просто "доказать" сходимость не так сложно. Математически точного доказательства я не осилил, а идею завтра обкатаю на коллегах. Вот с предсказанием количества шагов ничего придумать не могу и не уверен, что можно вывести функцию.

update: ага, теорему Гудстайна мне сунули
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments