Défi

Étant donné un entier positif N, affichez la somme des premiers Ninverses sous forme de fraction exacte, qui est représentée par une paire d'entiers dans un ordre cohérent représentant le numérateur et le dénominateur.

Règles

• La sortie doit être exacte.

• La sortie doit être une paire d'entiers dans un ordre cohérent représentant le numérateur et le dénominateur.

• L'utilisation de types numériques non entiers (intégrés ou bibliothèque) est interdite.

  • Clarification / exception: les types numériques non entiers sont corrects si et seulement si toutes les valeurs utilisées, calculées et retournées sont des entiers (c'est-à-dire que votre langue utilise des nombres rationnels par défaut, mais vous n'utilisez que l'arithmétique entière dans votre réponse)

• La sortie doit être aussi réduite que possible. ( 3/2ça va, 6/4non)

• Les failles standard sont interdites.

• Les soumissions doivent fonctionner pour des entrées d'au moins 20, ou cette méta , selon la valeur la plus élevée.

Cas de test

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

Génération de cas de test (Python 3)

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

Semblable à ce défi et à ce défi .

Les numérateurs sont OEIS A001008 et les dénominateurs sont OEIS A002805 .

Python 2 , 80 79 octets

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

Essayez-le en ligne!

Imprime le numérateur et le dénominateur.

Yay! Prise en charge de MathJax !!!! On observe:

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

Ensuite, en pensant à la récursivité, pour positif, dans l' umérateur:$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!$$

et on ne peut s'empêcher de penser à l' Dénominateur récursivement aussi; ainsi le .$n!$exec

Nous devons payer le Piper à Fraction Réduite avec un calcul GCD dans la whileboucle; et puis nous avons terminé.

Gelée , 10 octets

!:RS,!:g/$

Essayez-le en ligne!

Comment ça fonctionne

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

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

Essayez-le en ligne!

Exécuter des exemples

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

Comment ça fonctionne

!(,%+.)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 octets, en utilisant le type de fraction

1#.1%1+i.

Essayez-le en ligne!

J donne des fractions pour la division int-int si non divisible.

05AB1E , 10 octets

!DIL÷O)D¿÷

Essayez-le en ligne!

Utilise la même méthode que toutes les autres entrées. La sortie est dans le formulaire [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 octets

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

Essayez-le en ligne!

---

14 octets si les types fractionnaires intégrés sont autorisés

HarmonicNumber

Essayez-le en ligne!

JavaScript (ES6), 60 octets

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

Essayez-le en ligne!

Comment?

La méthode est similaire à la réponse Python de @ 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$$

$b=0$

$p/a$$q/a$

Perl 6 , 57 53 octets

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

Essayez-le en ligne!

Un bloc de code anonyme qui prend un entier et renvoie un tuple de denominator, numerator.

Si nous étions autorisés à utiliser des types fractionnaires, ce serait le 32 octets beaucoup plus simple:

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

Essayez-le en ligne!

Octave , 29 octets

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

Essayez-le en ligne!

C ++ 17 (gcc) , 108 octets

Utilisez uniquement l'arithmétique entière:

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

Essayez-le en ligne!

---

C ++ 17 (gcc) , 108 octets

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

Essayez-le en ligne!

Comme ci-dessous, mais utilisez C ++ 17 std::gcd.

---

C ++ (gcc) , 109 octets

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

Essayez-le en ligne!

Parce que C ++ n'a pas de support natif bigint, cela débordera certainement pour n>20.

Exiger:

• Déclaration obsolète de gcc import.
• gcc std::__gcd.
• -O0 (Je pense que oui) sinon le compilateur optimisera d/=a .
• Au moins 64 bits long.

Explication:

• $d=n!, a=H_n$
• Arrondissez a*dà l'entier le plus proche en convertissant a*d+.5en longet attribuez-le à n. Maintenant, n/dc'est la sortie.
• Simplifiez la fraction avec std::__gcd.

Pari / GP , 34 octets

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

Essayez-le en ligne!

---

17 octets si les types fractionnaires intégrés sont autorisés

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

Essayez-le en ligne!

MATL, 13 octets

:tptb/sht&Zd/

Essayez-le sur MATL Online

Même méthode que celle utilisée dans la réponse Jelly de @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.     

(Sortie implicite, imprime d'abord le dénominateur puis le numérateur.)

Les imprécisions en virgule flottante signifient que cela ne fonctionne pas pour n = 20, car les valeurs intermédiaires sont trop grandes. On dirait que la sortie du scénario de test était une faute de frappe, cela renvoie la même réponse que les autres réponses pour n = 20.

Voici une version préservant le type entier (25 octets) que j'ai essayée entre-temps, avant de le découvrir:

25 octets, entrée jusqu'à 43

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

Essayez-le en ligne!

Convertit les nombres uint64avant d'opérer sur eux, fait l'arithmétique explicitement dans une boucle (sans utiliser prodou sum). Plus important encore, divise les numérateurs et dénominateurs partiels par leur GCD à chaque étape du processus, à la fin de chaque itération. Cela augmente la plage d'entrée pour autoriser njusqu'à 43. Une partie du code est basé sur la réponse Python de @Chas Brown.

Méthode alternative (originale) utilisant LCM au lieu de factorielle:

16 15 octets

:t&Zmtb/sht&Zd/

Essayez-le sur MATL Online

Excel VBA, 141 octets

Prend des entrées [A1]et des sorties sur la console.

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)

Non golfé et commenté

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

dc , 87 octets

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

Essayez-le en ligne!

Cela laisse le numérateur et le dénominateur en haut de la pile dans cet ordre, comme le permet cette sortie par défaut. Puisqu'il dcn'a pas de fonction gcdintégrée, il utilise l' algorithme euclidien pour calculer le gcd.

Stax , 11 octets

ó╢Δ'åç4}ú┌7

Exécuter et déboguer

Explication:

Nous voulons calculer:

$$\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}$$

Nous avons donc:

$$\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 caractères, 112 octets

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

tester:

  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 

En quelques mots, réduisez la "fonction somme sur 2 nombres de fractions" (un nombre de fractions est une liste de 2 nombres entiers) sur l'ensemble:

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

cela ci-dessous semble faux:

 f 56
74359641471727289 16124934538402170

mais si je change le type d'entrée alors:

  f 56x
252476961434436524654789 54749786241679275146400 
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000

APL (Dyalog Unicode) , 15 12 octets

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

Essayez-le en ligne!

Fonction tacite, prenant un seul argument ⍵. Enregistre un octet en supprimant le ⌽si nous sommes autorisés à imprimer le dénominateur en premier.

Merci @dzaima pour 3 octets.

Comment:

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