Numéros de Bernoulli

23

Les nombres de Bernoulli (spécifiquement, les seconds nombres de Bernoulli) sont définis par la définition récursive suivante:

deuxièmes numéros de Bernoulli

Où mCkdénote une combinaison .

Étant donné un entier non négatif men entrée, émettez la représentation décimale OU une fraction réduite pour le mdeuxième nombre de Bernoulli. Si vous affichez une représentation décimale, vous devez avoir au moins 6 décimales (chiffres après la virgule décimale) de précision, et elle doit être précise lorsqu'elle est arrondie à 6 décimales. Par exemple, pour m = 2, 0.166666523est acceptable car il arrondit à 0.166667. 0.166666389n'est pas acceptable, car il arrondit à 0.166666. Les zéros de fin peuvent être omis. La notation scientifique peut être utilisée pour les représentations décimales.

Voici l'entrée et la sortie attendue mjusqu'à 60 inclusivement, en notation scientifique arrondie à 6 décimales et en fractions réduites:

0 -> 1.000000e+00 (1/1)
1 -> 5.000000e-01 (1/2)
2 -> 1.666667e-01 (1/6)
3 -> 0.000000e+00 (0/1)
4 -> -3.333333e-02 (-1/30)
5 -> 0.000000e+00 (0/1)
6 -> 2.380952e-02 (1/42)
7 -> 0.000000e+00 (0/1)
8 -> -3.333333e-02 (-1/30)
9 -> 0.000000e+00 (0/1)
10 -> 7.575758e-02 (5/66)
11 -> 0.000000e+00 (0/1)
12 -> -2.531136e-01 (-691/2730)
13 -> 0.000000e+00 (0/1)
14 -> 1.166667e+00 (7/6)
15 -> 0.000000e+00 (0/1)
16 -> -7.092157e+00 (-3617/510)
17 -> 0.000000e+00 (0/1)
18 -> 5.497118e+01 (43867/798)
19 -> 0.000000e+00 (0/1)
20 -> -5.291242e+02 (-174611/330)
21 -> 0.000000e+00 (0/1)
22 -> 6.192123e+03 (854513/138)
23 -> 0.000000e+00 (0/1)
24 -> -8.658025e+04 (-236364091/2730)
25 -> 0.000000e+00 (0/1)
26 -> 1.425517e+06 (8553103/6)
27 -> 0.000000e+00 (0/1)
28 -> -2.729823e+07 (-23749461029/870)
29 -> 0.000000e+00 (0/1)
30 -> 6.015809e+08 (8615841276005/14322)
31 -> 0.000000e+00 (0/1)
32 -> -1.511632e+10 (-7709321041217/510)
33 -> 0.000000e+00 (0/1)
34 -> 4.296146e+11 (2577687858367/6)
35 -> 0.000000e+00 (0/1)
36 -> -1.371166e+13 (-26315271553053477373/1919190)
37 -> 0.000000e+00 (0/1)
38 -> 4.883323e+14 (2929993913841559/6)
39 -> 0.000000e+00 (0/1)
40 -> -1.929658e+16 (-261082718496449122051/13530)
41 -> 0.000000e+00 (0/1)
42 -> 8.416930e+17 (1520097643918070802691/1806)
43 -> 0.000000e+00 (0/1)
44 -> -4.033807e+19 (-27833269579301024235023/690)
45 -> 0.000000e+00 (0/1)
46 -> 2.115075e+21 (596451111593912163277961/282)
47 -> 0.000000e+00 (0/1)
48 -> -1.208663e+23 (-5609403368997817686249127547/46410)
49 -> 0.000000e+00 (0/1)
50 -> 7.500867e+24 (495057205241079648212477525/66)
51 -> 0.000000e+00 (0/1)
52 -> -5.038778e+26 (-801165718135489957347924991853/1590)
53 -> 0.000000e+00 (0/1)
54 -> 3.652878e+28 (29149963634884862421418123812691/798)
55 -> 0.000000e+00 (0/1)
56 -> -2.849877e+30 (-2479392929313226753685415739663229/870)
57 -> 0.000000e+00 (0/1)
58 -> 2.386543e+32 (84483613348880041862046775994036021/354)
59 -> 0.000000e+00 (0/1)
60 -> -2.139995e+34 (-1215233140483755572040304994079820246041491/56786730)

Implémentation de référence (en Python 3):

def factorial(n):
    if n < 1:
        return 1
    else:
        return n * factorial(n - 1)

def combination(m,k):
    if k <= m:
        return factorial(m)/(factorial(k) * factorial(m - k))
    else:
        return 0

def Bernoulli(m):
    if m == 0:
        return 1
    else:
        t = 0
        for k in range(0, m):
            t += combination(m, k) * Bernoulli(k) / (m - k + 1)
        return 1 - t

Règles

  • C'est le code-golf , donc le code le plus court en octets gagne
  • Vous ne pouvez utiliser aucune fonction, intégrée ou incluse dans une bibliothèque externe, qui calcule l'un ou l'autre type de nombres de Bernoulli ou de polynômes de Bernoulli.
  • Votre réponse doit donner une sortie correcte pour toutes les entrées jusqu'à 60 inclus.

Classement

L'extrait de pile au bas de cet article génère le classement à partir des réponses a) comme une liste des solutions les plus courtes par langue et b) comme un classement général.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

## Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les rayant. Par exemple:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou que vous souhaitez répertorier les pénalités de drapeau d'interprète séparément), assurez-vous que le score réel est le dernier numéro de l'en-tête:

## Perl, 43 + 2 (-p flag) = 45 bytes

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de code:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Afficher l'extrait de code

code-golf math sequence combinatorics Mego
la source
@MorganThrapp L'implémentation de référence sert uniquement à clarifier la définition d'un nombre de Bernoulli, et non à résoudre réellement le problème.
Mego
Ah, gotcha. Je pensais que c'était une implémentation entièrement fonctionnelle.
Morgan Thrapp
2
@Mego Aucun flotteur standard (pas même une précision quad) ne peut stocker B_60 en précision quad. Devrions-nous alors utiliser un format de précision étendue si nous sortons en décimales?
lirtosiast
8
Je n'aime pas l'exigence de précision. Certaines langues n'ont pas les outils pour travailler avec des flotteurs avec une précision suffisante pour B_60, et je préfère ne pas traiter de tels problèmes lors du golf d'un problème mathématique. Il est frustrant de rédiger une solution, puis de constater qu'elle n'est pas valide en raison de ce qui semble être une technicité.
xnor
2
@xnor 6 chiffres de précision semblent déjà incroyablement laxistes.
primo

Réponses:

8

Julia, 23 20 octets

Enregistré 3 octets grâce à Alex A.

Il utilise la même formule que ma solution Mathematica et ma solution PARI / GP .

n->n>0?-zeta(1-n)n:1
alephalpha
la source
2
20 octets:n->n>0?-zeta(1-n)n:1
Alex A.
@AlexA. Je ne sais pas pourquoi, mais zeta(n)jette une erreur quand nest un entier négatif. J'utilise Julia 0.2.1 sur linux.
alephalpha
1
Oh mon Dieu, votre version de Julia est assez obsolète. Cela fonctionne très bien pour moi sur 0.4.1.
Alex A.
25

Mathematica, 40 28 23 22 octets

En utilisant la célèbre formule n * ζ (1− n ) = - B n , où ζ est la fonction Riemann Zeta .

If[#>0,-Zeta[1-#]#,1]&

La même longueur:

B@0=1;B@n_=-Zeta[1-n]n

Solution originale, 40 octets, utilisant la fonction génératrice des nombres de Bernoulli .

#!SeriesCoefficient[t/(1-E^-t),{t,0,#}]&
alephalpha
la source
+2 si je pouvais ...
LegionMammal978
9

Julia, 58 octets

B(m)=m<1?1:1-sum(k->big(binomial(m,k))*B(k)/(m-k+1),0:m-1)

Cela crée une fonction récursive Bqui accepte un entier et renvoie un BigFloat(c'est-à-dire virgule flottante de haute précision).

Non golfé:

function B(m::Integer)
    m == 0 && return 1
    return 1 - sum(k -> big(binomial(m, k)) * B(k) / (m-k+1), 0:m-1)
end
Alex A.
la source
9

Minkolang 0,14 , 97 octets

J'ai essayé de le faire récursivement en premier, mais mon interprète, tel qu'il est actuellement conçu, ne peut pas le faire. Si vous essayez de récuser à partir d'une boucle for, il démarre une nouvelle récursivité. J'ai donc opté pour l'approche de tabulation ... qui avait des problèmes de précision. J'ai donc fait le tout avec des fractions. Sans prise en charge intégrée des fractions. [ soupir ]

n1+[xxi$z0z2%1+F0c0=$1&$d4Mdm:1R:r$dz1Az0A]$:N.
11z[i0azi6M*i1azi-1+*d0c*1c2c*-1c3c*4$X]f
z1=d1+f

Essayez-le ici. Bonus: le tableau a toutes les fractions pour chaque numéro de Bernoulli précédent!

Explication (un peu)

n1+                 Take number from input (N) and add 1
   [                Open for loop that runs N+1 times (starts at zero)
    xx              Dump the top two values of the stack
      i$z           Store the loop counter in the register (m)
         0          Push 0
          z2%1+     Push 1 if N is even, 2 if odd
               F    Gosub; pops y,x then goes to codebox(x,y), to be returned to

    0c                                 Copy the first item on the stack
      ,                                1 if equal to 0, 0 otherwise
       $1&                             Jump 11 spaces if top of stack is not 0

                                       (If top of stack is not 0, then...)
          $d                           Duplicate whole stack
            4M                         Pop b,a and push GCD(a,b)
              dm                       Duplicate and merge (a,b,c,c -> a,c,b,c)
                :                      Divide
                 1R                    Rotate 1 item to the right (0G works too)
                   :                   Divide
                    r                  Reverse stack

                                       (In both cases...)
                     $d                Duplicate whole stack
                       z1A             Store denominator of B_m in array
                           z0A         Store numerator of B_m in array
                              ]        Close for loop
                               $:      Divide (float division)
                                 N.    Output as number and stop.

11                                           Push two 1s (a, b)
  z[                                         Open a for loop that repeats m times
    i0a                                      Retrieve numerator of B_k (p)
       zi                                    Push m, k
         6M                                  Pop k,m and push mCk (binomial) (x)
           *                                 p*x (c)
            i1a                              Retrieve denominator of B_k (q)
               zi-1+                         m-k+1 (y)
                    *                        q*y (d)
                     d                       Duplicate top of stack
                      0c*                    a*d
                         1c2c*               b*c
                              -              a*d-b*c
                               1c3c*         b*d
                                    4$X      Dump the bottom four items of stack
                                       ]f    Jump back to F

z          m
 1=        0 (if m is 1) or 1 (otherwise)
   d1+     Duplicate and add 1 (1 or 2)
      f    Jump back to F

La troisième ligne est responsable de 1/2si mest 1 et 0/1si mest un nombre impair supérieur à 1. La deuxième ligne calcule B_mavec la formule de sommation donnée dans la question, et le fait entièrement avec des numérateurs et des dénominateurs. Sinon, ce serait beaucoup plus court. La première moitié de la première ligne fait de la comptabilité et choisit d'exécuter la deuxième ou la troisième ligne, et la seconde moitié divise le numérateur et le dénominateur par leur GCD (le cas échéant) et stocke ces valeurs. Et sort la réponse à la fin.

El'endia Starman
la source
8

Python 2, 118 octets

6 octets enregistrés grâce à xsot .
Enregistré 6 10 de plus grâce à Peter Taylor .

n=input()
a=[n%4-1,n<2]*n;exec"a=[(a[j-1]+a[j+1])*j/2for j in range(len(a)-2)];"*~-n
print+(n<1)or-n/(2.**n-4**n)*a[1]

Utilise l'identité suivante:

où A n est le n ème nombre alternatif , qui peut être formellement défini comme le nombre de permutations alternées sur un ensemble de taille n , divisé par deux (voir aussi: A000111 ).

L'algorithme utilisé a été initialement donné par Knuth et Buckholtz (1967) :

Soit T 1, k = 1 pour tout k = 1..n

Les valeurs suivantes de T sont données par la relation de récurrence:

T n + 1, k = 1/2 [ (k - 1) T n, k-1 + (k + 1) T n, k + 1 ]

A n est alors donné par T n, 1

(voir aussi: A185414 )

Python 2, 152 octets

from fractions import*
n=input()
a=[n%4-1,n<2]*n
for k in range(n-1):a=[(a[j-1]+a[j+1])*j/2for j in range(n-k)]
print+(n<1)or Fraction(n*a[1],4**n-2**n)

Imprime la représentation fractionnelle exacte, nécessaire pour les valeurs supérieures à 200 environ.

primo
la source
1
Si vous passez range(2,n)à, range(n-2)vous pouvez raccourcir n-k+1en n+~k. Aussi, est - il une raison que vous utilisez au >>1lieu de /2? Enfin, une amélioration triviale, mais vous pouvez économiser quelques octets par alias range.
xsot
Merci pour les suggestions. J'avais à l'origine deux expressions, quand je les ai rejointes, j'ai oublié de changer >>1avec /2.
primo
1
Il y a une économie d' un caractère dans la ligne de sortie: print+(n<1)or-(-1.)**(n+n/2)*n/(4**n-2**n)*a[n%2^1%n]. Et le calcul peut être fait pour le même nombre de caractères quea=[1]*(n+1);exec"a=[(a[j-1]+a[j+1])*j/2for j in range(len(a)-1)];"*(n-1)
Peter Taylor
@PeterTaylor the n+n/2est intelligent; 1 n'a pas besoin d'être isolé, car de toute façon toutes les autres valeurs impaires sont nulles. Le calcul alternatif est en fait 4 octets plus court avec des inversions de bits, mais aussi considérablement plus lent, pour une raison quelconque.
primo
1
Je travaillais à partir de la table OEIS et je pensais que vous aviez trouvé rangeet ignoré une itération pour être un moyen intelligent de raccourcir l'initialisation. La façon dont vous avez maintenant divisé en paires et indices impairs est très agréable et permet une économie supplémentaire en tirant le signe dans la définition de a: a=[(-1)**(n/2),n<2]*n. La valeur de retour est alors +(n<1)or-n/(2.**n-4**n)*a[1]. Vous avez également un point-virgule errant à la fin de la ligne 2.
Peter Taylor
6

PARI / GP, 52 23 octets

En utilisant la célèbre formule n * ζ (1− n ) = - B n , où ζ est la fonction Riemann Zeta .

n->if(n,-n*zeta(1-n),1)

Solution originale, 52 octets, utilisant la fonction génératrice des nombres de Bernoulli .

n->n!*polcoeff(-x/sum(i=1,n+1,(-x)^i/i!)+O(x^n*x),n)
alephalpha
la source
Ne peut voter qu'une seule fois. C'est dommage que ce ne soit pas exact, cependant.
primo
Selon la documentation, la zetafonction est calculée en utilisant des nombres de Bernoulli, en fait.
primo
@primo, oui, je considère toutes les réponses qui utilisent la zêta intégrée comme de la triche.
Peter Taylor
Encore plus facile, bernfracavec bernreal8 octets chacun et ils sont déjà des fonctions, donc pas besoin de n->. Mais +1 pour une bonne solution.
Charles
6

Python 3, 112 octets

Edit: j'ai nettoyé cette réponse. Si vous voulez voir toutes les autres façons auxquelles j'ai pensé pour répondre à cette question en Python 2 et 3, regardez dans les révisions.

Si je n'utilise pas la table de recherche (et j'utilise plutôt la mémorisation), j'arrive à obtenir la définition récursive à 112 octets! COURTISER! Notez que b(m)renvoie a Fraction. Comme d'habitude, le nombre d'octets et un lien pour les tests .

from fractions import*
def b(m):
 s=k=0;p=1
 while k<m:a=m-k;s+=Fraction(p*b(k))/-~a;p=p*a//-~k;k+=1
 return 1-s

Et une fonction qui utilise une table de recherche et renvoie la table entière des fractions de b(0)à b(m), inclus.

from fractions import*
def b(m,r=[]):
 s=k=0;p=1
 while k<m:
  if k>=len(r):r=b(k,r)
  a=m-k;s+=Fraction(p*r[k])/-~a;p=p*a//-~k;k+=1
 return r+[1-s]
Sherlock9
la source
1
Je pense que vous pouvez omettre le zéro de fin sur les littéraux flottants, par exemple 1.au lieu de 1.0.
Alex A.
@AlexA. Terminé. Retiré .0de stout, car il deviendra rapidement un flotteur plus tard.
Sherlock9
Pouvez-vous utiliser à la p=v=1;exec('[...];p+=1'*k)place de votre boucle la plus intérieure?
2015
5

CJam, 69 49 34 33 octets

{_),:):R_:*_@f/@{_(;.-R.*}*0=\d/}

Démo en ligne

Merci à Cabbie407 , dont la réponse m'a fait connaître l'algorithme Akiyama – Tanigawa.

Dissection

{           e# Function: takes n on the stack
  _),:)     e# Stack: n [1 2 3 ... n+1]
  :R        e# Store that array in R
  _:*       e# Stack: n [1 2 3 ... n+1] (n+1)!
  _@f/      e# Stack: n (n+1)! [(n+1)!/1 (n+1)!/2 (n+1)!/3 ... (n+1)!/(n+1)]
            e#   representing [1/1 1/2 ... 1/(n+1)] but avoiding floating point
  @{        e# Repeat n times:
    _(;.-   e#   Take pairwise differences
    R.*     e#   Pointwise multiply by 1-based indices
  }*        e#   Note that the tail of the array accumulates junk, but we don't care
  0=\d/     e# Take the first element and divide by (n+1)!
}
Peter Taylor
la source
Multipliant par n! pour éviter la perte de précision est intelligent, sinon légèrement ridicule. Je me demande si l'algorithme n'a pas pu être légèrement refactorisé pour éviter cela.
primo
Je ne pense pas que le refactoring pourrait éviter d'avoir à évoluer pour la simple raison que, puisque nous savons que tous les autres nombres de Bernoulli sont 0, il y a évidemment beaucoup de soustraction de valeurs similaires en cours, donc il y a beaucoup d'endroits où la perte de signification catastrophique peut arriver.
Peter Taylor
4

PARI / GP, 45 octets

n->if(n,2*n/(2^n-4^n)*real(polylog(1-n,I)),1)

En utilisant la même formule que ma réponse Python , avec A n généré via polylog.

Script de test

Exécutez gp, à l'invite, collez ce qui suit:

n->if(n,2*n/(2^n-4^n)*real(polylog(1-n,I)),1)
for(i=0, 60, print(i, ": ", %(i)))
primo
la source
1
Merci d'avoir fourni un script de test - cela a rendu le test beaucoup plus facile!
Mego
@Mego pour vous et moi tous les deux;)
primo
4

Mathematica, 52 48 42 octets

1-Sum[#~Binomial~k#0@k/(#-k+1),{k,0,#-1}]&

Fonction sans nom qui utilise la définition littérale.

LegionMammal978
la source
Est-ce Sign@#nécessaire?
alephalpha
Je l'ai testé sur mon ordinateur. Après avoir supprimé le Sign@#, il renvoie toujours la bonne réponse pour 0.
alephalpha
3

Python 2, 132 130 octets

import math,fractions
f=math.factorial
B=lambda m:~-m*m%2or 1+sum(B(k)*f(m)/f(k)/f(m-k)/fractions.Fraction(k+~m)for k in range(m))

Ceci est juste une version golfée de l'implémentation de référence.

Ceci est un peu lent dans la pratique, mais peut être accéléré de manière significative avec la mémorisation:

import math,fractions
f=math.factorial

def memoize(f):
 memo = {}
 def helper(x):
  if x not in memo:
   memo[x] = f(x)
  return memo[x]
 return helper

@memoize
def B(m):
 return~-m*m%2or 1+sum(B(k)*f(m)/f(k)/f(m-k)/fractions.Fraction(k+~m)for k in range(m))

for m in range(61):
 print(B(m))

Vous pouvez essayer cette version en ligne sur Ideone .

Dennis
la source
3

gawk4, 79 octets

Code de 77 octets + 2 octets pour l' -Mindicateur

PREC^=2{for(n=$0;m++<=n;)for($(j=m)=1/m;j>1;)$j=(-$j+$--j)*j;printf"%.6f",$1}

Il s'agit d'une implémentation de l'algorithme Akiyama – Tanigawa de la page Wikipedia.

Nous avons eu des problèmes avec la "règle des 6 chiffres décimaux", car cela imprime le nombre entier, puis 6 chiffres, mais il n'y a pas de liste ici pour comparer les résultats.

Un défaut est que cela imprime un signe moins devant la 0.000000plupart du temps, mais je ne pense pas que ce soit faux.

Exemple d'utilisation

echo 58 | awk -M 'PREC^=2{for(n=$0;m++<=n;)for($(j=m)=1/m;j>1;)$j=(-$j+$--j)*j;printf"%.6f",$1}'

Sortie de 0 à 60

0 -> 1,000000
1 -> 0,500000
2 -> 0,1666667
3 -> -0,000000
4 -> -0,033333
5 -> 0,000000
6 -> 0,023810
7 -> 0,000000
8 -> -0.033333
9 -> 0,000000
10 -> 0,075758
11 -> -0,000000
12 -> -0.253114
13 -> -0,000000
14 -> 1.166667
15 -> -0,000000
16 -> -7.092157
17 -> -0,000000
18 -> 54,971178
19 -> -0.000000
20 -> -529.124242
21 -> -0,000000
22 -> 6192.123188
23 -> 0,000000
24 -> -86580.253114
25 -> 0,000000
26 -> 1425517.166667
27 -> 0,000000
28 -> -27298231.067816
29 -> 0,000000
30 -> 601580873.900642
31 -> 0,000000
32 -> -15116315767.092157
33 -> 0,000000
34 -> 429614643061.166667
35 -> 0,000000
36 -> -13711655205088.332772
37 -> 0,000000
38 -> 488332318973593.166667
39 -> -0,000000
40 -> -19296579341940068.148633
41 -> -0,000000
42 -> 841693047573682615.000554
43 -> -0,000000
44 -> -40338071854059455413.076812
45 -> -0,000000
46 -> 2115074863808199160560.145390
47 -> -0,000000
48 -> -120866265222965259346027.311937
49 -> -0,000000
50 -> 7500866746076964366855720.075758
51 -> -0,000000
52 -> -503877810148106891413789303.052201
53 -> -0,000000
54 -> 36528776484818123335110430842.971178
55 -> -0,000000
56 -> -2849876930245088222626914643291.067816
57 -> -0,000000
58 -> 238654274996836276446459819192192.149718
59 -> -0.000000
60 -> -21399949257225333665810744765191097.392674
Cabbie407
la source
Ça printf"%e"marcherait?
primo
Non, ce ne serait pas le cas, car les 0.00000s ne sont que très petits et pas vraiment nuls.
Cabbie407
2

GolfScript, 63 octets

~:i.!+.[3i&(2i>]*i(,{i\-,{1$1$(=2$2$)=+*2/}%\;}/~\2i?.(*\--1?**

Démo en ligne .

En utilisant la même formule que ma réponse Python .

Script de test

61,{[.`
  ~:i.!+.[3i&(2i>]*i(,{i\-,{1$1$(=2$2$)=+*2/}%\;}/~\2i?.(*\--1?**
]p}/

Le lien apphb expirera à ce sujet. Si vous n'avez pas GolfScript installé localement, je recommande d'utiliser l' interpréteur de golf anarchy (utilisez le formulaire, sélectionnez GolfScript, collez, soumettez).

primo
la source
2

Perl, 101 octets

#!perl -p
@a=($_%4-1,$_<2)x$_;
@a=map$_*($a[$_-1]+$a[$_+1])/2,0..@a-3for 2..$_;
$_=!$_||$_/(4**$_-2**$_)*$a[1]

En comptant le shebang comme trois, l'entrée provient de stdin.

En utilisant la même formule que ma réponse Python .

Exemple d'utilisation

$ echo 60 | perl bernoulli.pl
-2.13999492572253e+034

Démo en ligne .

primo
la source
2

R, 93 octets

function(m){if(m==0){1}else{v=c();for(k in 0:(m-1))v=c(v,choose(m,k)*f(k)/(m-k+1));1-sum(v)}}

Pas vraiment original comme solution. Si vous avez des commentaires, n'hésitez pas!

Non golfé:

function(m)
    if(m==0){1}
    else
         v=c()
         for(k in 0:(m-1))
            v=c(v,choose(m,k)*f(k)/(m-k+1))

1-sum(v)
Frédéric
la source
Je sais que c'est un peu tard maintenant mais vous pouvez économiser 3 octets en changeant l' ordre if/ elseinstruction et en utilisant m>0ainsi qu'en bouclant à la 1:m-1place.
Billywob
2

En fait , 46 45 octets (non concurrents)

Cela faisait des mois que je voulais faire une réponse sérieusement / réellement et maintenant je peux. Comme cela utilise des commandes que Serious n'avait pas en novembre 2015, ce n'est pas une compétition. Suggestions de golf bienvenues. Essayez-le en ligne!

Modifier: En février 2017, une mise à jour d'Actually a changé les littéraux de fonction. Normalement, cela ne serait tout simplement pas en compétition pour tout défi écrit avant février, mais comme cette réponse est déjà non concurrentielle, j'ai quand même édité cette réponse. Prendre plaisir.

Cela utilise la définition explicite des nombres de Bernoulli sur Wikipédia.

;╖ur⌠;╝ur⌠;;0~ⁿ(╛█*╜(uⁿ*⌡MΣ╛uk⌡M┬i@;π;)♀\*@k▼

Ungolfing

;╖     Duplicate and save m in register 0.
ur     Range [0..m]
  ⌠      Start first for loop
  ;╝     Duplicate and save k in register 1.
  ur     Range [0..k]
    ⌠      Start second for loop (as string).
    ;;     Duplicate v twice.
    0~ⁿ    Push -1, and pow() to get (-1)**v.
    (╛█    Rotate a duplicate v to TOS, push k, and binom(k, v).
    *      Multiply (-1)**v by binom(k, v).
    ╜(uⁿ   Push m, rotate last duplicate v to TOS, increment, and pow() to get (v+1)**m.
    *      (-1)**v * binom(k, v) * (v+1)**m
    ⌡      End second for loop (string turned to function).
  MΣ     Map over range [0..v] and sum
  ╛u     Push k and increment (the denominator)
           (Note: second for loop does numerators only as denominator only depends on k)
  k      Push fraction in list form [numerator, denominator]
  ⌡      End first for loop
M      Map over range [0..k]
┬i@    Transpose all of the fractions, flatten and swap.
         Stack: [denominators] [numerators]
;π     Duplicate and take product of denominators.
;)     Duplicate product and move to bottom of stack.
         Stack: product [denominators] [numerators] product
♀\     For all items in denominators, integer divide product by item.
         Return a list of these scaled-up denominators.
*      Dot product of numerators and the scaled-up denominators as new numerator.
         (In effect, getting the fractions to the same denominator and summing them)
@k     Swap new numerator and product (new denominator) and turn into a list (fraction).
▼      Divide fraction by gcd(numerator, denominator) (Simplify fraction).
Sherlock9
la source
2
Utilise des commandes que Serious n'avait pas en novembre 2015? Mec, cela utilise un langage entièrement nouveau qui n'existait pas en novembre 2015! Je suis tellement fier ...
Mego
1

Rubis, 66 61 octets

Ceci est une version Ruby de ma réponse Python.

b=->m{s,p=0r,1;m.times{|k|a=m-k;s+=p*b[k]/-~a;p=p*a/-~k};1-s}

Étant donné que cela utilise Rationaldans ses réponses, je suis assez sûr que cela fonctionne jusqu'à 60, mais j'ai eu du mal à fonctionner même b[24], j'ai donc implémenté à nouveau la table de recherche pour 86 81 80 octets.

t=->m{s,p,r=0r,1,m>0?t[m-1]:[];m.times{|k|a=m-k;s+=p*r[k]/-~a;p=p*a/-~k};r<<1-s}
Sherlock9
la source
1

J, 10 octets

(%1-^@-)t:

Calcule le n ème nombre de Bernoulli en trouvant le n ème coefficient de la fonction génératrice exponentielle de x / (1 - e -x ).

Usage

Si l'entrée reçoit un entier ou flotte comme argument, elle sortira un flottant. Si on lui donne un entier étendu, marqué d'un suffixe x, il affichera soit un entier étendu soit un rationnel, deux entiers étendus séparés par r.

   f =: (%1-^@-)t:
   f 1
0.5
   f 1x
1r2
   (,.f"0) i. 10x
0     1
1   1r2
2   1r6
3     0
4 _1r30
5     0
6  1r42
7     0
8 _1r30
9     0

Explication

(%1-^@-)t: Input: n
(      )t: Takes a monad and creates a new monad that
           computes the coefficients of its egf
(      )   A monad that operates on x
      -      Negate x
    ^@       Computes its exponential, e^-x
  1-         Subtract it from 1
 %           Divide x by it, x/(1 - e^-x)
miles
la source
1

Axiome, 134 147 octets

b(n:NNI):FRAC INT==(v:=[1/1];k:=1;repeat(k>n=>break;r:=1-reduce(+,[binomial(k,j)*v.(j+1)/(k-j+1)for j in 0..k-1]);v:=append(v,[r]);k:=k+1);v.(n+1))

ungolf et test

(23) -> b
   (23)
   b n ==
           1
     v := [-]
           1
     k := 1
     repeat
       if n < k
         then break
         else
                               binomial(k,j)v(j + 1)
           r := 1 - reduce(+,[[--------------------- for j in 0..(k - 1)]])
                                     k - j + 1
           v := append(v,[r])
           k := k + 1
     v(n + 1)
                                                   Type: FunctionCalled b
(50) -> [[i,b(i)]  for i in [0,1,2,3,4,5,6,7,8,9,10]]
   (50)
             1     1              1            1              1             5
   [[0,1],[1,-],[2,-],[3,0],[4,- --],[5,0],[6,--],[7,0],[8,- --],[9,0],[10,--]]
             2     6             30           42             30            66
                                         Type: List List Fraction Integer

(51) -> b 1000
   (51)
   -
   18243104738661887254572640256857788879338336867042906052197158157641126_
    2572624911158657472577321069709615489924627495522908087488299539455188_
    7918567582241551668492697244184914012242579830955617098629924652251740_
    9791915637226361428342780548971002281045465308441161372350696920220116_
    2441791760680262602019620260255790058416539271332852806000966628467639_
    0683434226380702951226108116666172815817157023611889303668166839919156_
    3797683877845690114843122753427426880591799883780255338278664578660218_
    5045895962670442011443630321460259486764674312436994856054301765557425_
    1371150213401051058408679874766352952749178734973676859834707623881634_
    6251471489942512878190574323531299070406930309477389251738705417680653_
    1183648189451892725726445949589759600705334767585389769924857630972963_
    9976364832442643512622073858780110731539833099817555775136008111170797_
    6250597322951308884900670113339167641953793994512377610306198429310933_
    1214632141683542607746641232089854815064629129596536997380608256428801_
    9784909897301658268809203555030692846151917069465607257641149187197651_
    0905515966840312411845543650593021402849221691341852819791233589301994_
    1012291773441794027493574651881059432274494354092231954894280742068472_
    7146192942133436054611475404867886313250114399681532753236429290625909_
    3411000391368336312138915621701535954814084208794241665492294270773347_
    6055878415765927582014214726584822236443691314366097570085473354584000_
    9985915190584047337934331297339403392719579093995842312746836871169674_
    9786460913411872527166990047126222109345933847358924230951718379883743_
    2563465487604170316077418754242710065269818190591271690695446633836120_
    3745255515267088218383996330164203403732365333352120338272021319718003_
    5994220458994876460018350270385634117807768745161622933834063145505621_
    9106004731529642292049578901
     /
    342999030
                                                   Type: Fraction Integer

(52) -> b 60
           1215233140483755572040304994079820246041491
   (52)  - -------------------------------------------
                             56786730
                                                   Type: Fraction Integer
RosLuP
la source
1

APL (NARS), 83 caractères, 166 octets

r←B w;i
r←,1⋄i←0x⋄w+←1
→3×⍳w≤i+←1⋄r←r,1-+/{(1+i-⍵)÷⍨(⍵!i)×r[⍵+1]}¨0..i-1⋄→2
r←r[i]

Entrée comme sortie entière aussi grande rationnelle

  B 0
1
  B 1
1r2 
  B 2
1r6 
  B 3
0 
  B 4
¯1r30 
  B 10
5r66 
  B 100
¯94598037819122125295227433069493721872702841533066936133385696204311395415197247711r33330 
  B 1000
¯1824310473866188725457264025685778887933833686704290605219715815764112625726249111586574725773210697096154899246
  27495522908087488299539455188791856758224155166849269724418491401224257983095561709862992465225174097919156
  37226361428342780548971002281045465308441161372350696920220116244179176068026260201962026025579005841653927
  13328528060009666284676390683434226380702951226108116666172815817157023611889303668166839919156379768387784
  56901148431227534274268805917998837802553382786645786602185045895962670442011443630321460259486764674312436
  99485605430176555742513711502134010510584086798747663529527491787349736768598347076238816346251471489942512
  87819057432353129907040693030947738925173870541768065311836481894518927257264459495897596007053347675853897
  69924857630972963997636483244264351262207385878011073153983309981755577513600811117079762505973229513088849
  00670113339167641953793994512377610306198429310933121463214168354260774664123208985481506462912959653699738
  06082564288019784909897301658268809203555030692846151917069465607257641149187197651090551596684031241184554
  36505930214028492216913418528197912335893019941012291773441794027493574651881059432274494354092231954894280
  74206847271461929421334360546114754048678863132501143996815327532364292906259093411000391368336312138915621
  70153595481408420879424166549229427077334760558784157659275820142147265848222364436913143660975700854733545
  84000998591519058404733793433129733940339271957909399584231274683687116967497864609134118725271669900471262
  22109345933847358924230951718379883743256346548760417031607741875424271006526981819059127169069544663383612
  03745255515267088218383996330164203403732365333352120338272021319718003599422045899487646001835027038563411
  78077687451616229338340631455056219106004731529642292049578901r342999030
RosLuP
la source
0

Haskell, 95 octets

import Data.Ratio
p=product
b m=sum[p[k-v+1..k]*(v+1)^m%(p[-v..0-1]*(k+1))|k<-[0..m],v<-[0..k]]

Cela met en œuvre la définition explicite des nombres de Bernoulli décrite sur la page Wikipedia .

Sherlock9
la source
0

Perl 6, 83 octets

my &B={$^m??1-[+] (^$m).map: {combinations($m,$_)*B($_)/($m+1-$_)}!!1};say B slurp;

Une solution plus rapide de 114 octets:

my @b=1;for 1..+slurp() {@b.push: 1-[+] (^$^m).map: {([*] $m+1-$_..$m)*@b[$_]/($m+1-$_)/([*] 1..$_)}};say @b[*-1];
bb94
la source
Votre code pour un défi de golf de code doit être aussi court que possible, même si cela prend quelques vies de l'univers pour se terminer pour certaines entrées.
Mego
0

Javascript, 168 octets

function h(b,a){return a?h(a,b%a):b}for(var c=[],a=[],e=0,b,d,f,g;e<=k;)for(c[b=d=e]=1,a[e]=++e;d;)f=c[--d]*a[b]-(c[b]*=g=a[d]),r=h(f*=b,g=a[b]*=g),c[d]=f/r,a[--b]=g/r;

Définissez la variable 'k' sur le nombre de Bernoulli souhaité, et le résultat est c [0] sur a [0]. (Numérateur dénominateur)

Exemple d'utilisation

k = 2;
console.log(c[0] + "/" + a[0]);

Pas aussi petit que les autres, mais le seul que j'ai écrit qui se rapproche. Voir https://marquisdegeek.com/code_ada99 pour mes autres tentatives (hors golf).

Marquis de Geek
la source
0

Axiome, 57 octets

g(n)==factorial(n)*coefficient(taylor(t*%e^t/(%e^t-1)),n)

code pour test et résultats

(18) -> [[i, g(i)]  for i in 0..29]
   (18)
              1      1                1              1                1
   [[0,1], [1,-], [2,-], [3,0], [4,- --], [5,0], [6,--], [7,0], [8,- --],
              2      6               30             42               30
                5                  691               7                 3617
    [9,0], [10,--], [11,0], [12,- ----], [13,0], [14,-], [15,0], [16,- ----],
               66                 2730               6                  510
                43867                 174611               854513
    [17,0], [18,-----], [19,0], [20,- ------], [21,0], [22,------], [23,0],
                 798                    330                  138
          236364091               8553103                 23749461029
    [24,- ---------], [25,0], [26,-------], [27,0], [28,- -----------], [29,0]]
             2730                    6                        870
                                       Type: List List Expression Integer

(19) -> g 60
           1215233140483755572040304994079820246041491
   (19)  - -------------------------------------------
                             56786730
                                                 Type: Expression Integer

il faut noter que la fonction n'est pas celle que quelqu'un a écrite ci-dessus mais t*%e^t/(%e^t-1))avec% e Euler costant

RosLuP
la source
0

Pyth , 22 octets

L?b-1sm*.cbdcyd-btdUb1

Essayez-le en ligne!

Définit une fonction appelée par y<number>exemple yQ.

L                      # y=lambda b:
 ?b                  1 # ... if b else 1
   -1                  # 1 -
     s                 #     sum(
      m            Ub  #         map(lambda d: ... , range(b)) 
       *.cbd           #           combinations(b, d) *
            cyd        #             y(d) /      (float division)
               -btd    #                    b - (d - 1)
ar4093
la source