Contar somas de dois quadrados

45

Dado um número não negativo n, imprima o número de maneiras de expressar ncomo a soma de dois quadrados de números inteiros n == a^2 + b^2( OEIS A004018 ). Observe que ae bpode ser positivo, negativo ou zero, e sua ordem é importante. Menos bytes ganha.

Por exemplo, n=25dá 12porque 25pode ser expresso como

(5)^2  + (0)^2
(4)^2  + (3)^2
(3)^2  + (4)^2
(0)^2  + (5)^2
(-3)^2 + (4)^2
(-4)^2 + (3)^2
(-5)^2 + (0)^2
(-4)^2 + (-3)^2
(-3)^2 + (-4)^2
(0)^2  + (-5)^2
(3)^2  + (-4)^2
(4)^2  + (-3)^2

Aqui estão os valores até n=25. Tenha cuidado para que seu código funcione n=0.

0 1
1 4
2 4
3 0
4 4
5 8
6 0
7 0
8 4
9 4
10 8
11 0
12 0
13 8
14 0
15 0
16 4
17 8
18 4
19 0
20 8
21 0
22 0
23 0
24 0
25 12

Aqui estão os valores até n=100como uma lista.

[1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8, 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0, 12]

Curiosidades: a sequência contém termos arbitrariamente altos e o limite de sua média atual é π.

Entre os melhores:

Mostrar snippet de código

code-golf math combinatorics number-theory xnor
fonte
4
Espere o que?? "A sequência contém termos arbitrariamente altos e o limite de sua média atual é π."
Stewie Griffin
@StewieGriffin As duas declarações são consistentes. Considere a sequência 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... Cortando a sequência após qualquer número diferente de zero, a média até agora é 1. E, as execuções de 0 têm cada vez menos impacto posteriormente na sequência.
Xnor
5
Eu sei que é consistente. =) Eu verifiquei os 10.000 primeiros números quando publiquei o comentário. O que não entendo é: por que diabos isso é igual a Pi?
Stewie Griffin
29
@StewieGriffin A soma dos termos até N corresponde aos pontos (a, b) com a ^ 2 + b ^ 2 <= N. Estes são os pontos de treliça no círculo do raio sqrt (N), cuja área é πN.
Xnor
2
@xnor e lá vai a mágica :(
Andras Deak

Respostas:

19

Python ( 59 57 56 bytes)

lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))

Demonstração online

Como na minha resposta CJam, isso usa a inversão de Möbius e é executado em tempo pseudoquasilinear.

Obrigado ao Sp3000 pela economia de 2 bytes e ao feersum por 1.

Peter Taylor
fonte
1
Esses parênteses são irritantes.
lirtosiast
@ThomasKwa, conte-me sobre isso. O que realmente me surpreendeu, em uma das versões pelas quais passei no caminho para a primeira que publiquei, foi que -1**xé sempre -1. Eu esperava -1que fosse um token literal inteiro único, em vez de um unário de baixa precedência menos um seguido por um.
Peter Taylor
2
Parabéns pela recompensa! Seu código é mais curto do que qualquer coisa que eu criei. Sua solução é baseada em uma idéia matemática totalmente nova e inesperada, e me alegra que isso seja possível, mesmo em um desafio tão simples. O resultado inverso do Mobius é bastante bonito e tive o prazer de obter uma prova para Eu mesmo.
Xnor
1 byte pode ser salvo movendo a multiplicação por 4 para depois **x.
feersum 5/12/15
@PeterTaylor Você pode elaborar como seu algoritmo funciona / você pode me indicar um recurso? Não vejo bem como é possível aplicar a inversão de möbius ao problema do número de somas de suqares.
flawr
15

Mathematica, 13 bytes

Se os internos forem permitidos, é assim que se faz no Mathematica.

2~SquaresR~#&

Para 0 <= n <= 100

2~SquaresR~# & /@ Range[0, 100]

{1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0 , 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4 , 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8 , 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0 12}

DavidC
fonte
1
Porque é claro que o Mathematica tem um built-in para isso.
HyperNeutrino
14

Python 2, 44 bytes

f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2

É quase o mesmo que a solução do xsot (que é baseada na solução de Peter Taylor ), mas economiza 8 bytes, simplificando a maneira como os sinais são tratados.

Observe que, para um programa completo, podemos salvar 2 bytes na função sem incorrer em custos fora da função:

f=lambda n,x=1:x>n or(n%x<1)-f(n,x+2)/4<<2
print+f(input())

Dois bytes adicionais para um programa completo desta maneira:

n=input()
f=lambda x:x>n or(n%x<1)-f(x+2)/4<<2
print+f(1)

Pois n > 0existe uma solução muito legível de 40 bytes:

f=lambda n,x=1:n/x and(n%x<1)*4-f(n,x+2)
Mitch Schwartz
fonte
1
Parabéns por ganhar a recompensa! A subtração recursiva é uma maneira limpa e curta de expressar a soma alternada para divisores ímpares sem precisar extrair um sinal do próprio divisor. Além disso, agradeça a xsot por otimizar a solução de Peter Taylor para uma solução recursiva com manipulação inteligente de n = 0.
Xnor
12

Pitão, 13 bytes

/sM^^R2}_QQ2Q

Suíte de teste

/sM^^R2}_QQ2Q
                 Q = eval(input())
       }_QQ      Inclusive range from -Q to Q (all possible a and b)
    ^R2          Map to their squares
   ^       2     Form all pairs
 sM              Sum pairs
/           Q    Count occurances of Q
isaacg
fonte
Tarde, mas acho que você não precisa do último Q.
Erik the Outgolfer
12

J, 16 bytes

+/@,@:=+&*:/~@i:

Este é um verbo monádico (em outras palavras, uma função unária). Experimente online ou veja passar em todos os casos de teste .

Explicação

+/@,@:=+&*:/~@i:  Denote input by n
              i:  The array of integers from -n to n
           /~@    Take outer product wrt the following function:
       +           the sum of
        &*:        squares of both inputs
                  This results in a 2D array of a^2+b^2 for all a, b between -n and n
      =           Replace by 1 those entries that are equal to n, and others by 0
   ,@:            Flatten the binary matrix
+/@               Take its sum
Zgarb
fonte
11

Python 2, 69 55 53 52 bytes

f=lambda n,x=1:+(x>n)or(2-x%4)*(n%x<1)+f(n,x+2)/4<<2

Esta é uma função recursiva baseada na excelente solução de Peter Taylor .

xsot
fonte
1
Esta é uma grande melhoria. Mas ainda há uma maneira de torná-lo mais curto, e encorajo você a procurá-lo.
Xnor
1
@xnor Outro byte desativado. Espero que você não tenha mais truques nas mangas.
xsot
2
Eu não sei se eu deveria fazer uma resposta dele, é apenas a sua solução mais um truque: f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2. Além disso, acho que não nos preocupamos em exceder a profundidade de recursão máxima padrão?
Mitch Schwartz
1
@MitchSchwartz Eu acho que é uma melhoria incrível digna da recompensa e provavelmente a otimização final que o xnor tinha em mente.
Xsot # 9/15
1
@MitchSchwartz Sim, essa é a otimização em que eu estava pensando! E o /4<<2truque do xsot o torna mais curto do que eu tinha.
xnor
8

Julia, 40 bytes

n->n>0?4sum(i->(n-i^2)^.5%1==0,1:n^.5):1

Ungolfed:

function f(n)
  if n==0
    return 1           # Handle special case of n=0
  else
    m=0                # Start the counter at zero
    for i=1:sqrt(n)    # Loop over the values (i) whose squares are
                       # less than n (except zero)
      k=sqrt(n-i^2)    # Find k such that n=k^2+i^2
      if k==floor(k)   # if k is an integer, we've found a pair
        m+=4           # Add one for each of k^2+i^2, (-k)^2+(-i)^2, and the other two
      end
    end
    return m           # Return the resulting count
  end
end

Observe que o loop não inclui i==0, porque quando né um quadrado, ele já está incluído i=sqrt(n)e existem apenas quatro, e não oito, para esse formulário ( 0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2).

Glen O
fonte
7

CJam, 25 23 bytes

Zri:R#Ym*{Rf-Yf#:+R=},,

Esta é uma solução teórica que requer tempo e memória O (9 n ) para a entrada n .

Ao custo de um byte extra - para um total de 24 bytes - podemos reduzir a complexidade para O (n 2 ) :

ri:R)Y*Ym*{Rf-Yf#:+R=},,

Experimente online!

Como funciona

Ou

Z                  Push 3.
 ri:R              Read an integer from STDIN and save it in R.
     #             Compute 3**R.

ou

ri:R               Read an integer from STDIN and save it in R.
    )Y*            Add 1 and multiply by 2.

Então

Ym*                Take the second Cartesian power, i.e., compute all pairs.
   {          },   Filter the pairs:
    Rf-              Subtract R from each.
       Yf#           Square the differences.
          :+         Add the squares.
            R=       Compare with R.
                   If = pushed 1, keep the pair.
                ,  Count the kept pairs.
Dennis
fonte
E em uma economia de um byte é possível obter a complexidade para baixo para O (n)
Peter Taylor
Sim eu vi. Isso é incrível.
Dennis
7

CJam ( 25 24 22 21 bytes)

{:X!X{X\2*)%!4*\-}/z}

Demonstração online

Isso é executado em tempo pseudoquasilinear * e usa a declaração do OEIS que

A transformação de Moebius é a sequência do período 4 [4, 0, -4, 0, ...]. - Michael Somos, 17 de setembro de 2007

A entrada 0é obviamente um caso especial (as transformações e aniquiladores da Möbius não combinam bem), mas acabou custando apenas um caractere.

* Pseudo- porque é quase linear no valor da entrada, não no tamanho da entrada; quase porque faz Theta(n)operações em números inteiros de tamanho na ordem de n; uma boperação de mod de bits deve levar b lg btempo; portanto, no geral, isso leva Theta(n lg n lg lg n)tempo.

Peter Taylor
fonte
6

Japonês , 42 37 33 bytes

Japt é uma versão abreviada de Ja vaScri pt . Intérprete

V=Un oU+1;Vr@X+(Vf_p2 +Y*Y¥U)l ,0

Como funciona

           // Implicit: U = input number
V=Un oU+1  // Set variable V to range(-U, U+1). Ends up like [-U,-U+1,...,U-1,U]
Vr@    ,0  // Reduce each item Y in V with this function, starting at 0:
X+(     l  //  Return the previous value X + the length of:
Vf_p2      //   V filtered by items Z where Z*Z
+Y*Y==U)   //    + Y*Y equals U.
           // This ends up as the combined length of all fitting pairs of squares.
           // Implicit: return last expression

Talvez exista uma técnica melhor; sugestões são bem vindas.

ETHproductions
fonte
6

Python 3, 68 61 60 bytes

lambda n:0**n+4*sum(i**.5%1+(n-i)**.5%1==0for i in range(n))

Usar duas compreensões de lista aninhadas é muito caro. Em vez disso, isso verifica se as duas coordenadas no círculo do raio sqrt (n) são inteiros.

Peter Taylor venceu isso com uma abordagem baseada na inversão de Moebius .

lirtosiast
fonte
Bem feito. Eu estava mexendo em uma função recursiva, mas não conseguia resolver com n=0elegância.
Xsot #
5

Oitava, 28 bytes

@(n)nnz((a=(-n:n).^2)'+a==n)
alefalpha
fonte
5

Haskell, 42 bytes

f n|q<-[-n..n]=sum[1|a<-q,b<-q,a*a+b*b==n]

Exapmle do uso:

*Main> map f [0..25]
[1,4,4,0,4,8,0,0,4,4,8,0,0,8,0,0,4,8,4,0,8,0,0,0,0,12]
*Main>
nimi
fonte
3
Amarrar qum guarda é inteligente, lembrarei desse truque.
Xnor
5

Julia, 89 79 63 bytes

g(x)=cos(π*x^.5)^2÷1
a(n)=(n==0)+4sum([g(i)g(n-i)for i=1:n])

Esta é uma função nomeada aque aceita um número inteiro e retorna um número flutuante. Chama uma função auxiliarg .

Ungolfed:

function g(x::Integer)
    floor(cos(π*sqrt(x))^2)
end

function a(n::Integer)
    (n == 0) + 4*sum([g(i)*g(n-i) for i=1:n])
end

A abordagem aqui usa uma simplificação da fórmula de Wesley Ivan Hurt listada no OEIS. A simplificação foi encontrada por Glen O, a mesma pessoa que raspou 26 bytes nesta resposta!

Alex A.
fonte
Use em x^.5vez de sqrt(x)salvar 3 bytes. E (n==0)economiza 2 bytes 1÷(n+1). E você pode salvar mais 4 caracteres usando em cos(π*sqrt(x))^2÷1vez de floor(cos(π*sqrt(x))^2). Além disso, use em 1:n/2vez de 1:n÷2, porque não há mal em usar um float g(x)e ele ficará bloqueado para os números inteiros de iqualquer maneira. E sum(i->g(i)g(n-i),1:n/2)também raspará mais alguns personagens.
Glen O
@GlenO Ótimas sugestões, obrigado. O sumtruque falha por n=0isso, então eu mantive a compreensão da matriz.
Alex A.
1
Portanto, ele pode ser recuperado - se você deixar o i=0caso acontecer na soma, poderá ativar o sinal 4g(n). Portanto (n==0)-4g(n)-4g(n/2)+8sum(i->g(i)g(n-i),0:n/2), o que não ocorrerá no erro. Mas você pode fazer ainda melhor, observando as simetrias -(n==0)+4sum([g(i)g(n-i)for i=1:n])
Glen O
@GlenO Essa simplificação é seriamente genial. Eu recomendo que você a envie como uma fórmula alternativa para a sequência no OEIS!
Alex A.
4

Pitão, 16 15 bytes

lfqQs^R2T^}_QQ2

Experimente online no Pyth Compiler .

Como funciona

lfqQs^R2T^}_QQ2

          }_QQ   Compute the inclusive range from -Q to Q (input).
         ^    2  Take the second Cartesian power, i.e., compute all pairs.
 f               Filter; for each T in the list of pairs:
     ^R2T          Compute the squares of T's elements.
    s              Add the squares.
  qQ               Compare the sum with Q.
                 If q returned True, keep T.
l                Count the kept pairs.
Dennis
fonte
4

TI-BASIC, 23 bytes

sum(seq(Σ(X²+Y²=Ans,X,-Ans,Ans),Y,-Ans,Ans

Bem direto. Σ(é somatório.

Estranhamente, sum(seq(sum(seq(lança um ERR:ILLEGAL NEST, e o mesmo acontece Σ(Σ(, mas sum(seq(Σ(está bem. Eu escolhi colocar o Σ(interior para salvar um parente próximo.

lirtosiast
fonte
Qual é a diferença entre sume Σ?
alephalpha
1
@alephalpha Σ (faz um somatório, somando todos os X²+Y²=Ans valores de X entre -Anse Ans. sum (é a soma de uma lista , portanto, precisamos criar a lista primeiro usando seq (..., Y, -Ans, Ans
lirtosiast
4

JavaScript (ES6), 66 60 bytes

n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

6 bytes salvos graças a @ edc65 !

Explicação

n=>eval(`              // use eval to allow for loops in an unparenthesised arrow function
  for(r=0,             // r = number of pairs
    a=~n;a++<n;        // a = first number to square
  )
      for(b=~n;b++<n;) // b = second number to square
        r+=a*a+b*b==n  // add one to the result if a^2 + b^2 == n
                       // implicit: return r
`)

Teste

n = <input type="number" oninput='result.innerHTML=(

n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

)(+this.value)' /><pre id="result"></pre>
Expandir snippet

user81655
fonte
1
60:n=>eval('for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n')
edc65
@ edc65 Nice! Não pensei em usar evalos forloops em uma função de seta sem parênteses. Eu também esqueci o ~operador haha.
user81655
4

Python 3, 93 62 69 bytes

O Itertools não estava funcionando, então usei dois intervalos novamente, mas movi o intervalo para salvar bytes.

Editar: o código anterior não funcionou, pois defini o intervalo acima de n antes de definir n.

lambda n:sum(i*i+j*j==n for i in range(-n,n+1)for j in range(-n,n+1))
Sherlock9
fonte
2

APL, 23 20 19 bytes

{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}

Explicação:

{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}        Monadic function:
                 ⍳⍵          1 2 3 ... ⍵
               ,⍨            Duplicate
             0,              Concatenate to 0
          ×⍨                 Square everything
      ∘.+⍨                   Make an addition table
     ∊                       Flatten
   ⍵=                        1s where equal to the input
 +/                          Sum up the 1s

Além do fato de que o APL não possui J's i: (números de -n a n), isso funciona da mesma forma que a resposta J.

Não podemos usar um trem porque obter o -\⍳2×⍵ não analisar como(-\) ⍳ (2×⍵) custaria três bytes; da mesma forma com outro par de atops. Todos esses parênteses tornam a função regular mais curta.

Experimente aqui . A saída de 1significa que todos os valores correspondem.

lirtosiast
fonte
2

Matlab 41 bytes

Ainda menor que as respostas anteriores

@(n)nnz(~mod(sqrt(n-(1:n^.5).^2),1))*4+~n

Essencialmente, a resposta da Agawa001 com energia e sqrt substituídos

Jonas
fonte
2

Doces , 17 14 bytes

Entrada empurrada para a pilha inicialmente

~TbAT1C(sWs+Aeh)Z

~T0C(sWs+Aeh)Z

peekA    # copy arg from stack to register A
range2   # create double sided range on stack, -A, 1-A, ... A-1, A
digit0   # prefix argument to 'cart', 
cart     # cartesian product of current stack(0), and other stack(0)
while    # while stack not empty
  sqr    # pop and square and push
  swap   # swap two stack elements
  sqr    # pop and square and push
  add    # pop and pop and add and push
  pushA  # push original argument
  equal  # equality test 0/1
  popAddZ  # Z := Z + pop
endwhile
pushZ    # push Z onto stack, will be output to stdout on termination
Dale Johnson
fonte
2

CJam, 28

qi_mF{3a>},{~)\4%2-&}%4+:*1?

Não é realmente curto, mas eficiente. Por exemplo, o resultado para 15625 é instantaneamente 28. Usa a fórmula baseada em fatoração da OEIS.
Experimente online

Explicação:

qi       read input and convert to integer
_        make a copy (will be used to handle the 0 case at the end)
mF       factorize into [prime exponent] pairs
{…},     filter the array of pairs
  3a>    with the condition that the pair is greater than [3]
          which means the prime factor must be ⩾3
{…}%     transform each pair as follows:
  ~      dump the prime factor and exponent onto the stack
  )      increment the exponent
  \      swap with the prime
  4%     get the remainder mod 4 (it will be 1 or 3)
  2-     subtract 2 (resulting in -1 or 1)
  &      bitwise AND with the incremented exponent (see below)
4+       append a 4 to the array
:*       multiply all
1?       if the input was 0, use 1, else use the above result

Alguns detalhes sobre o cálculo:

  • se o primo for 1 mod 4, o código calcula (exponent + 1) & -1, que éexponent + 1
  • se o primo for 3 mod 4, o código calcula (exponent + 1) & 1, que é 0 se o expoente for ímpar e 1 se for par

Todos esses valores multiplicados juntos e multiplicados por 4 são exatamente a fórmula OEIS.

aditsu
fonte
2

Python 2, 68 bytes

def x(n):r=range(-n,n+1);print sum(a*a+b*b==n for a in r for b in r)

Define uma função chamada x() que leva um número n.

Experimente online. http://ideone.com/aRoxGF

Rɪᴋᴇʀ
fonte
Está faltando uma declaração printou return.
Zgarb 28/11/2015
Obrigado, eu esqueci completamente. O link tem a declaração de impressão. Eu editei meu código enquanto fazia o código.
Rɪᴋᴇʀ
OK sem problemas. Mas isso também parece fornecer resultados incorretos para n=0e n=1(0 e 2 em vez de 1 e 4). Talvez os limites de alcance precisem ser ajustados?
Zgarb 28/11/2015
@ Zgarb Sim, eles devem terminar às n+1.
lirtosiast
1
Eu vou procurar.
Rɪᴋᴇʀ
2

Pitão, 41 35 33 30 27 bytes

Experimente online.

Edit: Graças a isaacg , eu consegui me *Ftrabalhei! SIM!

?Q*F+4m.&tt%ed4hhdr-PQ2 8 1
                                (implicit) Q = input()
?Q                              If Q != 0
      m                           Map to d (exponent, prime) from ...
                  r-PQ2 8         run-length-encoded(PQ with 2's removed)
       .&                           Bitwise and
           %ed4                       d[-1] % 4
         tt                           -2
                hd                  with d[0]
               h                      +1
    +4                            Append 4 to the resulting array
  *F                              Then multiply it all together
                          1     Else 1

Editar: Coloque o bit a bit e volte para economizar mais bytes! Também removi todas as coisas "Anteriormente". Estava começando a ficar confuso.

Graças ao aditsu e à sua solução CJam, e ao maltysen e suas dicas (um dia vou começar m*Fda trabalhar. Um dia ...)

J4Vr-PQ2 8=J*J.&tt%eN4hhN;?QJ1
                                (implicit) Q=input()
J4                              J=4
    -PQ2                        Remove all 2's from the prime factorization of Q
   r     8                      run-length encode (exponent, prime factor)
  V                      ;      For N in range( the above ):
          =J*J                      J = J * ...
                tt%eN4                N[-1] mod 4 -2 
                      hhN             (exponent + 1)
              .&                    bitwise and
                          ?QJ1  if Q != 0 print(J) else print(1)

Observe que,

  • se o primo é 1 mod 4, obtemos -1 & (exponent + 1), que éexponent + 1

  • mas se o primo for 3 mod 4, obtemos 1 & (exponent + 1), que é 0se o expoente for ímpar e 1se for par

Multiplique tudo isso juntos (vezes 4 no início) e obteremos o número de somas de dois quadrados que somam nossa entrada.

Sherlock9
fonte
2

Python, 57 bytes

Bom desafio. Infelizmente, não estou conseguindo mais curto do que isso no momento.

lambda n:0**n+sum(2-d%4for d in range(1,n+1)if d%2>n%d)*4
Willem
fonte
2

PARI / GP, 34 28 bytes

Usando funções geradoras:

Economizou 6 bytes graças a Mitch Schwartz .

n->sum(i=-n,n,x^i^2)^2\x^n%x

Usando built-ins, 33 bytes (economizados 1 byte graças a Mitch Schwartz .):

n->if(n,2*qfrep(matid(2),n)[n],1)

qfrep (q, B, {flag = 0}): vetor de (metade) o número de vetores de normas de 1 a B para a forma quadrática integral e definida q. Se flag for 1, conte vetores de norma par de 1 a 2B.

alefalpha
fonte
matid(2)salva um byte.
Mitch Schwartz
1
E até 28 para a abordagem de função geradora:n->sum(i=-n,n,x^i^2)^2\x^n%x
Mitch Schwartz
1

Matlab, 72 bytes

n=input('');m=fix(sqrt(n));m=(-m:m).^2;disp(nnz(bsxfun(@plus,m,m')==n))
Luis Mendo
fonte
Você não precisa dispneste desafio Luis! =)
Stewie Griffin
@StewieGriffin Thanks! Mas, neste caso, é um programa, não uma função. Portanto, de acordo com a resposta aceita no seu link, é necessário, não é?
Luis Mendo
1

Matlab, 63 50 bytes

@(y)nnz(~mod(sqrt(y-power((1:sqrt(y)),2)),1))*4+~y

  • Isso supera o outro código com o mesmo título, assim eu coloco: D.

  • O programa encontra as soluções inteiras positivas e multiplica por 4 para incluir as negativas.

  • Pode executar todos os 25 primeiros casos de teste

    for i=1:25 ans(i)
end

   1

   4

   4

   0

   4

   8

   0

   0

   4

   4

   8

   0

   0

   8

   0

   0

   4

   8

   4

   0

   8

   0

   0

   0

   0

   12
Abr001am
fonte
Você não precisa dispneste desafio ! =)
Stewie Griffin
obrigado @StewieGriffin eu incluí-lo apenas como um jogo justo relacionado ao luis 'one
Abr001am 26/11/2015
Dicas: Quando você planeja postar os resultados do MATLAB, use format compact=)
Stewie Griffin
1

JavaScript, 89 bytes

n=prompt()
p=Math.pow
for (x=c=(+n?0:1);x<=n;x++)if(x&&p(n-p(x,2),.5)%1===0)c+=4
alert(c)

Sei que essa não é a resposta JavaScript mais curta, mesmo que eu remova as linhas de E / S, mas acho que é a resposta JS com melhor desempenho, fornecendo o resultado para um milhão em alguns segundos (dez milhões demoravam cerca de minuto).

Adam Dally
fonte
Você pode usar == em vez de ===?
lirtosiast
Eu poderia, apenas usando as melhores práticas, ha ha.
Adam Dally
1

PHP, 70 bytes, não competindo

for($x=-1;$x++<=$n=$argv[1];)$s+=(-($n%($x-~$x)<1))**$x*4;echo$n?$s:1;

algoritmo roubado de uma das respostas do Python ... esqueci qual; queria entender pelo menos parcialmente o que está acontecendo antes de eu postar.

Titus
fonte
for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1;economiza 5 bytes. $x-~$xé igual a 2*$x+1e agora você pode iniciar sem atribuir a variável.
Jörg Hülsermann 31/10