Desafío

Dado un entero positivo N, genera la suma de los primeros Nrecíprocos como una fracción exacta, que se representa como un par de enteros en un orden consistente que representa numerador y denominador.

Reglas

• La salida debe ser exacta.

• La salida debe ser como un par de enteros en un orden consistente que represente numerador y denominador.

• Se prohíbe el uso de tipos numéricos no enteros (integrados o de biblioteca).

  • Aclaración / excepción: los tipos numéricos no enteros están bien si y solo si todos los valores utilizados, calculados y devueltos son enteros (es decir, su idioma usa números racionales por defecto, pero solo usa aritmética de enteros en su respuesta)

• La producción debe ser lo más reducida posible. ( 3/2está bien, 6/4no está)

• Las lagunas estándar están prohibidas.

• Los envíos deben funcionar para entradas de al menos hasta 20, o este meta , lo que sea mayor.

Casos de prueba

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

Generación de casos de prueba (Python 3)

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

Similar a este desafío y este desafío .

Los numeradores son OEIS A001008 , y los denominadores son 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

Pruébalo en línea!

Imprime el numerador y el denominador.

¡Hurra! Soporte MathJax !!!! Uno observa:

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

Luego, pensando en la recursividad, para positivo, en el umerador:$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!$$

y uno no puede evitar pensar en el Denominador recursivamente también; así el .$n!$exec

Debemos pagar el Piper de fracción reducida con un cálculo de GCD en el whilebucle; y luego terminamos.

Jalea , 10 bytes

!:RS,!:g/$

Pruébalo en línea!

Cómo funciona

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

Pruébalo en línea!

Ejecutar ejemplos

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

Cómo funciona

!(,%+.)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, usando el tipo de fracción

1#.1%1+i.

Pruébalo en línea!

J da fracciones para la división int-int si no es divisible.

05AB1E , 10 bytes

!DIL÷O)D¿÷

Pruébalo en línea!

Utiliza el mismo método que todas las demás entradas. La salida está en el formulario [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 bytes

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

Pruébalo en línea!

---

14 bytes si se permiten tipos fraccionales incorporados

HarmonicNumber

Pruébalo en línea!

JavaScript (ES6), 60 bytes

Las devoluciones [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]

Pruébalo en línea!

¿Cómo?

El método es similar a la respuesta de 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 bytes

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

Pruébalo en línea!

Un bloque de código anónimo que toma un número entero y devuelve una tupla de denominator, numerator.

Si se nos permitiera usar tipos fraccionarios, sería el byte 32 mucho más simple:

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

Pruébalo en línea!

Octava , 29 bytes

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

Pruébalo en línea!

C ++ 17 (gcc) , 108 bytes

Solo use aritmética de enteros:

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

Pruébalo en línea!

---

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

Pruébalo en línea!

Igual que a continuación, pero usa 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;}

Pruébalo en línea!

Debido a que C ++ no tiene soporte nativo para bigint, esto definitivamente se desbordará n>20.

Exigir:

• importdeclaración obsoleta de gcc .
• gcc's std::__gcd.
• -O0 (Creo que sí) de lo contrario el compilador optimizará d/=a .
• Al menos 64 bits long.

Explicación:

• $d=n!, a=H_n$
• Redondea a*dal entero más cercano lanzando a*d+.5a longy asigna a n. Ahora n/des la salida.
• Simplifica la fracción con std::__gcd.

Pari / GP , 34 bytes

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

Pruébalo en línea!

---

17 bytes si se permiten tipos fraccionales incorporados

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

Pruébalo en línea!

MATL, 13 bytes

:tptb/sht&Zd/

Pruébalo en MATL Online

El mismo método que el utilizado en @Dennis 'Jelly answer .

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

(Salida implícita, imprime el denominador primero y luego el numerador).

Las imprecisiones de punto flotante significan que esto no funciona para n = 20, porque los valores intermedios son demasiado grandes. Parece que la salida del caso de prueba fue un error tipográfico, esto devuelve la misma respuesta que las otras respuestas para n = 20.

Aquí hay una versión de preservación de tipo entero (25 bytes) que intenté mientras tanto, antes de descubrir esto:

25 bytes, entrada hasta 43

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

Pruébalo en línea!

Lanza los números a uint64antes de operar con ellos, realiza la aritmética explícitamente en un bucle (sin usar prodo sum). Más importante aún, divide los numeradores y denominadores parciales por su MCD en cada paso del camino, al final de cada iteración. Esto aumenta el rango de entrada para permitir nhasta 43. Parte del código se basa en la respuesta Python de @Chas Brown.

Método alternativo (original) usando LCM en lugar de factorial:

16 15 bytes

:t&Zmtb/sht&Zd/

Pruébalo en MATL Online

Excel VBA, 141 bytes

Toma entradas [A1]y salidas de la consola.

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)

No golfista y comentado

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

cc , 87 bytes

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

Pruébalo en línea!

Esto deja el numerador y el denominador en la parte superior de la pila en ese orden, como lo permite este valor predeterminado de salida. Como dcno tiene gcdincorporado, esto utiliza el algoritmo euclidiano para calcular el gcd.

Stax , 11 bytes

ó╢Δ'åç4}ú┌7

Ejecutar y depurarlo

Explicación:

Queremos calcular:

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

Entonces tenemos:

$$\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 caracteres, 112 bytes

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

prueba:

  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 pocas palabras, reduzca la "función de suma en 2 números de fracción" (un número de fracción es una lista de 2 enteros) en el conjunto:

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

esto a continuación parece incorrecto:

 f 56
74359641471727289 16124934538402170

pero si cambio el tipo de entrada que:

  f 56x
252476961434436524654789 54749786241679275146400 
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000

APL (Dyalog Unicode) , 15 12 bytes

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

Pruébalo en línea!

Función tácita, tomando un solo argumento ⍵. Guarda un byte eliminando ⌽si se nos permite imprimir el denominador primero.

Gracias @dzaima por 3 bytes.

Cómo:

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