Números de Bernoulli

23

Os números de Bernoulli (especificamente, o segundo número de Bernoulli) são definidos pela seguinte definição recursiva:

segundos números de Bernoulli

Onde mCkdenota uma combinação .

Dado um número inteiro não negativo mcomo entrada, imprima a representação decimal OU uma fração reduzida para o msegundo número de Bernoulli. Se você produzir uma representação decimal, deverá ter pelo menos 6 casas decimais (dígitos após o ponto decimal) de precisão, e ela deve ser precisa quando arredondada para 6 casas decimais. Por exemplo, para m = 2, 0.166666523é aceitável porque arredonda para 0.166667. 0.166666389não é aceitável, porque arredonda para 0.166666. Zeros à direita podem ser omitidos. Notação científica pode ser usada para representações decimais.

Aqui está a entrada e a saída esperada para maté 60 inclusive, em notação científica arredondada para 6 casas decimais e como frações reduzidas:

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)

Implementação de referência (em 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

Regras

  • Isso é código-golfe , então o código mais curto em bytes ganha
  • Você não pode usar nenhuma função, interna ou incluída em uma biblioteca externa, que calcule o tipo de números de Bernoulli ou os polinômios de Bernoulli.
  • Sua resposta deve fornecer uma saída correta para todas as entradas até 60, inclusive.

Entre os melhores

O snippet de pilha na parte inferior desta postagem gera o cabeçalho das respostas a) como uma lista da solução mais curta por idioma eb) como um cabeçalho geral.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

## Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

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

Você também pode transformar o nome do idioma em um link que será exibido no snippet:

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

Mostrar snippet de código

code-golf math sequence combinatorics Mego
fonte
@MorganThrapp A implementação de referência é apenas para tornar mais clara a definição de um número de Bernoulli, não para realmente resolver o problema.
Mego
Ah, entendi. Eu pensei que era uma implementação totalmente funcional.
Morgan Thrapp
2
@Mego Nenhum flutuador padrão (nem mesmo a precisão quad) pode armazenar B_60 a precisão quad. Devemos usar um formato de precisão estendido se estiver produzindo como decimais?
lirtosiast
8
Não gosto do requisito de precisão. Alguns idiomas não têm as ferramentas para trabalhar com flutuadores com precisão suficiente para B_60, e eu prefiro não lidar com esses problemas ao jogar em um problema matemático. É frustrante escrever uma solução e descobrir que ela é inválida devido ao que parece ser um detalhe técnico.
Xnor
2
@ xnor 6 dígitos de precisão já parecem incrivelmente relaxados.
Primo

Respostas:

8

Julia, 23 20 bytes

Economizou 3 bytes graças a Alex A.

Ele usa a mesma fórmula da minha solução Mathematica e da solução PARI / GP .

n->n>0?-zeta(1-n)n:1
alefalpha
fonte
2
20 bytes:n->n>0?-zeta(1-n)n:1
Alex A.
@AlexA. Não sei por que, mas zeta(n)lança um erro quando né um número inteiro negativo. Estou usando Julia 0.2.1 no linux.
Alephalpha #
1
Oh meu, a sua versão de Julia está bastante desatualizado. Funciona muito bem para mim no 0.4.1.
Alex A.
25

Mathematica, 40 28 23 22 bytes

Usando a famosa fórmula n * ζ (1− n ) = - B n , onde ζ é a função Riemann Zeta .

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

O mesmo comprimento:

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

Solução original, 40 bytes, usando a função geradora dos números de Bernoulli .

#!SeriesCoefficient[t/(1-E^-t),{t,0,#}]&
alefalpha
fonte
+2 se eu pudesse ...
LegionMammal978 /
9

Julia, 58 bytes

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

Isso cria uma função recursiva Bque aceita um número inteiro e retorna um BigFloat(ou seja, ponto flutuante de alta precisão).

Ungolfed:

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.
fonte
9

Minkolang 0.14 , 97 bytes

Na verdade, tentei fazê-lo recursivamente primeiro, mas meu intérprete, como projetado atualmente, na verdade não pode fazê-lo. Se você tentar se recuperar de dentro de um loop for, ele inicia uma nova recursão. Então eu fui para a abordagem de tabulação ... que tinha problemas de precisão. Então eu fiz a coisa toda com frações. Sem suporte interno para frações. [ suspiro ]

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

Experimente aqui. Bônus: a matriz possui todas as frações para cada número anterior de Bernoulli!

Explicação (daqui a pouco)

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

A terceira linha é responsável por 1/2se mfor 1 e 0/1se mfor um número ímpar maior que 1. A segunda linha calcula B_mcom a fórmula da soma dada na pergunta e o faz inteiramente com numeradores e denominadores. Caso contrário, seria muito mais curto. A primeira metade da primeira linha faz alguma contabilidade e escolhe se quer executar a segunda ou terceira linha, e a segunda metade divide o numerador e o denominador pelo seu GCD (se aplicável) e armazena esses valores. E gera a resposta no final.

El'endia Starman
fonte
8

Python 2, 118 bytes

Salvo 6 bytes devido ao xsot .
Guardou 6 10 mais devido a 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]

Usa a seguinte identidade:

onde A n é o n th alternada número , que pode ser formalmente definida como o número de permutações alternada com um conjunto de tamanho n , para metade (ver também: A000111 ).

O algoritmo usado foi originalmente dado por Knuth e Buckholtz (1967) :

Seja T 1, k = 1 para todos k = 1..n

Os valores subsequentes de T são dados pela relação de recorrência:

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

Um n é então dado por T n, 1

(veja também: A185414 )

Python 2, 152 bytes

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 a representação fracionária exata, necessária para valores maiores que 200.

primo
fonte
1
Se você mudar range(2,n)para range(n-2)você pode reduzir n-k+1para n+~k. Além disso, existe um motivo para você usar em >>1vez de /2? Por fim, uma melhoria trivial, mas você pode salvar alguns bytes usando o alias range.
Xsot #
Obrigado pelas sugestões. Originalmente, eu tinha duas expressões, quando me juntei a eles eu negligenciei mudando >>1com /2.
Primo
1
Há uma economia de um caractere na linha de saída: print+(n<1)or-(-1.)**(n+n/2)*n/(4**n-2**n)*a[n%2^1%n]. E o cálculo pode ser feito para a mesma contagem de caracteres comoa=[1]*(n+1);exec"a=[(a[j-1]+a[j+1])*j/2for j in range(len(a)-1)];"*(n-1)
Peter Taylor
@ PeterTaylor n+n/2é inteligente; 1 não precisa ser destacado, porque todos os outros valores ímpares são zero de qualquer maneira. O cálculo alternativo é na verdade 4 bytes mais curto com inversões de bits, mas também consideravelmente mais lento, por algum motivo.
Primo
1
Eu estava trabalhando na tabela OEIS e pensei que você havia encontrado rangee pulando uma iteração para ser uma maneira inteligente de diminuir a inicialização. A maneira que você agora dividir a pares e ímpares índices é muito agradável, e permite uma maior poupança puxando o sinal para a definição de a: a=[(-1)**(n/2),n<2]*n. Então o valor de retorno é +(n<1)or-n/(2.**n-4**n)*a[1]. Você também tem um ponto-e-vírgula perdido no final da linha 2.
Peter Taylor
6

PARI / GP, 52 23 bytes

Usando a famosa fórmula n * ζ (1− n ) = - B n , onde ζ é a função Riemann Zeta .

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

Solução original, 52 bytes, usando a função geradora dos números de Bernoulli .

n->n!*polcoeff(-x/sum(i=1,n+1,(-x)^i/i!)+O(x^n*x),n)
alefalpha
fonte
Só pode votar uma vez. É uma pena que não seja exato, no entanto.
Primo
De acordo com a documentação, a zetafunção é calculada usando números de Bernoulli, de fato.
Primo
@primo, sim, considero todas as respostas que usam zeta embutido como trapaça.
Peter Taylor
Ainda mais fácil, bernfrace bernrealsão 8 bytes cada e já são funções, portanto não há necessidade de n->. Mas +1 para uma boa solução.
Charles
6

Python 3, 112 bytes

Edit: Eu limpei esta resposta. Se você quiser ver todas as outras maneiras pelas quais pensei em responder a essa pergunta no Python 2 e 3, consulte as revisões.

Se eu não usar a tabela de pesquisa (e usar a memorização), consigo obter a definição recursiva para 112 bytes! WOO! Observe que b(m)retorna a Fraction. Como sempre, a contagem de bytes e um link para teste .

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

E uma função que usa uma tabela de pesquisa e retorna a tabela inteira de frações de b(0)para b(m), inclusive.

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
fonte
1
Eu acho que você pode omitir o zero à direita em literais de flutuação, por exemplo, em 1.vez de 1.0.
Alex A.
@AlexA. Feito. Removido .0a partir sinteiramente, porque ele vai rapidamente tornar-se uma bóia mais tarde.
Sherlock9
Você pode usar em p=v=1;exec('[...];p+=1'*k)vez do seu loop mais interno?
lirtosiast
5

CJam, 69 49 34 33 bytes

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

Demonstração online

Agradeço ao Cabbie407 , cuja resposta me conscientizou do algoritmo Akiyama – Tanigawa.

Dissecação

{           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
fonte
Multiplicando por n! para evitar a perda de precisão é inteligente, se não um pouco ridículo. Gostaria de saber se o algoritmo não poderia ser refatorado levemente para evitar isso.
Primo
Não acho que a refatoração possa evitar a necessidade de escalar pela simples razão de que, como sabemos que todos os outros números de Bernoulli são 0, obviamente há muita subtração de valores semelhantes acontecendo, por isso há muitos lugares onde a perda de significância catastrófica pode acontecer.
Peter Taylor
4

PARI / GP, 45 bytes

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

Usando a mesma fórmula da minha resposta Python , com A n gerado via polylog.

Script de Teste

Execute gp, no prompt, cole o seguinte:

n->if(n,2*n/(2^n-4^n)*real(polylog(1-n,I)),1)
for(i=0, 60, print(i, ": ", %(i)))
primo
fonte
1
Obrigado por fornecer um script de teste - isso facilitou muito mais o teste!
Mego
@Mego for you and me both;)
primo
4

Mathematica, 52 48 42 bytes

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

Função sem nome que usa a definição literal.

LegionMammal978
fonte
É Sign@#necessário?
Alephalpha # 1/15
Eu testei no meu computador. Depois de remover o Sign@#, ainda retorna a resposta correta para 0.
Alephalpha #
3

Python 2, 132 130 bytes

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

Esta é apenas uma versão básica da implementação de referência.

Isso é um pouco lento na prática, mas pode ser acelerado significativamente com a memorização:

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

Você pode experimentar esta versão online no Ideone .

Dennis
fonte
3

gawk4, 79 bytes

Código de 77 bytes + 2 bytes para -Msinalizador

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

É uma implementação do algoritmo Akiyama – Tanigawa da página da Wikipedia.

Houve algum problema com a "regra de 6 dígitos decimais", porque isso imprime o número inteiro e, em seguida, 6 dígitos, mas não há lista aqui para comparar os resultados.

Uma falha é que isso imprime um sinal de menos na frente do 0.000000 muitas vezes, mas não acho que isso esteja errado.

Exemplo de uso

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

Saída de 0 a 60

0 -> 1.000000
1 -> 0,500000
2 -> 0,166667
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
fonte
Funcionaria printf"%e"?
Primo
Não, não seria, porque os 0.00000são apenas muito pequenos e não são realmente zero.
Cabbie407
2

GolfScript, 63 bytes

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

Demonstração Online .

Usando a mesma fórmula da minha resposta Python .

Script de Teste

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

O link apphb irá expirar nisso. Se você não tiver o GolfScript instalado localmente, recomendo o uso do intérprete anarchy golf (use o formulário, selecione GolfScript, cole, envie).

primo
fonte
2

Perl, 101 bytes

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

Contando o shebang como três, a entrada é retirada de stdin.

Usando a mesma fórmula da minha resposta Python .

Uso da amostra

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

Demonstração Online .

primo
fonte
2

R, 93 bytes

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

Não é realmente original como solução. Se algum comentário, por favor, sinta-se livre!

Ungolfed:

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
fonte
Eu sei que isso é um pouco tarde agora, mas você pode salvar 3 bytes alterando a ordem de instrução if/ elsee usar m>0, bem como fazer o loop 1:m-1.
Billywob
2

Na verdade , 46 45 bytes (não concorrentes)

Estou pensando em fazer uma resposta séria / realmente há meses e agora posso. Como ele usa comandos que a Seriously não possuía em novembro de 2015, não é concorrente. Sugestões de golfe são bem-vindas. Experimente online!

Edit: Em fevereiro de 2017, houve uma atualização na verdade que mudou quais literais de funções são quais. Normalmente, isso seria simplesmente não concorrente para qualquer desafio escrito antes de fevereiro, mas como essa resposta já não é competitiva, editei essa resposta de qualquer maneira. Apreciar.

Isso usa a definição explícita dos números de Bernoulli na Wikipedia.

;╖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
fonte
2
Usa comandos Sério, não tinha em novembro de 2015? Cara, isso usa uma linguagem totalmente nova que não existia em novembro de 2015! Estou tão orgulhoso ...
Mego
1

Ruby, 66 61 bytes

Esta é uma versão Ruby da minha resposta em Python.

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

Como isso é usado Rationalem suas respostas, tenho certeza que isso funciona até 60, mas tive problemas para rodar mesmo b[24], então implementei a tabela de pesquisa novamente para 86 81 80 bytes.

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
fonte
1

J, 10 bytes

(%1-^@-)t:

Calcula o n th número de Bernoulli, encontrando o n th coeficiente da função geradora exponencial de x / (1 - e -x ).

Uso

Se a entrada recebe um número inteiro ou flutua como argumento, ela produzirá uma flutuação. Se for fornecido um número inteiro estendido, marcado com um sufixo x, ele produzirá um número inteiro estendido ou um racional, dois números inteiros estendidos separados por 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

Explicação

(%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)
milhas
fonte
1

Axioma, 134 147 bytes

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 e teste

(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
fonte
1

APL (NARS), 83 caracteres, 166 bytes

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]

Entrada como saída inteira como grande racional

  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
fonte
0

Haskell, 95 bytes

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]]

Isso implementa a definição explícita dos números de Bernoulli descritos na página da Wikipedia .

Sherlock9
fonte
0

Perl 6, 83 bytes

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

Uma solução mais rápida de 114 bytes:

my @b=1;for 1..+slurp() {@b.push: 1-[+] (^$^m).map: {([*] $m+1-$_..$m)*@b[$_]/($m+1-$_)/([*] 1..$_)}};say @b[*-1];
bb94
fonte
Seu código para um desafio de código de golfe precisa ser o mais curto possível, mesmo que demore algumas vidas do universo para terminar para determinadas entradas.
Mego
0

Javascript, 168 bytes

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;

Defina a variável 'k' como o número de Bernoulli desejado e o resultado é c [0] sobre um [0]. (numerador denominador)

Uso da amostra

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

Não é tão pequeno quanto os outros, mas o único que escrevi que se aproxima. Consulte https://marquisdegeek.com/code_ada99 para minhas outras tentativas (que não são de golfe).

Marquis de Geek
fonte
0

Axioma, 57 bytes

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

código para teste e resultados

(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

é preciso notar que a função não é a que alguém escreveu acima, mas t*%e^t/(%e^t-1))com% e Euler costant

RosLuP
fonte
0

Pitão , 22 bytes

L?b-1sm*.cbdcyd-btdUb1

Experimente online!

Define uma função que é chamada como y<number>, por exemplo 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
fonte