52
\$\begingroup\$

Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers n == a^2 + b^2 (OEIS A004018). Note that a and b can be positive, negative, or zero, and their order matters. Fewest bytes wins.

For example, n=25 gives 12 because 25 can be expressed as

(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

Here are the values up to n=25. Be careful that your code works for 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

Here are the values up to n=100 as a list.

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

Fun facts: The sequence contains terms that are arbitrarily high, and the limit of its running average is π.

Leaderboard:

    var QUESTION_ID=64812,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/64812/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
    body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
6
  • 5
    \$\begingroup\$ Wait, what?? "The sequence contains terms that are arbitrarily high, and the limit of its running average is π." \$\endgroup\$ Commented Nov 26, 2015 at 11:58
  • 1
    \$\begingroup\$ @StewieGriffin The two statements are consistent. Consider the sequence 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... Cutting the sequence off after any nonzero number, the average so far is 1. And, the runs of 0's have less and less impact later in the sequence. \$\endgroup\$
    – xnor
    Commented Nov 26, 2015 at 12:04
  • 6
    \$\begingroup\$ I know it's consistent.. =) I had checked the 10.000 first numbers when I posted the comment. What I don't get is: Why on earth does it equal Pi? \$\endgroup\$ Commented Nov 26, 2015 at 12:19
  • 32
    \$\begingroup\$ @StewieGriffin The sum of the terms up to N corresponds to the points (a,b) with a^2+b^2<=N. These are the lattice points in the circle of radius sqrt(N), whose area is πN. \$\endgroup\$
    – xnor
    Commented Nov 26, 2015 at 12:23
  • 4
    \$\begingroup\$ @xnor and there goes the magic:( \$\endgroup\$ Commented Nov 29, 2015 at 1:02

50 Answers 50

1
2
1
\$\begingroup\$

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)

I know this isn't the shortest JavaScript answer even if I were to remove the i/o lines, but I do think it is the best performing JS answer giving me the result for a million within a few seconds (ten million took about a minute).

\$\endgroup\$
2
  • \$\begingroup\$ Can you use == instead of ===? \$\endgroup\$
    – lirtosiast
    Commented Nov 30, 2015 at 3:54
  • \$\begingroup\$ I could, just using best practices, ha ha. \$\endgroup\$
    – Adam Dally
    Commented Dec 1, 2015 at 0:07
1
\$\begingroup\$

PHP, 70 bytes, not competing

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

algorithm stolen from one of the Python answers ... I forgot which one; wanted to at least partially understand what´s happening before I posted.

\$\endgroup\$
1
  • \$\begingroup\$ for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1; saves 5 Bytes. $x-~$x is equal to 2*$x+1 and you can now start without assigning the variable. \$\endgroup\$ Commented Oct 31, 2016 at 12:35
1
\$\begingroup\$

PHP, 80 Bytes

for($m=-$a=1+$argv[1];++$m<$a;)for($n=-$a;$n++<$a;)$c+=$a-1==$m**2+$n**2;echo$c;
\$\endgroup\$
1
  • 1
    \$\begingroup\$ $c+=condition; instead of if(condition)$c++; (-4) Do you feel stalked? :D pre-increment on $m and $n will improve speed a bit. \$\endgroup\$
    – Titus
    Commented Oct 31, 2016 at 0:49
1
\$\begingroup\$

ASP, 53 + 4 = 57 bytes

#show N:N=#count{o(A,B):k=A**2+B**2,A=-k..k,B=-k..k}.

Answer Set Programming is a logical language, similar to prolog. I use here the Potassco implementation, clingo.

Input is taken from parameters (-ck= is 4 bytes long). Call example:

clingo -ck=25

Output sample:

12

You can try it in your browser ; unfortunately, this method doesn't handle call flags, so you need to add the line #const k=25 in order to make it work.

\$\endgroup\$
1
\$\begingroup\$

Add++, 31 bytes

D,f,@,.5^1+iR2€Ω^d0BFB]d‽+A€=¦+

Try it online!

How it works

This defines a function, \$f\$, that takes the input, \$x\$, as an argument and returns the correct output. We start by yielding \$y := \lfloor\sqrt{x}+1\rfloor\$. We then push the range \$a := [1, 4, ..., y^2]\$, the list of square numbers up to the smallest square number larger than \$x\$. We then duplicate this array and push \$0\$ to the stack. At this point, the stack looks like this, for an input of \$25\$:

[[1 4 9 16 25 36] [1 4 9 16 25 36] 0]

We then collect these values into a single list, which yields the list of \$n^2\$ for each \$n \in [-y, y]\$. We then duplicate this list and operate the table operator over the addition command. The table operator takes a dyad, \$g(p, q)\$, and two arrays, \$A\$ and \$B\$. It then takes the Cartesian Product of \$A\$ and \$B\$ and iterates \$g(a, b)\$ over each pair \$(a, b)\$ where \$a \in A\$ and \$b \in B\$.

In this code, this yields the array \$\big[a^2+b^2 \: | \: a, b \in [-y, y]\big]\$. We then compare each element of this list with the input, yielding a boolean array. Finally, we count the number of \$1\$s in this array by taking its sum, and returning that total.

Most of the code should be understandable when paired with the explanation. A few of the overlooked commands:

  • Ω : The reverse operator. Takes a dyad and reverses the order of the arguments
  • : The table operator, as described above.
  • ¦ : The fold operator. Takes an array and a dyad and reduces by the dyad. ¦+ is an alias for sum.
\$\endgroup\$
1
\$\begingroup\$

MathGolf, 9 bytes

╤■mæ²Σk=Σ

Try it online.

Explanation:

╤         # Take the (implicit) input-integer, and push a list in the range [-input, input]
 ■        # Take the cartesian product of this, creating a list of all possible pairs
  mæ      # Map these pairs to, using the following four commands:
    ²     #  Take the square of both values in the pair
     Σ    #  Sum those
      k=  #  And check whether it's equal to the input-integer (1 if truthy; 0 if falsey)
  Σ       # After the map, sum the list
          # (after which the entire stack joined together is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 7 bytes

(ŸãnOQO

Try it online or verify the test cases in the range \$[0,100]\$.

Explanation:

(        # Get the negative of the (implicit) input-integer
 Ÿ       # Push a list in the range [(implicit) input-integer, -input]
  ã      # Get the cartesian product of this list, creating all possible pairs
   n     # Square each value in each pair
    O    # Sum each inner pair
     Q   # Check for each sum whether it's equal to the (implicit) input-integer
         # (1 if truthy; 0 if falsey)
      O  # And sum those
         # (after which the result is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

Jelly, 7 bytes

rNp`²§ċ

Try it online!

How it works

rNp`²§ċ - Main link. Takes n on the left
 N      - Yield -n
r       - Take the range [-n, -n+1, ..., -1, 0, 1, ..., n-1, n]
   `    - Use this list for both arguments for:
  p     -   Cartesian product
    ²   - Square each number
     §  - Take the sums of each pair
      ċ - Count the number of times n appears
\$\endgroup\$
1
\$\begingroup\$

Japt -x, 11 bytes

õUn)ï £¶Xx²

Try it

õUn)ï £¶Xx²     :Implicit input of integer U
õ               :Inclusive range from U to
 Un             :  -U
   )            :End range
    ï           :Cartesian product with itself
      £         :Map each X
       ¶        :  Test U for equality with
        Xx      :    X reduced by addition after
          ²     :      Squaring each
                :Implicit output of sum of resulting array
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 52 bytes

56 bytes:

$n=pop;for$a(@a=-$n..$n){map$i+=$_*$_+$a*$a==$n,@a}say$i

If output can be in base 1, then 52 bytes:

$n=pop;for$a(@a=-$n..$n){print$_*$_+$a*$a==$n for@a}
\$\endgroup\$
4
  • \$\begingroup\$ Why waste so many bytes using an array? You can do the -$n..$n in the for statement... \$\endgroup\$ Commented Nov 26, 2015 at 9:13
  • \$\begingroup\$ @WouterVerheist I use @a twice, and wouldn't save bytes writing -$n..$n twice. However, presumably I can incorporate the assignment to @a into the first time it's used, which will save 3 bytes. If I have an opportunity to test it and remember to do so, I'll do so and revise this answer. \$\endgroup\$
    – msh210
    Commented Nov 26, 2015 at 14:56
  • \$\begingroup\$ Ah, yes, missed that. I must be blind. \$\endgroup\$ Commented Nov 26, 2015 at 14:58
  • \$\begingroup\$ @WouterVerhelst But thanks for the tip: you saved me three bytes. \$\endgroup\$
    – msh210
    Commented Nov 26, 2015 at 17:44
0
\$\begingroup\$

Python, 76 74 bytes

I'm sure this can be golfed more, but I need to get back to work.

lambda n:sum([1for a in range(-n,n+1)for b in range(-n,n+1)if a*a+b*b==n])

Try it online

Thanks to @mathmandan for taking off 2 bytes.

\$\endgroup\$
3
  • \$\begingroup\$ Quick note: a*a+b*b is shorter than a**2+b**2. Also the square brackets aren't required here, so you can get down to 72 bytes. (FYI, it looks like def f(n):r=range(-n,n+1);print sum(1for j in r for i in r if i*i+j*j==n) is also the exact same score.) \$\endgroup\$
    – mathmandan
    Commented Nov 26, 2015 at 18:02
  • \$\begingroup\$ Thanks. The a*a is almost obvious - stupid I didn't see that. The brackets are needed for the comprehension to work. So it's down to 74. Also putting lambda n,r=range results in the same length. Too bad... \$\endgroup\$
    – agtoever
    Commented Nov 27, 2015 at 8:02
  • 1
    \$\begingroup\$ Without the square brackets, it won't make a list, but it'll make a generator, which works fine with sum. docs.python.org/2/tutorial/classes.html#generator-expressions (Removed square brackets and tested fine in 2.7.4.) \$\endgroup\$
    – mathmandan
    Commented Nov 27, 2015 at 16:05
0
\$\begingroup\$

C, 224 219 182 175 158 bytes

Non-golfed version (with descriptive variables):

#include <math.h>

main (argc, argv) 
    char **argv;
{

    int n, count, max, i, j;
    n = atoi (argv[1]);
    count = 0;
    max = sqrt ((float) n);

    for (i = -max; i <= max; i++)
        for (j = -max; j <= max; j++)
            if (i * i + j * j == n)
                count++;

    printf ("%d", count);
}

Golfed version (with short variables):

#include<math.h>
main(c,v)char**v;{int n,o,x,i,j;n=atoi(v[1]);o=0;x=sqrt((float)n);for(i=-x;i<=x;i++)for(j=-x;j<=x;j++)if(i*i+j*j==n)o++;printf("%d",o);}

Update Sorry about the multiple edits, I'm learning how to abuse K&R-style C ;)

\$\endgroup\$
1
  • \$\begingroup\$ You can remove the sqrt and just set the forloop bounds to -n and +n. This calculates a lot more but is shorter ;) \$\endgroup\$
    – Simon
    Commented Dec 5, 2015 at 19:28
0
\$\begingroup\$

C++, 175 bytes

#include<iostream> using namespace std; int main() {int i,j,k=0,n; cin>>n; for(i=1;i<n;++i) for(j=1;j<n;++j) if(i*i+j*j==n) ++k; for(i=1;i<=n;++i) if(i*i==n) ++k; cout<<4*k;}

Ungolfed

#include<iostream>
using namespace std;
int main()
{
int i,j,k=0,n;
cin>>n;
for(i=1;i<n;++i)
 for(j=1;j<n;++j)
  if(i*i+j*j==n)
   ++k;
for(i=1;i<=n;++i)
 if(i*i==n)
  ++k;
cout<<4*k;
}
\$\endgroup\$
2
  • \$\begingroup\$ I hope it's okay now. \$\endgroup\$ Commented Nov 30, 2015 at 16:46
  • \$\begingroup\$ Not quite. 1. Given input of 0, it gives output of 0. That's a special case, and should be 1. 2. It doesn't compile as is. The #include needs a newline before the following statement. 3. Some tips: you can remove 11 chars just by cutting out unnecessary whitespace. You can remove more with some basic transformations like for(i=1;i<n;++i) being equivalent to for(i=0;++i<n;). If you change the range of the loop over j then I think you can eliminate the second loop over i entirely. \$\endgroup\$ Commented Nov 30, 2015 at 22:29
0
\$\begingroup\$

Ruby, 66 58 56 54 bytes

->n{r=-n..n;r.map{|x|r.count{|y|n==x*x+y*y}}.reduce:+}

Thanks to sherlock9.

56 bytes

->n{r=-n..n;r.map{|x|r.count{|y|n==x**2+y**2}}.reduce:+}

58 bytes

->n{c=0;r=(-n..n);r.map{|x|c+=r.count{|y|n==x**2+y**2}};c}

66 bytes

->n{c=0;(-n..n).each{|x|c+=n.downto(-n).count{|y|n==x**2+y**2}};c}

Ungolfed:

-> n {
  r = -n..n
  r.map { |x|
    r.count { |y|
      n == x*x + y*y
    }
  }.reduce:+
}

Usage:

->n{r=-n..n;r.map{|x|r.count{|y|n==x*x+y*y}}.reduce:+}[25]
=> 12
\$\endgroup\$
1
  • \$\begingroup\$ You can shave two bytes by using x*x+y*y \$\endgroup\$
    – Sherlock9
    Commented Nov 29, 2015 at 1:12
0
\$\begingroup\$

Swift 2.0, 110 108 107 bytes

var n=Int(readLine()!)!,c=0;for(var i = -n;i<=n;i++){for(var j = -n;j<=n;j++){if i*i+j*j==n{c++}}};print(c)

First attempt

\$\endgroup\$
4
  • \$\begingroup\$ I think you could save many bytes by removing whitespace. \$\endgroup\$
    – geokavel
    Commented Dec 6, 2015 at 3:35
  • \$\begingroup\$ I can only remove two but thanks! \$\endgroup\$
    – Simon
    Commented Dec 6, 2015 at 13:14
  • \$\begingroup\$ What about when you create the variables? \$\endgroup\$
    – geokavel
    Commented Dec 6, 2015 at 15:57
  • \$\begingroup\$ The online swift compiler gives errors in that cases, dont have a mac close atm \$\endgroup\$
    – Simon
    Commented Dec 6, 2015 at 20:39
0
\$\begingroup\$

C++, 81 bytes

#define F(x) for(int x=~n;x++<n;)
void f(int n,int&r){r=0;F(a)F(b)r+=a*a+b*b==n;}

Returns via reference parameter. Simply two ranges over [-n,n], so it works for n=0.

\$\endgroup\$
0
\$\begingroup\$

Axiom 115 bytes

g(n)==(v:INT:=truncate(sqrt(n)::Float);c:=0;for i in -v..v repeat for j in -v..v repeat if i^2+j^2=n then c:=c+1;c)

ungolfed

gg(n:NNI):NNI== 
   v:NNI:=truncate(sqrt(n)::Float)
   c:NNI:=0
   for i in -v..v repeat
      for j in -v..v repeat
          if i^2+j^2=n then c:=c+1
   c

results

(5) -> [i,g(i)]  for i in 0..25
   Compiling function g with type NonNegativeInteger -> NonNegativeInteger
   (5)
   [[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]]
                                      Type: Tuple List NonNegativeInteger

dobious results

(13) -> g(10018)
   (13)  8
                                                    Type: PositiveInteger
(14) -> g(10019)
   (14)  0
                                                 Type: NonNegativeInteger
(15) -> g(10020)
   (15)  0
\$\endgroup\$
0
\$\begingroup\$

Husk, 8 bytes

#¹´×+m□ṡ

Try it online! or Verify first 25 values

Husk, 8 bytes

#¹mṁ□π2ṡ

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Thunno 2 S, 7 bytes

ṄIDṖ²ʂ=

Try it online!

Explanation

ṄIDṖ²ʂ=  # Implicit input
ṄI       # Push [-input..input]
  DṖ     # Cartesian product
    ²ʂ   # Square and sum
      =  # Equals input?
         # Sum the list
         # Implicit output
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 45 + 1 (-a) = 46 bytes

$_=!$_+4*grep{$_=sqrt"@F"-$_*$_;!/\./}1..sqrt

Try it online!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.