Os números quadrados escritos em binário são uma linguagem comum?

Estou tendo problemas para tentar determinar se todos os números quadrados (1, 4, 9, 16, ...) escritos em formato binário (1, 100, 1001, ...) são uma linguagem comum.

Após algumas tentativas de encontrar um padrão comum desses números, descobri que, para qualquer número quadrado $n^2$, $n^2 mod 4$é igual a 0 ou 1 e, portanto, sou capaz de desenhar um gráfico do DFA com 4 estados para reconhecer esse idioma. Mas, aparentemente, o DFA que eu desenhei realmente reconhece um superconjunto da linguagem de números quadrados em questão. Eu estou preso aqui.

Alguém poderia me dar algumas pistas sobre esse problema? Se não é um idioma comum, como devo provar?

Também estou muito interessado em saber como devo abordar esse tipo de pergunta da melhor maneira no futuro. Eu sei que em muitos casos, se tivermos a intuição de que os autômatos precisam acompanhar o que já foi visto (como$a^i b^i$), há um estado indeterminado necessário para o cálculo dos autômatos, portanto, não é finito ou regular. Podemos então usar o lema de bombeamento para provar que não é regular. No entanto, não sei dizer se esse idioma ainda é regular, então não tenho uma ideia do que fazer a seguir.

Obrigado!

Aqui está uma solução de alta tecnologia. Denotam seu idioma por . Szalay mostrou que A partir daqui, é muito fácil mostrar que não é regular, reduzindo para .$L$

Bem, esta é a terceira vez que reescrevo esta resposta. O usuário Yuval Filmus apontou dois erros muito bobos que cometi nas duas versões anteriores.

Bem, finalmente encontrei uma solução simples para o problema. Eu acho que funciona.

Primeiro, temos essas palavras desse tipo:

$1(00)^p1(00)^p001$

São números quadrados.

Prova:

Procurei informações sobre números quadrados e, em seguida, descobri "números octogonais centralizados", que são números formados por camadas de múltiplos de oito, mas não a primeira. A primeira camada é uma, a segunda oito, a terceira dezesseis e assim por diante.

Portanto, cada camada tem um "oito" a mais que a anterior. O número de oito em um número octogonal centralizado pode ser calculado usando a fórmula de Gauss:

$\frac{n^2 + n}{2}$

Em seguida, multiplicamos por oito e adicionamos um, porque a primeira camada é apenas um ponto.

$\frac{8(n^2 + n)}{2}+1$

Simplyfying:

$4(n^2 + n) + 1$

Essa fórmula nos fornece os números quadrados ímpares para cada n.

Vou calcular a fórmula para o número quatro e todas as potências de quatro.

Primeiro, quadrado o número, isso simplesmente dobra os zeros do número. Em seguida, adicionamos o número ao produto. Isso coloca um "um" na posição a partir da direita. é o comprimento da palavra binária.$\lceil|n|/2\rceil$$|n|$

No momento, temos palavras desta forma:

$1(00)^p1(00)^p0$

Nós multiplicamos por quatro, isso simplesmente adiciona dois zeros no final do número. Finalmente, somamos um. Acabamos.

Bombeamento

Eu defino .$i=0$

Primeiro o caso fácil

Se deixarmos vazio, obteremos o número um e um ou mais zeros. Isso nos dá palavras com peso hamming dois (o número de unidades é dois). Existe apenas um número desigual com o peso de hamming dois, o número nove (o único número quadrado ímpar da forma 2n + 1 é 9, vi isso na wikipedia: veja aqui ). Como todos os números que estamos bombeando são maiores que nove, provamos esse caso.$x$

Caso difícil

Deixamos o primeiro "um" em seu lugar e tiramos apenas zeros. Podemos fazer zeros até .$p-1$

A palavra terá a seguinte aparência:

$10(00)^m1(00)^n001$ .

Onde e são números inteiros maiores ou iguais a um e$m$$n$$n > m$

Primeiro acredito que o número obtido é um quadrado, depois mostrarei que é falso:

Como sabemos que todos os números quadrados ímpares podemos obter com esta fórmula:

$4(n^2 + n) + 1$

Começamos a decompor o número, subtraímos um, este simples define o último como zero e, depois, dividimos por quatro, isso remove dois zeros no final da palavra binária.

Então teremos palavras assim:

$10(00)^m1(00)^n0$ , e são números inteiros maiores ou iguais a um e . Essas palavras são um prefixo da palavra completa.$n$$m$$n > m$

Como acreditamos que essa cadeia faz parte de um número quadrado, a palavra teve que ser formada pela seguinte fórmula:

$(n^2 + n)$

$n$ não pode ser ainda

Veremos novamente esta fórmula:

$n^2 + n$

Como acreditamos que as palavras que bombeamos são números quadrados. Chamamos as palavras que têm bombeado e temos que:$m$

$m = n^2 + n$

Além disso, temos que pode ser representado como a soma de dois números binários, e , cada um deles é uma potência de dois. E nós temos que e$m$$m_1$$m_2$$\sqrt{m_1} < m_2$$m_1 > m_2$

A primeira coisa que notamos é que deve ser menor que . Isso ocorre porque é maior que a raiz quadrada de , se for igual a , então será maior que .$n$$m_2$$m_2$$m_1$$n$$m_2$$n^2$$m$

Agora, quando esquadrinhamos um número binário par, temos que o número ao quadrado possui "mais zeros" à direita do primeiro "um" que o número original. Então "o mais à direita" dentro de está à esquerda do "mais à direita" dentro de . Se adicionarmos a , temos que "o mais à direita" dentro de é o "mais à direita" em . Como é menor que . Temos que o "mais à direita" dentro de está à direita do "mais à direita" em . Portanto .$n^2$$n$$n$$n^2$$n^2 + n$$n$$n$$m_2$$n^2 + n$$m$$m \neq n^2 +n$$n^2 + n = m$chegamos a uma contradição e, portanto, não pode ser mesmo.$n$

$n$ não pode ser desigual

Novamente, temos que é um número feito adicionando a , então$m$$n$$n^2$$m = n^2 + n$

Então notamos que ; Isto é porque:$(n + 1)^2 - (n + 1) = n^2 + n$

$(n + 1)^2 - (n + 1) = n^2 + 2n + 1 -n -1$ ;

E depois:

$(n + 1)^2 - (n + 1) = n^2 + n$ .

Outra maneira de ver isso é imaginar como um quadrado com lados de comprimento . Este quadrado é formado por quadrados menores do tamanho um. Então, quando adicionamos quadrados de tamanho um ao quadrado anterior, o quadrado anterior agora é um retângulo cujos lados são e . Agora, podemos imaginar como outro quadrado com lados de comprimento . Este quadrado também é formado por quadrados menores do tamanho um. Se removermos quadrados, temos um retângulo de lados e .$n^2$$n$$n$$n$$n+1$$(n + 1)^2$$n + 1$$n + 1$$n$$n+1$

Temos que é um número par e a prova segue o mesmo de antes para todos os números ímpares menores que$n + 1$$n$$m_2 - 1$

Novamente, quando quadrado um número par binário, temos que o número tem "mais zeros" à direita do primeiro "um" que o número original. Portanto, "o mais à direita" dentro está à esquerda do "mais à direita" dentro de . Se subtrairmos a , temos que "o mais à direita" dentro de é o "mais à direita" em . Como é menor que . Temos que o "mais à direita" dentro de está à direita do "mais à direita" em .$(n + 1)^2$$n + 1$$n + 1$$(n + 1)^2$$n^2 + n$$n + 1$$n + 1$$m_2$$n^2 + n$$m$

Se .$n = m_2 - 1$

Novamente, temos que . Como ( ao quadrado) é um número que é uma potência de dois, ele possui apenas um único "um" inicial e depois zera. Quando subtraímos a , estamos girando todos os zeros à esquerda do dígito mais à esquerda de dentro de em "uns" e o número resultante não é como as palavras que estamos bombeando, deve haver pelo menos um "zero de separação" entre esses.$n^2 + n = (n + 1)^2 - (n + 1)$$m_2^2$$m_2$$m_2$$m_2^2$$m_2$$m_2^2$

Portanto . Mas desde que nós dissemos que chegamos a uma contradição e, portanto, não pode ser desigual.$m \neq n^2 +n$$n^2 + n = m$$n$

Como não pode ser par ou desigual, temos que não existe como um número inteiro. Portanto, as palavras que bombeamos não são o produto da fórmula para números quadrados ímpares. Como todas as palavras que estamos escrevendo são ímpares, elas não podem ser números quadrados.$n$$n$