Dénominateur de séries harmoniques

16

Plus tôt, nous avons fait la pseudo - factorielle d'un nombre, qui est le LCM des nombres de 1à n.

Il serait utile d'ajouter des fractions ensemble.

Cependant, nous constatons que le dénominateur de 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6est 20au lieu du pseudofactoriel de 6, qui l'est 60.

Votre tâche consiste à trouver le dénominateur d' 1/1 + 1/2 + ... + 1/nun entier positif donné n.

Cas de test

 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

Les références

Classement

Afficher l'extrait de code

code-golf sequence Leaky Nun
la source
Quelle est la taille d'une entrée pour laquelle elle doit fonctionner?
Brad Gilbert b2gills
@ BradGilbertb2gills Aussi gros que raisonnable.
Leaky Nun

Réponses:

8

M , 9 6 octets

Merci à FryAmTheEggman pour avoir économisé 3 octets! Code:

RİSg¹İ

M a un énorme avantage ici, car il fonctionne avec des fractions plutôt qu'avec des flottants. Explication:

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)

Utilise l' encodage Jelly . Essayez-le en ligne! .

En outre, il existe une solution à 4 octets , qui produit parfois un zéro non significatif (par exemple 280 -> 0280). Je ne sais pas si cela est autorisé ou non:

RİSV

Essayez-le en ligne! .

Adnan
la source
1
1. L'explication du code à 6 octets n'est pas tout à fait correcte. g¹calcule le diviseur commun le plus gratifiant de la fraction et n . L'utilisation g1serait probablement plus claire. 2. Vtransforme la fraction en une chaîne et l'évalue niladiquement. <num>/est (non cumulatif) réduit par un opérateur niladique. C'est un non-sens, mais comme il n'y a qu'un seul nombre (l'argument implicite 0 ), il ne fait tout simplement rien. Le lien suivant, le dénominateur, est niladique, donc la valeur de retour précédente est imprimée implicitement et remplacée par cette nilade.
Dennis
@Dennis Merci! Correction de l'explication.
Adnan
@Adnan Y a-t-il de la documentation pour M?
Esolanging Fruit
@ Challenger5 Pas que je sache. Il s'agit en fait d'une variante de Jelly, mais avec des fractions de précision arbitraires. La documentation Jelly peut être utilisée, mais sachez que de nombreuses fonctionnalités implémentées dans Jelly ne le sont pas dans M.
Adnan
5

Julia, 22 octets

Une fonction anonyme.

n->1.//(1:n)|>sum|>den
Lynn
la source
Même durée:n->sum(inv,1//1:n).den
Alex A.
4

Mathematica, 27 octets

Une fonction anonyme.

Denominator@*HarmonicNumber

Par exemple:

 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520
Lynn
la source
Vous pouvez trouver une solution de 26 octets si vous creusez dans le chat :)
Leaky Nun
Oh! Je devrais laisser Martin poster celui-là, s'il le souhaite. Celui-ci est adorablement littéral, donc je le garderai.
Lynn
Pourriez-vous illustrer comment le code est utilisé?
DavidC
3

Python 2, 69 67 octets

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

Testez-le sur Ideone .

Comment ça fonctionne

Soit H (n) la somme des inverses multiplicatifs des n premiers entiers positifs. À tout moment, nous avons que a / b = 1 + H (k - 1) . En fait, a , b et k sont tous initialisés à 1 et 1/1 = 1 = 1 + H (0) .

Nous répétons l'extrait de code

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

(sous forme de chaîne) n (entrée) fois et exécutez le résultat. À chaque étape, nous mettons à jour a , b et k en utilisant l'identité a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk .

Une fois toutes les copies exécutées, a / b = 1 + H (n) , qui a le même dénominateur que H (n) .

La forme entièrement réduite de a / b est (a ÷ pgcd (a, b)) / (b ÷ pgcd (a, b)) . Au lieu de calculer le plus grand diviseur commun, nous initialisons r à 1 et continuons à incrémenter r jusqu'à ce que ra soit un multiple de b .

De toute évidence, cela fait de ra le plus petit multiple commun de a et b . Puisque gcd (a, b) · lcm (a, b) = ab , nous avons que b ÷ gcd (a, b) = lcm (a, b) ÷ a = ra ÷ a = r , faisant de r la sortie souhaitée.

Dennis
la source
3

Haskell, 52

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

Si le fichier est chargé dans GHCI, f peut être utilisé comme fonction.

Vaelus
la source
1
Vraisemblablement, vous voulez dire en importminuscules? Il enregistre un octet pour utiliser un mapau lieu d'une compréhension:sum$map(1%)[1..n]
xnor
2

Gelée, 9 octets

!©÷RSg®®÷

Essayez-le ici.

             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
la source
Je pense qu'il est possible d'atteindre le même nombre de bytecards sans ce registre.
Leaky Nun
2

MATL , 14 13 octets

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

Essayez-le en ligne!

Explication

Pour l'entrée N , la sortie est délimitée par N ! (factorielle de N ). Le code calcule n / k pour n = 1, ..., N ! et pour k = 1, ..., N . Il additionne ensuite k , ce qui donne le nombre harmonique multiplié par chaque n . Le résultat souhaité est l'indice n de la première de ces valeurs qui est un entier.

Luis Mendo
la source
2

Rubis, 57 47 octets

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

Merci à Kevin Lau d' avoir raccourci cela de dix octets.

Peter Kagey
la source
Attribuez une variable à 1.to_rafin que vous n'ayez pas besoin d'injecter et de convertir des chaînes. De plus, puisque la valeur par défaut de Ruby reduceest d'utiliser le premier élément comme initial, et 1/1=1vous n'avez pas besoin de définir spécifiquement 0comme valeur initiale.
Value Ink
2

Mathematica, 26 octets

Denominator@Tr[1/Range@#]&

Une fonction sans nom prenant nen entrée et renvoyant le dénominateur. Utilise l'astuce standard d'abus Tr(trace) pour additionner la liste des réciproques.

Martin Ender
la source
1

JavaScript (ES6), 88 octets

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}

Fonctionne uniquement jusqu'à m = 20 en raison des limites de la précision numérique de JavaScript.

Neil
la source
1

05AB1E , 8 octets

Code:

!йL/O¿/

Explication:

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

Il pourrait y avoir des problèmes de précision pour n> 19 en raison de la division de Python ... Utilise l' encodage CP-1252 .

Essayez-le en ligne! .

Adnan
la source
0

J, 20 octets

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

Basé sur l'approche utilisée par la solution de @ Lynn .

Si la précision n'est pas nécessaire pour les grandes valeurs de n ou si nous pouvons supposer que n sera passé comme un entier étendu, suffixé par x, une solution plus courte peut être utilisée pour 15 octets .

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

Usage

   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

Explication

(!%!+.[:+/!%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
miles
la source
0

Perl 6 ,  36  32 octets

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

Explication:

{
  (
    [+]        # 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
}

Tester:

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
la source
0

Hoon , 95 octets

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

Créez une liste [1...n], repliez-la avec ++mulpour la factorielle, créez une liste [n!/1, n!/2, ... n!/n]et additionnez-la, trouvez GCD de n!et la liste et divisez la factorielle par ce nombre.

Il y a probablement un moyen beaucoup plus simple de calculer le dénominateur, mais je ne peux pas le comprendre: /

RenderSettings
la source
Oh Hoon, pourquoi votre tokenizer a besoin de tant d'espaces blancs redondants?
Leaky Nun
Toutes mes entrées Hoon semblent laides à cause des nouvelles lignes :( Le code Hoon normal utilise deux espaces entre les jetons, mais une nouvelle ligne est plus courte
RenderSettings
0

Python 3, 153 150 146 142 octets

Je suis sûr que cela peut aller plus loin. Mais je suis nouveau ici

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))
George
la source
Bienvenue chez PPCG!
Leaky Nun
0

Axiome, 34 octets

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

tester 

(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
la source
0

PHP, 81 octets

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

Essayez-le en ligne!

Jörg Hülsermann
la source