25
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
13
  • 2
    \$\begingroup\$ Related \$\endgroup\$
    – Manish Kundu
    Apr 3, 2018 at 11:26
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Erik the Outgolfer
    Apr 3, 2018 at 11:52
  • 2
    \$\begingroup\$ @EriktheOutgolfer I wasn't aware of that challenge, but the answer to this can be substantially different, see mine for example. \$\endgroup\$
    – orlp
    Apr 3, 2018 at 12:04
  • 2
    \$\begingroup\$ @ManishKundu I just explained how this challenge is different... \$\endgroup\$
    – orlp
    Apr 3, 2018 at 12:09
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Dennis
    Apr 3, 2018 at 14:07

30 Answers 30

Reset to default
10
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
9
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
9
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ The code.. it's staring at me. What do I do? \$\endgroup\$
    – caird coinheringaahin g ♦
    Apr 3, 2018 at 23:23
5
\$\begingroup\$

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
}
Improve this answer
\$\endgroup\$
13
  • 1
    \$\begingroup\$ You could shave off 3 bytes by replacing r?0:1 with !r. 42 bytes \$\endgroup\$
    – etene
    Apr 3, 2018 at 12:49
  • 2
    \$\begingroup\$ It looks like you're taking additional input here in order to set the initial value of r, which isn't permitted. \$\endgroup\$
    – Shaggy
    Apr 3, 2018 at 12:52
  • 1
    \$\begingroup\$ @etene Well spotted, thank you! \$\endgroup\$
    – O.O.Balance
    Apr 3, 2018 at 13:00
  • 2
    \$\begingroup\$ @KevinCruijssen better yet the second n= isn't necessary either: f(n,r){n=n?f(n-1,r+n)+f(n-1,r-n):!r;}F(n){f(n,0);}. \$\endgroup\$
    – Christoph
    Apr 3, 2018 at 13:59
  • 2
    \$\begingroup\$ @O.O.Balance the trick is two's complement. This means that -x = ~x+1and therefore ~x = -x-1. \$\endgroup\$
    – Christoph
    Apr 3, 2018 at 14:03
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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)'))
Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

APL (Dyalog), 31 22 bytes

9 bytes saved thanks to @H.PWiz

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

Try it online!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Octave, 42 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Well, +1 I guess. :) Hadn't seen this when I posted mine. \$\endgroup\$
    – Stewie Griffin
    Apr 3, 2018 at 11:39
  • \$\begingroup\$ Heh. I hadn't seen yours either until now \$\endgroup\$
    – Luis Mendo
    Apr 3, 2018 at 11:39
2
\$\begingroup\$

J, 32 bytes

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

Try it online!

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Haskell, 41 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nice, I had the same, but 0^abs k. \$\endgroup\$
    – H.PWiz
    Apr 3, 2018 at 21:06
1
\$\begingroup\$

Jelly, 10 bytes

RżN$ŒpS€ċ0

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl 5, -p 35 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 30 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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|+#
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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