Cuenta sumas de dos cuadrados

45

Dado un número no negativo n, genera el número de formas de expresar ncomo la suma de dos cuadrados de enteros n == a^2 + b^2( OEIS A004018 ). Tenga en cuenta que ay bpuede ser positivo, negativo o cero, y su orden es importante. Pocos bytes ganan.

Por ejemplo, n=25da 12porque 25se puede expresar 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

Aquí están los valores hasta n=25. Tenga cuidado de que su 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

Aquí están los valores hasta en n=100una 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]

Datos curiosos: la secuencia contiene términos que son arbitrariamente altos, y el límite de su promedio de ejecución es π.

Tabla de clasificación:

Mostrar fragmento de código

code-golf math combinatorics number-theory xnor
fuente
44
¿¿Esperar lo?? "La secuencia contiene términos que son arbitrariamente altos, y el límite de su promedio de ejecución es π".
Stewie Griffin
@StewieGriffin Las dos declaraciones son consistentes. Considera la secuencia 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... Cortando la secuencia después de cualquier número distinto de cero, el promedio hasta ahora es 1. Y, las corridas de 0 tienen cada vez menos impacto en la secuencia.
xnor
55
Sé que es consistente .. =) Había verificado los primeros 10.000 números cuando publiqué el comentario. Lo que no entiendo es: ¿Por qué demonios es igual a Pi?
Stewie Griffin
29
@StewieGriffin La suma de los términos hasta N corresponde a los puntos (a, b) con a ^ 2 + b ^ 2 <= N. Estos son los puntos de la red en el círculo de radio sqrt (N), cuya área es πN.
xnor
2
@xnor y ahí va la magia :(
Andras Deak

Respuestas:

19

Python ( 59 57 56 bytes)

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

Demostración en línea

Al igual que con mi respuesta de CJam, esto utiliza la inversión de Möbius y se ejecuta en tiempo pseudoquasilineal.

Gracias a Sp3000 por el ahorro de 2 bytes y feersum por 1.

Peter Taylor
fuente
1
Esos paréntesis son molestos.
lirtosiast
@ThomasKwa, cuéntame sobre eso. Lo que realmente me sorprendió, en una de las versiones que pasé en el camino a la primera que publiqué, fue que -1**xsiempre es así -1. Esperaba -1que fuera un token literal entero único en lugar de un unario menos de baja precedencia seguido de uno.
Peter Taylor
2
¡Felicidades por la recompensa! Su código es más corto que todo lo que se me ocurrió. Su solución se basa en una idea matemática totalmente nueva e inesperada, y me alegra que esto sea posible incluso en un desafío tan directo. El resultado inverso de Mobius es bastante bonito y me dio el placer de obtener una prueba de yo mismo.
xnor
Se puede guardar 1 byte moviendo la multiplicación por 4 a después **x.
fiesta
@PeterTaylor ¿Puede explicar cómo funciona su algoritmo / puede indicarme un recurso? No puedo ver cómo puede aplicar la inversión de möbius al número de sumas del problema de suqares.
falla
15

Mathematica, 13 bytes

Si se permiten incorporados, esta es la forma de hacerlo en 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
fuente
1
Porque, por supuesto, Mathematica tiene una función incorporada para esto.
HyperNeutrino
14

Python 2, 44 bytes

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

Esto es casi lo mismo que la solución de xsot (que se basa en la solución de Peter Taylor ), pero ahorra 8 bytes al simplificar la forma en que se manejan los signos.

Tenga en cuenta que para un programa completo, podemos guardar 2 bytes en la función sin incurrir en un costo fuera de la función:

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

Dos bytes adicionales para un programa completo de esta manera:

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

Porque n > 0hay una solución de 40 bytes muy legible:

f=lambda n,x=1:n/x and(n%x<1)*4-f(n,x+2)
Mitch Schwartz
fuente
1
¡Felicidades por ganar la recompensa! La resta recursiva es una forma limpia y corta de expresar la suma alterna para divisores impares sin necesidad de extraer un signo del divisor mismo. Además, agradezca a xsot por simplificar la solución de Peter Taylor a una solución recursiva con un manejo inteligente de n = 0.
xnor
12

Pyth, 13 bytes

/sM^^R2}_QQ2Q

Banco de pruebas

/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
fuente
Tarde, pero no creo que necesites lo último Q.
Erik the Outgolfer
12

J, 16 bytes

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

Este es un verbo monádico (en otras palabras, una función unaria). Pruébelo en línea o vea cómo pasa todos los casos de prueba .

Explicación

+/@,@:=+&*:/~@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
fuente
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 es una función recursiva basada en la excelente solución de Peter Taylor .

xsot
fuente
1
Esto es una gran mejora. Pero, todavía hay una manera de hacerlo más corto, y le animo a que lo busque.
xnor
1
@xnor Otro byte abajo. Espero que no tengas más trucos bajo la manga.
xsot
2
No sé si debería hacer una respuesta de ella, es sólo la solución más un truco: f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2. Además, supongo que no nos importa exceder la profundidad de recursión máxima predeterminada.
Mitch Schwartz
1
@MitchSchwartz Creo que es una mejora increíble digna de la recompensa y probablemente la optimización final que xnor tenía en mente.
xsot
1
@MitchSchwartz Sí, ¡esa es la optimización en la que estaba pensando! Y el /4<<2truco de xsot lo hace más corto que el que tenía.
xnor
8

Julia, 40 bytes

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

Sin golf:

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

Tenga en cuenta que el ciclo no incluye i==0, porque cuando nes un cuadrado, ya está incluido por i=sqrt(n), y solo hay cuatro, no ocho, para esa forma ( 0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2).

Glen O
fuente
7

CJam, 25 23 bytes

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

Esta es una solución teórica que requiere O (9 n ) tiempo y memoria para la entrada n .

A costa de un byte adicional, para un total de 24 bytes , podemos reducir la complejidad a O (n 2 ) :

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

Pruébalo en línea!

Cómo funciona

Ya sea

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

o

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

Entonces

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
fuente
Y con un ahorro de un byte es posible reducir la complejidad a Õ (n)
Peter Taylor
Yo sí vi. Eso es increíble.
Dennis
7

CJam ( 25 24 22 21 bytes)

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

Demostración en línea

Esto se ejecuta en tiempo pseudoquasilineal * y usa la declaración del OEIS que

La transformación de Moebius es la secuencia del período 4 [4, 0, -4, 0, ...]. - Michael Somos, 17 sep 2007

La entrada 0es obviamente un caso especial (las transformaciones de Möbius y los aniquiladores no van bien juntos), pero terminaron costando solo un personaje.

* Pseudo- porque es cuasilineal en el valor de la entrada, no en el tamaño de la entrada; cuasi porque realiza Theta(n)operaciones en enteros de tamaño del orden de n; Una boperación de mod de bits debería llevar b lg btiempo, por lo que en general esto lleva Theta(n lg n lg lg n)tiempo.

Peter Taylor
fuente
6

Japt , 42 37 33 bytes

Japt es una versión abreviada de Ja vaScri pt . Interprete

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

Cómo 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

Quizás haya una mejor técnica; Las sugerencias son bienvenidas.

ETHproducciones
fuente
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 dos comprensiones de listas anidadas es demasiado costoso. En cambio, esto verifica si ambas coordenadas en el círculo de radio sqrt (n) son enteros.

Peter Taylor ha superado esto con un enfoque basado en la inversión de Moebius .

lirtosiast
fuente
Bien hecho. Estaba jugando con una función recursiva pero no podía resolver con n=0elegancia.
xsot
5

Octava, 28 bytes

@(n)nnz((a=(-n:n).^2)'+a==n)
alephalpha
fuente
5

Haskell, 42 bytes

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

Uso exapmle:

*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
fuente
3
Atar qa un guardia es inteligente, recordaré este truco.
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 es una función con nombre aque acepta un número entero y devuelve un flotante. Llama a una función auxiliar g.

Sin golf:

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

El enfoque aquí utiliza una simplificación de la fórmula de Wesley Ivan Hurt que figura en OEIS. ¡Glen O, la misma persona que recortó 26 bytes de esta respuesta, encontró la simplificación!

Alex A.
fuente
Use en x^.5lugar de sqrt(x)guardar 3 bytes. Y (n==0)ahorra 2 bytes más 1÷(n+1). Y puede guardar 4 caracteres más utilizando en cos(π*sqrt(x))^2÷1lugar de floor(cos(π*sqrt(x))^2). Además, use en 1:n/2lugar de 1:n÷2, porque no hay daño al usar un flotador g(x)y de itodos modos estará bloqueado a los enteros . Y sum(i->g(i)g(n-i),1:n/2)afeitará algunos personajes más, también.
Glen O
@GlenO Grandes sugerencias, gracias. Sin embargo, el sumtruco falla n=0, así que mantuve la comprensión de la matriz.
Alex A.
1
Por lo tanto, se puede recuperar: si deja que el i=0caso suceda en la suma, puede activar el inicio de sesión 4g(n). Entonces (n==0)-4g(n)-4g(n/2)+8sum(i->g(i)g(n-i),0:n/2), lo que no se encontrará con el error. Pero puedes hacerlo aún mejor, observando las simetrías ...(n==0)+4sum([g(i)g(n-i)for i=1:n])
Glen O
@GlenO que la simplificación es serio genio. ¡Recomiendo que lo envíe como una fórmula alternativa para la secuencia en OEIS!
Alex A.
4

Pyth, 16 15 bytes

lfqQs^R2T^}_QQ2

Pruébelo en línea en el compilador Pyth .

Cómo 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
fuente
4

TI-BASIC, 23 bytes

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

Muy claro. Σ(es sumatoria.

Extrañamente, sum(seq(sum(seq(lanza un ERR:ILLEGAL NEST, y lo hace Σ(Σ(, pero sum(seq(Σ(está bien. Elegí poner el Σ(interior para salvar a un pariente cercano.

lirtosiast
fuente
¿Cuál es la diferencia entre sumy Σ?
alephalpha
1
@alephalpha Σ (toma una suma, sumando todos los X²+Y²=Ansvalores de X de entre -Ansy Ans. sum (es la suma de una lista , por lo que debemos crear la lista primero 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 guardados gracias a @ edc65 !

Explicación

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
`)

Prueba

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 fragmento

usuario81655
fuente
1
60:n=>eval('for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n')
edc65
@ edc65 ¡Bien! No pensé en usar evalpara poner los forbucles en una función de flecha sin paréntesis. También me olvidé del ~operador jaja.
user81655
4

Python 3, 93 62 69 bytes

Itertools no funcionaba, así que volví a usar dos rangos, pero moví el rango para guardar bytes.

Editar: el código anterior en realidad no funcionó, ya que definí el rango sobre 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
fuente
2

APL, 23 20 19 bytes

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

Explicación:

{+/⍵=∊∘.+⍨×⍨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

Aparte del hecho de que APL no tiene la función J i:(números de -n a n), esto funciona más o menos como la respuesta J.

No podemos usar un tren porque hacer -\⍳2×⍵que no se analice como (-\) ⍳ (2×⍵)costaría tres bytes; de manera similar con otro par de atops. Todos esos paréntesis acortan la función regular.

Pruébalo aquí . La salida de 1significa que todos los valores coinciden.

lirtosiast
fuente
2

Matlab 41 bytes

Incluso más pequeño que las respuestas anteriores.

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

Esencialmente, la respuesta de Agawa001 con potencia y sqrt reemplazados

Jonas
fuente
2

Candy , 17 14 bytes

Entrada empujada a la pila 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
fuente
2

CJam, 28

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

No realmente corto, pero eficiente. Por ejemplo, el resultado para 15625 es instantáneamente 28. Utiliza la fórmula basada en factorización de OEIS.
Pruébalo en línea

Explicación:

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

Algunos detalles sobre el cálculo:

  • si el primo es 1 mod 4, el código calcula (exponent + 1) & -1, que esexponent + 1
  • si el primo es 3 mod 4, el código calcula (exponent + 1) & 1, que es 0 si el exponente es impar y 1 si es par

Todos estos valores multiplicados juntos y multiplicados por 4 son exactamente la fórmula OEIS.

aditsu
fuente
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 una función llamada x()que toma un número n.

Pruébalo en línea. http://ideone.com/aRoxGF

Rɪᴋᴇʀ
fuente
Te falta una declaración printo return.
Zgarb
Gracias, lo olvidé por completo. Sin embargo, el enlace tiene la declaración impresa. Edité mi código mientras lo hacía.
Rɪᴋᴇʀ
Ok, no te preocupes. Pero esto también parece dar resultados incorrectos para n=0y n=1(0 y 2 en lugar de 1 y 4). Tal vez los límites de rango necesitan ajuste?
Zgarb
@ Zgarb Sí, deberían terminar en n+1.
lirtosiast
1
Lo buscaré.
Rɪᴋᴇʀ
2

Pyth, 41 35 33 30 27 bytes

Pruébalo en línea.

Editar: Gracias a isaacg , tengo my *Fpara trabajar! ¡SI!

?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: ¡ Ponga el bit a bit y vuelva para obtener más ahorros de bytes! También eliminé todas las cosas "Anteriormente". Estaba empezando a estar abarrotado.

Gracias a aditsu y su solución CJam, y a maltysen y sus consejos (algún día iré m*Fda trabajar. Un día ...)

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)

Tenga en cuenta que,

  • si el primo es 1 mod 4, obtenemos -1 & (exponent + 1), que esexponent + 1

  • pero si el primo es 3 mod 4, obtenemos 1 & (exponent + 1), que es 0si el exponente es impar, y 1si es par

Multiplique todo junto (multiplicado por 4 al principio) y obtenemos el número de sumas de dos cuadrados que se suman a nuestra entrada.

Sherlock9
fuente
2

Python, 57 bytes

Buen desafío Desafortunadamente, no lo estoy haciendo más corto que esto en este momento.

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

PARI / GP, 34 28 bytes

Usando funciones generadoras:

Guardado 6 bytes gracias a Mitch Schwartz .

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

Utilizando incorporados, 33 bytes (1 byte guardado gracias a Mitch Schwartz ):

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

qfrep (q, B, {flag = 0}): vector de (mitad) el número de vectores de normas de 1 a B para la forma cuadrática integral y definida q. Si el indicador es 1, cuente los vectores de la norma par de 1 a 2B.

alephalpha
fuente
matid(2)Guarda un byte.
Mitch Schwartz
1
Y hasta 28 para el enfoque de función generadora: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
fuente
¡ No necesitas dispen este desafío Luis! =)
Stewie Griffin
@StewieGriffin ¡Gracias! Pero en este caso es un programa, no una función. Entonces, de acuerdo con la respuesta aceptada en su enlace, es necesario, ¿no?
Luis Mendo
1

Matlab, 63 50 bytes

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

  • Esto supera al otro código con el mismo derecho, por lo que lo pongo: D.

  • El programa encuentra las soluciones enteras positivas y luego las multiplica por 4 para abarcar las negativas.

  • Puede realizar los 25 primeros casos de prueba

    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
fuente
¡ No necesitas dispen este desafío ! =)
Stewie Griffin
gracias @StewieGriffin lo incluí solo como un juego limpio relacionado con el de luis '
Abr001am
Consejos: cuando esté planeando publicar los resultados de 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)

Sé que esta no es la respuesta de JavaScript más corta, incluso si tuviera que eliminar las líneas de E / S, pero creo que es la respuesta JS de mejor rendimiento que me da el resultado de un millón en unos segundos (diez millones tomaron aproximadamente un minuto).

Adam Dally
fuente
¿Puedes usar == en lugar de ===?
lirtosiast
Podría, simplemente usando las mejores prácticas, ja, ja.
Adam Dally
1

PHP, 70 bytes, no compitiendo

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

algoritmo robado de una de las respuestas de Python ... Olvidé cuál; Quería entender al menos parcialmente lo que está sucediendo antes de publicar.

Titus
fuente
for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1;ahorra 5 bytes. $x-~$xes igual a 2*$x+1y ahora puede comenzar sin asignar la variable.
Jörg Hülsermann