Числа Бернулли

23

В числе Бернулли ( в частности, вторые числа Бернулли) определяются следующим рекурсивным определением:

вторые числа Бернулли

Где MCKобозначает комбинацию .

Если в mкачестве входных данных задано неотрицательное целое число , выведите десятичное представление ИЛИ уменьшенную дробь для mвторого числа Бернулли. Если вы выводите десятичное представление, у вас должно быть как минимум 6 десятичных знаков (цифр после десятичной точки) точности, и оно должно быть точным при округлении до 6 десятичных знаков. Например, для m = 2, 0.166666523является приемлемым, потому что округляет до 0.166667. 0.166666389не приемлемо, потому что округляет до 0.166666. Конечные нули могут быть опущены. Научные обозначения могут использоваться для десятичных представлений.

Вот входные и ожидаемые выходные данные mдо 60 включительно, в научной записи, округленные до 6 десятичных знаков и в виде сокращенных дробей:

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)

Ссылочная реализация (в 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

правила

  • Это код-гольф , поэтому выигрывает самый короткий код в байтах
  • Вы не можете использовать какие-либо функции, встроенные или включенные во внешнюю библиотеку, которые вычисляют либо числа Бернулли, либо полиномы Бернулли.
  • Ваш ответ должен давать правильные результаты для всех входов до 60 включительно.

Leaderboard

Фрагмент стека в нижней части этого поста создает таблицу лидеров из ответов а) в виде списка кратчайшего решения для каждого языка и б) в качестве общей таблицы лидеров.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

## Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

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

Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

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

Вы также можете сделать имя языка ссылкой, которая будет отображаться во фрагменте кода:

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

Показать фрагмент кода

code-golf math sequence combinatorics Mego
источник
@MorganThrapp Ссылочная реализация предназначена только для того, чтобы прояснить определение числа Бернулли, а не для того, чтобы фактически решить проблему.
Мего
Ах, понял. Я думал, что это была полностью функциональная реализация.
Морган Трепп
2
@Mego Ни одно стандартное число с плавающей запятой (даже с точностью до четверки) не может хранить B_60 с точностью до четверки. Должны ли мы использовать расширенный формат точности, если выводим в виде десятичных дробей?
Lirtosiast
8
Мне не нравится требование точности. Некоторые языки не имеют инструментов для работы с поплавками с достаточной точностью для B_60, и я бы предпочел не иметь дело с такими проблемами при игре в гольф математической задачи. Это расстраивает, когда вы пишете решение, а потом обнаруживаете, что оно недействительно из-за того, что кажется техническим.
xnor
2
@xnor 6 цифр точности кажется невероятно слабым.
Прим

Ответы:

8

Юлия, 23 20 байт

Сохранено 3 байта благодаря Алексу А.

Он использует ту же формулу , как мое решение Mathematica и решение PARI / GP .

n->n>0?-zeta(1-n)n:1
alephalpha
источник
2
20 байтов:n->n>0?-zeta(1-n)n:1
Алекс А.
@AlexA. Я не знаю почему, но zeta(n)выдает ошибку, когда nотрицательное целое число. Я использую Julia 0.2.1 на Linux.
alephalpha
1
О боже, твоя версия Джулии довольно устарела. У меня на 0.4.1 работает просто отлично.
Алекс А.
25

Mathematica, 40 28 23 22 байта

Используя знаменитую формулу n * ζ (1− n ) = - B n , где ζ - дзета-функция Римана .

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

Одинаковой длины:

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

Исходное решение, 40 байт, с использованием производящей функции чисел Бернулли .

#!SeriesCoefficient[t/(1-E^-t),{t,0,#}]&
alephalpha
источник
+2 если бы я мог ...
LegionMammal978
9

Юлия, 58 байт

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

Это создает рекурсивную функцию, Bкоторая принимает целое число и возвращает BigFloat(то есть с плавающей запятой высокой точности).

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
Алекс А.
источник
9

Минколанг 0,14 , 97 байт

Сначала я попытался сделать это рекурсивно, но мой переводчик, как он сейчас разрабатывает, на самом деле не может этого сделать. Если вы попытаетесь выполнить рекурсию из цикла for, она начнет новую рекурсию. Поэтому я пошел на табулирование ... у которого были проблемы с точностью. Так что я сделал все с дробями. Без встроенной поддержки дробей. [ вздох ]

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

Попробуй это здесь. Бонус: в массиве есть все дроби для каждого предыдущего числа Бернулли!

Пояснение (немного)

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

Третья строка отвечает за, 1/2если mравно 1, а 0/1если mнечетное число больше 1. Вторая строка рассчитывается B_mпо формуле суммирования, приведенной в вопросе, и полностью с помощью числителей и знаменателей. В противном случае это было бы намного короче. Первая половина первой строки выполняет некоторую бухгалтерию и выбирает, выполнять ли вторую или третью строку, а вторая половина делит числитель и знаменатель на их GCD (если применимо) и сохраняет эти значения. И выводит ответ в конце.

El'ndia Starman
источник
8

Python 2, 118 байт

Сохранено 6 байтов благодаря xsot .
Сохранено 6 10 больше из-за Питера Тейлора .

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]

Использует следующую идентичность:

где A n - это n- й переменный номер , который можно формально определить как число чередующихся перестановок в наборе размера n , деленное пополам (см. также: A000111 ).

Используемый алгоритм был первоначально дан Кнутом и Бакгольцем (1967) :

Пусть T 1, k = 1 для всех k = 1..n

Последующие значения T задаются рекуррентным соотношением:

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

Тогда A n определяется как T n, 1

(см. также: A185414 )

Python 2, 152 байта

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)

Печатает точное дробное представление, необходимое для значений больше 200 или около того.

Примо
источник
1
Если вы измените range(2,n)на range(n-2)вы можете сократить n-k+1до n+~k. Кроме того , есть причина использовать >>1вместо /2? Наконец, тривиальное улучшение, но вы можете сэкономить несколько байтов с помощью псевдонимов range.
xsot
Спасибо за предложения. Я первоначально имел два выражения, когда я присоединился к ним я проглядел изменения >>1с /2.
Примо
1
Там это экономия один символ в строке вывода: print+(n<1)or-(-1.)**(n+n/2)*n/(4**n-2**n)*a[n%2^1%n]. И вычисление может быть сделано для того же количества символов, что иa=[1]*(n+1);exec"a=[(a[j-1]+a[j+1])*j/2for j in range(len(a)-1)];"*(n-1)
Питер Тейлор
@PeterTaylor n+n/2умный; 1 не нужно выделять, потому что все остальные нечетные значения в любом случае равны нулю. Альтернативные вычисления на самом деле на 4 байта короче с инверсией битов, но также по некоторым причинам значительно медленнее.
Примо
1
Я работал с таблицей OEIS и подумал, что вы нашли rangeи пропустили одну итерацию, чтобы сделать умный способ сократить инициализацию. Путь теперь вы отщепляются четные и нечетные индексы очень хорошо, и позволяет дополнительную экономию, потянув знак в определение a: a=[(-1)**(n/2),n<2]*n. Затем возвращаемое значение +(n<1)or-n/(2.**n-4**n)*a[1]. У вас также есть запятая точка с запятой в конце строки 2.
Питер Тейлор
6

PARI / GP, 52 23 байта

Используя знаменитую формулу n * ζ (1− n ) = - B n , где ζ - дзета-функция Римана .

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

Исходное решение, 52 байта, с использованием производящей функции чисел Бернулли .

n->n!*polcoeff(-x/sum(i=1,n+1,(-x)^i/i!)+O(x^n*x),n)
alephalpha
источник
Можно только проголосовать один раз. Обидно, но не точно.
Примо
Согласно документацииzeta функция вычисляется с использованием чисел Бернулли, на самом деле.
Примо
@primo, да, я считаю все ответы, в которых используются встроенные дзеты, обманом.
Питер Тейлор
Еще проще, bernfracи bernrealэто 8 байт каждый , и они уже функционирует, поэтому нет необходимости в n->. Но +1 за хорошее решение.
Чарльз
6

Python 3, 112 байт

Изменить: я убрал этот ответ. Если вы хотите увидеть все другие способы, которыми я думал, чтобы ответить на этот вопрос в Python 2 и 3, посмотрите в ревизиях.

Если я не использую таблицу поиска (и вместо этого использую памятку), мне удается получить рекурсивное определение до 112 байт! WOO! Обратите внимание, что b(m)возвращает Fraction. Как обычно, количество байтов и ссылка для тестирования .

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

И функция, которая использует справочную таблицу и возвращает всю таблицу дробей от b(0)до b(m), включительно.

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
источник
1
Я думаю, что вы можете опустить конечный ноль на литералах с плавающей точкой, например, 1.вместо 1.0.
Алекс А.
@AlexA. Выполнено. Удалено .0из sполностью, потому что это быстро станет поплавком позже.
Sherlock9
Можете ли вы использовать p=v=1;exec('[...];p+=1'*k)вместо вашего внутреннего цикла?
lirtosiast
5

CJam, 69 49 34 33 байта

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

Онлайн демо

Благодаря Cabbie407 , чей ответ позволил мне узнать об алгоритме Акияма – Танигава.

рассечение

{           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)!
}
Питер Тейлор
источник
Умножение через ! предотвращать потерю точности является умным, если не слегка смешным. Интересно, если бы алгоритм не мог быть немного реорганизован, чтобы избежать этого.
Примо
Я не думаю, что рефакторинг мог бы избежать необходимости масштабирования по той простой причине, что, поскольку мы знаем, что каждое другое число Бернулли равно 0, очевидно, что происходит значительное вычитание аналогичных значений, поэтому во многих местах происходит катастрофическая потеря значимости может случиться.
Питер Тейлор
4

PARI / GP, 45 байт

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

Используя ту же формулу, что и в моем Python-ответе , с A n, сгенерированным через polylog.

Тестовый скрипт

Запустите gp, в командной строке вставьте следующее:

n->if(n,2*n/(2^n-4^n)*real(polylog(1-n,I)),1)
for(i=0, 60, print(i, ": ", %(i)))
Примо
источник
1
Спасибо за предоставление тестового скрипта - это сделало тестирование намного проще!
Мего
@Mego для вас и меня обоих;)
primo
4

Mathematica, 52 48 42 байта

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

Безымянная функция, которая использует буквальное определение.

LegionMammal978
источник
Это Sign@#необходимо?
алефальфа
Я проверил это на своем компьютере. После удаления Sign@#он по-прежнему возвращает правильный ответ для 0.
алефальфа
3

Python 2, 132 130 байт

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

Это всего лишь гольф-версия эталонной реализации.

Это немного медленно на практике, но может быть значительно ускорено с запоминанием:

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

Вы можете попробовать эту версию онлайн на Ideone .

Деннис
источник
3

gawk4, 79 байт

Код 77 байтов + 2 байта для -Mфлага

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

Это реализация алгоритма Акияма – Танигава со страницы Википедии.

Возникли проблемы с «правилом 6-десятичных цифр», поскольку при этом выводится целое число, а затем 6 цифр, но здесь нет списка для сравнения результатов.

Недостатком является то, что это печатает знак минус перед все 0.000000время, но я не думаю, что это неправильно.

Пример использования

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

Выход от 0 до 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
источник
Будет printf"%e"работать?
Примо
Нет, не будет, потому что 0.00000они очень маленькие и не равны нулю.
Cabbie407
2

GolfScript, 63 байта

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

Демо онлайн .

Используя ту же формулу, что и мой ответ Python .

Тестовый скрипт

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

Ссылка apphb истечет на это. Если у вас не установлен GolfScript локально, я рекомендую использовать анархический интерпретатор гольфа (используйте форму, выберите GolfScript, вставьте, отправьте).

Примо
источник
2

Perl, 101 байт

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

Считая Шебанг как три, ввод берется из стандартного ввода.

Используя ту же формулу, что и мой ответ Python .

Образец использования

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

Демо онлайн .

Примо
источник
2

R, 93 байта

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

Не совсем оригинально как решение. Если есть комментарии, пожалуйста, не стесняйтесь!

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)
Фредерик
источник
Я знаю, что сейчас немного поздно, но вы можете сэкономить 3 байта, изменив порядок операторов if/ elseи используя вместо этого m>0цикл 1:m-1.
Billywob
2

На самом деле , 46 45 байт (не конкурирующих)

Я собирался сделать Серьезный / Фактический ответ в течение нескольких месяцев, и теперь я могу. Поскольку в нем используются команды, которых серьезно не было в ноябре 2015 года, это неконкурентоспособно. Предложения по игре в гольф приветствуются. Попробуйте онлайн!

Редактировать: В феврале 2017 года было обновлено «Фактически», которое изменило, какие литералы функций какие. Обычно это просто неконкурентоспособность для любого задания, написанного до февраля, но так как этот ответ уже неконкурентен, я все равно отредактировал этот ответ. Наслаждаться.

Здесь используется явное определение чисел Бернулли в Википедии.

;╖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
источник
2
Использует команды серьезно не было в ноябре 2015 года? Чувак, здесь используется совершенно новый язык , которого не было в ноябре 2015 года! Я так горжусь ...
Мего
1

Рубин, 66 61 байт

Это Ruby-версия моего ответа на Python.

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

Поскольку он использует Rationalв своих ответах, я вполне уверен, что это работает до 60, но у меня были проблемы с запуском даже b[24], поэтому я снова реализовал таблицу поиска для 86 81 80 байт.

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
источник
1

J, 10 байт

(%1-^@-)t:

Вычисляет n- е число Бернулли, находя n- й коэффициент экспоненциальной производящей функции x / (1 - e -x ).

использование

Если для ввода задано целое число или число с плавающей точкой в ​​качестве аргумента, оно выведет число с плавающей точкой. Если задано расширенное целое число, помеченное суффиксом x, оно выведет либо расширенное целое число, либо рациональное, два расширенных целых числа, разделенных 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

объяснение

(%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)
миль
источник
1

Аксиома, 134 147 байт

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

разгрызть и проверить

(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
источник
1

APL (NARS), 83 символа, 166 байтов

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]

Ввод как целочисленный вывод как большой рациональный

  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
источник
0

Haskell, 95 байт

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

Это реализует явное определение чисел Бернулли, изложенных на странице Википедии .

Sherlock9
источник
0

Perl 6, 83 байта

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

Более быстрое 114-байтовое решение:

my @b=1;for 1..+slurp() {@b.push: 1-[+] (^$^m).map: {([*] $m+1-$_..$m)*@b[$_]/($m+1-$_)/([*] 1..$_)}};say @b[*-1];
bb94
источник
Ваш код для игры в гольф кода должен быть как можно короче, даже если для определенных входных данных требуется несколько жизней вселенной.
Мего
0

Javascript, 168 байт

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;

Установите переменную 'k' на желаемое число Бернулли, и результат будет c [0] вместо a [0]. (числитель и знаменатель)

Образец использования

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

Не такой маленький, как другие, но единственный, который я написал, приближается. См. Https://marquisdegeek.com/code_ada99 для моих других (не для гольфа) попыток.

Маркиз де гик
источник
0

Аксиома, 57 байт

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

код для теста и результатов

(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

нужно отметить, что эта функция не та, что написана выше, а t*%e^t/(%e^t-1))с% e Euler costant

RosLuP
источник
0

Pyth , 22 байта

L?b-1sm*.cbdcyd-btdUb1

Попробуйте онлайн!

Определяет функцию, которая вызывается как y<number>, например 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
источник