Приветствую всех, сегодня я хочу рассказать про одну из самых интересных неразгаданных загадок математики. Гипотеза Коллатца, или же дилемма 3n+1 прославилась благодаря простоте своей формулировки, при этом оставаясь не доказанной уже более 90 лет.
Краткая формулировка, то бишь немного измененная выдержка из википедии (en и ру):
Берём любое натуральное число n:
Если оно чётное, то делим его на 2,
Если нечётное, то умножаем на 3 и прибавляем 1.
Над полученным числом выполняем те же самые действия, и так далее.
Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.
Пример:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (пришли в единицу за 7 шагов)
9 → 28 → 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (тут потребовалось уже 19 шагов)
Я далеко не математик, но интуитивно понял, что главная проблема здесь в том, что мы не знаем, до каких пор будет расти число, поскольку множитель 3 больше делителя 2, на который мы делим число в случае его четности. Поэтому мы не можем использовать типичную для подобных задач индукцию, и утверждать, что каждое k число будет меньше предыдущего, поэтому мы рано или поздно придем в единицу.
Собственно говоря, доказывать гипотезу Коллатца я и не собирался, но грех не запрограммировать такую простую задачку.
Я написал условия "в лоб":
public static long coll_func(BigDecimal n){
BigDecimal copyNum = n;
long stepsCounter = 0;
while(!n.equals(BigDecimal.valueOf(1))){
stepsCounter++;
if(n.remainder(BigDecimal.valueOf(2)).equals(BigDecimal.valueOf(0))){
n = n.divide(BigDecimal.valueOf(2));
}
else{
n = n.multiply(BigDecimal.valueOf(3)).add(BigDecimal.valueOf(1));
}
}
return stepsCounter;И это работало! Действительно, запустив из main эту функцию в цикле, я мог увидеть количество шагов, которое понадобится, чтобы прийти в единицу для различных чисел.
Но сильно бросается в глаза тот факт, что для приведенных в примере цепочек имеется достаточно большая общая часть:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
9 → 28 → 14 → 7 → 22 → 11 → 34 → 17→ 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
То есть программа каждый раз пересчитывает эти значения по новой, а мне бы хотелось этого избежать. Я захотел сделать кэш, чтобы при заходе в 10ку, программа понимала: блин, а где‑то я это уже видела, и просто добавляла к текущим 13 шагам 6 из кэша, получая 19.
Я нашел на просторах интернета информацию о кэше Guava и решил использовать его. Выяснил, что можно настроить автоудаление по времени, максимальный размер, уровень многопоточной изоляции и многое другое.
Делается это при создании объекта CacheBuilder(до вызова .build() можно настроить разные опции кэша):
Cache<BigDecimal, Long> collatzCache = CacheBuilder.newBuilder().build();Кстати, зависимость maven использовал эту:
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>33.2.1-jre</version>
</dependency>Однако, для того, чтобы функция начала нормально кэшироваться, мне пришлось переделать бесконечный цикл на рекурсию и кэшировать результат ее вызова в методе main.
Выглядеть это стало следующим образом:
public static long collatzFunc(BigDecimal n, long stepsCounter) {
if (n.equals(BigDecimal.ONE)) return stepsCounter;
if (isEven(n))
n = n.divide(BigDecimal.valueOf(2));
else
n = n.multiply(BigDecimal.valueOf(3)).add(BigDecimal.ONE);
Long stepsInCache = collatzCache.getIfPresent(n);
if (stepsInCache != null)//If the function has a value in the cache, we get it from there.
return stepsInCache + stepsCounter + 1;
else return collatzFunc(n, stepsCounter + 1);//otherwise, simple recursive call
}
Метод isEven проверяет BigDecimal на четность, изначально я использовал
private static boolean isEven(BigDecimal n) {
return n.remainder(BigDecimal.valueOf(2)).equals(BigDecimal.ZERO);
}Но затем заменил на более лаконичное:
private static boolean isEven(BigDecimal n) {return !n.testBit(0);}Метод main (проверяем гипотезу на числах от 1 до diapason-1 и выводим число с самым долгим путем в единицу):
public static void main(String[] args) {
long maxSteps = 0;
long maxHardNumber = 0;
for (long i = 1; i < diapason; i++) {
long l = collatzFunc(BigDecimal.valueOf(i), 0);
collatzCache.put(BigDecimal.valueOf(i), l);
if (l > maxSteps) {
maxSteps = l;
maxHardNumber = i;
}
}
System.out.println("The most hard humber is " + maxHardNumber + ". We need " + maxSteps + " steps to make 1");
}Проведя такого рода оптимизацию, я начал экспериментировать с размером кэша и способами его чистки, в следствии чего мне удалось найти метод softValues, который задает значениям из кэша Strength.SOFT и это лучшим образом влияет на производительность! Сборщик мусора удаляет значения из такого кэша только тогда, когда ему требуется память.
Таким образом мой кэш создавался следующей строчкой:
CacheBuilder.newBuilder().softValues().build();(в то время, как первоначальное решение с циклом проверяло первые 100 млн натуральных чисел за 27 минут 44 секунды, решение с кэшем и softValues справилось всего за 7 минут 19 секунд. Прирост более чем в 3,7 раз, неплохо)
Также интересно, что ни одна из реализаций алгоритма, даже на относительно слабом железе не уходит в туман и не падает от OutOfMemory, спокойно проверяя миллионы 19-значных чисел, причем справляясь за адекватное время.
На самом деле самым противным на отрезке [1,100 000 000) стало число 63 728 127: чтобы привести его в единицу, пришлось сделать 949 шагов. А если подумать, то 949 шагов — это не очень много, поэтому вычисления для компьютера не сложны и не вызывают переполнения памяти.
На отрезке [1, 50 000 000) я получил следующее время выполнения для различных конфигураций:
Конфигурация |
Время выполнения, сек. |
Кэш с фиксированным максимальным размером в 10 000 000, где по истечению лимита элементы вытесняются по принципу FIFO (first in, first out) |
159 |
Кэш без указания максимального размера, с модом softValues |
78 |
Без кэша, цикл |
501 |
Без кэша, рекурсия |
387 |
Интересный факт, в википедии указано, что по состоянию на апрель 2021 года проверены все натуральные числа до 9.8x10²¹, и каждое из них продемонстрировало соответствие гипотезе Коллатца.
Я прогнал алгоритм на числе 9.8x10²¹+1 и уверенно могу вам сказать: это число тоже соответствует гипотезе Коллатца, путь в единицу из него занимает 505 шага.
Таким образом, вы можете самостоятельно запустить этот код, и, дописав в википедию, что проверили еще парочку миллиардов чисел на соответствие гипотезе, обеспечить математическому сообществу крепкий и здоровый сон)
Код проекта на GitHub: https://github.com/youngmyn/collatz‑theory
Источники:
Самая простая нерешённая задача — гипотеза Коллатца [Veritasium] (youtube.com) — очень классное видео по теме, которое и вдохновило меня на написание этой статьи
Гипотеза Коллатца — Википедия (wikipedia.org) — Русская википедия гипотезы
Collatz conjecture — Wikipedia — Английская википедия гипотезы
Cache (Guava: Google Core Libraries for Java 23.0 API)) — кэш гуава
https://habr.com/ru/articles/673 224/ — классная статья про математический подход к созданию оптимальной реализации lru cache
Комментарии (29)
muxa_ru
28.08.2024 16:29А если проверять на чётность не всё число, а только последнюю цифру, то не экономичнее выйдет по ресурсам?
youngmyn Автор
28.08.2024 16:29В статье есть про это строчка:
Но затем заменил на более лаконичное:
private static boolean isEven(BigDecimal n) {return !n.testBit(0);}
gleb_l
28.08.2024 16:29+1У четных чисел, представленных в двоичной системе, нулевой бит равен 0. Что значит проверять последнюю цифру?
A_J
28.08.2024 16:29Не очень понятно, зачем так извращаться, тем более с Guava, если программа на С без оптимизаций справляется за 11 секунд (в однопоточном режиме).
youngmyn Автор
28.08.2024 16:29ЯП не панацея от всех бед, статья скорее про способы оптимизации самого алгоритма.
A_J
28.08.2024 16:29+1Ну так и с алгоритмом можно поступить проще. Если вам не нужно знать точное число шагов, а только факт завершения, то достаточно проверить, что текущее число меньше максимального уже проверенного.
Даже если вы таки хотите считать точное число шагов, то полноценный кэш тоже не нужен. Достаточно обычного массива с числом шагов, индексируемого целым числом.youngmyn Автор
28.08.2024 16:29Дико извиняюсь, в комментарии выше изобрел велосипед, вы буквально это и сказали.
Ну, написал реализацию к вашей мысли и время выполнения замерил)
Milliard
28.08.2024 16:29+1Интересный факт, в википедии указано, что «По состоянию на июль 2023 года проверены все натуральные числа до 10¹⁰⁰ (десять в сотой степени), и каждое из них продемонстрировало соответствие гипотезе Коллатца.»
Число 10¹⁰⁰ взято с потолка. Ссылки на источник в википедии нет. Да и не скоро появятся компьютерные мощности для такой проверки. В английской вики указано 2⁶⁸ ≈ 3*10²⁰ на июль 2020. В русской (версия от 06.08.2023) 9,8*10²¹ на апрель 2021. Это больше похоже на правду.
youngmyn Автор
28.08.2024 16:29Да, согласен. Смутило то, что отдельно друг от друга каждый отдельный миллиард считается достаточно быстро. Поправлю
DenSigma
28.08.2024 16:29А тут нет такой зависимости, что с ростом начального числа подцепочка, которую можно применить, в большинстве случаев является последней, то есть, генерирована с БОЛЬШЕГО начального числа? Тогда никаких мапов выгоднее не применять, а просто последнее начальное число с количеством цепочки хранить в массиве, а поиск в этом массиве начинать с конца, с самом большом числе и просто перебирать?
Логично же, что число с большей длиной цепочки при прохождении далее по числам по порядку будет чаще задействоваться?
youngmyn Автор
28.08.2024 16:29Не уверен, что до конца понял вашу идею. Можете привести пример цепочки/подцепочки и поиска?
SnakeSolid
28.08.2024 16:29Если я правильно понял, то хвост рекурсии для большинства пар (N, N + 1) совпадает. Из-за чего хранить все значения от 2 до N - 1 в кеше очень расточительно по памяти. Достаточно хранить те, которые присутствовали на последнем шаге (на M последних шагах).
Пример
1000 -> 500 -> 250 -> 125 -> 376 -> 188 -> 94 -> 47 -> 142 -> 71 -> 214 -> 107 -> 322 -> 161 -> 484 -> 242 -> 121 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
1001 -> 3004 -> 1502 -> 751 -> 2254 -> 1127 -> 3382 -> 1691 -> 5074 -> 2537 -> 7612 -> 3806 -> 1903 -> 5710 -> 2855 -> 8566 -> 4283 -> 12850 -> 6425 -> 19276 -> 9638 -> 4819 -> 14458 -> 7229 -> 21688 -> 10844 -> 5422 -> 2711 -> 8134 -> 4067 -> 12202 -> 6101 -> 18304 -> 9152 -> 4576 -> 2288 -> 1144 -> 572 -> 286 -> 143 -> 430 -> 215 -> 646 -> 323 -> 970 -> 485 -> 1456 -> 728 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
1002 -> 501 -> 1504 -> 752 -> 376 -> 188 -> 94 -> 47 -> 142 -> 71 -> 214 -> 107 -> 322 -> 161 -> 484 -> 242 -> 121 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
1003 -> 3010 -> 1505 -> 4516 -> 2258 -> 1129 -> 3388 -> 1694 -> 847 -> 2542 -> 1271 -> 3814 -> 1907 -> 5722 -> 2861 -> 8584 -> 4292 -> 2146 -> 1073 -> 3220 -> 1610 -> 805 -> 2416 -> 1208 -> 604 -> 302 -> 151 -> 454 -> 227 -> 682 -> 341 -> 1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
Жирным выделены значения, совпавшие с предыдущим вычислением.
youngmyn Автор
28.08.2024 16:29Ну даже в вашем примере 1002 и 1003 демонстрируют, насколько разными могут быть пути в 1.
+в паре рядом стоящих чисел всегда одно четное, а другое - нет, поэтому их дороги разойдутся сразу же(одно поделится на 2, второе умножится на 3). Мне не очевидно, что эти хвосты будут совпадатьSnakeSolid
28.08.2024 16:29Да, с 1002 и 1003 на 10% совпадают, а 1001 и 1002 на 90%. В среднем может оказаться что программа с таким подходом отработает за 10 минут вместо 7, но памяти потребует на порядок меньше. На больших числах это вполне может сработать, особенно если хранить 2-3 предыдущих цепочки.
youngmyn Автор
28.08.2024 16:29Про память сложно спорить.
Но мне все равно неочевидно что у рядом стоящих чисел должны быть схожие цепочки. Раз уж мы делим на 2, я бы подумал про хранение таких цепочек в радиусе от чисел- 2ⁿ, условно сохранять цепочки из чисел 63,65, 1023,1025 и тд.
Но опять же, мне сложно отследить их связность без тестирования на больших данных, либо математического/логического вывода
SnakeSolid
28.08.2024 16:29Я накидал простой скрипт, чтобы это проверить. На большинстве диапазонов до 1000000 средняя длина общей цепочки (N, N + 1) равна половине средней длины цепочки для N. Для двух и трех последних чисел скорее всего охват будет до 90%, но нужно проверить.
Мне кажется вполне логичным предположить, что на больших числах эта тенденция не будет меняться.
Функция расчета
function mean_length(from, to) local diff_length = []; local curr_length = []; local result = []; local pred = Set(); for i = from:to local curr = Set(); local t = i; push!(curr, t) while t > 1 if t % 2 == 0 t = div(t, 2) else t = t * 3 + 1 end push!(curr, t) end push!(curr_length, length(curr)) push!(diff_length, length(intersect(pred, curr))) pred = curr end mean(curr_length), mean(diff_length) endВывод для разных диапазонов
for i = 1:10 println(i*100000, ":", (i+1)*100000, " -> ", mean_length(i*100000, (i+1)*100000)) end 100000:200000 -> (122.84768152318478, 61.473475265247345) # средняя длина, средняя разность 200000:300000 -> (128.31124688753113, 64.26448735512645) 300000:400000 -> (131.92660073399267, 65.98678013219867) 400000:500000 -> (134.72327276727233, 67.37789622103779) 500000:600000 -> (136.33956660433395, 68.02739972600274) 600000:700000 -> (138.21428785712143, 69.15675843241567) 700000:800000 -> (139.85148148518516, 69.9819001809982) 800000:900000 -> (140.99823001769983, 70.55780442195578) 900000:1000000 -> (142.59238407615925, 71.4380156198438) 1000000:1100000 -> (142.85390146098538, 71.35284647153529)
maxlilt
28.08.2024 16:29Упрощенно можно рассматривать условием завершения не достижение единицы а достижение 2 в степени n.
youngmyn Автор
28.08.2024 16:29Где n - количество шагов, которое можно прибавить к текущему и получить общее количетво шагов, чтоб прийти в единицу.
Можно хранить
Mapсо степенями двойки и их значениями, и использовать как доп.кэш. Действительно, элегантно.
domix32
28.08.2024 16:29Я далеко не математик, но интуитивно понял, что главная проблема здесь в том, что мы не знаем, до каких пор будет расти число, поскольку множитель 3 больше делителя 2, на который мы делим число в случае его четности.
Неверно. Мы либо пытаемся доказаться, что функция точно убывающая (то бишь сходится к некоторому значению), либо что функцией можно покрыть все числа.
youngmyn Автор
28.08.2024 16:29Ну, когда я это писал, в моей голове было что-то схожее со сходимостью, из разряда, что если каждый четный член в последовательности увеличивается на 1, а каждый нечетный уменьшается на 2 относительно предыдущего, то с какого бы мы числа не начали, она уменьшится до определенного числа.
Я хотел сказать только то, что в случае этой последовательнсти, такого явного зигзага, который доказуемо уменьшается - нет.
gleb_l
А какое примерно отношение максимального числа к количеству ключей в кэше? Может проще иметь хеш-таблицу ключей, которые на предыдущем шаге привели к 1? Тогда храниться все будет в разы компактнее => больше ключей поместится в память, => можно будет быстрее исследовать больший диапазон. А после того, как мы достигли верхней границы, пробегаемся по ключам и считаем уже для них последовательности сведения к 1 (здесь можно и с кешированием полных путей) - то есть такая двухступенчатая ракета ;)
youngmyn Автор
Ответ на этот вопрос сложнее чем кажется, варьируется сильно от диапазона и стратегии хранения ключей в кэше.
В статье есть ссылка, про исследование кэша на оптимальность: https://habr.com/ru/articles/673224/
В случае с хэш-таблицей, у меня есть подозрение, что на больших числах кэш все равно будет переполняться и сильно тормозить. Нужна стратегия чистки памяти, в моем случае soft references помогли
gleb_l
Так это без разницы. Храните по ключу null в качестве полезной нагрузки - это будет съедать явно меньше памяти, чем вся цепочка. Смысл моей идеи в том, чтобы опираться только на факт того, что встреченное число приводит последовательность после него к 1, и по завершению расчета проитерироваться по этим найденным фактам. Вот я и спрашиваю, какое отношение верхней границы к количеству известных цепочек, и главное, как меняется эта пропорция с увеличением N? Если она сублинейна - то дело выгодное :)
youngmyn Автор
С текущей конфигурацией кэша:
при проходе 23млн кэш хранит в себе каждый ключ,
на 24м миллионе освобождает память и выкидывает 15млн ключей из памяти.
Ну и в дальнейшем эти история повторяется, размер кэша скачет от 8 до 23х млн значений, вне зависимости от верхней границы.
Но вообще, это количество, при использовании обычного кэша действительно около-линейно.
Ваш комментарий натолкнул меня на мысль (хотя возможно это и имелось ввиду):
Когда мы итерируемся от 1 до +ထ, и находимся в некоторой точке K, то если рекурсия заходит в любое число, меньшее К, мы можем завершать проход, и начинать следующую итерацию, увеличив K на 1(поскольку, по умолчанию, если мы попали в число, меньшее чем K, то это значит, что некоторое время назад мы его валидировали, и успешно)
Если нам не нужно количество шагов, то можно вообще не использовать никакой кэш, а написать что то вроде:
функция, которая выходит из бесконечного цикла либо при приходе в 1, либо в точку, уже валидированную ранее:
метод main
Более того, первые 50млн чисел этот код проверяет(но не считает шаги) на соответствие гипотезе за 10 секунд!
gleb_l
Это зависит от развития последовательности с какого-то числа - если тех, что быстро уходят вниз, много, то да. Но нет гарантии, что последовательность не будет долго болтаться где-то между K и K*3, и я бы делал так - если число меньше К - то сразу перезапускать, иначе проверить в хэш-таблице. Если там нет - сделать следующее действие. То есть меньшие числа - перезапуск, большие - кэш.
youngmyn Автор
Да, склоняюсь, к тому, что это оптимальное решение из тех, что у меня в голове сейчас.
gleb_l
И кеш, кстати, можно периодически чистить по мере того, как растет K - скажем, раз в 100000 чисел проходить по нему и удалять все, что меньше K. Он тогда и переполняться не будет скорее всего.