Dado um número inteiro positivo N , sua tarefa é retornar o número de etapas exigidas pelo seguinte algoritmo para atingir N :
Encontre o menor número triangular T i tal que T i ≥ N . Construa a lista correspondente L = [1, 2, ..., i] .
Enquanto a soma dos termos de L for maior que N , remova o primeiro termo da lista.
Se a soma dos termos de L agora for menor que N , incremente i e inclua-a na lista. Continue com o passo 2.
Paramos assim que N é alcançado. Somente o primeiro passo é executado sistematicamente. Os passos 2 e 3 podem não ser processados.
Exemplos
Abaixo está um exemplo para N = 11 :
Portanto, a saída esperada para N = 11 é 4 .
Outros exemplos:
- N = 5 - Começamos com T 3 = 1 + 2 + 3 = 6 , seguido por 2 + 3 = 5 . Saída prevista: 2 .
- N = 10 - Somente o primeiro passo é necessário porque 10 é um número triangular: T 4 = 1 + 2 + 3 + 4 = 10 . Saída prevista: 1 .
100 primeiros valores
Abaixo estão os resultados para 1 ≤ N ≤ 100 :
1, 2, 1, 4, 2, 1, 2, 10, 2, 1, 4, 2, 6, 2, 1, 22, 8, 2, 10, 2,
1, 2, 12, 6, 2, 4, 2, 1, 16, 2, 18, 50, 2, 6, 2, 1, 22, 6, 2, 4,
26, 2, 28, 2, 1, 8, 30, 16, 2, 6, 4, 2, 36, 2, 1, 2, 4, 12, 40, 2,
42, 14, 2,108, 2, 1, 46, 2, 6, 4, 50, 2, 52, 18, 2, 4, 2, 1, 56, 12,
2, 20, 60, 4, 2, 22, 10, 2, 66, 2, 1, 4, 10, 24, 2, 40, 72, 8, 2, 6
Regras
- Você pode escrever um programa completo ou uma função que imprima ou retorne o resultado.
- Você é obrigado a processar qualquer N ≤ 65536 em menos de um minuto em hardware de gama média.
- Com tempo suficiente, seu programa / função deve, teoricamente, funcionar para qualquer valor de N que seja suportado nativamente pelo seu idioma. Caso contrário, explique o motivo na sua resposta.
- Isso é código de golfe, então a resposta mais curta em bytes vence!
code-golf
math
integer-partitions
Arnauld
fonte
fonte
Respostas:
Geléia ,
2931 bytesUm link monádico que retorna o resultado (N = 65536 leva menos de dois segundos).
Experimente online!
Quão?
Para uma explicação completa do algoritmo, consulte o post fantástico de Martin Ender .
A implementação de programa completo de 29 bytes que criei do algoritmo descrito leva 4 min 30 para N = 65536 no meu laptop, portanto, suponho que não conte.
Usar um loop while para cada etapa 3 e reutilizá-la como etapa 1 é igual ao comprimento que eu posso gerenciar com a inicialização da lista, pois nenhuma verificação na etapa 3 significa criar uma lista até que nada permaneça e depois encontrar o primeiro índice do valor:
fonte
Mathematica, 79 bytes
Explicação
Não me incomodei em implementar o algoritmo no desafio, então queria procurar um atalho para a solução. Embora eu tenha encontrado um, infelizmente não bate a resposta do Mathematica que implementa o algoritmo. Dito isso, tenho certeza de que ainda não está otimizado, e pode haver outros idiomas que podem se beneficiar dessa abordagem ou de algumas das idéias obtidas no processo.
Por isso, afirmo que a sequência que devemos calcular é:
f (n) = 2 * ( A212652 (n) - A002024 (n)) + 1 + A023532 (n-1)
Como alternativa, é f (n) = 1 se n for um número triangular ef (n) = 2 * ( A212652 (n) - A002024 (n) + 1) caso contrário.
Na primeira expressão, A023532 simplesmente codifica esses dois casos diferentes. As outras duas seqüências (mais 1) são a diferença entre o maior número inteiro k na decomposição mais longa de n em números inteiros consecutivos (k-i + 1) + (k-i + 2) + ... + k = n e o maior número inteiro j, de modo que 1 + 2 + ... + j <n .
Em palavras um pouco mais simples, é aqui como encontramos a resposta para os números não triangular: primeiro, encontrar o maior número triangular T j que é menos do que n . Então j é o penúltimo número inteiro que é adicionado durante a etapa 1 (porque depois de adicionar j + 1 , teremos excedido n ). Decomponha n em tantos (ou tão pequenos) números inteiros consecutivos quanto possível e chame o máximo entre esses números k . O resultado é simplesmente 2 * (kj) . A razão intuitiva para isso é que o máximo na decomposição cresce 1 ponto a cada dois passos e paramos quando atingimosk .
Precisamos mostrar quatro coisas para provar que isso funciona:
Já mostramos por que (1) é verdadeiro. Em seguida, provamos que não podemos terminar em uma etapa de inserção, exceto a inicial (o que não ocorre para números não triangulares).
Suponha que tenhamos terminado uma etapa de inserção, atingindo n após adicionar um valor p à soma. Isso significa que, antes desta etapa de inserção, o valor era np ( ou menos se adicionássemos vários valores de uma vez). Mas essa etapa de inserção foi precedida por uma etapa de exclusão (já que não poderíamos ter atingido n durante a etapa 1). O último valor q removemos durante esta etapa de exclusão foi necessariamente menor que p devido à maneira como o algoritmo funciona. Mas isso significa que, antes de removermos q , tínhamos n-p + q ( ou menos ), que é menor que n. Mas isso é uma contradição, porque teríamos que parar de remover números inteiros quando atingimos n-p + q em vez de remover outro q . Isso prova o ponto (2) acima. Então agora sabemos que sempre terminamos em uma etapa de exclusão e que, portanto, todos os números não triangulares têm saídas pares.
A seguir, provamos (3) que cada etapa de inserção pode inserir apenas um valor. Este é essencialmente um corolário de (2). Mostramos que, após adicionar um valor, não podemos atingir n exatamente e, como a prova estava usando uma desigualdade, também não podemos terminar abaixo de n (já que n-p + q ainda seria menor que n e não deveríamos ter removido que muitos valores em primeiro lugar). Portanto, sempre que adicionamos um único valor, é garantido que excedamos n, porque ficamos abaixo de n removendo um valor menor. Portanto, sabemos que a extremidade superior da soma cresce 1 em cada dois passos. Sabemos o valor inicial deste extremidade superior (é o menor m tal queT m > n ). Agora só precisamos descobrir esse limite superior quando chegarmos à soma final. Então o número de etapas é simplesmente o dobro da diferença (mais 1).
Para fazer isso, provamos (4) que a soma final é sempre a decomposição de n em tantos números inteiros quanto possível, ou a decomposição em que o máximo nessa decomposição é mínimo (ou seja, é a decomposição mais antiga possível). Faremos isso novamente por contradição (a redação desta parte pode ser um pouco mais rigorosa, mas eu já gastei muito tempo nisso ...).
Digamos que a decomposição mais antiga / mais longa possível de n seja a + (a + 1) + ... (b-1) + b , a ≤ b , e digamos que o algoritmo a ignore. Isso significa que, no momento em que b é adicionado, a não deve mais fazer parte da soma. Se a fizesse parte da soma s , teríamos n ≤ s naquele momento. Portanto, ou a soma contém apenas os valores de a a b , que é igual a n e paramos (portanto, não pulamos essa decomposição) ou há pelo menos um valor menor que a na soma, ganhe nesse caso n <se esse valor seria removido até atingirmos a soma exata (novamente, a decomposição não foi ignorada). Portanto, teríamos que nos livrar de a antes de adicionar b . Mas isso significa que teríamos que chegar a uma situação em que a seja o menor componente da soma e o maior ainda não seja b . No entanto, nesse ponto, não podemos remover a , porque a soma é claramente menor que n (já que b está ausente), portanto, é necessário adicionar valores primeiro até adicionarmos b e pressionar n exatamente. Isso prova (4).
Então, juntando essas coisas: sabemos que o primeiro par de etapas nos fornece um valor máximo de A002024 (n) . Sabemos que o valor máximo da decomposição final é A212652 (n) . E sabemos que esse máximo é incrementado uma vez em cada par de etapas. Portanto, a expressão final é 2 * ( A212652 (n) - A002024 (n) + 1) . Essa fórmula quase funciona para números triangulares, exceto que para aqueles que precisamos apenas de 1 etapa em vez de 2, é por isso que corrigimos o resultado com a função indicadora dos números triangulares (ou sua inversa, o que for mais conveniente).
Finalmente, quanto à implementação. Para a sequência anterior, estou usando a fórmula MIN (ímpar d | n; n / d + (d-1) / 2) da OEIS. Acontece que salvamos alguns bytes se levarmos o fator 2 para essa expressão para obter MIN (ímpar d | n; 2n / d + d-1) , porque esse -1 então cancela com o +1 na minha primeira versão de f (n) que codifica diretamente os dois casos para números triangulares e não triangulares. No código, isso é:
Para a última sequência (
1, 2, 2, 3, 3, 3, ...
), podemos usar um formulário fechado simples:E, finalmente, a função indicadora inversa dos números triangulares é 0 sempre que 8n + 1 é um quadrado perfeito. Isso pode ser expresso no Mathematica como
Existem várias maneiras de expressar essas duas últimas seqüências e de mudar um deslocamento constante entre elas. Portanto, tenho certeza de que essa ainda não é uma implementação ideal, mas espero que isso possa dar aos outros um ponto de partida para examinar novas abordagens no suas próprias línguas.
Desde que eu resolvi esse problema, aqui está um gráfico da sequência de n = 1000 (eu também poderia calcular 100k em alguns segundos, mas na verdade não mostra nenhum insight adicional):
Pode ser interessante examinar as variações dessas linhas muito retas, mas deixarei isso para outra pessoa ...
fonte
Mathematica, 72 bytes
Função pura usando um argumento inteiro.
Como funciona
Um
For
laço.Inicialização; defina
l
(inferior),u
(superior),c
(contador) ek
(soma) como 0.Condição; repita enquanto
k
não for igual à entrada.Incremento; incrementar o contador
c
.Corpo
Se a entrada for maior que
k
:Enquanto a entrada for maior que
k
, incrementeu
e aumentek
emu
.Se a entrada não for maior que
k
:Enquanto que a entrada é menor do que
k
, decrementok
porl
e incrementol
.Retorne
c
após o loop.fonte
For[,...]
batidasWhile[...]
.Python 2 , 104 bytes
Experimente online!
Alterna entre adicionar termos ao final da lista e remover termos desde o início.
fonte
Haskell ,
70 63 6864 bytesEDITAR:
a
. Corrigidos erros de um por um na explicação.a
eb
linearmente para obter termos na fórmula da soma para cancelar.1#1
é uma função anônima que recebe e retorna um número inteiro.Use como
(1#1) 100
.Experimente online!
Como funciona
(a#b)n
representa a etapa atual do cálculo.a, b
são números1, 3, 5, ..
enquanton
pode ser positivo ou negativo, dependendo da etapa.[(a+1)/2,(a+3)/2..(b-1)/2]
e o número da meta-n
.[(b+1)/2,(b+3)/2..(a-1)/2]
e o número da metan
.a, b
e as listas é capaz de somar com a expressão curtas=a*a-b*b
.s= -8*sum[(a+1)/2..(b-1)/2]
.s=8*sum[(b+1)/2..(a-1)/2]
.s>8*n
, então,b
é incrementado por 2 antes da recorrência.s<8*n
, a recursão altera a etapa trocandoa
eb
, e negandon
, e 1 é adicionado ao resultado.s==8*n
, nenhuma das duas compreensões da lista fornecer elementos, então a soma é0
.(1#1) n
representa um "estágio 2" fictício antes de iniciar, que é imediatamente alterado para a etapa 1, a partir da qual é criada a lista[1..0]=[]
.fonte
PHP> = 7.0, 74 bytes
use o operador da nave espacial
Experimente online!
Expandido
fonte
$argn
?-R
muito menosargv
ouargi
. Eu conhecia argc e argv, é claro. Muito interessante, obrigado.C,
9491 bytesExperimente on-line
fonte
return
), mas, para os que o fizerem, sinta-se à vontade para incorporá-los à sua resposta.JavaScript (ES6), 82 bytes
Snippet de teste
Mostrar snippet de código
fonte
dc , 61 bytes
Experimente online!
Explicação
Macro recursiva principal:
Esta macro:
S
representa exatamente o número atual. Sai se houver.S+N
(super-aproximação) ouS-N
(sub-aproximação), a escolha alterna entre iterações.Quando sai, a trilha deixada na pilha informa ao programa principal quantas iterações foram necessárias.
fonte
Python 3,
150138 bytesChangelog:
fonte
else
necessário? Eu acredito que aselse
execuções sempre, porque o loop sempre termina normalmente (sembreak
), e parece funcionar bem sem ele .A=l.append
peça e usá-lal+=[x]
.Lote, 126 bytes
Explicação:
l
é zero se a etapa 2 nunca foi executada. Isso permiten
rastrear o número de iterações da etapa 3. Como o algoritmo nunca para na etapa 3, ele deve ter executado a etapa 1 uma vez e a etapa 2n+1
vezes para um total den+n+2
etapas. No entanto, se o parâmetro for um número triangular, a etapa 2 nunca será executada, portanto, precisamos subtrair uma etapa.fonte
Python 2,
8681 bytesExperimente online!
Calcula o caso de teste 65536 em
0.183s
no TIO.Esta versão recursiva em 84 bytes não pode computar todos os valores até 65536:
Experimente online!
fonte
Mathematica, 92 bytes
Função pura pegando um argumento inteiro e retornando um número inteiro.
As variáveis
a
eb
representam os números iniciais e finais (que mudam constantemente) na soma em consideração, enquantoq
representam o total atual (dos números dea+1
atéb
);t
mantém o controle de todos os valoresq
encontrados até o momento. Após inicializar essas variáveis, oFor
loop continua em execuçãoIf[q<#,q+=++b,q-=++a]
, o que adiciona um novo número ao final ou subtrai o número na frente, conforme determinado pela especificação, atéq
igualar a entrada.Agora só precisamos extrair o número de etapas da
t
lista deq
valores encontrados ao longo do caminho. Por exemplo, quando a entrada é11
, oFor
loop sai comt
igual{0,1,3,6,10,15,14,12,9,15,11}
. A melhor maneira que encontrei para calcular o número de etapas a partir disso é contar quantas vezes as diferenças mudam de subir para diminuir; é isso que o comando detalhadoLength@Split@Sign@Differences@t
faz, mas suspeito que possa ser melhorado.fonte
C (tcc), 71 bytes (61 + 10)
Argumentos da linha de comando (incluindo um espaço):
Fonte:
Como funciona:
c
conta o número de etapas.m
eM
armazene o mínimo e o máximo do intervalo,s
a soma. Inicialmente, são todos zero.Continuamente,
c
é aumentado es
comparado an
. Contanto que sejam desiguais:Se
c
for ímpar, contanto ques<n
, adicione um número inteiro ao final do intervalo: aumenteM
em um es
emM
.Se
c
for par, desde ques>n
remova um número inteiro do início do intervalo: diminuas
emm
e aumentem
em um.Quando o loop sair,
c
foi aumentado muitas vezes. Decrementar produz o resultado correto e é calculado no registro correto para atuar como o valor de retorno.Curiosamente, usa exatamente os mesmos nomes de variáveis que a resposta C de Khaled.K . Eles não são copiados.
fonte
Perl 6 , 114 bytes
(inspirado por um antigo Haskell implementação )
Experimente
Ele roda com uma entrada de 65536 em menos de 45 segundos no meu computador, mas não consegui executá-lo em menos de 60 segundos com o TIO.run.
Eu tenho o Rakudo v2017.04 +, onde ele tem v2017.01 .
O Rakudo / NQP / MoarVM obtém otimizações quase diariamente, portanto, pode haver um número intermediário necessário para obtê-lo com o tempo.
Expandido
Observe que o Rakudo possui uma otimização para
Range.sum
que ele não precise percorrer todos os valores.fonte