Given a nonnegative integer \$n\$, determine whether \$n\$ can be expressed as the sum of two square numbers, that is \$\exists a,b\in\mathbb Z\$ such that \$n=a^2+b^2\$.
0 -> truthy
1 -> truthy
2 -> truthy
3 -> falsy
4 -> truthy
5 -> truthy
6 -> falsy
7 -> falsy
11 -> falsy
9997 -> truthy
9999 -> falsy
Relevant OEIS sequences:
This is code-golf, so shortest answer as measured in bytes wins.
def f(n):[*{(n-2*x*x)**-2for x in range(n+1)}][n]
Numerics on this and the previous one may be fragile. I don't know whether n**-2 is guaranteed to give the same value as (-n)**-2.
If necessary this can be fixed at the cost of 1 byte.
def f(n):[*{(n-2*x*x)**-2 for x in range(n+1)}][n]
def f(n):[*{(n-2*x*x)**2 for x in range(n+1)}-{0}][n]
def f(n):[*{sorted({x*x,n-x*x})[1]for x in range(n+1)}][n]
Signals by exit code: Errors out for True and returns without error for False. The error is triggered by trying to access list positions which are out of bounds if n is the sum of two squares. In the last two versions the special case a=b triggers a zero division error.
All versions avoid double loops. The first version does it rather clumsily by computing x^2 and n-x^2, taking the maximum and checking for collisions (by counting uniques). The convoluted way of taking the max catches the special case a=b.
The second version implements the same logic a bit smarter: instead of taking the maximum of two values it makes use of he observation that
`n = a^2 + b^2`
can be rewritten
`abs(n-2a^2) = abs(n-2b^2)`
instead of the absolute value we can also take squares. AS before we can check for collisions as long as we do not forget the special case a=b.
The last version takes the reciprocal such that the a=b case triggers a zero division error.
function(n)all((n-(1:n)^2)^.5%%1)
Outputs NA if n is not the sum of 2 squares, FALSE if n is the sum of 2 squares.
If we are restricted to TRUE/FALSE output, then add +4 bytes for 37 bytes, or +3 bytes for 36 bytes if we can reverse the output.
Or R>=4.1, 32 bytes by replacing the word function with a \.
Edit: -2 bytes thanks to @Giuseppe.
function(n)n%in%outer(k<-(0:n)^2,k,`+`)
n%in%outer(k,k,"+") be shorter?
\$\endgroup\$
2^n is in 2^k %o% 2^k, which is shorter than having to call outer: 37 bytes
\$\endgroup\$
Commented
Feb 8, 2022 at 21:00
a,b;f(n){for(a=n;~a*n;b=b?--b:--a)n*=a*a+b*b!=n;a=n;}
-14 bytes - thanks to Kevin Cruijssen
-7 bytes - by omitting return (using global variable)
-1 byte - by using - instead of !=
-2 bytes - thanks to AZTECCO
-11 bytes - thanks to AZTECCO x2
for-loops instead of while-loops. Also, you currently have a hard-coded upper-bound of 2,000,000 (\$2\times1000^2\$), so you might want to mention that in your answer. Both shorter and more correct would be to use the input n instead of 1e3 though: 74 bytes
\$\endgroup\$
Commented
Feb 7, 2022 at 9:49
g=g mean?:)
\$\endgroup\$
RM, 5 bytesẊ²Ṡ=a
Ẋ # Cartesian product of (implicit range) self with (implicit range) self
² # Square each
Ṡ # Sums of each
a # Do any...
= # Equal the input?
^((x(x*))(?=.*(?=\2*$)(\3+$))\4|){2}$
Try it online! - ECMAScript
Try it online! - Perl
Try it online! - Java
Try it online! - Python
Try it online! - Ruby
Try it online! - PCRE
Try it online! - .NET
Takes its input in unary, as a string of x characters whose length represents the number. Uses a variant of the multiplication/squaring algorithm explained in this post.
Commented and indented:
^ # tail = N = input number
( # subtract a perfect square from tail
# subtract a nonzero perfect square from tail
(x(x*)) # \2 = any positive integer; \3 = \2-1; tail -= \2
(?=
.* # find the smallest value of tail that satisfies the following
(?=\2*$) # assert \2 divides tail
(\3+$) # assert \3 divides tail at least once; \4 = \2*\2 - \2
)
\4 # along with "tail -= \2" above, acts as "tail -= \2*\2"
|
# or just subtract 0 from tail
){2} # do this twice
$ # assert that tail == 0
This can be generalized to sums of any number of squares by changing the 2 in {2} to the desired count.
^(\1?(\2xx|^x)*){2}$
Try it online! / Attempt This Online! - Perl
Try it online! / Attempt This Online! - Java
Try it on regex101 / Attempt This Online! - PCRE2
Try it online! - .NET
^ # tail = N = input number
( # The following will be captured in \1
\1? # Optionally subtract the previous perfect square from tail
(\2xx|^x)* # If on the first iteration, subtract a perfect square from tail;
# if on the second iteration and "\1?" was evaluated once,
# combines with it to subtract a perfect square from tail that
# is greater than or equal to the previous one; if "\1?" was
# evaluated zero times, this adjusts the first perfect square
# subtracted, optionally increasing it to a larger one, which
# effectively makes the "other" perfect square zero.
){2} # Iterate this twice
$ # Assert that tail == 0
~+Ċ~^₂ᵐ
If you put a variable name such as Z as argument, you’ll get the actual couple of values whose squared sum is the input.
It’s a direct description of the problem:
~+Ċ Get a couple of two values Ċ whose sum is the input
Ċ~^₂ᵐ Both elements of Ċ must be squares of some numbers
Returns a positive integer for Truthy, and 0 for Falsey.
f=(n,x=1)=>x>n?!n:!(n%x)-f(n,x+2)
This is a trivial modification of @MitchSchwartz's brilliant answer to Count sums of two squares.
It can be proven that if \$ n \$ has more \$ 4k + 1 \$ divisors than \$ 4k + 3 \$ divisors, that it can be written as the sum of two squares. One way to achieve this would be to add 1 if n%(4*k+1)==0, and -1 if n%(4*k+3)==0. Writing this down, we can see that the task comes down to computing the following alternating sum:
!(n%1) - !(n%3) + !(n%5) - !(n%7) + ...
which can then be written as:
!(n%1) - (!(n%3) - (!(n%5) - (!(n%7) - ... )))`
The base case of !n handles the special case where n=0, by returning 1 instead.
function(n,k=2^(0:n)^2)2^n%in%(k%o%k)
This checks whether \$2^n\$ can be written as \$2^{a^2}\times 2^{b^2}\$. This will rapidly run into numerical issues, but is shorter than pajonk's similar answer because we can then use %o% instead of outer. Note that Dominic's R answer remains 4 bytes shorter.
range(n*n+1) be range((n+1)*(n+1)) or range((n+1)**2) to combine the two statements of range(n+1)?
\$\endgroup\$
range(n+1) for both summands, as one of them will always be <= n/2.
\$\endgroup\$
~n*~n (== -(n+1) * -(n+1)) for the same byte count.
\$\endgroup\$
ŻpŻ²§i
Outputs 0 for falsy, and a non-zero positive integer for truthy. The Footer in the TIO link simply splits the range \$[0, n]\$ into truthy (top line) and falsey (bottom line)
ŻpŻ²§i - Main link. Takes n on the left
Ż - Zero range; [0, 1, ..., n]
Ż - Zero range; [0, 1, ..., n]
p - Cartesian product
² - Square everything
§ - Sums of each pair
i - Index of n, or 0
a=.5
f(n)=min(ceil(mod((n-[0...floor(n^a)]^2)^a,1)))
Try It On Desmos! - Prettified
l=[0...n]
f(n)=min(sign([aa+bb-nfora=l,b=l])^2)
ÝãnOIå
Bugfixed and -2 bytes thanks to @Mr.Xcoder, making it now similar as @emanresuA's Vyxal answer and @cairdCoinheringaahing's Jelly answer.
Try it online or verify the smaller test cases.
Explanation:
Ý # Push a list in the range [0, (implicit) input]
ã # Create all possible pairs with the cartesian product
n # Square each integer
O # Sum each inner pair
Iå # Check if this list contains the input
# (after which the result is output implicitly)
0, right?)
\$\endgroup\$
Commented
Feb 7, 2022 at 19:49
ÝãnOsk might save 2 bytes (with falsy output -1 and truthy output any nonnegative integer)
\$\endgroup\$
Commented
Feb 7, 2022 at 19:50
(load library
(d V repeat-val
(d R(q((N)(map* *(0to N)(0to N
(q((N)(any(map* contains?(V(map* s(V N(a N 1))(R N))(a N 1))(R N
(d S from your code (though not from the TIO version) to get 125 bytes. This is important because I'm about to post a different solution that ties your bytecount... ;)
\$\endgroup\$
(d X(q((N I)(i(l N 1)N(X(s N I)(a I 2
(d S(q((I N)(i(a(X I 1)(X(s N I)1))(i(l N I)0(S(a I 1)N))1
(q((N)(S 0 N
The last line is an anonymous function that takes a number and returns 1 if it is the sum of two squares, 0 otherwise. Try it online!
Look, ma, no library!
First, we define a helper function X that takes a number N and determines if it is (not) a square. A perfect square is the sum of consecutive odd numbers; therefore, subtracting the sum of the first several odd numbers from N (for an appropriate value of "several") will result in 0 if N is square. Thus, we recurse over increasingly large odd numbers (which we track as I) and subtract each one from N until N equals 0 (in which case N is square) or N is less than 0 (in which case N is not square):
(def not-square? ; Define not-square?
(lambda (N I) ; as a function of two arguments:
(if (less? N 1) ; If N is less than 1,
N ; return N (0 if square, negative if not square)
(not-square? ; Else, recurse with these arguments:
(sub2 N I) ; New N is previous N minus current odd number
(add2 I 2))))) ; New I is the next odd number
Next, we'll define a function S that determines whether a number N is the sum of two squares. Our algorithm here is to recurse over integers I starting at 0: if I is not square, or N minus I is not square, try the next I until N is less than I, at which point N cannot be the sum of two squares. On the other hand, if I and N minus I are both square, then N is the sum of two squares.
(def sum-squares? ; Define sum-squares?
(lambda (I N) ; as a function of two arguments:
(if ; If
(add2 ; the sum of
(not-square? ; 0 if
(sub2 N I) ; N minus I
1) ; is square, < 0 otherwise
; and
(not-square? I 1)) ; 0 if I is square, < 0 otherwise
; is truthy (nonzero), then:
(if (less? N I) ; If N is less than I
0 ; then return 0
(sum-squares? ; Else, recurse with these arguments:
(add2 I 1) ; New I is the next integer
N)) ; Same N
1 ; Else (I and N minus I are both square), return 1
Finally, our submission is an anonymous function that takes N only and passes it to sum-squares? with a starting I of 0:
(lambda (N)
(sum-squares? 0 N))
.+
$*
^((^1|11\2)*\1?){2}$
Try it online! Link includes test cases. Edit: Saved 5 bytes thanks to @Deadcode. Explanation: ^((^1|11\2)*) matches a square number at the beginning of the string. Repeating the expression with {2} does not in itself change this, but it allows the use of \1? to add a square number matched on the first iteration. (The first stage simply converts the decimal input to unary.)
\1? matter?
\$\endgroup\$
\1?. Now that I've explained it, I can see that its placement does not matter.
\$\endgroup\$
Ｎθ≔Ｘ…·⁰θ²η⊙η⊙η⁼θ⁺ιλ
Try it online! Link is to verbose version of code. Explanation:
Ｎθ
Input n.
≔Ｘ…·⁰θ²η
Generate a list of squares from 0 to n² inclusive (in case n<2).
⊙η⊙η⁼θ⁺ιλ
Check whether any pair sums to n.
=LET(x,SEQUENCE(SQRT(A1)+1,,1)^2,1-AND(ISERROR(XMATCH(A1-x,x))))
List all \$k^2\$ in \$[0..n]\$. Match all \$n - k^2\$ to list. If all matches are errors, then false, otherwise true.
0y&:U&+m
(Or this version for larger inputs)
1 for truthy, 0 for falsy. (Thanks to @Giuseppe for -1 byte and this neater output.)
Square every number from 0 upto the input, add all the combinations of them, and check if the input is in there. (The "larger inputs" version does the sensible - but non-golfy - thing of limiting the check upto the square root of the given number; same logic, two extra bytes, a lot less resource hunger.)
Returns 0 for truthy and 1 for falsy. Quite short considering it's a conventional language.
@(n)0||(k=0:n).^2+k.^2'-n
~n=1 in[i^2+j^2==n for i=0:n,j=0:n]
Thanks to MarcMush we can save a lot more! We can also replace f(n) with the slightly shorter version ~n!
&&true and √ (maybe also by using any)
\$\endgroup\$
~n=n∈(N=(0:n).^2).+N'
Based on David Scholz’s solution.
Thanks to dingledooper for shaving 5 bytes
~n=n in(N=(0:n).^2).+N'
\$\endgroup\$
Commented
Feb 17, 2022 at 21:16
}Q+M^^R2hQ2
I have a feeling that pyth can do better. 11 Bytes, you know, it's in comparison to other golfing languages a lot.
The algorithm is not different from the published answers and, consequently, the performance is not sufficient to calculate the two largest test values in less than 60 sec.
}Q # check whether the input value Q is within:
+M # the sums
^ 2 # of cartesian product with itself
^R2 # of squared
hQ # range of 0..Q
lambda n:(r:=range(n+1))and n in(i*i+j*j for i in r for j in r)
o=@(x)any(~mod(sqrt(x-(0:(x/2)^.5).^2),1));
taking advantage of vectorized code to search from 0 to sqrt(x/2), checking sqrt(x - i^2) is an integer with mod([],1)
o (so leaving it as an anonymous function definition), swapping (x/2) for just x, and outputting the other way around (so 1 for not sum of 2 squares) by removing ~ and changing to all...
\$\endgroup\$
Commented
Feb 10, 2022 at 20:36
