#oeis

Sequência de Kolakoski: {A sequência consiste apenas de 1s e 2s {a(1) = 1 {a(n) é o comprimento da n-ésima execução 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, . . . Comece com a(1) = 1. Por definição da sequência, isso significa que a primeira sequência tem comprimento 1, então deve ser um único 1, e a(2) = 2. Assim, a segunda sequência (que começa com este 2) deve ter comprimento 2, então o terceiro termo também deve ser a(3) = 2, e o quarto termo não pode ser um 2, então deve ser a(4) = 1. Como a(3) = 2, a terceira sequência deve ter comprimento 2, então deduzimos a(5) = 1, a(6) = 2 e assim por diante. - Labos Elemer , corrigido por Graeme McRae Nota histórica: a sequência talvez fosse melhor denominada sequência de Oldenburger-Kolakoski, visto que foi discutida por Rufus Oldenburger em 1939; veja os links. - Clark Kimberling , 06 de dezembro de 2012. No entanto, para evitar confusão, esta sequência será conhecida no OEIS como sequência de Kolakoski. É indesejável que algumas entradas se refiram à sequência de Oldenburger-Kolakoski e outras à sequência de Kolakoski. - NJA Sloane , 22 de novembro de 2017 É um problema ainda não resolvido demonstrar que a densidade de 1s é igual a 1/2. Um problema mais simples é construir uma bijeção combinatória entre o conjunto de posições dos 1s e o conjunto de posições dos 2s. - Gus Wiseman , 1 de março de 2016 A sequência é livre de cubos e todas as subpalavras quadradas têm comprimentos que são um de 2, 4, 6, 18 e 54 (ver A294447 ) [Carpi, 1994]. Esta é uma sequência fractal: substitua cada trecho pelo seu comprimento e recupere a sequência original. - Kerry Mitchell , 08 de dezembro de 2005 Kupin e Rowland escrevem: Usamos um método de Goulden e Jackson para limitar freq_1(K), a frequência limite de 1 na palavra de Kolakoski K. Provamos que |freq_1(K) - 1/2| <= 17/762, assumindo que o limite existe, e estabelecemos o limite semirrigoroso |freq_1(K) - 1/2| <= 1/46. - Jonathan Vos Post , 16 de setembro de 2008 Conjectura-se que freq_1(K) seja 1/2 + O(log(K)) (veja o link do PlanetMath). - Jon Perry , 29 de outubro de 2014 Conjectura: Considerando a sequência em palavras de comprimento 10, por exemplo, lotes 1-10, 11-20, etc., então só pode haver 4, 5 ou 6 '1's em cada lote. - Jon Perry , 26 de setembro de 2012 De Jean-Christophe Hervé , 04 de outubro de 2014: (Início) A sequência não contém palavras da forma ababa, porque isso implicaria o impossível 111 (1 b, 1 a, 1 b) em algum lugar anterior. Isso demonstra a conjectura feita por Jon Perry : mais de 6 1's ou 6 2's em uma palavra de 10 elementos exigiria algo como aabaabaaba, o que implicaria o impossível 12121 antes (a palavra aabaababaa também é impossível por causa de ababa). A observação sobre os sextetos abaixo mostra inclusive que o número de 1's em qualquer 9-tuplo é sempre 4 ou 5. Existem apenas 6 trios que aparecem na sequência (112, 121, 122, 211, 212 e 221); e, pelo argumento anterior, apenas 18 sextetos: os 6 trios duplos (112112, etc.); 112122, 112212, 121122, 121221, 211212 e 211221; e aqueles obtidos invertendo a ordem dos trios (122112, etc.). Quanto à densidade de 1s na sequência, esses 12 sextetos têm todos uma densidade de 1/2 de 1s, e os 6 trios duplos levam a uma palavra com essa densidade exata após a transformação pelas regras de Kolakoski, por exemplo: 112112 -> 12112122 (4 1s/8); Isso ocorre porque o segundo trio inverte a quantidade de 1s e 2s gerada pelo primeiro trio. Portanto, a sequência pode ser dividida em trios duplos de um lado, uma parte cuja transformação (que está na sequência) tem uma densidade de 1s de 1/2; e uma parte com os outros sextetos, que tem exatamente a mesma densidade de 1s.

A200000 Número de meandros que preenchem uma grade n x n, reduzido por simetria 1, 1, 0, 4, 42, 9050, 6965359, 26721852461, 429651752290375, 31194475941824888769, 9828395457980805457337560, 13684686862375136981850903785368, 83297108604256429529069019958551956425, 2226741508593975401942934273354241209226704830, 260577257822688861848154672171293101310412373160498171, 133631198381015786582155688877301469836628906260462969996612568, 299985729493560746632648983353916422875677601725131683097521792924081609

COMENTÁRIOS A sequência contabiliza os caminhos fechados distintos que visitam cada célula de uma rede quadrada n x n pelo menos uma vez, que nunca cruzam nenhuma aresta entre quadrados adjacentes mais de uma vez e que não se autointersectam. Caminhos relacionados por rotação e/ou reflexão da rede quadrada não são considerados distintos.a(1) e a(2) são os únicos dois termos iguais a 1? E a(3) é o único termo igual a 0? -

Daniel Forgues , 24 de novembro de 2011A resposta é sim: Existem vários padrões que podem ser generalizados facilmente para qualquer grade de tamanho n>3, por exemplo, #13 e #6347 dos gráficos para a(6) (resp. #24 ou #28 de a(5) para n ímpar). -

MF Hasler , 24 de novembro de 2011 LINKS

Tabela de n, a(n) para n=1..17.Dale Gerdemann,

Ilustração em vídeo para a(5) = 42OEIS Wiki,

Número de meandros que preenchem uma grade n por n (reduzido por simetria)Jon Wild,

Ilustração para a(4) = 4Jon Wild,

Ilustração para a(5) = 42Jon Wild,

Ilustração para a(6) = 9050 [Aviso: este é um arquivo grande!]Zhao Hui Du,

código-fonte em C++ para A200000 e A200749 EXEMPLO a(1) conta os caminhos que visitam a única célula da rede 1 X 1: existe um, o "ponto gordo".As 4 soluções para n=4, as 42 soluções para n=5 e as 9050 soluções para n=6 são ilustradas nos arquivos .png de apoio.

REFERÊNCIAS CRUZADAS Cf. A200749 (versão não reduzida por simetria).Cf.

A200893 (meandros em retângulos n x k em vez de quadrados, reduzidos por simetria).Cf.

A201145 (meandros em retângulos n x k, não reduzidos por simetria).Sequência no contexto:

A355124 A384687 A111829 *

A198209 A220774 A296683 Sequências adjacentes:

A199997 A199998 A199999 *

Para n = 1, há apenas um cômodo para procurar, então a(1) = 1.Para n = 2, o príncipe procura no quarto 1 na primeira noite. Se a princesa não estiver lá, significa que ela estava no quarto 2. Se o príncipe procurar no quarto 1 novamente, então ele certamente verá a princesa, pois ela precisa se mover do quarto 2 para o quarto 1 (ela não pode ficar no mesmo quarto). Portanto, a(2) = 2.Para n = 3, o príncipe procura no quarto 2 na primeira noite. Se a princesa não estiver lá, isso significa que ela estava no quarto 1 ou no quarto 3. Na segunda noite, ela deve ir ao quarto 2 e é lá que o príncipe a encontrará. Portanto, a(3) = 2.Para n = 4, uma solução que garante encontrar a princesa em a(4)=4 noites é procurar nos quartos (2,3,3,2).Para n = 5, uma solução que garante encontrar a princesa em a(5)=6 noites é procurar nos quartos (2,3,4,4,3,2).No caso geral para n >= 3, uma solução que garante o sucesso no número mínimo de noites é procurar quartos (2,3,...,n-1,n-1,...,3,2), então a(n) = 2*n - 4.

a(m^2*k+m) ≤ 2m+a(k+1), ∀ k > 0, m ≥ 2

EXEMPLO: Para n = 0 até n = 5, o mais rápido é mover n vezes 1 pedra da origem até o próximo buraco.Para n = 6, pode-se mover duas vezes três pedras três buracos adiante e, em seguida, três vezes duas pedras dois buracos "para trás", portanto a(6) = 2 + 3 = 5. Da mesma forma, para a(3*4 = 12) = 3 + 4 = 7 e a(4*5 = 20) = 4 + 5 = 9. No entanto, para números oblongos maiores, existem soluções melhores, e a(m*(m+1)) < 2m+1 para m > 4.