Herausforderung

Bei einer positiven Ganzzahl Nwird die Summe der ersten NReziprokwerte als exakter Bruch ausgegeben , der als ein Paar von Ganzzahlen in einer konsistenten Reihenfolge dargestellt wird, die Zähler und Nenner darstellt.

Regeln

• Die Ausgabe muss exakt sein.

• Die Ausgabe sollte als Ganzzahlenpaar in einer konsistenten Reihenfolge erfolgen, die Zähler und Nenner darstellt.

• Die Verwendung von nicht ganzzahligen numerischen Typen (eingebaut oder Bibliothek) ist verboten.

  • Erläuterung / Ausnahme: Nicht ganzzahlige numerische Typen sind nur dann in Ordnung, wenn alle verwendeten, berechneten und zurückgegebenen Werte Ganzzahlen sind (dh Ihre Sprache verwendet standardmäßig rationale Zahlen, aber Sie verwenden in Ihrer Antwort nur Ganzzahlarithmetik).

• Die Leistung sollte so gering wie möglich sein. ( 3/2ist okay, 6/4ist nicht)

• Standardlücken sind verboten.

• Übermittlungen sollten für Eingaben von mindestens 20 oder für dieses Meta funktionieren , je nachdem, welches höher ist.

Testfälle

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

Testfallgenerierung (Python 3)

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

Ähnlich wie diese Herausforderung und diese Herausforderung .

Zähler sind OEIS A001008 und Nenner sind OEIS A002805 .

Python 2 , 80 79 Bytes

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

Probieren Sie es online!

Gibt den Zähler und den Nenner aus.

Yay! MathJax-Unterstützung !!!! Man beobachtet:

$$\sum_{i=1}^{n} \frac{1}{i} = \sum_{i=1}^{n} \frac{n!}{n!i} = \frac{\sum_{i=1}^{n} \frac{n!}{i}}{n!}$$

Denken Sie dann an die Rekursion für positives Ergebnis im Umerator:$n$N

$$\sum_{i=1}^{n+1} \frac{(n+1)!}{i} = (n+1) \sum_{i=1}^{n} \frac{n!}{i} + \frac{(n+1)!}{n+1} = (n+1) \sum_{i=1}^{n} \frac{n!}{i} + n!$$

und man kann nicht umhin, an den Denominator denkenauch rekursiv; also die .$n!$exec

Wir müssen den Reduced Fraction Piper mit einer GCD-Berechnung in der whileSchleife bezahlen ; und dann sind wir fertig.

Gelee , 10 Bytes

!:RS,!:g/$

Probieren Sie es online!

Wie es funktioniert

!: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.

J , 16 Bytes

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

Probieren Sie es online!

Führen Sie Beispiele aus

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

Wie es funktioniert

!(,%+.)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 Bytes, unter Verwendung des Bruchtyps

1#.1%1+i.

Probieren Sie es online!

J gibt Brüche für die Int-Int-Division an, wenn diese nicht teilbar sind.

05AB1E , 10 Bytes

!DIL÷O)D¿÷

Probieren Sie es online!

Verwendet die gleiche Methode wie alle anderen Einträge. Die Ausgabe erfolgt in der Form [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. 

Wolfram Language (Mathematica) , 30 Byte

#/GCD@@#&@{Tr[#!/Range@#],#!}&

Probieren Sie es online!

---

14 Byte, wenn eingebaute gebrochene Typen zulässig sind

HarmonicNumber

Probieren Sie es online!

JavaScript (ES6), 60 Byte

Rückgabe [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]

Probieren Sie es online!

Wie?

Die Methode ähnelt der Python-Antwort von @ ChasBrown .

$a$$b$$a=0$$b=1$

$$a\gets an+b\\ b\gets bn\\ n\gets n-1$$

$n=0$

$(a,b)$$(p,q)$$a\gets \gcd(a,b)$

$$a\gets b\\ b\gets a \bmod b$$

bis .$b=0$

Wir geben schließlich den reduzierten Zähler und den reduzierten Nenner .q /$p/a$$q/a$

Perl 6 , 57 53 Bytes

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

Probieren Sie es online!

Ein anonymer Codeblock, der eine Ganzzahl annimmt und ein Tupel von zurückgibt denominator, numerator.

Wenn wir Bruchteile verwenden könnten, wäre dies der viel einfachere 32-Byte-Typ:

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

Probieren Sie es online!

Oktave , 29 Bytes

@(n)sym(sprintf('+1/%i',1:n))

Probieren Sie es online!

C ++ 17 (gcc) , 108 Bytes

Verwenden Sie nur Ganzzahlarithmetik:

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

Probieren Sie es online!

---

C ++ 17 (gcc) , 108 Bytes

#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;}

Probieren Sie es online!

Wie unten, jedoch mit C ++ 17 std::gcd.

---

C ++ (gcc) , 109 Bytes

#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;}

Probieren Sie es online!

Da C ++ keine native Bigint-Unterstützung hat, läuft dies definitiv über n>20.

Benötigen:

• gcc's veraltete importAussage.
• gcc's std::__gcd.
• -O0(Ich denke schon) sonst wird der Compiler optimieren d/=a.
• Mindestens 64-Bit long.

Erläuterung:

• $d=n!, a=H_n$
• Runden Sie a*dauf die nächste Ganzzahl, indem Sie a*d+.5auf longund zuweisen n. Jetzt n/dist die Ausgabe.
• Vereinfachen Sie den Bruch mit std::__gcd.

Pari / GP , 34 Bytes

n->l=[sum(i=1,n,n!/i),n!];l/gcd(l)

Probieren Sie es online!

---

17 Byte, wenn eingebaute gebrochene Typen zulässig sind

n->sum(i=1,n,1/i)

Probieren Sie es online!

MATL, 13 Bytes

:tptb/sht&Zd/

Probieren Sie es auf MATL Online aus

Gleiche Methode wie in der @ Tennis 'Jelly-Antwort .

: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.     

(Implizite Ausgabe, druckt zuerst den Nenner und dann den Zähler.)

Gleitkommaungenauigkeiten bedeuten, dass dies für n = 20 nicht funktioniert, da die Zwischenwerte zu groß sind. Es sieht so aus, als ob die Testfallausgabe ein Tippfehler war. Dies gibt dieselbe Antwort wie die anderen Antworten für n = 20 zurück.

Hier ist eine integer-typerhaltende Version (25 Bytes), die ich in der Zwischenzeit ausprobiert habe, bevor ich dies herausgefunden habe:

25 Bytes, Eingabe bis zu 43

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

Probieren Sie es online!

Wandelt die Zahlen uint64vor der Bearbeitung in Zahlen um und führt die Arithmetik explizit in einer Schleife durch (ohne Verwendung von prododer sum). Insbesondere werden die Teilzähler und Nenner bei jedem Schritt am Ende jeder Iteration durch ihre GCD dividiert. Dadurch wird der Eingabebereich auf bis zu n43 erhöht. Ein Teil des Codes basiert auf der Antwort von @Chas Brown auf Python.

Alternative (ursprüngliche) Methode mit LCM anstelle von Fakultät:

16 15 Bytes

:t&Zmtb/sht&Zd/

Probieren Sie es auf MATL Online aus

Excel VBA, 141 Bytes

Überträgt Eingaben von [A1]und Ausgaben an die Konsole.

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)

Ungolfed und Kommentiert

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

Gleichstrom , 87 Bytes

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

Probieren Sie es online!

Auf diese Weise bleiben Zähler und Nenner in dieser Reihenfolge oben auf dem Stapel, wie dies in der Standardausgabe zulässig ist . Da dces keinen gcdeingebauten Algorithmus gibt , verwendet dieser den euklidischen Algorithmus zur Berechnung des gcd.

Stax , 11 Bytes

ó╢Δ'åç4}ú┌7

Führen Sie es aus und debuggen Sie es

Erläuterung:

Wir wollen berechnen:

$$\sum_{i=1}^n{\frac 1 i}$$

$b$$a_i$

$$\sum_{i=1}^n{\frac{a_i}b}=\frac{\sum_{i=1}^n{a_i}}{b}$$

$b=n!$

$$\begin{align} \frac{a_i}{n!}&=\frac 1 i&|\times n! \\ a_i&=\frac{n!}i \end{align}$$

Also haben wir:

$$\sum_{i=1}^n{\frac 1 n}=\frac{\sum_{i=1}^n{\frac{n!}i}}{n!}$$

|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

APL (NARS), 56 Zeichen, 112 Byte

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

Prüfung:

  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 

Reduzieren Sie in wenigen Worten die "Summenfunktion für 2 Bruchzahlen" (eine Bruchzahl ist eine Liste mit 2 ganzen Zahlen) auf der Menge:

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

das unten scheint falsch:

 f 56
74359641471727289 16124934538402170

aber wenn ich die Art der Eingabe ändere als:

  f 56x
252476961434436524654789 54749786241679275146400 
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000

APL (Dyalog Unicode) , 15 12 Bytes

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

Probieren Sie es online!

Stillschweigende Funktion mit einem einzigen Argument ⍵. Speichert ein Byte, indem entfernt wird, ⌽wenn der Nenner zuerst gedruckt werden darf.

Danke @dzaima für 3 Bytes.

Wie:

⌽!(,÷∨)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.