May ficou frio, o aquecimento foi desligado e os poderes de computação (e aquecimento) não eram, mas estavam inativos. Então, por que não carregá-los com algo inútil , que irá aquecer e divertir?Mas vou começar de longe. No outro dia, me deparei com um problema para uma escola secundária com a seguinte redação: “Vários números inteiros positivos consecutivos foram escritos consecutivamente de tal maneira que a soma de cada três números consecutivos é divisível inteiramente pelo número mais à esquerda deste triplo. "Qual é o número máximo de números que podem ser gravados se o número da última linha for ímpar?”Com essa restrição, é fácil provar que em cada triplo de números ímpares haverá mais do que números pares. E como a diferença entre eles não pode ser maior que um, o comprimento máximo da sequência é limitado a cinco números. E como exemplo, podemos dar a sequência 4 5 3 2 1 .Prova detalhada pode ser encontrada aqui.Mas e se removermos a restrição indicada na estranheza do último número? À direita, você pode adicionar os números 7 6 8 , expandindo a sequência para oito números. Você também pode adicionar uma dúzia e anexar os nove ausentes à esquerda. Bem, e provavelmente essa não será a única e nem a mais longa permutação.Na verdade, tentando raciocinar logicamente, não encontrei evidências das limitações de tais seqüências e decidi envolver uma calculadora no aquecedor doméstico para análise . Pesquisa exaustiva e completa de todos os N ! As opções mostraram rapidamente a falha do método, mas a enumeração direcional permitiu um progresso significativo, e o resultado foi esperado e inesperado ao mesmo tempo.Verificou-se que, para todos os N até 29, inclusive, essas permutações de números de 1 a N são, de fato, encontradas para os comprimentos 27 e 29 em uma única variante. Mas então existem lacunas. Para permutações com os tamanhos 30, 31, 32 e 33, não há soluções; para o número 34, existe uma.tal33 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
Então, novamente, dois espaços. Para os valores 37 e 38, essas seqüências não são únicas e, em seguida, uma falha. Eu estava até desesperado, os próximos dez ficaram completamente vazios, mas a sorte sorriu, pois N = 51 a permutação necessária ainda é encontrada.aqui está ela46 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
Existem até dois deles, mas eles se cruzam na maior parte.Além disso, o vazio é novamente planejado, pelo menos para os números 52 e 53 não há soluções, mas não procurei mais. No entanto, a cada passo, o tempo de espera cresce exponencialmente e a casa já está muito mais quente, decidi parar por agora.Se você reduzir o número encontrado de opções possíveis em uma tabela, poderá criar o gráfico a seguir
Bem, sim, há algo para meditar.No problema original, não havia necessidade de iniciar a série natural a partir de uma. O principal é que todos os números de a a b sejam encontrados na sequência. Mas tentei, só piora, há ainda menos opções. O que, de fato, é explicável. Quanto maior o número estiver na posição esquerda do triplo, menor a multiplicidade pode ser obtida pela soma dos outros dois, ou seja, menos opções disponíveis. Bem, a questão do limite superior dos comprimentos de tais seqüências permanece em aberto. Com o crescimento da dimensionalidade, a probabilidade de sucesso é claramente reduzida, mas é anulada? Ou ainda, embora raramente encontrem permutações (des) interessantes.Por fim, talvez você possa trazer o código do programa de aquecimento,verdade que ele está em Haskellimport 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