25.05.2020 18:11
shale 36 2900 Источник
image

Май выдался холодным, отопление отключили, а вычислительные (и обогревательные) мощности какие-никакие, а простаивают. Так почему бы не загрузить их чем-нибудь бесполезным, что и согреет, и развлечет.

Но начну издалека. На днях попалась на глаза задачка для средней школы со следующей формулировкой: «Несколько последовательных натуральных чисел выписали в строку в таком порядке, что сумма каждых трёх подряд идущих чисел делится нацело на самое левое число этой тройки. Какое максимальное количество чисел могло быть выписано, если последнее число строки нечётно?»

При таком ограничении нетрудно доказать, что в каждой тройке нечётных чисел будет больше, чем чётных. И поскольку разница между ними не может быть больше единицы, максимальная длина последовательности ограничена пятью числами. А в качестве примера можно привести последовательность 4 5 3 2 1.

Подробное доказательство можно найти здесь.

Но что если убрать указанное ограничение на нечётность последнего числа? Тогда справа можно добавить числа 7 6 8, расширив последовательность до восьми чисел. Можно еще и десятку добавить, а недостающую девятку присоединить слева. Ну и, наверное, это будет не единственная и не самая длинная перестановка.

Собственно, стараясь рассуждать логически, я не нашел доказательства ограниченности таких последовательностей и решил привлечь к анализу домашний обогреватель вычислитель. Грубый полный перебор всех N! вариантов быстро показал несостоятельность метода, а вот направленный перебор позволил значительно продвинуться, и результат оказался и ожидаемым и неожиданным одновременно.

Выяснилось, что для всех N до 29 включительно такие перестановки чисел от 1 до N действительно находятся, правда, для длин 27 и 29 в единственном варианте. А вот дальше появляются пробелы. Для перестановок с размерами 30, 31, 32 и 33 решений нет, для числа 34 есть одно.

такое
33 23 10 13 7 6 1 29 27 2 25 21 4 17 15 19 11 8 3 5 31 9 22 14 30 26 34 18 16 20 12 28 32 24

Далее снова два пробела. Для значений 37 и 38 подобные последовательности есть и не единичные, а затем провал. Я даже было отчаялся, следующий десяток оказался полностью пустым, но удача улыбнулась, для N=51 таки находится нужная перестановка.

вот она
46 45 1 44 49 39 10 29 21 37 5 32 23 41 51 31 20 11 9 2 43 35 8 27 13 14 25 3 47 40 7 33 16 17 15 19 26 50 28 22 6 38 34 4 30 18 42 48 36 12 24

Их даже две, но они пересекаются по большей части.

Дальше снова намечается пустота, по крайней мере, для чисел 52 и 53 решений нет, а дальше не искал. Все же с каждым шагом время ожидания растет по экспоненте, да и в доме уже заметно потеплело, решил пока на этом остановиться.

Если свести найденные количества возможных вариантов в одну таблицу, можно построить следующий график



Ну да, есть над чем помедитировать.

В исходной задаче не было требования начинать натуральный ряд с единицы. Главное чтобы в последовательности встречались все числа от a до b. Но я пробовал, становится только хуже, вариантов находится еще меньше. Что, собственно, объяснимо. Чем большее число стоит на левой позиции тройки, тем меньшую кратность можно получить суммой двух других, т.е. тем меньше доступных вариантов. Ну а вопрос верхнего предела длин таких последовательностей остается открытым. С ростом размерности вероятность успеха явно снижается, но вот обнуляется ли? Или дальше так и будут, пусть и редко, встречаться такие вот (не)интересные перестановки.

Напоследок, пожалуй, можно привести код программы-грелки,

правда, он на Хаскеле 
import Data.List (delete)
import Control.Parallel.Strategies
import System.Environment

pvc :: Int -> Int -> [Int] -> [[Int]]
pvc a b [] = [[a,b]]
pvc a b xs = [a:ys | 
    x <- xs, 
    mod (a + b + x) a == 0, 
    ys <- pvc b x (delete x xs)]

gen :: Int -> [[[Int]]]
gen n = 
    let ab = [(a, b) | a <- [1..n], b <- delete a [1..n]]
    in  map hlp ab `using` parList rseq
    where
    hlp (a,b) = pvc a b $ delete a $ delete b [1..n]

main = do
    [n] <- getArgs
    print $ concat $ gen $ read n