Comments 12
сдвигается в среднем на полбита влево
это какой-то бит Шрёдингера.
Собсна задача по сложности никак не изменилась. У прошлого доказывателя оставлял не так давно комментарий с видосиком, где сам Теренс Тао рассказаывает к чему на текущий момент пришли. Собственно вот эта граница в лог с гулькой как раз то что люди смогли вычислить эмпирически и статистически это покрывает 99% случаев. И как раз последний процент и есть Terra Incognita которая мешает доказать правдивость гипотезы. А все связанные теоремы не сказать чтобы легко формулируются и доказываются, чтобы их можно было использовать человеком.
Меня больше зантересовали числа которые формируются при помощи операций, про которые писал автор прошлой статьи. Если назвать деление на два down и умножение на 3 up и некоторое произвольное число X, то можно сформировать некоторую математику вокруг полиномов вида ((((X(u|d)u|d)u|d)u|d)u|d)... и вытекает ряд вопрос относительно свойств таких чисел:
Наткнулся на то что некоторый произвольный полином может иметь несколько целых решений, которые появляются с определенным шагом.
- все ли произвольные полиномы выдают целые решения или часть из них так и будет рациональным числом?
- все ли полиномы имеющие целые решения буду генерировать бесконечные последовательности решений или есть полиномы для которых существует единственное целое решение.
- как произвольный X коррелирует с остальными числами? Взаимно простые, просто простые, непростые и прочие.
- существует ли общий алгоритм для получения из X некоторого Y посредством применения всех u/d операций
- сколько вариантов получения некоторого Y сущетвует?
И многое многое другое. Но я сильно не копался в них, поэтому более формального списка вопросов не писал. Возможно часть из этого покрывается другими вещами.
Я тут от нефиг делать написал простенький макрос для экселя.
Он последовательно перебирая числа по порядку выбирает для которого будет наибольшее суммарное число операций умножения и деления чтобы получить 1.
Больше всего порадовало число 27. нужно совершить 111 операций чтобы добраться до 1
Вот выборка с числами и количеством циклов :
Обратите внимание, что большинство чисел нечётные.
Кроме одного... на него потребовалось на один цикл больше предшествующего.
И оно больше него в 2 раза.
Я не утверждаю что оно единственное.
Просто между ним и предшествующим большего числа циклов не нашлось.
Только не циклы, а длину цепи. Цикл пока один единственный и он как раз в единице. А так длины иногда имеют свойство взрываться и вроде в OEIS под это дело отдельную последовательность выделили.
И оно больше него в 2 раза.
Ну так можно буквально любое из нечетных взять, домножить на два и получить цепь на единицу больше. Например, возьмем из вашей таблички 230631 с количеством 442 шага. Множим на два - 461262 и получаем цепь длиной 443, где первой же итерацией мы как раз и делим на два.
Так что как минимум непонятен критерий по которому вы отбирали вашу табличку. Отдельно привет за макросы экселя.
Всё так, но между ними наверняка найдётся число с более длинной цепочкой шагов.
И тогда второе число в табличку просто не попадает.
Макрос после прихода к единице сравнивает количество шагов с наибольшим последним. И если количество шагов больше, то вписывает в список и число и количество шагов.
Тогда следующее количество сравнивается уже с ним.
Я там конечно проредил список в самом начале.
Иначе он бы был слишком длинным.
Но там где числа стали по больше я уже оставил как есть.
Тенденция идет к тому, что шаг между числами для увеличения числа шагов становится всё больше.
И на вычисление всей цепочки уходит больше времени.
Сейчас у меня последний найденный результат число в два раза большее чем то что в таблице уже есть, и шагов соответственно на 1 больше.
И это то, что компьютер всю ночь считал.
И это то, что компьютер всю ночь считал.
Ну так переехали бы на питон с каким-нибудь numpy или ещё чем-нибудь и отгружали б данные в csv, все побыстрее было б. С простеньким lru_cache досчитывает до предпоследних строчек минут за двадцать
simple.py
from functools import lru_cache
from time import time
@lru_cache(maxsize=100000)
def steps2(n):
if n == 1 : return 1
return 1 + steps(n//2) if n & 1 == 0 else steps(3*n+1)
last = 0
ts = time()
for i in range(10000000000):
curr = steps2(i)
if curr > last + 1:
ts2 = time()
print(f"{ts2-ts:0.2f} {i} {curr}")
last = curr;Он по тому так долго считает, что у меня код не оптимизирован.
Я вообще подозреваю в нём где-то есть ошибка.
У меня вообще стоит 32 битный эксель на 64 битной машине.
В диспетчере показывает загрузку процессора на 14% и 5 Мб использованной памяти. Я вообще удивляюсь что он что-то смог сосчитать.
Эксель он вообще глюканутый какой-то. 16 гигов памяти, а он на 5 Мб крутится.
Вообще не ставил задачей найти максимальное число шагов.
Просто на глаза попалась эта гипотеза и я решил побаловаться.
Из языков программирования освоен только VBA который в экселе, и то только на минимальном уровне.
У меня профессия Токарь, ну плюсом ещё конструктор и технолог.
Вся жизнь посвящена обработке металлов резанием.
У меня профессия Токарь, ну плюсом ещё конструктор и технолог.
Питон как раз ваш друг в такой ситуации. И выглядит лучше и возможностей побольше, включая и производительность и оптимизировать проще.
Питон хороший друг, и с этим не по споришь.
Только мне уже 57. Осваивать его уже поздно.
Родись я лет на 7-10 позже, я бы был программистом.
Но к тому времени, когда появился 286й процессор у меня уже был 4й разряд токаря. и 3й курс в институте на вечернем...
А Макросы в экселе я осваивал чисто из интереса. Мне тогда ещё 40 не было.
Книжка попалась и время было.
Накорябал несколько файликов с макросами. Ошибка на ошибке....
Иногда стряхиваю пыль с мозгов таким способом.
Взгляд программиста на гипотезу Коллатца