Denominador de series armónicas

16

Anteriormente, hicimos el pseudofactorial de un número, que es el MCM de los números de 1a n.

Sería útil para sumar fracciones juntas.

Sin embargo, encontramos que el denominador de 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6es en 20lugar del pseudofactorial de 6, que es 60.

Su tarea es encontrar el denominador de 1/1 + 1/2 + ... + 1/nun entero positivo dado n.

Casos de prueba

 n result
 1 1
 2 2
 3 6
 4 12
 5 60
 6 20
 7 140
 8 280
 9 2520
10 2520
11 27720
12 27720
13 360360
14 360360
15 360360
16 720720
17 12252240
18 4084080
19 77597520
20 15519504
21 5173168
22 5173168
23 118982864
24 356948592
25 8923714800
26 8923714800
27 80313433200
28 80313433200
29 2329089562800
30 2329089562800

Referencias

Tabla de clasificación

Mostrar fragmento de código

code-golf sequence Monja permeable
fuente
¿Qué tamaño de entrada tiene para trabajar?
Brad Gilbert b2gills
@ BradGilbertb2gills Tan grande como sea razonable.
Leaky Nun

Respuestas:

8

M , 9 6 bytes

¡Gracias a FryAmTheEggman por guardar 3 bytes! Código:

RİSg¹İ

M tiene una gran ventaja aquí, porque funciona con fracciones en lugar de flotantes. Explicación:

R       # Get the list [1 ... n].
 İ      # Inverse each, resulting into [1/1, 1/2, 1/3, ..., 1/n].
  S     # Sum it up. (86021/27720 for n=12)
   g¹   # Compute the greatest common denominator with n. (1/27720 for n=12)
     İ  # Calculate the inverse again. (27720 for n=12)

Utiliza la codificación Jelly . Pruébalo en línea! .

Además, hay una solución de 4 bytes , que a veces genera un cero inicial (p 280 -> 0280. Ej .). No estoy seguro de si esto está permitido o no:

RİSV

Pruébalo en línea! .

Adnan
fuente
1
1. La explicación del código de 6 bytes no es del todo correcta. g¹calcula el divisor común más grande de la fracción y n . El uso g1probablemente sería más claro. 2. Vlanza la fracción a una cuerda y la evacua niládica. <num>/es (no acumulativo) reducir por un operador niladic. Esto no tiene sentido, pero como solo hay un número (el argumento implícito 0 ), simplemente no hace nada. El siguiente enlace, el denominador, es niládico, por lo que el valor de retorno anterior se imprime implícitamente y se reemplaza por ese niládico.
Dennis
@ Dennis Gracias! Se arregló la explicación.
Adnan
@Adnan ¿Hay alguna documentación para M?
Esolanging Fruit
@ Challenger5 No que yo sepa. En realidad es una variante de Jelly, pero con fracciones de precisión arbitrarias. La documentación de Jelly se puede usar, pero tenga en cuenta que muchas funciones implementadas en Jelly no se implementan en M.
Adnan
5

Julia, 22 bytes

Una función anónima.

n->1.//(1:n)|>sum|>den
Lynn
fuente
Misma duración:n->sum(inv,1//1:n).den
Alex A.
4

Mathematica, 27 bytes

Una función anónima.

Denominator@*HarmonicNumber

Por ejemplo:

 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520
Lynn
fuente
Podrías encontrar una solución de 26 bytes si profundizas en el chat :)
Leaky Nun
Oh! Debería dejar que Martin publique esa, si le gusta. Este es adorablemente literal, así que lo guardaré.
Lynn
¿Podría ejemplificar cómo se usa el código?
DavidC
3

Python 2, 69 67 bytes

a=b=k=r=1
exec'a=a*k+b;b*=k;k+=1;'*input()
while r*a%b:r+=1
print r

Pruébalo en Ideone .

Cómo funciona

Sea H (n) la suma de los inversos multiplicativos de los primeros n enteros positivos. En todo momento, tenemos que a / b = 1 + H (k - 1) . De hecho, un , b , y k están inicializadas a 1 , y 1/1 = 1 = 1 + H (0) .

Repetimos el fragmento de código

a=a*k+b;b*=k;k+=1;

(como una cadena) n (entrada) veces y ejecuta el resultado. En cada paso, actualizamos un , b , y k utilizando la identidad a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk .

Después de que se hayan ejecutado todas las copias, a / b = 1 + H (n) , que tiene el mismo denominador que H (n) .

La forma completamente reducida de a / b es (a ÷ gcd (a, b)) / (b ÷ gcd (a, b)) . En lugar de calcular el máximo divisor común, inicializamos r como 1 y seguimos incrementando r hasta que ra sea ​​un múltiplo de b .

Claramente, esto hace que ra sea el mínimo común múltiplo de a y b . Dado que gcd (a, b) · mcm (a, b) = ab , tenemos que b ÷ gcd (a, b) = mcm (a, b) ÷ a = ra ÷ a = r , haciendo r la salida deseada.

Dennis
fuente
3

Haskell, 52

Import Data.Ratio
f n=denominator$sum[1%k|k<-[1..n]]

Si el archivo se carga en GHCI, f puede usarse como una función.

Vaelus
fuente
1
¿Presumiblemente te refieres a importminúsculas? Se ahorra un byte para usar un en maplugar de una comprensión:sum$map(1%)[1..n]
xnor
2

Jalea, 9 bytes

!©÷RSg®®÷

Pruébalo aquí

             Argument: n
! ÷R         Compute [n!÷1, n!÷2, … n!÷n].
 ©             (And store n! in the register.)
    S        Find the sum of this list.
     g®      GCD with n!.
       ®÷    Divide n! by this GCD.
Lynn
fuente
Creo que es posible lograr el mismo bytecount sin ese registro.
Leaky Nun
2

MATL , 14 13 bytes

:p:G:!/s1\&X<

Pruébalo en línea!

Explicación

Para la entrada N , la salida está limitada por N ! (factorial de N ). El código calcula n / k para n = 1, ..., N ! y para k = 1, ..., N . Luego suma k , lo que da el número armónico multiplicado por cada n . El resultado deseado es el índice n del primero de esos valores que es un entero.

Luis Mendo
fuente
2

Ruby, 57 47 bytes

->n{(1..n).reduce{|a,i|a+1.to_r/i}.denominator}

Gracias a Kevin Lau por acortar esto en diez bytes.

Peter Kagey
fuente
Asigne una variable para 1.to_rque no necesite hacer la inyección de cadena y la conversión. Además, dado que el valor predeterminado de Ruby reducees usar el primer elemento como inicial, y 1/1=1no es necesario establecerlo específicamente 0como valor inicial.
Value Ink
2

Mathematica, 26 bytes

Denominator@Tr[1/Range@#]&

Una función sin nombre que toma ncomo entrada y devuelve el denominador. Utiliza el truco estándar de abuso Tr(rastreo) para sumar la lista de reciprocos.

Martin Ender
fuente
1

JavaScript (ES6), 88 bytes

m=>{for(d=1,i=0;i<m;d*=++i);for(n=i=0;i<m;n+=d/++i);for(g=d;g;[g,n]=[n%g,g]);return d/n}

Solo funciona hasta m = 20 debido a los límites de la precisión numérica de JavaScript.

Neil
fuente
1

05AB1E , 8 bytes

Código:

!йL/O¿/

Explicación:

!         # Take the factorial of the input.
 Ð        # Triplicate this.
  ¹L      # Get the list [1 ... input].
    /O    # Divide and sum up.
      ¿   # Get the GCD of the sum and the factorial.
       /  # Divide the factorial by this.

Puede haber algunos problemas de precisión para n> 19 debido a la división de Python ... Utiliza la codificación CP-1252 .

Pruébalo en línea! .

Adnan
fuente
0

J, 20 bytes

(!%!+.[:+/!%1+i.)@x:

Basado en el enfoque utilizado por la solución de @ Lynn .

Si la precisión no es necesaria para valores grandes de n o si podemos suponer que n se pasará como un entero extendido, con el sufijo x, se puede usar una solución más corta para 15 bytes .

!%!+.[:+/!%1+i.

Uso

   f =: (!%!+.[:+/!%1+i.)@x:
   f 30
2329089562800
   (,:f"0) >: i. 15
1 2 3  4  5  6   7   8    9   10    11    12     13     14     15
1 2 6 12 60 20 140 280 2520 2520 27720 27720 360360 360360 360360

Explicación

(!%!+.[:+/!%1+i.)@x:  Input: n
                  x:  Convert n into an extended integer
              i.      Creates the range [0, 1, ..., n-1]
            1+        Add one to each, range is now [1, 2, ..., n]
          !           Get factorial of n
           %          Divide n! by each value in the range [1, 2, ..., n]
      [:+/            Sum those values
   !                  Get n!
    +.                Get gcd between n! and the sum
 !                    Get n!
  %                   Divide n! by the gcd and return
millas
fuente
0

Perl 6 ,  36  32 bytes

{([+] 1.FatRat X/1..$_).denominator}
{([+] 1.FatRat X/1..$_).nude[1]}

Explicación:

{
  (
    [+]        # reduce with &infix:<+>

      # the following produces a Seq of Rational numbers
      # 1/1, 1/2, 1/3 ... 1/n

      1.FatRat # FatRat.new: 1,1
      X/       # crossed using &infix:</>
      1 .. $_  # Range from 1 to the input inclusive

  ) # resulting in a FatRat

  .nude # (nu)merator (de)nominator
  .[1]  # grab the denominator
}

Prueba:

my &hd = {([+] 1.FatRat X/1..$_).nude[1]}

say (1..10)».&hd; # (1 2 6 12 60 20 140 280 2520 2520)

say hd 100; # 2788815009188499086581352357412492142272
say chars hd 1000; # 433
say chars hd 10000; # 4345
Brad Gilbert b2gills
fuente
0

Hoon , 95 bytes

|=
@
=+
n=(gulf 1 +<)
=+
f=(roll n mul)
(div f d:(egcd f (roll (turn n |=(@ (div f +<))) add)))

Cree una lista [1...n], dóblela con ++mulel factorial, cree una lista [n!/1, n!/2, ... n!/n]y sumécela, encuentre el MCD de n!y la lista, y divida el factorial por ese número.

Probablemente haya una forma mucho más fácil de calcular el denominador, pero no puedo entenderlo: /

RenderSettings
fuente
Oh Hoon, ¿por qué tu tokenizador necesita tantos espacios en blanco redundantes?
Leaky Nun
Todas mis entradas de Hoon se ven feas debido a las nuevas líneas :( El código normal de Hoon usa dos espacios entre los tokens, pero una nueva línea es más corta
RenderSettings
0

Python 3, 153 150 146 142 bytes

Estoy seguro de que esto puede jugar más golf. Pero soy nuevo aqui

f=lambda x:0**x or x*f(x-1)
z=int(input());i=f(z)
r=sum(i/y for y in range(1,z+1))  
p=lambda a,b:a if b<1else not a%b+b or p(b,a%b)
print(i/p(r,i))
Jorge
fuente
Bienvenido a PPCG!
Leaky Nun
0

Axioma, 34 bytes

f(x)==denominator(sum(1/n,n=1..x))

prueba 

(24) -> [[i,f(i)] for i in 1..30]
   (24)
   [[1,1], [2,2], [3,6], [4,12], [5,60], [6,20], [7,140], [8,280], [9,2520],
    [10,2520], [11,27720], [12,27720], [13,360360], [14,360360], [15,360360],
    [16,720720], [17,12252240], [18,4084080], [19,77597520], [20,15519504],
    [21,5173168], [22,5173168], [23,118982864], [24,356948592],
    [25,8923714800], [26,8923714800], [27,80313433200], [28,80313433200],
    [29,2329089562800], [30,2329089562800]]
                                       Type: List List Expression Integer
RosLuP
fuente
0

PHP, 81 bytes

for($p=1;$z++<$argn;$n=$n*$z+$p/$z)$p*=$z;for($t=1+$n;$p%--$t||$n%$t;);echo$p/$t;

Pruébalo en línea!

Jörg Hülsermann
fuente