Introdução
A229037 possui uma plotagem bastante intrigante (pelo menos nos primeiros termos):
Existe a conjectura de que possa realmente ter algum tipo de propriedade fractal.
Como essa sequência é construída?
Definir a(1) = 1, a(2) = 1
, em seguida, para cada n>2
encontrar um positivo mínimo número inteiro a(n)
de tal modo que para cada sequência aritmética 3 prazo n,n+k,n+2k
de índices, os valores correspondentes da sequência a(n),a(n+k),a(n+2k)
é não uma sequência de aritmética.
Desafio
Dado um número inteiro positivo n
como entrada, imprima os primeiros n
termos a(1), ... , a(n)
desta sequência. (Com qualquer formatação razoável. Possíveis caracteres / sequências iniciais / de treinamento são irrelevantes.)
Existem trechos para gerar esta sequência disponível, mas acho que outras abordagens podem ser mais fáceis de jogar / mais adequadas para determinados idiomas.
Informe-nos como o seu programa funciona. Se você cruzar um algoritmo particularmente eficiente, convém mencionar isso também, pois isso permitirá plotar mais termos da sequência em menor tempo.
Primeiros casos de teste:
1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13
Mais casos de teste:
a(100) = 4
a(500) = 5
a(1000) = 55
a(5000) = 15
a(10000) = 585
Todos os termos até n=100000
estão disponíveis aqui: https://oeis.org/A229037/b229037.txt
Obrigado @ MartinBüttner pela ajuda e incentivo.
Respostas:
Python 2, 95 bytes
O principal truque é gerar os números que o novo valor deve evitar. Mantendo a sequência invertida até agora
l
, vejamos quais elementos podem formar uma progressão aritmética de três termos com o valor que estamos prestes a adicionar.Os outros números são os membros emparelhados
l
e cada segundo elemento del
, entãozip(l,l[1::2])
. Se esse par for,(b,c)
então a progressão aritmética(a,b,c)
acontece paraa=2*b-c
. Depois de gerar o conjunto dea
's para evitar, o código pega o mínimo do complemento, imprime e anexa à lista. (Na verdade, o cálculo é feito com números diminuídos em 1 e impressos em 1 mais alto, pararange(n)
servir como um universo de candidatos.)fonte
Mathematica, 95 bytes
Certamente não é a abordagem mais eficiente, mas isso é realmente bastante eficiente, comparado com os algoritmos que eu tentei na página OEIS.
Em vez de verificar todos os valores proibidos para cada s (n) quando chegamos lá, estou usando uma abordagem baseada em peneiras. Quando encontramos um novo valor s (n) , verificamos imediatamente quais valores isso proíbe m> n . Depois resolvemos os s (n + 1) procurando o primeiro valor que não era proibido.
Isso pode ser ainda mais eficiente alterando a condicional
--i>0
para2n-#<=--i>0
. Nesse caso, evitamos verificar valores proibidos para n maior que a entrada.Para uma versão um pouco mais legível, iniciei com esse código, que armazena os resultados
max
em uma funçãof
e, em seguida, jogamos na função pura de uma linha acima:fonte
Haskell,
90,89,84, 83 bytesProvavelmente pode ser jogado mais, mas isso ainda é um
começotentativa :Ungolfed:
Esta é uma implementação simples que retorna '0' fora dos limites. Então, para cada valor possível, verifica que, para todos os k <= n e dentro dos limites, [x, a (xk), a (x-2k)] não é uma sequência aritmética.
Limite superior da complexidade do tempo (usando o fato da página OEIS de que a (n) <= (n + 1) / 2:
Não tenho certeza de quão bom é esse limite, pois o cálculo dos primeiros valores de 1k de 't' e o uso de um modelo linear nos logs dos valores deram appx. O (22 ^ n), com valor de p <10 ^ (- 1291), caso isso importe.
Em um nível de implementação, compilando com '-O2', levou ~ 35 minutos para calcular os 20 primeiros valores.
fonte
Braquilog ,
3331 bytesExperimente online!
Caso seja importante: o golfe de 2 bytes foi possível graças a um recurso que eu solicitei depois de trabalhar nesse desafio.
Explicação
Geramos iterativamente a sequência como uma lista em ordem inversa, por exemplo
[2,2,1,1,2,1,1]
, e a revertemos no final.Existem alguns predicados aninhados aqui. Vamos vê-los de dentro para fora. O primeiro
ġh₃hᵐs₂ᶠ-ᵐ=
, pega uma subsequência candidataa(n),a(n-1),...,a(0)
e determina sea(n),a(n-k),a(n-2k)
é uma sequência aritmética para algunsk
.Por exemplo, com entrada de
[1,2,1,1,2,1,1]
:O próximo predicado para fora,,
~b.hℕ₁≜∧.¬{...}∧
insere uma subsequênciaa(n-1),a(n-2),...,a(0)
e gera a próxima maior subsequênciaa(n),a(n-1),a(n-2),...,a(0)
.Finalmente, o predicado principal
;Ė{...}ⁱ⁽↔
pega um número de entrada e gera muitos termos da sequência.fonte
Ruby , 71 bytes
Experimente online!
Gera todos os valores proibidos, depois pega o complemento dessa matriz em (1..n) e pega o primeiro valor do resultado. Isso significa que estou assumindo que,
a[n] <= n
para todos os n, que é facilmente comprovado usando indução (se os primeiros termos n / 2 são todos inferiores a n / 2, não pode haver uma progressão aritmética levando a n).O truque sintático aqui também é levemente interessante:
*a
é usado para inicializar uma matriz de argumentos adicionais (que seriam ignorados se passássemos por alguma) e, em seguida,a.fill
modifica a matriz de argumentos e a devolve implicitamente.fonte
a[s-o]
ea[s-2*o]
, você pode usara[s-=1]
ea[s-o]
APL (Dyalog Extended) , SBCS de 37 bytes
Muito obrigado a Adám por sua ajuda ao escrever e jogar esta resposta no The APL Orchard , um ótimo lugar para aprender a língua APL. Experimente online!
Edit: -6 bytes graças a Adám
Explicação
APL (Dyalog Unicode) ,
433938 bytes SBCSAqui está uma solução mais rápida, mas menos eficiente, que pode ser calculada
⍺(10000)
em alguns segundos.Experimente online!
fonte
MATLAB,
156147 bytesEu finalmente comecei a jogar isso um pouco:
Ungolfed:
A entrada é lida no STDIN e a impressão é feita automaticamente com o
ans=
material anexado. Espero que isso se qualifique como saída "razoável".Esta é também uma solução à base de peneiro: a variável
s(i,:)
mantém o controle dos valores de sequência que são proibidos paraa(i)
. Otry-catch
bloco é necessário para tratar o caso de umas
matriz vazia (ou seja, zero completo) : nesse caso, o menor valor de1
já é permitido.No entanto, a necessidade de memória (ou tempo de execução?) Fica bastante bagunçada acima
N=2000
. Então, aqui está uma solução mais eficiente e não competitiva:Nesta implementação, a
s
matriz novamente contém valores proibidos, mas de uma maneira bem ordenada, sem nenhum bloco zero (que está presente na versão concorrente). O vetor de índicei
acompanha o número de vetores proibidos ems
. À primeira vista, as células seriam ótimas para rastrear as informações armazenadass
, mas elas seriam lentas e não podíamos indexar várias delas ao mesmo tempo.Um recurso desagradável do MATLAB é que, embora você possa dizer
M(1,end+1)=3;
e expandir automaticamente uma matriz, você não pode fazer o mesmo com a indexação linear. Isso meio que faz sentido (como o MATLAB deve saber o tamanho da matriz resultante, na estrutura da qual deve interpretar os índices lineares?), Mas ainda me surpreendeu. Esta é a razão da linha supérfluas(N,max(i(j))) = 0;
: isso expandirá as
matriz para nós sempre que necessário. A estimativa do tamanho inicialN*0.07+20
vem de um ajuste linear para os primeiros elementos, a propósito.Para testar o tempo de execução, também verifiquei uma versão ligeiramente modificada do código, onde inicializei a
s
matriz para ter tamanhoN/2
. Para os primeiros1e5
elementos, isso parece ser um palpite muito generoso, por isso removi a etapa de expansãos
mencionada no parágrafo anterior. Juntos, isso implica que o código será mais rápido, mas também menos robusto em altíssimos níveis.N
(já que não sei como é a série).Então, aqui estão alguns tempos de execução, comparando
Eu as medi no R2012b, utilizando o máximo de 5 execuções dentro de uma definição de função nomeada
tic/toc
.N=100
:0.011342 s
0.015218 s
0.015076 s
N=500
:0.101647 s
0.085277 s
0.081606 s
N=1000
:0.641910 s
0.187911 s
0.183565 s
N=2000
:5.010327 s
0.452892 s
0.430547 s
N=5000
:2.021213 s
1.572958 s
N=10000
:6.248483 s
5.812838 s
Parece que a
v3
versão é significativamente, mas não surpreendentemente mais rápida. Não sei se um elemento de incerteza (para muito grandeN
) vale o pequeno aumento no tempo de execução.fonte
M=1;M(end+1)=2;
funciona perfeitamente bem para mim?M=rand(2); M(end+1)=2
vez disso :)Jelly ,
2419 bytesEsta é a minha primeira resposta Jelly em um bom tempo. Feliz por estar de volta.
Esta é uma porta da minha resposta APL que por si só é uma adaptação de muitos dos algoritmos usados aqui. A principal diferença é que esse índice é 0.
Editar: -5 bytes graças a Jonathan Allan.
Experimente online!
Explicação
fonte
ḟ
fará tão bem quantoœ-
salvar um byte“”
com a1
saída de uma representação Jelly de uma lista de um programa completo, economizando mais um.Œœị@2
pode ser jogado paraḊm2
salvar dois.L‘R
pode ser jogado paraŻJ
salvar um.ES6, 114 bytes
Retorna uma matriz dos primeiros n elementos da sequência, para que os índices sejam 1 fora da versão não destruída abaixo. Eu usei a abordagem da peneira. Esta versão fica mais lenta após cerca de n = 2000; uma versão anterior evitava ler o início da matriz, o que significava que não diminuía a velocidade até cerca de n = 2500. Uma versão mais antiga usava a matriz de peneiras como uma lista de valores proibidos, em vez de uma matriz booleana cujos valores eram proibidos; isso pode chegar a n = 5000 sem suar a camisa. Minha versão original tentou usar máscaras de bits, mas isso não ajudou em nada (e também era muito tempo, com 198 bytes).
A versão não tão lenta como esta:
fonte