Skip to main content
Add explanation
Source Link
dingledooper
  • 22.9k
  • 1
  • 36
  • 125

JavaScript (Node.js), 33 bytes

Returns a positive integer for Truthy, and 0 for Falsey.

f=(n,x=1)=>x>n?!n:!(n%x)-f(n,x+2)

Try it online!

This is a trivial modification of @MitchSchwartz's brilliant answer to Count sums of two squares.

Explanation

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.

JavaScript (Node.js), 33 bytes

Returns a positive integer for Truthy, and 0 for Falsey.

f=(n,x=1)=>x>n?!n:!(n%x)-f(n,x+2)

Try it online!

JavaScript (Node.js), 33 bytes

Returns a positive integer for Truthy, and 0 for Falsey.

f=(n,x=1)=>x>n?!n:!(n%x)-f(n,x+2)

Try it online!

This is a trivial modification of @MitchSchwartz's brilliant answer to Count sums of two squares.

Explanation

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.

Source Link
dingledooper
  • 22.9k
  • 1
  • 36
  • 125

JavaScript (Node.js), 33 bytes

Returns a positive integer for Truthy, and 0 for Falsey.

f=(n,x=1)=>x>n?!n:!(n%x)-f(n,x+2)

Try it online!