44
\$\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\$
  • 4
    \$\begingroup\$ Wait, what?? "The sequence contains terms that are arbitrarily high, and the limit of its running average is π." \$\endgroup\$ – Stewie Griffin Nov 26 '15 at 11:58
  • \$\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 Nov 26 '15 at 12:04
  • 5
    \$\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\$ – Stewie Griffin Nov 26 '15 at 12:19
  • 29
    \$\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 Nov 26 '15 at 12:23
  • 2
    \$\begingroup\$ @xnor and there goes the magic:( \$\endgroup\$ – Andras Deak Nov 29 '15 at 1:02

42 Answers 42

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
    \$\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 Oct 31 '16 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\$
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\$
  • \$\begingroup\$ Why waste so many bytes using an array? You can do the -$n..$n in the for statement... \$\endgroup\$ – Wouter Verhelst Nov 26 '15 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 Nov 26 '15 at 14:56
  • \$\begingroup\$ Ah, yes, missed that. I must be blind. \$\endgroup\$ – Wouter Verhelst Nov 26 '15 at 14:58
  • \$\begingroup\$ @WouterVerhelst But thanks for the tip: you saved me three bytes. \$\endgroup\$ – msh210 Nov 26 '15 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\$
  • \$\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 Nov 26 '15 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 Nov 27 '15 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 Nov 27 '15 at 16:05
0
\$\begingroup\$

Python, 133 129 bytes

from itertools import*
n=input()
l=[];s=0
for i in range(-n,n+1):l.append(i**2)
for j in product(l,l):
 if sum(j)==n:s+=1
print s

This demonstrates the use of itertools cartesian product. Try it online

\$\endgroup\$
  • \$\begingroup\$ @Mego I tried, I don't think there is anything to further golf. I will take that part out if you insist. \$\endgroup\$ – TanMath Nov 28 '15 at 21:01
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\$
  • \$\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 Dec 5 '15 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\$
  • \$\begingroup\$ I hope it's okay now. \$\endgroup\$ – ghosts_in_the_code Nov 30 '15 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\$ – Peter Taylor Nov 30 '15 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\$
  • \$\begingroup\$ You can shave two bytes by using x*x+y*y \$\endgroup\$ – Sherlock9 Nov 29 '15 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\$
  • \$\begingroup\$ I think you could save many bytes by removing whitespace. \$\endgroup\$ – geokavel Dec 6 '15 at 3:35
  • \$\begingroup\$ I can only remove two but thanks! \$\endgroup\$ – Simon Dec 6 '15 at 13:14
  • \$\begingroup\$ What about when you create the variables? \$\endgroup\$ – geokavel Dec 6 '15 at 15:57
  • \$\begingroup\$ The online swift compiler gives errors in that cases, dont have a mac close atm \$\endgroup\$ – Simon Dec 6 '15 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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