Zero-sum counting

Question

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.

Answer 1

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!

Answer 2

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!

Answer 3

Haskell, 42 bytes

f n=sum[1|0<-sum<$>mapM(\x->[x,-x])[1..n]]

Try it online!

This is 2 1 byte shorter than any recursive function that I could write.

Answer 4

05AB1E, 10 bytes

X®‚sã€ƶO_O

Try it online!

Explanation

X®‚          # push [1,-1]
   sã        # cartesian product with input
     €ƶ      # multiply each element in each list with its 1-based index
       O     # sum each list
        _    # logical negation of each sum
         O   # sum

Answer 5

C (gcc), 45 62 52 50 bytes

f(n,r){n=n?f(n-1,r+n)+f(n-1,r-n):!r;}F(n){f(n,0);}

Port of Kevin Cruijssen's Java 8 answer.

Try it online here.

Note that due to the improvements suggested in the comments, the code produces undefined behaviour to the point of not working when compiled with clang.

Thanks to etene for golfing 3 bytes. Thanks to Kevin Cruijssen for golfing 10 more bytes. Thanks to Christoph for golfing another 2 bytes.

Ungolfed version:

f(n, r) { // recursive function - return type and parameter type are omitted, they default to int
    n = // instead of returning, we set n - dirty trick
        n ? // if n is not 0, recurse
        f(n-1,r+n) // +n
       +f(n-1,r-n) // -n
        !r; // else if r != 0 return 0 else return 1
}
F(n) { // function to start the recursion; again implicitly int(int)
    n = f(n, 0); // call the recursive function; this time we simply don't return
}

Answer 6

05AB1E, 9 8 bytes

Thanks to Emigna for saving a byte!

Code:

LæO·sLO¢

Uses the 05AB1E encoding. Try it online!

Explanation

L           # Create the list [1, 2, .., input]
 æ          # Compute the powerset of this list
  O         # Sum each list
   ·        # Double each element
    sLO     # Compute the sum of [1, 2, .., input]
       ¢    # Count the number of occurrences

Answer 7

MATL, 14 13 bytes

[la]Z^G:!Y*~s

Thanks to @Giuseppe for saving 1 byte!

Try it online! Or verify all test cases.

Explanation

Consider n = 3 as an example. Stack is shown upside down, that is, newest appears below.

[la]   % Push array [1 -1]
       % STACK: [1 -1]
Z^     % Cartesian power with inplicit input n
       % STACK: [ 1  1  1
                  1  1 -1
                  1 -1  1
                  1 -1 -1
                 -1  1  1
                 -1  1 -1
                 -1 -1  1
                 -1 -1 -1]
G:     % Push n, range: gives [1 2 ... n]
       % STACK: [ 1  1  1
                  1  1 -1
                  1 -1  1
                  1 -1 -1
                 -1  1  1
                 -1  1 -1
                 -1 -1  1
                 -1 -1 -1],
                 [1  2  3]
!      % Transpose
       % STACK: [ 1  1  1
                  1  1 -1
                  1 -1  1
                  1 -1 -1
                 -1  1  1
                 -1  1 -1
                 -1 -1  1
                 -1 -1 -1],
                 [1
                  2
                  3]
Y*     % Matrix multiplication
       % STACK: [6
                 0
                 2
                -4
                 4
                -2
                 0
                -6]
~      % Logical negation
       % STACK: [0
                 1
                 0
                 0
                 0
                 0
                 1
                 0]
s      % Sum of vector. Implicit display
       % STACK: 2

Answer 8

Jelly, 8 bytes

ŒPS€ċÆṁ$

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.

Answer 9

APL (Dyalog), 31 22 bytes

9 bytes saved thanks to @H.PWiz

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

Try it online!

Answer 10

Java 8, 72 71 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

Answer 11

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.

Answer 12

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)'))

Answer 13

Haskell, 55 bytes

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!

Answer 14

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.

Answer 15

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.

Answer 16

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

Answer 17

Octave, 42 bytes

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

Try it online!

Answer 18

J, 32 bytes

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

Try it online!

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

Answer 19

Haskell, 41 bytes

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

Try it online!

Answer 20

Jelly, 10 bytes

RżN$ŒpS€ċ0

Try it online!

Answer 21

Perl 5, -p 35 bytes

#!/usr/bin/perl -p
$_=grep!eval,glob join"{+,-}",0..$_

Try it online!

Answer 22

Pari/GP, 30 bytes

n->Pol(prod(i=1,n,x^i+x^-i))%x

Try it online!

Answer 23

Stax, 9 bytes

è%é┐╬@₧╠¬

Run and debug it

One of the shortest answers so far defeated by Jelly.

I feel that checking explicitly which signs sum to zero is not very golfy, so instead I take the powerset and check how many sets in the powerset have the sum of half the nth triangular number. This method is, not surprisingly, of the same time complexity as checking which signs sum to zero.

ASCII equivalent:

RS{|+Hmx|+#

Answer 24

Prolog (SWI), 99 bytes

p(0,0,1).
p(0,_,0).
p(X,Y,Z):-A is X-1,B is Y+X,p(A,B,C),D is Y-X,p(A,D,E),Z is C+E.
X*Y:-p(X,0,Y).

Try it online!

Answer 25

Pyth, 14 13 bytes

lf!s.nT*F_BRS

Try it here

Explanation

lf!s.nT*F_BRS
            SQ  Take the list [1, ..., <implicit input>].
         _BR    Get the pairs [[1, -1], [2, -2], ...].
       *F       Take the Cartesian product.
 f!s.nT         Find the ones where the flattened sum is 0.
l               Take the length.

Answer 26

CJam, 25 bytes

ri,:)_Wf*:a.+:m*:e_1fb0e=

Try it online!

This is a fairly direct translation of @emigna's 05AB1E solution. It's certainly golfable.

Answer 27

Pyth, 10 bytes

/mysdySQsS

Try it online. Alternatively, verify all test cases at once.

Explaination:

/mysdySQsS    Implicit: Q=input()
      SQ      Generate range [1...Q]
     y        Generate powerset of above
 m            Map d in the above over...
  ysd         ... double the sum of d
        sS    Sum of range [1...Q] (final Q is implicit)
/             Count the matches (implicit output)

Answer 28

J, 28 bytes

(*>:){1j3#1+//.@(*/)/@,.=@i.

Uses the other definition from OEIS where a(n) = coefficient of x^(n(n+1)/4) in Product_{k=1..n} (1+x^k) if n = 0 or 3 mod 4 else a(n) = 0.

Try it online!

Explanation

(*>:){1j3#1+//.@(*/)/@,.=@i.  Input: n
                          i.  Range [0, n)
                        =     Self-Classify. Forms an identity matrix of order n
          1           ,.      Stitch. Prepend 1 to each row
                    /         Reduce using
                                Convolution
                 */               Product table
           +//.                   Sum along anti-diagonals
      1j3#                    Copy each once, padding with 3 zeroes after
     {                        Index at n*(n+1)
  >:                            Increment n
 *                              Times n

Answer 29

Husk, 9 bytes

#½Σḣ¹mΣṖḣ

Try it online!

Explanation

#½Σḣ¹mΣṖḣ  Implicit input
        ḣ  [1..input]
       Ṗ   Powerset
     mΣ    Sum each list
#          Count occurrence of
   ḣ¹        [1..input]
 ½Σ          Half of sum

Answer 30

Gol><>, 26 bytes

:IFPlMF2K+}:@-}||0lMF$z+|h

Try it online! or Run test cases from 1 to 16!

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