Liczby Bernoulliego

23

Te numery Bernoulliego (w szczególności, drugie numery Bernoulliego) są zdefiniowane w następujący rekurencyjnej definicji:

drugie liczby Bernoulliego

Gdzie mKoznacza kombinację .

Biorąc pod uwagę nieujemną liczbę całkowitą mjako dane wejściowe, wyprowadzaj reprezentację dziesiętną LUB zmniejszoną część dla mdrugiej drugiej liczby Bernoulliego. Jeśli wyprowadzasz reprezentację dziesiętną, musisz mieć co najmniej 6 miejsc dziesiętnych (cyfry po przecinku) precyzji i musi ona być dokładna, gdy zostanie zaokrąglona do 6 miejsc dziesiętnych. Na przykład, w przypadku m = 2, 0.166666523jest do przyjęcia, ponieważ rund 0.166667. 0.166666389jest nie do przyjęcia, ponieważ zaokrągla do 0.166666. Końcowe zera można pominąć. Do reprezentacji dziesiętnej można stosować notację naukową.

Oto dane wejściowe i oczekiwane wyniki dla mmaksymalnie 60 włącznie, w notacji naukowej, w zaokrągleniu do 6 miejsc po przecinku, i jako ułamki zredukowane:

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)

Implementacja referencyjna (w 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

Zasady

  • To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach
  • Nie można używać żadnych funkcji, wbudowanych lub zawartych w bibliotece zewnętrznej, które obliczają dowolny typ liczb Bernoulliego lub wielomiany Bernoulliego.
  • Twoja odpowiedź musi zawierać poprawny wynik dla wszystkich danych wejściowych do 60 włącznie.

Tabela liderów

Fragment kodu na dole tego postu generuje tabelę wyników na podstawie odpowiedzi a) jako lista najkrótszych rozwiązań dla każdego języka oraz b) jako ogólna tabela wyników.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik to suma dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:

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

Pokaż fragment kodu

code-golf math sequence combinatorics Mego
źródło
@MorganThrapp Implementacja referencyjna służy jedynie wyjaśnieniu definicji liczby Bernoulliego, a nie rozwiązaniu problemu.
Mego
Ach, gotcha. Myślałem, że to w pełni funkcjonalne wdrożenie.
Morgan Thrapp
2
@Mego Żadna standardowa liczba zmiennoprzecinkowa (nawet poczwórna precyzja) nie może przechowywać B_60 do poczwórnej precyzji. Czy zatem powinniśmy użyć formatu o rozszerzonej precyzji, jeśli wyprowadzamy dane jako miejsca dziesiętne?
lirtosiast
8
Nie podoba mi się wymóg precyzji. Niektóre języki nie mają narzędzi do pracy z liczbami zmiennoprzecinkowymi z wystarczającą dokładnością dla B_60 i wolałbym nie radzić sobie z takimi problemami podczas gry w matematykę. Napisanie rozwiązania, a następnie stwierdzenie, że jest nieważne z powodu czegoś, co wydaje się techniczną, jest frustrujące.
xnor
2
@ xnor 6 cyfr dokładności już wydaje się niewiarygodnie luźne.
primo,

Odpowiedzi:

8

Julia, 23 20 bajtów

Oszczędność 3 bajtów dzięki Alexowi A.

Używa tej samej formuły, co moje rozwiązanie Mathematica i rozwiązanie PARI / GP .

n->n>0?-zeta(1-n)n:1
alephalpha
źródło
2
20 bajtów:n->n>0?-zeta(1-n)n:1
Alex A.
@AlexA. Nie wiem dlaczego, ale zeta(n)generuje błąd, gdy njest liczbą całkowitą ujemną. Używam Julii 0.2.1 na Linuksie.
alephalpha
1
O rany, twoja wersja Julii jest dość przestarzała. Działa mi dobrze na 0.4.1.
Alex A.
25

Mathematica, 40 28 23 22 bajtów

Używając znanej formuły n * ζ (1− n ) = - B n , gdzie ζ jest funkcją Riemanna Zety .

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

Ta sama długość:

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

Oryginalne rozwiązanie, 40 bajtów, wykorzystujące funkcję generowania liczb Bernoulliego .

#!SeriesCoefficient[t/(1-E^-t),{t,0,#}]&
alephalpha
źródło
+2 gdybym mógł ...
LegionMammal978
9

Julia, 58 bajtów

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

Tworzy to funkcję rekurencyjną, Bktóra przyjmuje liczbę całkowitą i zwraca BigFloat(tj. Zmiennoprzecinkowy o wysokiej precyzji).

Nie golfowany:

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.
źródło
9

Minkolang 0,14 , 97 bajtów

Właściwie najpierw próbowałem zrobić to rekurencyjnie, ale mój tłumacz, tak jak obecnie zaprojektowany, tak naprawdę nie może tego zrobić. Jeśli spróbujesz wykonać rekurencję z pętli for, rozpocznie się nowa rekurencja. Więc wybrałem podejście tabelaryczne ... które miało problemy z precyzją. Zrobiłem wszystko z ułamkami. Bez wbudowanej obsługi ułamków. [ westchnienie ]

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

Wypróbuj tutaj. Bonus: tablica zawiera wszystkie ułamki dla każdego poprzedniego numeru Bernoulli!

Objaśnienie (za chwilę)

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

Trzecia linia odpowiada za 1/2if mrówną 1, a 0/1jeśli mliczba nieparzysta jest większa niż 1. Druga linia oblicza na B_mpodstawie wzoru sumowania podanego w pytaniu i robi to całkowicie za pomocą liczników i mianowników. W przeciwnym razie byłoby znacznie krócej. Pierwsza połowa pierwszego wiersza zajmuje się księgowością i wybiera, czy wykonać drugą czy trzecią linię, a druga połowa dzieli licznik i mianownik przez ich GCD (jeśli dotyczy) i przechowuje te wartości. I podaje odpowiedź na końcu.

El'endia Starman
źródło
8

Python 2, 118 bajtów

Zapisano 6 bajtów z powodu xsot .
Zaoszczędź 6 10 więcej dzięki Peterowi Taylorowi .

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]

Wykorzystuje następującą tożsamość:

gdzie A n jest n- tą liczbą naprzemienną , którą można formalnie zdefiniować jako liczbę naprzemiennych permutacji w zbiorze wielkości n , zmniejszoną o połowę (patrz także: A000111 ).

Zastosowany algorytm pierwotnie podali Knuth i Buckholtz (1967) :

Niech T 1, k = 1 dla wszystkich k = 1..n

Kolejne wartości T są podane przez relację powtarzalności:

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

N jest wstrzykiwany przez T n, 1

(patrz także: A185414 )

Python 2, 152 bajty

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)

Drukuje dokładną reprezentację ułamkową, niezbędną dla wartości większych niż około 200.

primo
źródło
1
Jeśli zmienisz range(2,n)na range(n-2), możesz skrócić n-k+1do n+~k. Czy istnieje powód, dla którego >>1zamiast tego używasz /2? Wreszcie trywialne ulepszenie, ale możesz zaoszczędzić kilka bajtów, aliasing range.
xsot,
Dziękuję za sugestie. I pierwotnie miał dwa wyrażenia, kiedy dołączył do nich przeoczyłem zmieniających >>1się /2.
primo
1
Jest to oszczędność jeden znak w linii wyjściowej: print+(n<1)or-(-1.)**(n+n/2)*n/(4**n-2**n)*a[n%2^1%n]. Obliczenia można wykonać dla tej samej liczby znaków, coa=[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/2is clever; 1 nie musi być wyróżniane, ponieważ wszystkie inne nieparzyste wartości i tak są zerowe. Alternatywne obliczenia są w rzeczywistości o 4 bajty krótsze przy odwróceniu bitów, ale z jakiegoś powodu są również znacznie wolniejsze.
primo,
1
Pracowałem z tabeli OEIS i pomyślałem, że znalazłeś rangei pomijając jedną iterację, by być sprytnym sposobem na skrócenie inicjalizacji. Droga już teraz podzielić się parzystych i nieparzystych indeksów jest bardzo ładny, i pozwala na dalsze oszczędności, pociągając za znak do definicji a: a=[(-1)**(n/2),n<2]*n. Zatem zwracana wartość to +(n<1)or-n/(2.**n-4**n)*a[1]. Masz również zbłąkany średnik na końcu drugiego wiersza
Peter Taylor
6

PARI / GP, 52 23 bajty

Używając znanej formuły n * ζ (1− n ) = - B n , gdzie ζ jest funkcją Riemanna Zety .

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

Oryginalne rozwiązanie, 52 bajty, wykorzystujące funkcję generowania liczb Bernoulliego .

n->n!*polcoeff(-x/sum(i=1,n+1,(-x)^i/i!)+O(x^n*x),n)
alephalpha
źródło
Można głosować tylko raz. Szkoda, że ​​to nie jest dokładne.
primo,
Zgodnie z dokumentacjązeta funkcja jest obliczana za pomocą liczb Bernoulliego, w rzeczywistości.
primo,
@primo, tak, uważam wszystkie odpowiedzi, które używają wbudowanej zeta, za oszustwo.
Peter Taylor,
Nawet łatwiej, bernfraci bernrealto 8 bajtów każdy i są one już działa, więc ma potrzeby n->. Ale +1 za dobre rozwiązanie.
Charles,
6

Python 3, 112 bajtów

Edycja: Wyczyściłem tę odpowiedź. Jeśli chcesz zobaczyć wszystkie inne sposoby, w jakie chciałem odpowiedzieć na to pytanie w Pythonie 2 i 3, zajrzyj do wersji.

Jeśli nie używam tabeli odnośników (zamiast tego używam zapamiętywania), uda mi się uzyskać definicję rekurencyjną do 112 bajtów! ZABIEGAĆ! Zauważ, że b(m)zwraca a Fraction. Jak zwykle liczba bajtów i link do testowania .

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

I funkcja, która korzysta z tabeli odnośników i zwraca całą tabelę ułamków od b(0)do b(m)włącznie.

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
źródło
1
Myślę, że można pominąć końcowe zero na liczbach zmiennoprzecinkowych, np. 1.Zamiast 1.0.
Alex A.
@AlexA. Gotowy. Usunięte .0z scałości, ponieważ szybko stają się pływak później.
Sherlock9,
Czy możesz użyć p=v=1;exec('[...];p+=1'*k)zamiast swojej najbardziej wewnętrznej pętli?
lirtosiast
5

CJam, 69 49 34 33 bajtów

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

Demo online

Dzięki Cabbie407 , którego odpowiedź uświadomiła mi algorytm Akiyama – Tanigawa.

Sekcja

{           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
źródło
Mnożenie przez n! zapobieganie utracie precyzji jest sprytne, jeśli nie nieco niedorzeczne. Zastanawiam się, czy algorytmu nie można było lekko zrefaktoryzować, aby tego uniknąć.
primo,
Nie sądzę, aby refaktoryzacja mogła uniknąć konieczności skalowania z tego prostego powodu, że skoro wiemy, że każda inna liczba Bernoulliego wynosi 0, to oczywiście dzieje się dużo odejmowania podobnych wartości, więc jest wiele miejsc, w których katastrofalna utrata znaczenia może wystąpić.
Peter Taylor,
4

PARI / GP, 45 bajtów

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

Przy użyciu tej samej formuły, co moja odpowiedź w języku Python , z A n wygenerowanym przez polilog.

Skrypt testowy

Uruchom gp, w odpowiedzi na monit wklej następujące informacje:

n->if(n,2*n/(2^n-4^n)*real(polylog(1-n,I)),1)
for(i=0, 60, print(i, ": ", %(i)))
primo
źródło
1
Dziękujemy za udostępnienie skryptu testowego - znacznie ułatwiło to testowanie!
Mego
@Mego dla ciebie i dla mnie obojga;)
primo
4

Mathematica, 52 48 42 bajtów

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

Nienazwana funkcja, która używa dosłownej definicji.

LegionMammal978
źródło
Czy to Sign@#konieczne?
alephalpha
Przetestowałem to na moim komputerze. Po usunięciu Sign@#nadal zwraca poprawną odpowiedź dla 0.
alephalpha
3

Python 2, 132 130 bajtów

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

To tylko wersja referencyjna implementacji w golfa.

Jest to trochę powolne w praktyce, ale można znacznie przyspieszyć dzięki zapamiętywaniu:

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

Możesz wypróbować tę wersję online w Ideone .

Dennis
źródło
3

gawk4, 79 bajtów

Kod 77 bajtów + 2 bajty na -Mflagę

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

Jest to implementacja algorytmu Akiyama – Tanigawa ze strony Wikipedii.

Wystąpił problem z „regułą 6 cyfr dziesiętnych”, ponieważ powoduje to wydrukowanie liczby całkowitej, a następnie 6 cyfr, ale nie ma tu listy, w której można by porównać wyniki.

Wadą jest to, że drukuje znak minus przed 0.000000wieloma razy, ale nie sądzę, że to źle.

Przykład użycia

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

Wyjście od 0 do 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,1666667
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
źródło
Czy printf"%e"zadziała?
primo
Nie, nie byłoby, ponieważ 0.00000s są tylko bardzo małe i nie są tak naprawdę zerowe.
Cabbie407,
2

GolfScript, 63 bajty

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

Demo online .

Używam tej samej formuły, co moja odpowiedź w języku Python .

Skrypt testowy

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

Link do Apphb przekroczy limit czasu. Jeśli nie masz zainstalowanego GolfScript lokalnie, polecam skorzystanie z anarchicznego interpretera golfa (użyj formularza, wybierz GolfScript, wklej, prześlij).

primo
źródło
2

Perl, 101 bajtów

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

Licząc shebang jako trzy, dane wejściowe są pobierane ze standardowego wejścia.

Używam tej samej formuły, co moja odpowiedź w języku Python .

Przykładowe użycie

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

Demo online .

primo
źródło
2

R, 93 bajty

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

Niezupełnie oryginalne jako rozwiązanie. Jeśli jakikolwiek komentarz, prosimy o kontakt!

Nie golfowany:

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
źródło
Wiem, że jest już trochę za późno, ale możesz zaoszczędzić 3 bajty, zmieniając kolejność instrukcji if/ elsei używaj zamiast niej m>0pętli 1:m-1.
Billywob,
2

W rzeczywistości , 46 45 bajtów (nie konkurują)

Zamierzałem odpowiedzieć poważnie / właściwie od miesięcy, a teraz mogę. Ponieważ korzysta z poleceń, których Poważnie nie było w listopadzie 2015 r., Nie jest konkurencyjny. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

Edycja: W lutym 2017 r. Wprowadzono aktualizację w rzeczywistości, która zmieniła, które literały funkcyjne są które. Zwykle byłoby to po prostu niekonkurujące z jakimkolwiek wyzwaniem napisanym przed lutym, ale ponieważ ta odpowiedź już nie jest konkurencyjna, i tak ją zredagowałem. Cieszyć się.

Wykorzystuje to wyraźną definicję liczb Bernoulliego na Wikipedii.

;╖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
źródło
2
Używa poleceń Poważnie nie miał w listopadzie 2015 roku? Człowieku, używa zupełnie nowego języka, który nie istniał w listopadzie 2015 roku! Jestem bardzo dumny ...
Mego
1

Ruby, 66 61 bajtów

To jest Rubinowa wersja mojej odpowiedzi w Pythonie.

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

Ponieważ używa to Rationalw swoich odpowiedziach, jestem całkiem pewien, że działa do 60, ale miałem nawet problemy z uruchomieniem b[24], więc ponownie zaimplementowałem tabelę wyszukiwania dla 86 81 80 bajtów.

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
źródło
1

J, 10 bajtów

(%1-^@-)t:

Oblicza n th liczby Bernoulliego przez znalezienie n th współczynnik funkcji wykładniczej tworzącej x / (1 - e -X ).

Stosowanie

Jeśli dane wejściowe zostaną podane jako liczba całkowita lub liczba zmiennoprzecinkowa jako argument, wyprowadzi wartość zmiennoprzecinkową. Jeśli podano rozszerzoną liczbę całkowitą, oznaczoną sufiksem x, wyświetli ona rozszerzoną liczbę całkowitą lub wymierne, dwie rozszerzone liczby całkowite oddzielone 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

Wyjaśnienie

(%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)
mile
źródło
1

Aksjomat, 134 147 bajtów

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

golf i 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
źródło
1

APL (NARS), 83 znaki, 166 bajtów

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]

Wejście jako wyjście całkowite jako duże racjonalne

  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
źródło
0

Haskell, 95 bajtów

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

To implementuje wyraźną definicję liczb Bernoulliego przedstawioną na stronie Wikipedii .

Sherlock9
źródło
0

Perl 6, 83 bajtów

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

Szybsze, 114-bajtowe rozwiązanie:

my @b=1;for 1..+slurp() {@b.push: 1-[+] (^$^m).map: {([*] $m+1-$_..$m)*@b[$_]/($m+1-$_)/([*] 1..$_)}};say @b[*-1];
bb94
źródło
Twój kod do golfowego wyzwania golfowego musi być możliwie jak najkrótszy, nawet jeśli upłynie kilka żywotów wszechświata, aby zakończyć się dla niektórych danych wejściowych.
Mego
0

JavaScript, 168 bajtów

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;

Ustaw zmienną „k” na żądaną liczbę Bernoulliego, a wynikiem będzie c [0] powyżej [0]. (licznik i mianownik)

Przykładowe użycie

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

Nie tak mały jak inne, ale jedyny, który napisałem, jest bliski. Zobacz inne https://marquisdegeek.com/code_ada99 dla moich innych prób (innych niż golf).

Markiz de Geek
źródło
0

Aksjomat, 57 bajtów

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

kod testu i wyników

(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

należy zauważyć, że ta funkcja nie jest tą, którą ktoś napisał powyżej, ale t*%e^t/(%e^t-1))z% e Euler costant

RosLuP
źródło
0

Pyth , 22 bajty

L?b-1sm*.cbdcyd-btdUb1

Wypróbuj online!

Definiuje funkcję wywoływaną jako y<number>np 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
źródło