Да, это одна из первых оптимизаций, которые я пробовал. Удивительно, но это не принесло никакого эффекта, время работы практически не изменилось!
Думаю, что время работы программы линейно зависит от количества перебранных вариантов (то есть, максимальных последовательностей длины N1<=N), а их количество не зависит от того, идем мы с начала или с конца.
Действительно, похоже на e/2! Я, правда, не представляю, как это можно доказать (хотя достаточно просто показать, что скорость роста не превосходит e^N). Но например, если доказать, что для большинства последовательностей в переборе алгоритм доходит как минимум до длины N/2, то это даст нижнюю оценку в (e/2)^N.
Насчет производительности: к сожалению, из-за экспоненциального роста оптимизация в разы дает только константное увеличение N. Например, даже если я ускорю программу в 10 раз, запустив на компьютере с 40 ядрами (вместо 4), то, в лучшем случае, я смогу проверить только 6-7 дополнительнх значений для N. Надо искать алгоритм с лучшей асимптотикой, но совсем не факт, что он существует.
Вообще, имхо, эта задача интересна с точки зрения теории чисел. Например, она в чем-то похожа на проблему нахождения простых чисел Мерсенна (простые числа, на единицу меньшие степени двойки). Их до сих пор найдено только около 50, и до сих пор неизвестно, конечно или бесконечно ли их число.
Думаю, что время работы программы линейно зависит от количества перебранных вариантов (то есть, максимальных последовательностей длины N1<=N), а их количество не зависит от того, идем мы с начала или с конца.
Насчет производительности: к сожалению, из-за экспоненциального роста оптимизация в разы дает только константное увеличение N. Например, даже если я ускорю программу в 10 раз, запустив на компьютере с 40 ядрами (вместо 4), то, в лучшем случае, я смогу проверить только 6-7 дополнительнх значений для N. Надо искать алгоритм с лучшей асимптотикой, но совсем не факт, что он существует.
Вообще, имхо, эта задача интересна с точки зрения теории чисел. Например, она в чем-то похожа на проблему нахождения простых чисел Мерсенна (простые числа, на единицу меньшие степени двойки). Их до сих пор найдено только около 50, и до сих пор неизвестно, конечно или бесконечно ли их число.
Такой вопрос: сколько времени у вас работала программа для N=51?