Um número inteiro positivo k
é um número Loeschiano se
k
pode ser expressa comoi*i + j*j + i*j
parai
,j
inteiros.
Por exemplo, os primeiros números loeschianos positivos são: 1
( i=1
, j=0
); 3
( i=j=1
); 4
( i=2
, j=0
); 7
( i=2
, j=1
); 9
( i=-3
, j=3
); ... Observe que i
, j
para um dado, k
não são únicos. Por exemplo, 9
pode também ser gerado com i=3
, j=0
.
Outras caracterizações equivalentes desses números são:
k
pode ser expresso comoi*i + j*j + i*j
parai
,j
inteiros não negativos. (Para cada par de números inteirosi
,j
há um par de números inteiros não negativos que fornece o mesmok
)Existe um conjunto de
k
hexágonos contíguos que formam um mosaico em uma grade hexagonal (veja ilustrações parak = 4
e parak = 7
). (Devido a essa propriedade, esses números encontram aplicação nas redes de comunicação celular móvel .)Veja mais caracterizações na página OEIS da sequência.
O desafio
Dado um número inteiro positivo , produza um resultado verdade, se for um número Loeschiano , ou um resultado falso, caso contrário.
O programa ou função deve manipular (digamos em menos de um minuto) entradas até 1000
ou até limitações de tipo de dados.
Código de golfe. Vitórias mais curtas.
Casos de teste
Os seguintes números devem gerar um resultado verdadeiro:
1, 4, 7, 12, 13, 108, 109, 192, 516, 999
Os seguintes números devem gerar um resultado falso:
2, 5, 10, 42, 101, 102, 128, 150, 501, 1000
fonte
i, j non-negative integers
ou9 (i=-3, j=3)
- qual é?Respostas:
Geléia ,
119 bytesExperimente online! ou verifique todos os casos de teste .
fundo
Nos resultados elementares da forma quadrática binária a² + ab + b² , o autor prova o seguinte teorema sobre números de Löschian.
Como observado na página relevante do OEIS , como todos os números inteiros são congruentes a 0 , 1 ou 2 do módulo 3 , o número 3 é o único primo que é congruente a 0 , e todos os números da forma (6k + 1) são congruentes a 1 , o teorema pode ser afirmado alternativamente da seguinte forma.
Um número inteiro não negativo n é um número Löschiano se, e somente se, todos os fatores primos de n que são congruentes a 2 módulo 3 tiverem expoentes pares.
Como funciona
fonte
Retina ,
6663454336 bytesApesar do título dizer Retina, este é apenas um regex .NET simples que aceita representações unárias de números Loeschianos.
As entradas 999 e 1000 demoram menos de um segundo.
Experimente online! (A primeira linha permite um conjunto de testes separado por avanço de linha, e as próximas duas cuidam da conversão para unárias por conveniência.)
Explicação
A solução é baseada na classificação de que a entrada pode ser escrita como
i*i + j*(i + j)
positivai
e não negativaj
(já que não precisamos lidar com entrada0
), e essan*n
é apenas a soma dos primeirosn
números inteiros ímpares. Jogar golfe foi um exercício interessante nas referências futuras.Uma "referência direta" é quando você coloca uma referência retroativa dentro do grupo a que se refere. É claro que isso não funciona quando o grupo é usado pela primeira vez, pois ainda não há nada a ser referenciado novamente, mas se você colocar isso em um loop, a referência anterior receberá a captura da iteração anterior a cada vez. Por sua vez, vamos criar uma captura maior a cada iteração. Isso pode ser usado para criar padrões muito compactos para coisas como números triangulares, quadrados e números de Fibonacci.
Como exemplo, usando o fato de que os quadrados são apenas somas dos primeiros
n
números inteiros ímpares, podemos combinar uma entrada quadrada como esta:Na primeira iteração,
..\1
não pode funcionar, porque\1
ainda não tem um valor. Então começamos com a^.
captura de um único personagem em grupo1
. Nas iterações subseqüentes,^.
não corresponde mais devido à âncora, mas agora..\1
é válido. Ele corresponde a mais dois caracteres que a iteração anterior e atualiza a captura. Dessa forma, combinamos números ímpares crescentes, obtendo um quadrado após cada iteração.Agora, infelizmente, não podemos usar essa técnica como está. Após a correspondência
i*i
, precisamos obtê-loi
também, para que possamos multiplicá-loj
. Uma maneira simples (mas longa) de fazer isso é usar o fato de que a correspondênciai*i
exigei
iterações, para que capturemos asi
coisas em grupo1
. Agora poderíamos usar grupos de balanceamento para extrair issoi
, mas como eu disse, isso é caro.Em vez disso, descobri uma maneira diferente de escrever essa "soma de números inteiros ímpares consecutivos" que também resulta
i
em um grupo de captura no final. Claro que oi
número ímpar é justo2i-1
. Isso nos permite aumentar a referência direta apenas 1 em cada iteração. Essa é essa parte:Isso
()
apenas envia uma captura vazia para o grupo1
(inicializandoi
para0
). Isso é praticamente equivalente ao da^.|
solução simples acima, mas usar|
neste caso seria um pouco mais complicado.Então nós temos o loop principal
(\1(?<1>.\1))
.\1
corresponde ao anteriori
,(?<1>.\1)
em seguida, atualiza grupo1
comi+1
. Em termos do novoi
, acabamos de combinar2i-1
personagens. Exatamente o que precisamos.Quando terminamos, combinamos algum quadrado
i*i
e o grupo1
ainda possuii
caracteres.A segunda parte está mais próxima da correspondência quadrada simples que mostrei acima. Vamos ignorar a referência anterior
1
por enquanto:É basicamente o mesmo que
(^.|..\4)*
, exceto que não podemos fazer uso^
porque não estamos no início da string. Em vez disso, usamos um condicional, para corresponder ao adicional.\1
somente quando já usamos o grupo4
. Mas, na verdade, isso é exatamente o mesmo. Isso nos dáj*j
.A única coisa que falta é o
j*i
termo. Combinamos isso com oj*j
uso do fato de que aj*j
computação ainda fazj
iterações. Portanto, para cada iteração, também avançamos o cursori
com\1
. Só precisamos ter certeza de não escrever isso em grupo4
, porque isso interferiria na correspondência de números ímpares consecutivos. É assim que chegamos ao:fonte
CJam (
1615 bytes)Demonstração online
Este é um bloco (uma "função anônima") que recebe entrada na pilha e sai
0
ou1
na pilha. Ele usa a caracterização de que um número é Loeschiano se não tiver um fator primo igual a 2 mod 3 com multiplicidade ímpar.Agradecemos a Dennis pela economia de um byte.
fonte
Python 2, 56 bytes
fonte
Haskell, 42 bytes
Exemplo de uso:
f 501
->False
.Tenta todas as combinações de
i
partir0
parak
ej
desde0
ai
.or
retornaTrue
se a igualdadek==i*i+j*j+i*j
é válida para pelo menos uma das combinações.O @flawr encontrou uma versão ligeiramente diferente com a mesma contagem de bytes:
fonte
or
, legal =) Talvez você tenha uma idéia de como jogar este fraseado alternativof k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]
:?Java 8, 81 bytes
implementação simples e ingênua. coincidentemente o mesmo código que o C #, mas usa em
->
vez de=>
.fonte
;
. DROGA!i
ouj
.Python, 67 bytes
https://repl.it/Cj6x
fonte
Geléia ,
15141312 bytes1 byte graças a milhas.
Experimente online!
Verifique as caixas de teste menores .
Um conselho ao testar números grandes (maiores que 50): não.
Verdade é um número positivo. Falsey é zero.
Explicação
fonte
Água-viva ,
5643412928 bytes2 bytes graças ao Zgarb
Experimente online!
Um garfo da minha resposta Jelly .
fonte
MATL ,
1413 bytesExperimente online! Ou verifique todos os casos de teste .
Saídas
1
ou0
.Explicação
fonte
Python, 49 bytes
Usa a forma quadrática equivalente dada no OEIS de
n == 3*i*i+j*j
. Verifique sen-3*i*i
é um quadrado perfeito para qualquer umi
, pegando sua raiz quadrada e verificando se é um número inteiro, ou seja, igual a 0 módulo 1. Observe que o Python calcula exatamente as raízes quadradas dos quadrados perfeitos, sem erro de ponto flutuante. O+0j
faz com que seja um número complexo para evitar um erro na raiz quadrada de um negativo.fonte
C (gcc),
7169 bytesfonte
i,j,r;f(n){for(r=i=n+1;i--;)for(j=n;j--;)r*=n!=i*i+j*j+i*j;return!r;}
.i
ouj
.i
ej
.k
, mas nãoi
ej
. Dê uma olhada nos exemplos.k
pode ser expresso comoi*i + j*j + i*j
para números inteirosi, j
não negativos ". Você olha mais de perto.C #,
848281 bytesUma solução ingênua. 1 = verdadeiro, 0 = falso
fonte
VBA,
6867 bytesPesquisa ingênua, começando a desacelerar levemente para n = 1000. O Excel reconhece retorno zero como falso, todos os outros retornos como verdade.
Note-se que a investigação de negativo i e j não é necessário, uma vez determinado i> j> = 0 :
(o mesmo resultado que para i e j )
(se um for negativo, não importa qual) e, em seguida,
E uma vez que ambos (i, j) e j são não-negativo, qualquer geração de números Loeschian envolvendo um número negativo pode ser conseguido usando números não-negativos.
Salvo um byte,
Next:Next
->Next b,a
graças a Taylor Scott.fonte
i
ouj
.Next:Next
paraNext b,a
:End Function
no final da sua soluçãoJavascript (usando biblioteca externa - Enumerável) (63 bytes)
Link para a biblioteca: https://github.com/mvegh1/Explicação do código numeroso: Crie um intervalo de números inteiros de 0 a k (chame isso de intervalo "i") e teste se algum "i" satisfaz um determinado predicado. Esse predicado cria um intervalo de 0 a k (chame isso de "j") e testa se algum "j" satisfaz um determinado predicado. Esse predicado é a fórmula loeschiana
fonte
Perl 6 ,
52 5150 bytesExplicação:
Teste:
fonte
i
ouj
.(0..$_ X 0..$_)
produz uma lista vazia se$_
for menor que0
, portanto, não há necessidade de verificar se há negativosi
ej
porque eles nunca serão negativos. Como é suposto produzir apenasTrue
um número loeschiano positivo, não preciso fazer nada de especial pelo caso negativo.9 = (3*3)+(-3*-3)+(3*-3)
é um loeschiano positivoi=3, j=-3
; MAS eu li demais que todo número Loeschiano não é negativoi
ej
. Portanto, não é necessário procurar números negativos. Então, na verdade, poderíamos excluir esses comentários. Desculpe por incomodar; minha culpa.{grep ->(\i,\j){$_==i*i+j*j+i*j},(-$_..$_ X -$_..$_)}(9)
resultar em((-3,0),(-3,3),(0,-3),(0,3),(3,-3),(3,0))
. Honestamente, eu provavelmente apenas o adaptei de outras respostas.PowerShell v2 +,
635655 bytesRecebe entrada
$k
, volta duas vezes para cima (loop externo$i = 0 to $k
, loop interno$j = 0 to $i
), cada iteração gera o resultado dei*i + j*j + i*j
(abreviado parai*(i+j) + j*j
). Esses resultados são encapsulados em parênteses e passados como uma matriz para-eq$k
. Isso atua como um filtro para selecionar apenas elementos que sejam iguais à entrada. Emite um valor diferente de zero (o número anterior) para verdade ou nada (vazio) para falsey. Processa1000
em cerca de 15 segundos na minha máquina.Casos de teste
fonte
Perl, 54 + 1 (
-n
sinalizador) = 55 bytesNecessidades
-n
e-M5.010
sinalizadores para executar:Produz alguns materiais se o número for um número Loeschiano e nada de outra maneira.
Essa implementação é bastante chata, então aqui está outra, de 87 bytes, baseada em regex, apenas para os olhos:
Cuidado com este, pois o retorno usa muita memória; portanto, não tente testar números muito grandes! (especialmente números que não são loeschianos)
fonte
Dyalog APL , 19 bytes
Verifica se k ∊ ( i + j ) ² - ij , para qualquer 0 ≤ i , j ≤ k .
⊢
é k∊
um membro de∘.
todas as combinações de×
i vezes j-⍨
subtraídas do2*⍨
quadrado de+
i mais j⍨
para todos os i e j em0,
zero prefixados aos⍳
números inteiros 1 a k1000 demora 3,3 segundos no meu M540 e menos ainda no TryAPL .
fonte
Matlab,
5352 bytesPesquisa simples sobre todas as possibilidades.
Gera um array vazio como falso e um vetor não vazio como valor de verdade.
Considerando a matriz all-zeros como falsy e a matriz not-all-zeros como verdade, podemos nos livrar da
find
função que resulta na solução de4746 bytes :Um byte salvo graças a @flawr
fonte
(a+b).^2-a.*b==n
é mais curto.C, 66 bytes
Ligue
f()
com o número para testar. A função retorna o número de soluções encontradas.Experimente em ideone .
fonte
Mathematica, 44 bytes
Função sem nome, tendo um número inteiro como entrada e retornando
True
ouFalse
. O comando0~Range~#~Tuples~2
cria todos os pares ordenados de números inteiros entre0
e a entrada#
. A função(+##)^2-##&
calcula o quadrado da soma de seus argumentos menos o produto de seus argumentos; quando chamado em dois argumentosi
ej
, é exatamentei^2+j^2+ij
como desejado. Portanto, essa função é chamada em todas as tuplas eMemberQ[...,#]
verifica se a entrada é um dos valores resultantes.fonte
ASP, 39 + 4 = 43 bytes
Saída: o problema é satisfatório se k for Loeschiano.
Conjunto de respostas A programação é uma linguagem lógica, semelhante ao prólogo. Eu uso aqui a implementação do Potassco , clingo .
A entrada é obtida dos parâmetros (
-ck=
tem 4 bytes). Exemplo de chamada:Amostra de saída:
Tentei com 1000:
Amostra de saída:
Você pode experimentá-lo no seu navegador ; infelizmente, esse método não trata de sinalizadores de chamada, então você precisa adicionar a linha
#const k=999
para fazê-la funcionar.Código não explicado e explicado:
fonte
PHP, 70 bytes
recebe entrada do argumento da linha de comando; sai com
1
para o número Loeschiano, com0
mais.Corra com
-nr
.demolir
fonte