Compter les sommes de deux carrés

45

Avec un nombre non négatif n, indiquez le nombre de façons d'exprimer nla somme de deux carrés d'entiers n == a^2 + b^2( OEIS A004018 ). Notez que aet bpeut être positif, négatif ou nul et que leur ordre est important. Le moins d'octets gagne.

Par exemple, n=25donne 12parce que 25peut être exprimé par

(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

Voici les valeurs jusqu'à n=25. Veillez à ce que votre code fonctionne pour 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

Voici les valeurs jusqu'à n=100une liste.

[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]

Faits amusants: la séquence contient des termes arbitrairement élevés et la limite de sa moyenne mobile est π.

Classement:

Afficher l'extrait de code

code-golf math combinatorics number-theory Xnor
la source
4
Attends quoi?? "La séquence contient des termes arbitrairement élevés et la limite de sa moyenne mobile est π."
Stewie Griffin
@StewieGriffin Les deux déclarations sont cohérentes. Considérons la séquence 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... En coupant la séquence après n'importe quel nombre différent de zéro, la moyenne jusqu'à présent est de 1. Et, les suites de 0 ont de moins en moins d'impact ultérieurement dans la séquence.
xnor
5
Je sais que c'est cohérent .. =) J'avais vérifié les 10 000 premiers chiffres lorsque j'ai posté le commentaire. Ce que je ne comprends pas, c'est: Pourquoi diable est-il égal à Pi?
Stewie Griffin
29
@StewieGriffin La somme des termes jusqu'à N correspond aux points (a, b) avec a ^ 2 + b ^ 2 <= N. Ce sont les points du réseau dans le cercle de rayon sqrt (N), dont l’aire est πN.
xnor
2
@xnor et voilà la magie :(
Andras Deak

Réponses:

19

Python ( 59 57 56 octets)

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

Démo en ligne

Comme avec ma réponse CJam, cela utilise l'inversion de Möbius et s'exécute en temps pseudoquasilinéaire.

Merci à Sp3000 pour des économies de 2 octets et feersum pour 1.

Peter Taylor
la source
1
Ces parenthèses sont ennuyeuses.
lirtosiast
@ThomasKwa, parlez-moi de ça. Ce qui m'a vraiment surpris, dans l'une des versions que j'ai traversées en allant à la première que j'ai postée, c'est que -1**xc'est toujours -1. Je m'attendais à ce -1qu'il s'agisse d'un jeton littéral entier unique plutôt que d'un moins unaire de précédence faible suivi d'un.
Peter Taylor
2
Félicitations pour la prime! Votre code est plus court que tout ce que j'avais imaginé. Votre solution est basée sur une idée mathématique totalement nouvelle et inattendue, et cela m’apporte avec joie que c’est possible même dans un défi aussi simple. Le résultat de Mobius-inverse est assez joli et j’ai pris le plaisir de tirer une preuve moi même.
xnor
1 octet peut être sauvegardé en déplaçant la multiplication de 4 à après **x.
Feersum
@PeterTaylor Pouvez-vous préciser le fonctionnement de votre algorithme / pouvez-vous m'indiquer une ressource? Je ne vois pas trop comment appliquer l'inversion de Möbius au problème du nombre de sommes de suqares.
flawr
15

Mathematica, 13 octets

Si les fonctions intégrées sont autorisées, voici comment procéder dans Mathematica.

2~SquaresR~#&

Pour 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, 8, 0, 0, 0, 0, 4, 8, 8 , 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 0, 8, 4, 0 , 12}

DavidC
la source
1
Bien entendu, Mathematica a une fonction intégrée pour cela.
HyperNeutrino
14

Python 2, 44 octets

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

C'est presque la même chose que la solution de xsot (basée sur la solution de Peter Taylor ), mais économise 8 octets en simplifiant le traitement des signes.

Notez que pour un programme complet, nous pouvons économiser 2 octets dans la fonction sans encourir de coût en dehors de la fonction:

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

Deux octets supplémentaires pour un programme complet de cette façon:

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

Car n > 0il existe une solution très lisible à 40 octets:

f=lambda n,x=1:n/x and(n%x<1)*4-f(n,x+2)
Mitch Schwartz
la source
1
Félicitations pour avoir gagné la prime! La soustraction récursive est un moyen simple et rapide d’exprimer la somme alternée pour les diviseurs impairs sans avoir à extraire un signe du diviseur lui-même. Nous devons également remercier xsot d’avoir rationalisé la solution de Peter Taylor en une solution récursive avec une gestion intelligente de n = 0.
xnor
12

Pyth, 13 octets

/sM^^R2}_QQ2Q

Suite de tests

/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
la source
En retard, mais je ne pense pas que vous ayez besoin du dernier Q.
Erik the Outgolfer
12

J, 16 octets

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

C'est un verbe monadique (en d'autres termes, une fonction unaire). Essayez-le en ligne ou voyez-le réussir tous les tests .

Explication

+/@,@:=+&*:/~@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
la source
11

Python 2, 69 55 53 52 octets

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

Ceci est une fonction récursive basée sur l'excellente solution de Peter Taylor .

Xsot
la source
1
C'est une grande amélioration. Cependant, il existe toujours un moyen de le raccourcir, et je vous encourage à le rechercher.
xnor
1
@xnor Un autre octet vers le bas. J'espère que vous n'avez plus d'astuces dans vos manches.
xsot
2
Je ne sais pas si je devrais faire une réponse, il est juste votre solution plus une astuce: f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2. De plus, je suppose que nous ne nous soucions pas de dépasser la profondeur de récursivité maximale par défaut?
Mitch Schwartz
1
@MitchSchwartz Je pense que c'est une amélioration incroyable digne de la prime et probablement de l'optimisation finale que xnor avait en tête.
xsot
1
@MitchSchwartz Oui, c'est l'optimisation à laquelle je pensais! Et le /4<<2truc de xsot le rend plus court que ce que j'avais.
xnor
8

Julia, 40 octets

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

Notez que la boucle n'inclut pas i==0, car quand nest un carré, il est déjà inclus par i=sqrt(n), et il n'y a que quatre, pas huit, pour cette forme ( 0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2).

Glen O
la source
7

CJam, 25 23 octets

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

C’est une solution théorique qui nécessite 0 (9 n ) temps et de la mémoire pour la saisie n .

Au prix d'un octet supplémentaire, pour un total de 24 octets , nous pouvons réduire la complexité à O (n 2 ) :

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

Essayez-le en ligne!

Comment ça marche

Non plus

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.

ensuite

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
la source
Et avec une économie d'un octet, il est possible de réduire la complexité à (n)
Peter Taylor
Oui j'ai vu. C'est incroyable.
Dennis
7

CJam ( 25 24 22 21 octets)

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

Démo en ligne

Cela fonctionne à l’heure pseudoquasilinéaire * et utilise l’affirmation de l’OEIS selon laquelle

La transformation de Moebius est une séquence de la période 4 [4, 0, -4, 0, ...]. - Michael Somos, 17 septembre 2007

L'entrée 0 est évidemment un cas particulier (les transformations de Möbius et les annihilateurs ne vont pas bien ensemble), mais ne coûtent qu'un personnage.

* Pseudo- parce que c'est quasilinéaire dans la valeur de l'entrée, pas dans la taille de l'entrée; quasi parce qu'il effectue des Theta(n)opérations sur des entiers de taille de l'ordre de n; Une bopération de mod-bit devrait prendre du b lg btemps, donc globalement cela prend du Theta(n lg n lg lg n)temps.

Peter Taylor
la source
6

Japt , 42 37 33 octets

Japt est une version abrégée de Ja vaScri pt . Interprète

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

Comment ça marche

           // 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

Peut-être il y a une meilleure technique; les suggestions sont les bienvenues.

ETHproductions
la source
6

Python 3, 68 61 60 octets

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

L'utilisation de deux interprétations de liste imbriquées est trop chère. Au lieu de cela, ceci vérifie si les deux coordonnées sur le cercle de rayon sqrt (n) sont des entiers.

Peter Taylor a surmonté cela avec une approche basée sur l'inversion de Moebius .

lirtosiast
la source
Bien joué. Je bricolais avec une fonction récursive mais je ne pouvais pas résoudre n=0élégamment.
xsot
5

Octave, 28 octets

@(n)nnz((a=(-n:n).^2)'+a==n)
Alephalpha
la source
5

Haskell, 42 octets

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

Exemple d'utilisation:

*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
la source
3
La liaison qdans un garde est intelligente, je me souviendrai de cette astuce.
xnor
5

Julia, 89 79 63 octets

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

C'est une fonction nommée aqui accepte un entier et renvoie un float. Il appelle une fonction d'assistance g.

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

Cette approche utilise une simplification de la formule de Wesley Ivan Hurt figurant dans OEIS. La simplification a été trouvée par Glen O, la même personne qui a rasé 26 octets de cette réponse!

Alex A.
la source
Utilisez x^.5plutôt que sqrt(x)de sauvegarder 3 octets. Et (n==0)enregistre 2 octets sur 1÷(n+1). Et vous pouvez enregistrer 4 caractères supplémentaires en utilisant cos(π*sqrt(x))^2÷1plutôt que floor(cos(π*sqrt(x))^2). Aussi, utilisez 1:n/2plutôt que 1:n÷2parce qu'il n'y a pas de mal à utiliser un float dans g(x)et qu'il sera verrouillé sur les entiers pour de itoute façon. Et sum(i->g(i)g(n-i),1:n/2)va raser d'autres personnages aussi.
Glen O
@GlenO Excellentes suggestions, merci. L' sumastuce échouant n=0cependant, j'ai donc gardé la compréhension du tableau.
Alex A.
1
Donc, il peut être récupéré - si vous laissez le i=0cas se produire dans la somme, vous pouvez activer le signe 4g(n). Donc (n==0)-4g(n)-4g(n/2)+8sum(i->g(i)g(n-i),0:n/2), ce qui ne courra pas dans l'erreur. Mais vous pouvez faire encore mieux en notant les symétries -(n==0)+4sum([g(i)g(n-i)for i=1:n])
Glen O
@GlenO Cette simplification est sérieusement génie. Je vous recommande de soumettre cela comme formule alternative pour la séquence sur OEIS!
Alex A.
4

Pyth, 16 à 15 octets

lfqQs^R2T^}_QQ2

Essayez-le en ligne dans le compilateur Pyth .

Comment ça marche

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
la source
4

TI-BASIC, 23 octets

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

Assez simple. Σ(est la sommation.

Étrangement, sum(seq(sum(seq(jette un ERR:ILLEGAL NEST, et donc Σ(Σ(, mais tout sum(seq(Σ(va bien. J'ai choisi de mettre le Σ(à l'intérieur pour sauver un proche-paren.

lirtosiast
la source
Quelle est la différence entre sumet Σ?
Alephalpha
1
@alephalpha Σ (prend une somme, en additionnant toutes les X²+Y²=Ansvaleurs de X entre -Anset Ans. sum (est la somme d'une liste , nous devons donc créer la liste d'abord en utilisant seq (..., Y, -Ans, Ans
lirtosiast
4

JavaScript (ES6), 66 60 octets

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

6 octets sauvegardés grâce à @ edc65 !

Explication

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

Tester

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>
Développer l'extrait

utilisateur81655
la source
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! Je n'ai pas pensé à utiliser evalpour mettre les forboucles dans une fonction de flèche sans parenthèses. J'ai aussi oublié l' ~opérateur haha.
user81655
4

Python 3, 93 62 69 octets

Itertools ne fonctionnait pas, j'ai donc utilisé à nouveau deux plages, mais je l'ai déplacé pour économiser des octets.

Edit: Le code précédent ne fonctionnait pas vraiment, car j'avais défini la plage sur n avant de définir n.

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

APL, 23 20 19 octets

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

Explication:

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

Autre que le fait que APL n'a pas de J i: (nombres de -n à n), cela fonctionne assez bien comme la réponse J.

Nous ne pouvons pas utiliser un train car obtenir le -\⍳2×⍵ pour ne pas analyser comme(-\) ⍳ (2×⍵) cela coûterait trois octets; de même avec une autre paire d'atops. Toutes ces parenthèses rendent la fonction régulière plus courte.

Essayez ici . La sortie de 1signifie que toutes les valeurs correspondent.

lirtosiast
la source
2

Matlab 41 octets

Encore plus petit que les réponses précédentes

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

Essentiellement, la réponse d'Agawa001 avec le pouvoir et le carré remplacés

Jonas
la source
2

Candy , 17 ans 14 octets

Entrée poussée initialement sur la pile

~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
la source
2

CJam, 28 ans

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

Pas vraiment court, mais efficace. Par exemple, le résultat pour 15625 est instantanément de 28. Utilise la formule basée sur la factorisation d'OEIS.
Essayez-le en ligne

Explication:

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

Quelques détails sur le calcul:

  • si le nombre premier est 1 mod 4, le code calcule (exponent + 1) & -1, qui estexponent + 1
  • si le nombre premier est 3 mod 4, le code calcule (exponent + 1) & 1, qui est 0 si l'exposant est impair et 1 si même

Toutes ces valeurs multipliées ensemble et multipliées par 4 sont exactement la formule OEIS.

Aditsu
la source
2

Python 2, 68 octets

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

Définit une fonction appelée x()qui prend un nombre n.

Essayez-le en ligne. http://ideone.com/aRoxGF

Rɪᴋᴇʀ
la source
Il vous manque une déclaration printou return.
Zgarb
Merci, j'ai complètement oublié. Le lien a cependant la déclaration d'impression. J'ai édité mon code pendant que je créais le code.
Rɪᴋᴇʀ
OK, pas de problème. Mais cela semble également donner des résultats incorrects pour n=0et n=1(0 et 2 au lieu de 1 et 4). Peut-être que les limites de la plage doivent être ajustées?
Zgarb
@Zgarb Ouais, ils devraient finir à n+1.
lirtosiast
1
Je vais le chercher.
Rɪᴋᴇʀ
2

Pyth, 41 35 33 30 27 octets

Essayez-le en ligne.

Edit: Merci à isaacg , je suis arrivé met *Fau travail! OUI!

?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

Modifier: Mettez le bitwise et retournez pour plus d'économies d'octets! De plus, j'ai enlevé tous les trucs "Anciennement". Il commençait à être encombré.

Merci à aditsu et à sa solution CJam, et à maltysen et ses astuces (Un jour, je me rendraim*Fd au travail. Un jour ...)

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)

Notez que,

  • si le nombre premier est 1 mod 4, on obtient -1 & (exponent + 1)ce qui estexponent + 1

  • mais si le nombre premier est 3 mod 4, nous obtenons 1 & (exponent + 1), ce qui est 0si l'exposant est impair, et 1si même

Multipliez le tout ensemble (4 fois au début) et nous obtenons le nombre de sommes de deux carrés qui s'ajoutent à notre entrée.

Sherlock9
la source
2

Python, 57 octets

Beau défi. Malheureusement, je n'ai pas le temps plus court que ça pour le moment.

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

PARI / GP, 34 28 octets

Utilisation des fonctions génératrices:

Enregistré 6 octets grâce à Mitch Schwartz .

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

Utilisation des fonctions intégrées, 33 octets (1 octet enregistré grâce à Mitch Schwartz .):

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

qfrep (q, B, {flag = 0}): vecteur de (moitié) le nombre de vecteurs de normes de 1 à B pour la forme quadratique intégrale et définie q. Si flag est égal à 1, compter les vecteurs de même norme de 1 à 2B.

Alephalpha
la source
matid(2)enregistre un octet.
Mitch Schwartz
1
Et jusqu'à 28 pour l'approche de la fonction génératrice:n->sum(i=-n,n,x^i^2)^2\x^n%x
Mitch Schwartz
1

Matlab, 72 octets

n=input('');m=fix(sqrt(n));m=(-m:m).^2;disp(nnz(bsxfun(@plus,m,m')==n))
Luis Mendo
la source
Tu n'as pas besoin dispde ce défi Luis! =)
Stewie Griffin
@StewieGriffin Merci! Mais dans ce cas, c'est un programme, pas une fonction. Donc, selon la réponse acceptée dans votre lien, c'est nécessaire, n'est-ce pas?
Luis Mendo
1

Matlab, 63 50 octets

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

  • Ceci bat l’autre code portant le même titre, je le résume donc: D.

  • Le programme trouve les solutions entières positives, puis multiplie par 4 pour englober les solutions négatives.

  • Il peut effectuer tous les 25 premiers cas de test

    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
la source
Vous n'avez pas besoin dispde ce défi ! =)
Stewie Griffin
merci @StewieGriffin je l'ai inclus juste comme un jeu équitable en rapport avec celui de Luis
Abr001am
Conseils: lorsque vous comptez publier les résultats de MATLAB, utilisez format compact=)
Stewie Griffin
1

JavaScript, 89 octets

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)

Je sais que ce n'est pas la réponse JavaScript la plus courte, même si je devais supprimer les lignes d'e / s, mais je pense que c'est la réponse JS la plus performante qui m'a donné le résultat pour un million en quelques secondes (dix millions ont pris environ minute).

Adam Dally
la source
Pouvez-vous utiliser == au lieu de ===?
lirtosiast
Je pourrais, juste en utilisant les meilleures pratiques, ha, ha.
Adam Dally
1

PHP, 70 octets, pas en concurrence

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

algorithme dérobé à l’une des réponses Python ... j’ai oublié laquelle; voulait au moins partiellement comprendre ce qui se passait avant que je poste.

Titus
la source
for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1;enregistre 5 octets. $x-~$xest égal à 2*$x+1et vous pouvez maintenant commencer sans affecter la variable.
Jörg Hülsermann