Dokładna częściowa suma szeregów harmonicznych

15

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą N, wypisuje sumę pierwszych Nodwrotności jako dokładną część, która jest reprezentowana jako para liczb całkowitych w spójnej kolejności reprezentującej licznik i mianownik.

Zasady

  • Dane wyjściowe muszą być dokładne.

  • Dane wyjściowe powinny być jako para liczb całkowitych w spójnej kolejności reprezentującej licznik i mianownik.

  • Używanie typów liczbowych niecałkowitych (wbudowanych lub biblioteki) jest zabronione.

    • Wyjaśnienie / wyjątek: typy liczbowe niecałkowite są w porządku, jeśli i tylko wtedy, gdy wszystkie użyte, obliczone i zwrócone wartości są liczbami całkowitymi (tzn. Twój język domyślnie używa liczb wymiernych, ale w odpowiedzi używasz tylko arytmetyki liczb całkowitych)
  • Wydajność powinna być jak najmniejsza. ( 3/2jest w porządku, 6/4nie jest)

  • Standardowe luki są zabronione.

  • Zgłoszenia powinny działać dla danych wejściowych co najmniej do 20 lub tej meta , w zależności od tego, która wartość jest wyższa.

Przypadki testowe

1: 1/1
2: 3/2 (1/1 + 1/2)
3: 11/6 (1/1 + 1/2 + 1/3)
4: 25/12 etc.
5: 137/60
6: 49/20
20: 55835135/15519504
56: 252476961434436524654789/54749786241679275146400
226: 31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161/5290225078451893176693594241665890914638817631063334447389979640757204083936351078274058192000

Generowanie przypadków testowych (Python 3)

import fractions
def f(x):
    return sum(fractions.Fraction(1,i) for i in range(1,x+1))

Podobne do tego wyzwania i tego wyzwania .

Liczniki to OEIS A001008 , a mianownikami są OEIS A002805 .

pizzapanty184
źródło
związane z
Leaky Nun
Jest gcd „funkcja wbudowana” jest dostępna w Twoim języku?
Chas Brown,
@ChasBrown gcdi inne wbudowane funkcje są w porządku. Typy wymierne / ułamkowe są niedozwolone.
pizzapants184
1
@JoKing W porządku, jeśli liczby są racjonalne, o ile używane są tylko liczby całkowite. Zaktualizuję pytanie.
pizzapants184

Odpowiedzi:

8

Python 2 , 80 79 bajtów

D=1;N=n=0;exec"n+=1;y=N=N*n+D;x=D=D*n;"*input()
while y:x,y=y,x%y
print N/x,D/x

Wypróbuj online!

Drukuje licznik i mianownik.

Tak! Wsparcie MathJax !!!! Obserwuje się:

i=1n1i=i=1nn!n!i=i=1nn!in!

Następnie, myśląc o rekurencji, dla n dodatniej, w Numeratorze:

i=1n+1(n+1)!i=(n+1)i=1nn!i+(n+1)!n+1=(n+1)i=1nn!i+n!

i nie można nie myśleć o Dmianowniku również rekurencyjnie; tak więc .n!exec

Musimy zapłacić Piper o zmniejszonej frakcji z obliczeniem GCD w whilepętli; i skończymy.

Chas Brown
źródło
7

Galaretka , 10 bajtów

!:RS,!:g/$

Wypróbuj online!

Jak to działa

!:RS,!:g/$  Main link. Argument: n

!           Compute n!.
  R         Range; yield [1, ..., n].
 :          Divide n! by each k in [1, ..., n].
   S        Take the sum. Let's call it s.
     !      Compute n! again.
    ,       Pair; yield [s, n!].
      :g/$  Divide [s, n!] by their GCD.
Dennis
źródło
5

J , 16 bajtów

!(,%+.)1#.!%1+i.

Wypróbuj online!

Uruchom przykłady

f =: !(,%+.)1#.!%1+i.
f 6x
   20 49
f 20x
   15519504 55835135
f 56x
   54749786241679275146400 252476961434436524654789

Jak to działa

!(,%+.)1#.!%1+i.    NB. Tacit verb
            1+i.    NB. 1 to n inclusive
          !%        NB. Divide factorial by 1 to n
       1#.          NB. Sum i.e. numerator (not reduced)
!                   NB. Factorial i.e. denominator (not reduced)
 (,%+.)             NB. Divide both by GCD

J , 9 bajtów, przy użyciu typu ułamkowego

1#.1%1+i.

Wypróbuj online!

J daje ułamki do podziału int-int, jeśli nie jest podzielny.

Bubbler
źródło
Czy 2 x:1#.1%1+i.liczy się jako poprawna odpowiedź, czy jest to nieprawidłowe użycie racjonalnego typu?
cole
5

05AB1E , 10 bajtów

!DIL÷O)D¿÷

Wypróbuj online!

Używa tej samej metody, co wszystkie inne wpisy. Dane wyjściowe są w formie [denominator, numerator].

!DIL÷O)D¿÷   Full program. Let's call the input I.
!D           Push the factorial twice to the stack. STACK: [I!, I!]
  IL         Range from 1 to I. STACK: [I!, I!, [1 ... I]]
    ÷        Vectorized integer division. STACK: [I!, [I! / 1, I! / 2, ..., I! / I]]
     O       Sum. STACK: [I!, I! / 1 + I! / 2 + ... + I! / I]
      )      Wrap stack. STACK: [[I!, I! / 1 + I! / 2 + ... + I! / I]]
       D     Duplicate. STACK: [[I!, I! / 1 + ... + I! / I], [I!, I! / 1 +... + I! / I]]
        ¿    GCD. STACK: [[I!, I! / 1 + ... + I! / I], gcd(I!, I! / 1 +... + I! / I)]
         ÷   Vectorized integer division. 
Pan Xcoder
źródło
3

JavaScript (ES6), 60 bajtów

Powraca [numerator, denominator].

f=(n,a=0,b=1)=>n?f(n-1,p=a*n+b,q=b*n):b?f(0,b,a%b):[p/a,q/a]

Wypróbuj online!

W jaki sposób?

Metoda jest podobna do odpowiedzi Pythona na @ ChasBrown .

aba=0b=1

aan+bbbnnn1

n=0

(za,b)(p,q)zagcd(za,b)

zabbzamodb

aż do b=0

p/zaq/za .

Arnauld
źródło
3

Perl 6 , 57 53 bajtów

{+($!=[*] 1..$_)/($!=($/=sum $! X/1..$_)gcd$!),$//$!}

Wypróbuj online!

Anonimowy blok kodu, który przyjmuje liczbę całkowitą i zwraca krotkę denominator, numerator.

Gdybyśmy mogli używać typów ułamkowych, byłoby to znacznie prostsze 32 bajtowe:

{sum(map 1/*.FatRat,1..$_).nude}

Wypróbuj online!

Jo King
źródło
2

C ++ 17 (gcc) , 108 bajtów

Używaj tylko arytmetyki liczb całkowitych:

#import<random>
int f(int x,long&n,long&d){n=0;d=1;int
a;while(n=n*x+d,d*=x,a=std::gcd(n,d),n/=a,d/=a,--x);}

Wypróbuj online!


C ++ 17 (gcc) , 108 bajtów

#import<random>
int f(long&n){double a=0;long
d=1;while(d*=n,a+=1./n,--n);n=a*d+.5;n/=a=std::gcd(n,d);d/=a;}

Wypróbuj online!

Tak jak poniżej, ale używaj C ++ 17 std::gcd.


C ++ (gcc) , 109 bajtów

#import<regex>
int f(long&n){double a=0;long
d=1;while(d*=n,a+=1./n,--n);n=a*d+.5;n/=a=std::__gcd(n,d);d/=a;}

Wypróbuj online!

Ponieważ C ++ nie ma natywnej obsługi biginta, na pewno się przepełni n>20.

Wymagać:

  • Przestarzałe importoświadczenie gcc .
  • gcc's std::__gcd.
  • -O0(Tak myślę) w przeciwnym razie kompilator zoptymalizuje się d/=a.
  • Co najmniej 64-bitowy long.

Wyjaśnienie:

  • Pozwolić re=n!,za=H.n.
  • Zaokrąglij a*ddo najbliższej liczby całkowitej, przesyłając a*d+.5do longi przypisz do n. Teraz n/djest wyjście.
  • Uprość ułamek za pomocą std::__gcd.
użytkownik202729
źródło
Nie możesz użyć auto a=0.zamiast double a=0(1 char mniej)?
Dan M.
Tak potrafi. I jeszcze jeden bajt z pętli: 106 bajtów
movatica
2

MATL, 13 bajtów

:tptb/sht&Zd/

Wypróbuj na MATL Online

Ta sama metoda, jak w odpowiedzi Jelly @Dennis .

:t    % Range from 1 to n, duplicate. 
pt    % Take the product of that (= factorial), duplicate that too.     
b/    % Bring the range to top of stack, divide factorial by each element    
sh    % Sum those. Concatenate factorial and this into a single array.     
t&Zd/ % Compute GCD of those and divide the concatenated array elements by the GCD.     

(Wyjściowe wyjście, najpierw drukuje mianownik, a następnie licznik.)

Niedokładności zmiennoprzecinkowe oznaczają, że to nie działa dla n = 20, ponieważ wartości pośrednie są zbyt duże.Wygląda na to, że dane wyjściowe przypadku testowego były literówką, to zwraca tę samą odpowiedź co inne odpowiedzi dla n = 20.

Oto wersja zachowująca typy liczb całkowitych (25 bajtów), w międzyczasie próbowałem, zanim się tego dowiedziałem:

25 bajtów, wejście do 43

O1i:3Y%"t@*b@*b+wht&Zd/Z}

Wypróbuj online!

Rzuca liczby uint64przed operacją na nich, wykonuje arytmetykę jawnie w pętli (bez użycia prodlubsum ). Co ważniejsze, dzieli częściowe liczniki i mianowniki przez ich GCD na każdym kroku, na końcu każdej iteracji. Zwiększa to zakres wejściowy, pozwalając na zwiększenie ndo 43. Część kodu oparta jest na odpowiedzi Pythona na @Chas Brown.

Alternatywna (oryginalna) metoda wykorzystująca LCM zamiast silni:

16 15 bajtów

:t&Zmtb/sht&Zd/

Wypróbuj na MATL Online

sundar - Przywróć Monikę
źródło
1

Excel VBA, 141 bajtów

Pobiera dane wejściowe [A1]i wyjściowe do konsoli.

s="=If(Row()>A$1,":[B:B]=s+"1,Row())":l=[LCM(B:B)]:[C:C]=s &"0,"&l &"/B1)":g=[GCD(LCM(B:B),SUM(C:C))]:?Format([Sum(C:C)]/g,0)"/"Format(l/g,0)

Niegolfowany i komentowany

Sub HarmonicSum(n)
    [A1] = n                            ''  Pipe input
    s = "=IF(ROW()>A$1,"                ''  Hold the start of formulas
    [B1:B40] = s + "1,ROW())"           ''  Get series of numbers 1 to N, trailing 1s
    l = [LCM(B1:B40)]                   ''  Get LCM
    [C1:C40] = s & "0," & l & "/B1)"    ''  Get LCM/M for M in 1 to N
    g = [GCD(LCM(B1:B40),SUM(C1:C40))]  ''  Get GCD
                                        ''  Format and print output
    Debug.Print Format([Sum(C1:C40)] / g, 0); "\"; Format(l / g, 0)
End Sub
Taylor Scott
źródło
1

dc , 87 bajtów

?sn1dsNsD[lndlDdlNln*+sN*sD1-dsn1<M]sMln1<MlDsAlNsB[lAlB%sTlBsAlTsBlB0<G]dsGxlDlA/lNlA/

Wypróbuj online!

Pozostawia to licznik i mianownik na szczycie stosu w tej kolejności, co jest dozwolone przez ten domyślnie wyjściowego. Ponieważ dcnie ma gcdwbudowanego, wykorzystuje to algorytm euklidesowy do obliczenia gcd.

R. Kap
źródło
1

Stax , 11 bajtów

ó╢Δ'åç4}ú┌7

Uruchom i debuguj

Wyjaśnienie:

Chcemy obliczyć:

ja=1n1ja

Potrzebujemy teraz mianownika b oraz lista liczników zaja:

ja=1nzajab=ja=1nzajab

Możemy zrobić b=n!, potem będzie:

zajan!=1ja|×n!zaja=n!ja

Więc mamy:

ja=1n1n=ja=1nn!jan!
|Fx{[/m|+L:_m Full program
|F            Factorial
  x           Push input again
   {  m       Map over range [1, n]
    [           Copy the factorial
     /          Divide factorial by current value
       |+     Sum
         L    Listify stack, top gets first element
          :_  Divide both values by gcd
            m Print each followed by newline
pustkowie
źródło
1

APL (NARS), 56 znaków, 112 bajtów

{⍵=1:⊂1 1⋄{(r s)←⍺⋄(i j)←⍵⋄m÷∨/m←((r×j)+s×i),s×j}/1,¨⍳⍵}

test:

  f←{⍵=1:⊂1 1⋄{(r s)←⍺⋄(i j)←⍵⋄m÷∨/m←((r×j)+s×i),s×j}/1,¨⍳⍵}
  f 1
1 1 
  f 2
3 2 
  f 3
11 6 
  f 20
55835135 15519504 

W kilku słowach zmniejsz „funkcję sumowania na 2 liczbach ułamkowych” (jedna liczba ułamkowa to lista 2 liczb całkowitych) na zbiorze:

1 2, 1 3,..., 1 n

to poniżej wydaje się błędne:

 f 56
74359641471727289 16124934538402170

ale jeśli zmienię typ danych wejściowych niż:

  f 56x
252476961434436524654789 54749786241679275146400 
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000
RosLuP
źródło
1

APL (Dyalog Unicode) , 15 12 bajtów

⌽!(,÷∨)1⊥!÷⍳

Wypróbuj online!

Funkcja milcząca, biorąc jeden argument . Zapisuje bajt, usuwając, jeśli wolno nam najpierw wydrukować mianownik.

Dzięki @dzaima za 3 bajty.

W jaki sposób:

⌽!(,÷∨)1⊥!÷⍳  Tacit function, argument will be called ⍵.
             Range 1..⍵ 
          ÷   Dividing
         !    the factorial of 
       1     Base-1 decode, aka sum;
 !(   )       Using that sum and the factorial of  as arguments, fork:
             (GCD
    ÷         dividing
   ,          the vector with both arguments)
             reversed.
J. Sallé
źródło