Golf w sekwencji, której wykładnicza funkcja generująca jest styczna

15

Prawie każdą funkcję można wyrazić jako wielomian z nieskończonymi terminami.

Na przykład, e^x = 1 + x + x^2/2! + x^3/3! + x^4/4! + ...

Na przykład, sin(x) = x - x^3/3! + x^5/5! - x^7/7! + ...

Współczynniki n-tego wyrażenia tworzą sekwencję, a odpowiednia funkcja nazywa się funkcją generującą sekwencję.

Współczynniki n-tego wyrażenia tworzą sekwencję.

Często n-ty termin miałby mianownik n!. Dlatego mnożymy współczynnik przez, n!aby uzyskać inną sekwencję, której wykładnicza funkcja generująca byłaby funkcją oryginalną.

Na przykład, sekwencja którego funkcja wykładnicza Generowanie to e^xbyłoby 1,1,1,1,....

Na przykład, sekwencja którego funkcja wykładnicza Generowanie to sin(x)byłoby 0,1,0,-1,0,1,0,-1,....

Zadanie

Twoim zadaniem jest znalezienie n-tego terminu w sekwencji, którego funkcją jest funkcja generowania wykładniczegotan(x) .

Przypadki testowe

n result
0 0
1 1
2 0
3 2
4 0
5 16
6 0
7 272
8 0
9 7936
10 0
11 353792
12 0
13 22368256
14 0
15 1903757312
16 0
17 209865342976
18 0
19 29088885112832
20 0
21 4951498053124096
22 0
23 1015423886506852352
24 0
25 246921480190207983616
26 0

(Skopiowano stąd .) (Ostrzeżenie: 0-te określenie jest inne)

Przykładowa implementacja

# copied from https://github.com/Mego/Seriously/blob/v2.0/SeriouslyCommands.py#L16
def memoized(f):
    memo = {}
    def m_fun(*args):
        if args in memo:
            return memo[args]
        else:
            res = f(*args)
            memo[args] = res
            return res
    return m_fun

# copied from https://github.com/Mego/Seriously/blob/v2.0/SeriouslyCommands.py#L169
@memoized
def binomial(n,r):
    if r > n:
        return 0
    elif r==n:
        return 1
    res = 1
    i = 1
    while i<=r:
        res *= (n+1-i)
        res /= i
        i+=1
    return int(res)

# 2*u(n+1) = Sum_{k=0..n} binomial(n, k)*u(k)*u(n-k)
# from A000111
@memoized
def u(n):
    if n<0: return 0
    if n==0: return 1
    if n==1: return 1
    return sum([binomial(n-1,k)*u(k)*u(n-1-k) for k in range(n)])//2     

def t(n):
    if n%2 == 0: return 0
    return u(n)

print('\n'.join([str(x) + ' ' + str(t(x)) for x in range(26)]))

Ideone to!

Bibliografia

Leaky Nun
źródło
4
Jeśli chcesz dowiedzieć się więcej na temat generowania funkcji i ich zastosowania w matematyce, zwłaszcza kombinatoryki i teorii liczb, gorąco polecam tę „słynną” funkcję generowania podręczników autorstwa H. Wilfa.
flawr
5
(Nie mogę się oprzeć): dosłownie twoje pierwsze zdanie jest wyjątkowo fałszywe!
Flądrowiec
Masz swoje znaczenie „funkcja generująca” i „wykładnicza funkcja generująca” wstecz. $ \ sin (x) $ to wykładnicza funkcja generująca sekwencję 0,1,0, -1,0,1,0, -1,0, ... - to nie sekwencja jest wykładniczą funkcją generującą z $ \ sin (x) $. Prosimy nas o zakodowanie sekwencji generowanej wykładniczo przez $ \ tan (x) $.
Glen O
Wygląda dobrze, z wyjątkiem: „Nazywa się to również funkcją generującą tę funkcję. Współczynniki n-tego wyrażenia tworzą sekwencję.”, Co prawdopodobnie powinno powiedzieć coś w rodzaju „Współczynniki n-tego wyrażenia tworzą sekwencję, i odpowiednia funkcja nazywa się funkcją generującą sekwencję ”.
Glen O
@GlenO Edytowane.
Leaky Nun

Odpowiedzi:

8

CJam ( 33 32 27 26 23 20 bajtów)

2,{ee::*_(@+.+}ri*0=

Demo online

Sekcja

To zasadniczo implementuje powtarzalność opisaną przez xnor .

2,        e# [0 1] represents the base case f(0,j) = j==1
{         e# Loop...
  ee::*   e#   Multiply each array element by its index
  _(@+.+  e#   Sum the array shifted left and the array shifted right
}ri*      e# ... n times
0=        e# Evaluate at j=0

Lub z innym podejściem, dla 23 bajtów:

ri_1&a{{1$+}*]W%0+}@*0=

Demo online . Dzięki Dennis za 3 bajty.

Sekcja

1a         e# Push [1]
{          e# Repeat...
  {1$+}*]  e#   Compute array of partial sums
  W%0+     e#   Reverse and append 0
}qi:A*     e# ... A times, where A is the input value
0=A1&*     e# Result is first element if A odd, and 0 otherwise

Lub z zupełnie innym podejściem, dla 29 bajtów:

qie!Ma-{W\+W+3ew{_$.=1=},!},,

Demo online

Niestety do wprowadzenia danych wymagany jest specjalny przypadek 0.

Sekcja

qi            e# Take an integer n from stdin
e!            e#   Compute all permutations of [0 ... n-1]
Ma-           e#   Special-case n=0
{             e#   Filter...
  W\+W+       e#     Prepend and postpend -1
  3ew         e#     Take slices of 3 consecutive elements
  {           e#     Filter...
    _$.=1=    e#       Test whether the middle element is the second largest
  },!         e#     ... and require no matches
},,           e#   ... and count

Być może myślisz „WTF ?! On odpowiada na złe pytanie”. Jeśli tak, jest to zrozumiałe, ale oba podejścia rzeczywiście dają prawidłowe wyniki .

Peter Taylor
źródło
W przypadku gdy pomoc pomaga, nocna wersja TIO zwraca pustą tablicę dla [WW]3ew.
Dennis
@Dennis, dzięki. Okazuje się jednak, że i tak 0musi to być szczególny przypadek, ponieważ ocenia 1.
Peter Taylor
1
Można by pomyśleć, że odpowiadasz na złe pytanie, jeśli nawet nie kliknąłeś moich linków.
Leaky Nun
ri_1&a{{1$+}*]W%0+}@*0=oszczędza 3 bajty.
Dennis
2
@LeakyNun, więc to byłby wtedy każdy. Widziałem tę listę linków i tl; dr.
Peter Taylor
7

Julia, 40 38 32 bajty

!n=2(2*4^n-2^n-0^n)abs(zeta(-n))

Dane wejściowe i wyjściowe mają postać BigFloats. Wypróbuj online!

tło

Seria Maclaurin funkcji stycznej spełnia tożsamość

ilekroć x leży w promieniu zbieżności, gdzie B n jest liczbą Bernoulliego.

Ponieważ B 2 (n + 1) i (-1) n mają ten sam znak, B 2n + 1 = 0, jeśli n> 0 i B 1 = 1/2 , możemy przepisać powyższe w następujący sposób.

Ponadto, ilekroć n jest nieujemną liczbą całkowitą, mamy taką wartość

gdzie ζ oznacza funkcję zeta Riemanna .

Z tego wynika, że ​​zgodnie z konwencją 0 0 = 1

która jest formułą używaną przez implementację.

Dennis
źródło
6

Python, 57 bajtów

f=lambda i,j=0:~-j*f(i-1,j-1)-~j*f(i-1,j+1)if i else j==1

Mniej golfa:

f=lambda i,j=0:j==1 if i==0 else (j-1)*f(i-1,j-1)+(j+1)*f(i-1,j+1)

Możemy obliczyć iwspółczynnik th wykładniczej funkcji generującej, różnicując iczasy funkcji stycznej i oceniając przy 0. Każda pochodna jest wielomianem w tan(x), a jej wartość przy 0 jest stałym elementem .

Rekurencyjnie wyrażamy współczynnik tan(x)**jw ipochodnej tanz funkcją f(i,j). Wyrażenie rekurencyjne pochodzi z relacji tan(x)' = 1 + tan(x)**2.

Tak więc pochodną tan(x)**jjest

j*tan(x)**(j-1)*(tan(x)**2+1), or equivalently
j*tan(x)**(j+1) + j*tan(x)**(j-1)

Tak więc, współtwórcami tan(x)**jw itej pochodnej są tan(x)**(j-1)i tan(x)**(j+1)w pierwszej (i-1)pochodnej, każdy o współczynniku równym jego mocy. Daje to rekurencyjną ekspresję

f(i,j) = (j-1)*f(i-1,j-1) + (j+1)*f(i-1,j+1)

Zauważ, że nie musimy wykluczać wykładników ujemnych, jponieważ i tak oceniają na zero i nie uczestniczą, ponieważ krzyżowanie j=0daje mnożnik 0.

Przypadek podstawowy i==0odpowiada tan(x)sam sobie j==1, a w przeciwnym razie zerowe współczynniki. Ostateczna ocena odbywa się na stałym poziomie j=0, który jest wprowadzany jako wartość domyślna.

xnor
źródło
To przesyła do 20 bajtów w CJam. Czy masz coś przeciwko, żebym udzielił tej podstawowej odpowiedzi, czy chcesz ją przenieść i opublikować?
Peter Taylor
Powinieneś to opublikować, nie znam CJam.
xnor
4

Mathematica, 20 bajtów

Tan@x~D~{x,#}/.x->0&

Proste podejście. Oblicz n- pochodną tan (x) i oceń ją przy x = 0 .

Stosowanie

Przykład

mile
źródło
3

Haskell, 48 bajtów

0%1=1
0%_=0
i%j=sum[k*(i-1)%k|k<-[j+1,j-1]]
(%0)

Możemy obliczyć iwspółczynnik th wykładniczej funkcji generującej, różnicując iczasy funkcji stycznej i oceniając przy 0. Każda pochodna jest wielomianem w tan(x), a wartość 0 jest jej stałym składnikiem.

Rekurencyjnie wyrażamy współczynnik tan(x)^jw ipochodnej tanz funkcją i%j. Wyrażenie rekurencyjne pochodzi z relacji tan(x)' = 1 + tan(x)^2.

Tak więc pochodną tan(x)^jjest

j*tan(x)^(j-1)*(tan(x)^2+1), or equivalently
j*tan(x)^(j+1) + j*tan(x)^(j-1)

Tak więc, współtwórcami tan(x)^jw itej pochodnej są tan(x)^(j-1)i tan(x)^(j+1)w pierwszej (i-1)pochodnej, każdy o współczynniku równym jego mocy.

xnor
źródło
3

Galaretka , 12 11 bajtów

Ṛ+\;S
ḂÇ⁸¡Ḣ

Podobnie jak odpowiedź CJama Petera Taylora , to oblicza n- ty ciąg sekwencji góra / dół Eulera, jeśli n jest nieparzyste, a przypadki specjalne nawet n jako 0 .

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

ḂÇ⁸¡Ḣ  Main link. Argument: n

Ḃ       Bit; yield n's parity.
 Ç⁸¡    Apply the helper link (Ç) n (⁸) times.
    Ḣ   Head; retrieve the first element of the resulting list.


Ṛ+\;S   Helper link. Argument: A (list or 1/0)

Ṛ       Cast A to list (if necessary) and reverse the result.
 +\     Take the cumulative sum.
   ;S   Append the sum of A.
Dennis
źródło
3

Szałwia, 26 bajtów

lambda n:tan(x).diff(n)(0)

Podobnie jak inne rozwiązania w językach zorientowanych na matematykę, ta funkcja oblicza npochodną th tan(x)i ocenia ją x = 0.

Wypróbuj online

Mego
źródło
2

J, 15 13 bajtów

Istnieje również wbudowane narzędzie, t:które oblicza n- ty współczynnik wykładniczej funkcji generującej tan (x) .

(1&o.%2&o.)t:

Dzięki @ Leaky Nun za przypomnienie mi przysłówków z serii Taylor w J, które pozwoliły zaoszczędzić 2 bajty.

Alternatywa dla 15 bajtów .

3 :'(3&o.d.y)0'

Innym podejściem jest obliczenie n- tej pochodnej tan (x) i oszacowanie jej przy x = 0 .

Uwaga: W J ilość pamięci wykorzystywanej przez funkcję pochodną d.rośnie szybko, gdy n przechodzi przez 10.

Stosowanie

   f =: (1&o.%2&o.)t:
   f 7
272
   (,.f"0) i. 11  NB. Additional commands are just for formatting the output
 0    0
 1    1
 2    0
 3    2
 4    0
 5   16
 6    0
 7  272
 8    0
 9 7936
10    0

Wyjaśnienie

(1&o.%2&o.)t:  Input: n
(         )    Define a monad (one argument function), call the input y
 1&o.          Get the trig function sin(x) and call it on y
      2&o.     Get the trig function cos(x) and call it on y
     %         Divide sin(y) by cos(y) to get tan(y)
           t:  Get the nth coefficient of the exponential generating series
               for that function and return

3 :'(3&o.d.y)0'  Input: n
3 :'          '  Define a monad (one argument function) with input y
     3&o.        Get the trig function tan(x)
           y     The input n
         d.      Get the nth derivative of tan(x)
             0   Evaluate the nth derivative at x = 0 and return
mile
źródło
2

Julia, 39 37 bajtów

!n=(spdiagm((0:n,1:n+1),(1,-1))^n)[2]

Zaoszczędzono 2 bajty dzięki Dennisowi.

Nie najkrótsze rozwiązanie Julii (patrz rozwiązanie Dennisa), ale to jest zrobione wyłącznie przy użyciu logiki pochodnej ... w postaci macierzy.

Zasadniczo wykorzystuje fakt, że pochodna tan (x) wynosi 1 + tan (x) ^ 2. Ponieważ zatem pochodna dowolnej mocy tan (x), powiedzmy tan (x) ^ k, jest k tan (x) ^ (k-1) tan (x) '= k tan (x) ^ (k-1) + k tan (x) ^ (k + 1), możemy użyć prostej mocy macierzy na macierzy o odpowiednich wartościach do wygenerowania rozszerzenia, przy czym drugi rząd lub kolumna (w zależności od konstrukcji) zawiera pochodne tan (x ) samo.

Musimy tylko znaleźć stałą w wynikowym wyrażeniu, a to pierwsza wartość w odpowiednim wierszu lub kolumnie.

Glen O
źródło
!n=(spdiagm((0:n,1:n+1),(1,-1))^n)[2]powinno działać.
Dennis
@Dennis - nice catch. Nie zdawałem sobie sprawy, spdiagmże pozwoli na ten styl konstrukcji - wypróbowałem go diagm, ale oczywiście nie działało.
Glen O
2

JavaScript (ES6), 127 45 bajtów

f=(n,m=0)=>n?++m*f(--n,m--)+--m*f(n,m):m-1?0:1

Port rozwiązań @ xnor.

Neil
źródło
0

Haskell, 95 93 bajtów

p=product
f n=sum[(-1)^(n`div`2+j+1)*j^n*p[k-j+1..n+1]`div`p[1..n+1-k+j]|k<-[1..n],j<-[0..k]]

Jest to w zasadzie implementacja ogólnej formuły z pewnymi drobnymi optymalizacjami.

wada
źródło
0

MATLAB z Symbolicznym zestawem narzędzi, 84 bajty

n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)

Przykładowe przebiegi:

>> n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)
7
ans =
272

>> n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)
8
ans =
0

>> n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)
9
ans =
7936
Luis Mendo
źródło
0

Haskell (za dużo bajtów)

Używając tylko operacji na listach i wyniku Raymonda Manzoniego :

c n = last $ map numerator $ zipWith (*) (scanl (*) (1) [2,3..]) (intersperse 0 $ foldr (.) id (replicate n (\xs->(xs ++ [(1%(1+2*length xs)) * (sum (zipWith (*) xs (reverse xs)))]))) [1])

Niestety przepełnia to skromne wartości n, ponieważ używa Intwartości. Spróbuję rozwiązać problem za pomocą Integerwartości. Do tego czasu sugestie są mile widziane.

Rodrigo de Azevedo
źródło
0

Aksjomat, 46 bajtów

f(n:NNI):NNI==(n=0=>0;eval(D(tan(x),x,n),x=0))

kod testu i wyników

(32) -> [[i, f(i)] for i in 0..26]
   (32)
   [[0,0], [1,1], [2,0], [3,2], [4,0], [5,16], [6,0], [7,272], [8,0], [9,7936],
    [10,0], [11,353792], [12,0], [13,22368256], [14,0], [15,1903757312],
    [16,0], [17,209865342976], [18,0], [19,29088885112832], [20,0],
    [21,4951498053124096], [22,0], [23,1015423886506852352], [24,0],
    [25,246921480190207983616], [26,0]]
                                       Type: List List NonNegativeInteger
RosLuP
źródło