Zero-sum counting

Write a program or function that given n ≥ 1 returns the number of solutions to ±1 ± 2 ± 3 ± ... ± n = 0.

For n = 6 there are no solutions, so the answer is 0. For n = 4 there are two solutions, so the answer is 2 (the two solutions are 1 - 2 - 3 + 4 = -1 + 2 + 3 - 4 = 0).

This is OEIS sequence A063865. Some example input/outpus are:

n       a(n)
1       0
2       0
3       2
4       2
5       0
6       0
7       8
8       14
9       0
10      0
11      70
12      124
13      0
14      0
15      722
16      1314

Shortest code in bytes wins.

• Related – Manish Kundu Apr 3 '18 at 11:26
• @ManishKundu Hm, I'd say that looks pretty much like a possible dupe target to me, just tack "length" at the end or instead of "filter by sum equals" do "sum each then count" to make an answer for this. – Erik the Outgolfer Apr 3 '18 at 11:52
• @EriktheOutgolfer I wasn't aware of that challenge, but the answer to this can be substantially different, see mine for example. – orlp Apr 3 '18 at 12:04
• @ManishKundu I just explained how this challenge is different... – orlp Apr 3 '18 at 12:09
• Yes, I saw that. While it's unfortunate that you accidentally hammered your own question, you shouldn't be compelled to cast a vote you disagree with. – Dennis Apr 3 '18 at 14:07

JavaScript (ES6), 35 bytes

Saved 1 byte thanks to @tsh

f=(n,s)=>n--?f(n,n-~s)+f(n,n+~s):!s

Try it online!

Wolfram Language (Mathematica), 33 bytes

Count[{1,-1}~Tuples~#.Range@#,0]&

Counts the n-tuples of 1 and -1 whose dot product with Range[n] is 0.

Try it online!

Try it online!

How it works

ŒPS€ċÆṁ$Main link. Argument: n ŒP Take the powerset of [1, ..., n]. S€ Take the sum of each subset.$  Combine the two links to the left into a monadic chain.
Æṁ       Compute the median of the sums, i.e, (1 + ... + n)/2.
ċ         Count the occurrences of the median.

Python 2, 74 bytes

def f(n):l=k=1;exec"l+=l<<n*k;k+=1;"*n;return(l>>n*n*-~n/4)%2**n*(~-n%4>1)

More of a fun submission, direct generating function computation.

Octave (with Communications Package), 39 bytes

@(n)sum((2*de2bi(0:2^n-1)-1)*(1:n)'==0)

Try it online!

Explanation:

Take a range 0 ... n^2-1 and convert it to binary. This gives a matrix with all combinations of 0 and 1. Multiply by 2 and subtract 1 to get a matrix with all combinations of -1 and +1.

Take the dot-product with a range 1 ... n to get all combinations of ±1 ± 2 ... ±n. Count how many are zero.

Basically the same thing, same byte count:

@(n)nnz(~((2*de2bi(0:2^n-1)-1)*(1:n)'))

APL (Dyalog), 31 22 bytes

9 bytes saved thanks to @H.PWiz

1⊥0=⊂∘⍳+.×¨∘,3-2×∘⍳⍴∘2

Try it online!

Python 2 and 3, 50 bytes

Recursive approach like most of the answers:

f=lambda n,r=0:f(n-1,r+n)+f(n-1,r-n)if n else r==0

Try it online

The double recursive call takes too much bytes... There's probably a way to simplify it.

Java 8, 7271 70 bytes

n->f(0,n)int f(int r,int n){return n>0?f(r+n,--n)+f(r+~n,n):r==0?1:0;}

Port of @Arnauld's JavaScript (ES6) answer.
-2 bytes thanks to @OlivierGrégoire.

Try it online.

Explanation:

n->                 // Method with integer parameter and integer return-type
f(0,n)            //  Call the recursive method with 0 and this parameter

int f(int r,int n){ // Recursive method with integer as both two parameters and return-type
return n>0?       //  If n is not 0 yet:
f(r+n,--n)      //   Recursive call with r+n (and n lowered by 1 first with --n)
+f(r+~n,n)      //   + Recursive call with r-n (and n also lowered by 1)
:r==0?           //  Else-if r is 0
1              //   Return 1
:               //  Else:
0;}            //   Return 0

A straightforward approach of computing all those sums and checking how many are zero.

f 0=[0]
f n=[(n+),(n-)]>>=(<$>f(n-1)) g x=sum[1|0<-f x] Try it online! EDIT: @H.PWiz has a shorter and way more elegant solution using mapM! Bash + GNU utilities, 63 bytes Bash can probably do better than this with recursive functions, but I can't resist this sort of eval/escape/expansion monstrosity: p=eval\ printf\ %s$p\\\\n \$[$($p \\\{+,-}{1..$1})]|grep -c ^0

Try it online!

Update: I don't think bash can do better with recursive functions. This is the best I could do for a score of 90. eval hell it is then.

Brachylog, 12 bytes

⟦₁{{ṅ|}ᵐ+0}ᶜ

Try it online!

Explanation

⟦₁               The range [1, …, Input]
{       }ᶜ     Count the number of times the following predicate succeeds on that range:
{  }ᵐ           Map for each element of the range:
ṅ                Negate
|               Or do nothing
+0         The sum of the elements after the map is 0

Octave, 42 bytes

@(n)sum((dec2bin(0:2^n-1)*2-97)*(1:n)'==0)

Try it online!

• Well, +1 I guess. :) Hadn't seen this when I posted mine. – Stewie Griffin Apr 3 '18 at 11:39
• Heh. I hadn't seen yours either until now – Luis Mendo Apr 3 '18 at 11:39

J, 32 bytes

1#.0=1#.1+i.*"1[:<:@+:@#:[:i.2^]

Try it online!

There is certainly much room for golfing. Exlpanation will follow.

(%0)
n%k|n<1=0^k^2|m<-n-1=m%(k+n)+m%(k-n)

Try it online!

• Nice, I had the same, but 0^abs k. – H.PWiz Apr 3 '18 at 21:06

Jelly, 10 bytes

How it works

:IFPlMF2K+}:@-}||0lMF$z+|h Main outer loop :IFPlMF ...... || : Duplicate top; effectively generate two explicit zeroes Top is the loop counter i; the rest is the generated 2**i sums I Take input as number F ........... | Pop n and loop n times P i++ lM Push stack length - 1, which is 2**(i-1) F ...... | Loop 2**(i-1) times Main inner loop: generate +i and -i from 2**(i-1) previous sums 2K+}:@-} Stack: [... x i] 2K [... x i x i] Copy top two +} [x+i ... x i] Add top two and move to the bottom :@ [x+i ... i i x] Duplicate top and rotate top 3 -} [i-x x+i ... i] Subtract and move to the bottom Counting zeroes 0lMF$z+|h
0lM        Push zero (zero count) and 2**n (loop count)
F...|   Loop 2**n times
\$z+    Swap top two; Take logical not; add to the count
h  Print top as number and halt