Denominator of harmonic series

16

Earlier, we did the pseudofactorial of a number, which is the LCM of the numbers from 1 to n.

It would be useful in adding fractions together.

However, we find that the denominator of 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 is 20 instead of the pseudofactorial of 6, which is 60.

Your task is to find the denominator of 1/1 + 1/2 + ... + 1/n given positive integer n.

Testcases

 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

References

Leaderboard

var QUESTION_ID=82815,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Leaky Nun

Posted 2016-06-13T17:23:18.850

Reputation: 45 011

How big of an input does it have to work for? – Brad Gilbert b2gills – 2016-06-13T21:12:08.093

@BradGilbertb2gills As big as is reasonable. – Leaky Nun – 2016-06-13T22:24:07.633

Answers

8

M, 9 6 bytes

Thanks to FryAmTheEggman for saving 3 bytes! Code:

RİSg¹İ

M has a huge advantage here, because it works with fractions rather than floats. Explanation:

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)

Uses the Jelly encoding. Try it online!.

Also, there is a 4-byte solution, which outputs a leading zero sometimes (e.g. 280 -> 0280). I'm not sure if this is allowed or not:

RİSV

Try it online!.

Adnan

Posted 2016-06-13T17:23:18.850

Reputation: 41 965

1>

  • The explanation of the 6-byte code isn't quite correct. g¹ computes the gratest common divisor of the fraction and n. Using g1 would probably be clearer. 2. V casts the fraction to a string and evaulates it niladically. <num>/ is (non-cumulative) reduce by a niladic operator. This is nonsense, but since there's only one number (the implicit argument 0), it simply does nothing. The next link, the denominator, is niladic, so the previous return value is printed implicitly and replaced with that nilad.
    • < – Dennis – 2016-06-13T19:49:47.933

    @Dennis Thanks! Fixed the explanation. – Adnan – 2016-06-13T20:13:35.937

    @Adnan Is there any documentation for M? – Esolanging Fruit – 2017-05-30T07:12:50.027

    @Challenger5 Not that I know of. It is actually a variant of Jelly, but with arbitrary precision fractions. The Jelly documentation can be used, but be awate that a lot of features implemented in Jelly aren't implemented in M. – Adnan – 2017-05-30T07:33:49.550

    5

    Julia, 22 bytes

    An anonymous function.

    n->1.//(1:n)|>sum|>den

    Lynn

    Posted 2016-06-13T17:23:18.850

    Reputation: 55 648

    Same length: n->sum(inv,1//1:n).den – Alex A. – 2016-06-14T00:29:29.977

    4

    Mathematica, 27 bytes

    An anonymous function.

    Denominator@*HarmonicNumber

    For example:

     In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520

    Lynn

    Posted 2016-06-13T17:23:18.850

    Reputation: 55 648

    You could find a 26-byte solution if you dig into the chat :) – Leaky Nun – 2016-06-13T17:57:38.743

    Oh! I should let Martin post that one, if he likes. This one is adorably literal, so I’ll keep it. – Lynn – 2016-06-13T18:01:33.967

    Would you exemplify how the code is used? – DavidC – 2016-06-13T20:15:10.863

    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

    Test it on Ideone.

    How it works

    Let H(n) be the sum of the multiplicative inverses of the first n positive integers. At all times, we have that a / b = 1 + H(k - 1). In fact, a, b, and k are all initialized to 1, and 1 / 1 = 1 = 1 + H(0).

    We repeat the code snippet

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

    (as a string) n (input) times and execute the result. In each step, we update a, b, and k using the identity a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk.

    After all copies have been executed, a / b = 1 + H(n), which has the same denominator as H(n).

    The fully reduced form of a / b is (a ÷ gcd(a,b)) / (b ÷ gcd(a,b)). Instead of calculating the greatest common divisor, we initialize r as 1 and keep incrementing r until ra is a multiple of b.

    Clearly, this makes ra the least common multiple of a and b. Since gcd(a,b) · lcm(a,b) = ab, we have that b ÷ gcd(a,b) = lcm(a,b) ÷ a = ra ÷ a = r, making r the desired output.

    Dennis

    Posted 2016-06-13T17:23:18.850

    Reputation: 196 637

    3

    Haskell, 52

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

    If the file is loaded into GHCI, f can be used as a function.

    Vaelus

    Posted 2016-06-13T17:23:18.850

    Reputation: 417

    1Presumbably you mean import lowercase? It saves a byte to use a map instead of a comprehension: sum$map(1%)[1..n] – xnor – 2016-06-15T05:47:33.817

    2

    MATL, 14 13 bytes

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

    Try it online!

    Explanation

    For input N, the output is upper-bounded by N! (factorial of N). The code computes n/k for n = 1, ..., N! and for k = 1, ..., N. Then it sums over k, which gives the harmonic number multiplied by each n. The desired result is the index n of the first of those values that is an integer.

    Luis Mendo

    Posted 2016-06-13T17:23:18.850

    Reputation: 87 464

    2

    Jelly, 9 bytes

    !©÷RSg®®÷

    Try it here.

                 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

    Posted 2016-06-13T17:23:18.850

    Reputation: 55 648

    I believe it is possible to achieve the same bytecount without that register. – Leaky Nun – 2016-06-13T22:49:19.743

    2

    Ruby, 57 47 bytes

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

    Thanks to Kevin Lau for shortening this by ten bytes.

    Peter Kagey

    Posted 2016-06-13T17:23:18.850

    Reputation: 2 789

    Assign a variable to 1.to_r so you don't need to do string injection and conversion. Also, since Ruby's default for reduce is to use the first element as the initial, and 1/1=1, you don't need to specifically set 0 as the initial value. – Value Ink – 2016-06-14T05:43:27.877

    2

    Mathematica, 26 bytes

    Denominator@Tr[1/Range@#]&

    An unnamed function taking n as input and returning the denominator. Uses the standard trick of abusing Tr (trace) to sum the list of reciprocals.

    Martin Ender

    Posted 2016-06-13T17:23:18.850

    Reputation: 184 808

    1

    Pari/GP, 30 bytes

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

    Try it online!

    alephalpha

    Posted 2016-06-13T17:23:18.850

    Reputation: 23 988

    1

    05AB1E, 8 bytes

    Code:

    !йL/O¿/

    Explanation:

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

    There might be some accuracy problems for n > 19 due to Python's division... Uses the CP-1252 encoding.

    Try it online!.

    Adnan

    Posted 2016-06-13T17:23:18.850

    Reputation: 41 965

    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}

    Only works up to m=20 because of the limits of JavaScript's numeric precision.

    Neil

    Posted 2016-06-13T17:23:18.850

    Reputation: 95 035

    0

    Axiom, 34 bytes

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

    test 

    (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

    Posted 2016-06-13T17:23:18.850

    Reputation: 3 036

    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;

    Try it online!

    Jörg Hülsermann

    Posted 2016-06-13T17:23:18.850

    Reputation: 13 026

    0

    Python 3, 153 150 146 142 bytes

    I'm sure this can golfed further. But I'm new here

    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

    Posted 2016-06-13T17:23:18.850

    Reputation: 1 495

    Welcome to PPCG! – Leaky Nun – 2016-06-13T22:30:35.927

    0

    J, 20 bytes

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

    Based on the approach used by @Lynn's solution.

    If precision is not necessary for large values of n or if we can assume n will be passed as an extended integer, suffixed by x, a shorter solution can be used for 15 bytes.

    !%!+.[:+/!%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

    Explanation

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

    Posted 2016-06-13T17:23:18.850

    Reputation: 15 654

    0

    Perl 6,  36  32 bytes

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

    Explanation:

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

    Test:

    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

    Posted 2016-06-13T17:23:18.850

    Reputation: 12 713

    0

    Hoon, 95 bytes

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

    Create list [1...n], fold over it with ++mul for the factorial, create list [n!/1, n!/2, ... n!/n] and sum it, find GCD of n! and the list, and divide the factorial by that number.

    There's probably a much easier way to calculate the denominator, but I can't figure it out :/

    RenderSettings

    Posted 2016-06-13T17:23:18.850

    Reputation: 620

    Oh Hoon, why your tokenizer needs so many redundant whitespaces? – Leaky Nun – 2016-06-14T22:54:09.410

    All my Hoon entries look ugly because of the newlines :( Normal Hoon code uses two spaces between tokens, but one newline is shorter – RenderSettings – 2016-06-14T23:40:19.287

    Asked: 2016-06-13T17:23:18.850

    Viewed: 911 times

    Active: 2017-07-05T18:17:06.103