Ментальный генератор случайных чисел, разработанный известным математиком Джорджем Марсалья, представляет собой интересный пример простой и одновременно загадочной системы. Несмотря на свою кажущуюся простоту, этот генератор порождает длинные циклы чисел и демонстрирует поведение, заслуживающее отдельного внимания и анализа. В основе работы генератора лежит операция с двумя цифрами числа - десятками и единицами, что позволяет создать механизм, который многие не сразу способны понять в деталях. Марсалья предложил использовать двухзначное число в качестве начального состояния (состояния-зёрна), после чего каждую следующую итерацию новая цифра состояния формировалась по правилу: заменить число n суммой десятков числа n и произведения единиц числа n на 6. После каждого шага на выходе появляется лишь последняя цифра нового состояния, что формирует последовательность, похожую на случайную, но на самом деле подчинённую строгим закономерностям.
Главный недостаток данного генератора - невозможность его названия настоящим генератором случайных чисел по современным стандартам, применяемым в программировании и криптографии. Тем не менее, этот подход рекомендуют в некоторых случаях для работы "в уме", когда отсутствует доступ к полноценной вычислительной технике. Важной особенностью данного генератора являются циклы, в которые он входит при определённых начальных значениях. Если начать, к примеру, с числа 1, то с каждым шагом последовательность проходит через все числа от 1 до 58, в итоге замыкаясь в циклическую повторяющуюся цепочку. Таким образом, каждое число от 1 до 58 - это элемент большого цикла, на который попадает генератор при старте с любого из этих чисел.
Пример такого цикла может выглядеть как последовательность: 1, 6, 36, 39 и далее со возвращением к 1. Такой длинный цикл - редкость для простых арифметических операций и показывает мощь простейших генераторов случайных чисел. В то же время существуют неподвижные состояния, которые при соответствии определённым условиям не меняются с шагами генератора. Примером такого особого состояния является число 59. При начале последовательности со значения 59 генератор не покидает это состояние - при каждом шаге результат снова будет 59, то есть генератор "застревает" в одной точке.
Аналогично, старт с нуля остаётся на нуле. Такие точки в теории динамических систем называют неподвижными или фиксационными точками. Это означает, что из других состояний генератор не попадает в состояние 59, и обратно - оно недостижимо от других чисел. Если же стартовать с числа, превышающего 59, например с 99, после нескольких шагов генератор перейдёт в ранее описанный большой цикл чисел от 1 до 58. При 99 следующий шаг будет 63, за ним последует 24, и только после этого последовательность попадёт в цикл.
Для большинства чисел между 60 и 98 генератор переходит в цикл всего за один шаг. Это поведение напоминает классическую задачу теории чисел - гипотезу Коллатца, где для любого положительного целого числа при последовательном применении простых правил (если нечётное - умножить на три и прибавить один, если чётное - разделить на два) вычисления со временем должны привести к числу один. Несмотря на кажущуюся простоту, гипотеза Коллатца остаётся нерешённой и привлекает внимание математиков уже несколько десятилетий. В данном генераторе доказано, что для любого стартового значения последовательность либо остаётся в неподвижной точке, либо попадает в один из циклов. Таким образом, процесс всегда заканчивается в цикле, что обеспечивает предсказуемость генератора при длительном использовании.
При работе со штатным диапазоном двухзначных начальных состояний всё поведение сводится к описанным циклам или фиксированным точкам. При использовании чисел больше 99, например 1066, процесс постепенно уменьшает порядок числа - каждый шаг алгоритма снижает количество цифр, и в итоге состояние попадает в диапазон чисел от 1 до 99. После этого генератор ведёт себя традиционно - либо зацикливается, либо останавливается в неподвижной точке, обычно 59. Такой механизм самопроизвольно нормализует исходное состояние к области, где свойства алгоритма хорошо понятны. Также стоит отметить несколько трёхзначных чисел, которые неизбежно приводят генератор к неподвижной точке 59.
К их числу относят 118, 177, 236 и несколько других величин, где через указанные операции переход происходит в "ловушку" состояния 59. Специалисты, тестировавшие полный диапазон стартовых значений от 0 до 99, отметили, что практически любой допустимый стартовый параметр даёт генератор, имеющий относительно ровное распределение выходных цифр, за исключением цифр 0 и 9, которые используются реже. Это говорит о том, что генератор обладает некоторой устойчивостью к предвзятости на ранних этапах, что является преимуществом для простых задач и интуитивного понимания случайности. Несмотря на свою ограниченность, ментальный генератор чисел Марсалья демонстрирует, насколько глубокими и замысловато взаимосвязанными могут быть даже элементарные арифметические процессы. Он влияет на развитие понимания алгоритмов псевдослучайности и послужил оправданием идеи, что в уме можно быстро и эффективно получать последовательности, пригодные для некоторых практических целей.
Изучение циклов и неподвижных точек помогает лучше разобраться в природе генераторов случайных чисел и представляет интерес для математиков и программистов, занимающихся теорией чисел и криптографией. Кроме того, связь с гипотезой Коллатца подчёркивает роль таких простых систем в исследовании сложных и по-прежнему нерешённых задач современной математики. В заключение, генератор представляет собой замечательный пример наглядного взаимодействия арифметики и теории динамических систем - каждый, кто интересуется и хочет лучше понять случайность и цикличность, найдёт в нём много полезных свойств. Отслеживание его циклов и уникальных состояний открывает путь к новым идеям и теоретическим находкам в области случайности и алгоритмического предсказания. .
