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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Related \$\endgroup\$ – Manish Kundu Apr 3 '18 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 '18 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 '18 at 12:04
  • 2
    \$\begingroup\$ @ManishKundu I just explained how this challenge is different... \$\endgroup\$ – orlp Apr 3 '18 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 '18 at 14:07

30 Answers 30

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!

\$\endgroup\$
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!

\$\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.

\$\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
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for O_O... \$\endgroup\$ – Esolanging Fruit Apr 3 '18 at 20:37
  • \$\begingroup\$ The code.. it's staring at me. What do I do? \$\endgroup\$ – caird coinheringaahing Apr 3 '18 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
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You could shave off 3 bytes by replacing r?0:1 with !r. 42 bytes \$\endgroup\$ – etene Apr 3 '18 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 '18 at 12:52
  • 1
    \$\begingroup\$ @etene Well spotted, thank you! \$\endgroup\$ – O.O.Balance Apr 3 '18 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 '18 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 '18 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
\$\endgroup\$
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
\$\endgroup\$
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.
\$\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.

\$\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)'))
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog), 31 22 bytes

9 bytes saved thanks to @H.PWiz

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

Try it online!

\$\endgroup\$
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.

\$\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
\$\endgroup\$
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!

\$\endgroup\$
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.

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

Octave, 42 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Well, +1 I guess. :) Hadn't seen this when I posted mine. \$\endgroup\$ – Stewie Griffin Apr 3 '18 at 11:39
  • \$\begingroup\$ Heh. I hadn't seen yours either until now \$\endgroup\$ – Luis Mendo Apr 3 '18 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.

\$\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!

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

Jelly, 10 bytes

RżN$ŒpS€ċ0

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, -p 35 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 30 bytes

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

Try it online!

\$\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!

\$\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.
\$\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.

\$\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|+#
\$\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)
\$\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
\$\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
\$\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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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