Écrivez un programme ou une fonction qui, pour n ≥ 1, renvoie le nombre de solutions à ± 1 ± 2 ± 3 ± ... ± n = 0.

Pour n = 6 il n'y a pas de solution, donc la réponse est 0. Pour n = 4 il y a deux solutions, donc la réponse est 2 (les deux solutions sont 1 - 2 - 3 + 4 = -1 + 2 + 3 - 4 = 0).

Il s'agit de la séquence OEIS A063865 . Voici quelques exemples d'entrées / sorties:

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

Le code le plus court en octets gagne.

JavaScript (ES6), 35 octets

1 octet enregistré grâce à @tsh

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

Essayez-le en ligne!

Wolfram Language (Mathematica) , 33 octets

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

nCompte les -tuples de 1 et -1 dont le produit scalaire avec Range[n]est 0.

Essayez-le en ligne!

Haskell , 42 octets

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

Essayez-le en ligne!

C'est 2 1 octet plus court que n'importe quelle fonction récursive que je pourrais écrire.

05AB1E , 10 octets

X®‚sã€ƶO_O

Essayez-le en ligne!

Explication

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

C (gcc), 45 62 52 50 octets

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

Port de la réponse Java 8 de Kevin Cruijssen .

Essayez-le en ligne ici .

Notez qu'en raison des améliorations suggérées dans les commentaires, le code produit un comportement non défini au point de ne pas fonctionner lorsqu'il est compilé avec clang.

Merci à etene pour avoir joué au golf 3 octets. Merci à Kevin Cruijssen d' avoir joué au golf 10 octets de plus. Merci à Christoph d' avoir joué encore 2 octets.

Version non golfée:

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
}

05AB1E , 9 8 octets

Merci à Emigna d' avoir enregistré un octet!

Code:

LæO·sLO¢

Utilise l' encodage 05AB1E . Essayez-le en ligne!

Explication

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

MATL , 14 13 octets

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

Merci à @Giuseppe d' avoir économisé 1 octet!

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Considérez n = 3comme exemple. La pile est affichée à l'envers, c'est-à-dire que le plus récent apparaît ci-dessous.

[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

Gelée , 8 octets

ŒPS€ċÆṁ$

Essayez-le en ligne!

Comment ça marche

Œ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 octets

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)

Plus d'une soumission amusante, calcul de fonction de génération directe.

Octave (avec module de communication), 39 octets

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

Essayez-le en ligne!

Explication:

Prenez une plage de 0 ... n ^ 2-1 et convertissez-la en binaire. Cela donne une matrice avec toutes les combinaisons de 0 et 1 . Multipliez par 2 et soustrayez 1 pour obtenir une matrice avec toutes les combinaisons de -1 et +1 .

Prenez le produit scalaire avec une plage de 1 ... n pour obtenir toutes les combinaisons de ± 1 ± 2 ... ± n . Comptez combien sont nuls.

Fondamentalement, la même chose, même nombre d'octets:

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

APL (Dyalog) , 31 22 octets

9 octets enregistrés grâce à @ H.PWiz

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

Essayez-le en ligne!

Python 2 et 3, 50 octets

Approche récursive comme la plupart des réponses:

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

Essayez-le en ligne

Le double appel récursif prend trop d'octets ... Il y a probablement un moyen de le simplifier.

Java 8, 72 71 70 octets

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 de la réponse JavaScript (ES6) de @Arnauld .
-2 octets grâce à @ OlivierGrégoire .

Essayez-le en ligne.

Explication:

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

Haskell , 55 octets

Une approche simple pour calculer toutes ces sommes et vérifier combien sont nulles.

f 0=[0]
f n=[(n+),(n-)]>>=(<$>f(n-1))
g x=sum[1|0<-f x]

Essayez-le en ligne!

EDIT: @ H.PWiz a une solution plus courte et beaucoup plus élégante en utilisant mapM!

Utilitaires Bash + GNU, 63 octets

Bash peut probablement faire mieux que cela avec des fonctions récursives, mais je ne peux pas résister à ce genre de evalmonstruosité / escape / expansion:

p=eval\ printf\ %s
$p\\\\n \$[$($p \\\{+,-}{1..$1})]|grep -c ^0

Essayez-le en ligne!

Mise à jour: je ne pense pas que bash puisse faire mieux avec les fonctions récursives. C'est le mieux que j'ai pu faire pour un score de 90 . evall'enfer c'est alors.

Brachylog , 12 octets

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

Essayez-le en ligne!

Explication

⟦₁               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 octets

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

Essayez-le en ligne!

J , 32 octets

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

Essayez-le en ligne!

Il y a certainement beaucoup de place pour le golf. Une explication suivra.

Haskell , 41 octets

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

Essayez-le en ligne!

Gelée , 10 octets

RżN$ŒpS€ċ0

Essayez-le en ligne!

Perl 5 , -p35 octets

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

Essayez-le en ligne!

Pari / GP , 30 octets

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

Essayez-le en ligne!

Prolog (SWI) , 99 octets

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

Essayez-le en ligne!

Pyth, 14 13 octets

lf!s.nT*F_BRS

Essayez-le ici

Explication

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.

CJam , 25 octets

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

Essayez-le en ligne!

Il s'agit d'une traduction assez directe de la solution 05AB1E de @ emigna. C'est certainement golfable.

Stax , 9 octets

è%é┐╬@₧╠¬

Exécuter et déboguer

Une des réponses les plus courtes jusqu'à présent vaincue par Jelly.

Je pense que vérifier explicitement quels signes somme à zéro n'est pas très golfique, donc je prends le jeu de puissance et vérifie combien de jeux dans le jeu de puissance ont la somme de la moitié du nième nombre triangulaire. Il n'est pas surprenant que cette méthode ait la même complexité temporelle que la vérification des signes dont la somme est nulle.

Équivalent ASCII:

RS{|+Hmx|+#

Pyth , 10 octets

/mysdySQsS

Essayez-le en ligne. Vous pouvez également vérifier tous les cas de test à la fois .

Explication:

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

J , 28 octets

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

Utilise l'autre définition d'OEIS où 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.

Essayez-le en ligne!

Explication

(*>:){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

Coque , 9 octets

#½Σḣ¹mΣṖḣ

Essayez-le en ligne!

Explication

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

Gol> <> , 26 octets

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

Essayez-le en ligne! ou Exécutez des cas de test de 1 à 16!

Comment ça marche

: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