Я хочу сыграть с вами в одну игру...
(с) Дж. Конвей, про игру "Жизнь"
Я знаю, что пикабу - это место, куда ходят разлагаться, а не вот это вот всё. Но в этот раз хочу разложиться, так сказать, со всей айтишной пролетарской яростью! А то мотоциклистам, вишь, можно разложиться на дороге на радость публике, а мы, ботаны, чем хуже?
Итак, представьте себе следующую работёнку для калькулятора.
Вы пишете список положительных дробей: например, 6655 / 1372, 1715 / 5324, 55 / 686 и т.п.
Берёте некоторое натуральное число, и начинаете играть. Находите в списке первую дробь, такую, что при умножении на ваше число получается не дробное, а натуральное.
Берёте результат умножения, снова находите дробь, произведение с которой даёт натуральное.
И так далее, пока не выяснится, что ни одна дробь не подходит.
Смотрите на последний результат и ищете в нём глубинный смысл.
Эта забава - не просто забава, а внезапно, запуск программы на языке фрактран. От английского fraction trans...что-нибудь. По-русски - дробедробилка.
И его тоже прудумал Джон Конвей.
Удивительное дело, но фрактран - тьюринг-полный язык, то есть, на нём можно запрограммировать что угодно, и вы даже не докажете, что эта программа зациклится либо остановится!
И это не просто "фиг знает что понавыдумывали", а имеет под собой твёрдую теоретическую базу: это реализация абстрактной машины Минского.
Про фрактран есть статьи на википедии, энциклопедии эзотерических языков (там, кстати, совершенно безумный интерпретатор фрактрана на языке J, - помехи в телетайпе), на хабре.
Я полтора года ходил вокруг фрактрана, как хатуль мадан вокруг сметанного дерева, и тоже родил статью на хабре. Это демонстрация задачи "измерить длину последовательности Коллаца - она же 3x+1 - до зацикливания"
Статья, конечно, TL;DR - но я же предупреждаю, что мы, задротские панки и панковские задроты, знаем толк в расшибании башки. Пожалею пикабушников-мимокрокодилов и не стану тащить её сюда.
Минимальная программа у меня получилась из 16 дробей, более-менее эффективная - из 68.
6655 / 1372
1715 / 5324
55 / 686
35 / 2662
605 / 343
245 / 1331
242 / 245
98 / 605
3 / 49
3 / 121
704 / 35
448 / 55
48 / 7
48 / 11
1331 / 4
3 / 2
(а вот как я её нашёл, - это уже в статье!)
Если начать с числа 2^x, то, когда программа остановится, мы получим число 3^n, где n - длина последовательности до достижения элемента 1.
Например, для x = 3, n = 8.
Действительно, последовательность выглядит так:
x1 = 3, нечётное
x2 = x1 * 3 + 1 = 10, чётное
x3 = x2 / 2 = 5, нечётное
x4 = x3 * 3 + 1 = 16, чётное
x5 = x4 / 2 = 8, чётное
x6 = x5 / 2 = 4, чётное
x7 = x6 / 2 = 2, чётное
x8 = x7 / 2 = 1, стоп.
Попробуйте взять 2^3 = 8, и убедиться, что на выходе получите 3^8 = 6561.
В общем, оказывается, программировать на фрактране не так уж сложно. За ширмой тяжеловесной арифметики прячется простая логическая структура. Любой школьник в программическом кружке её освоит, это почти как бейсик.
Так что, если кто тут увлекается программированием или преподаёт его, - развлекайтесь и развлекайте.