Exact Partial Sum of Harmonic Series

Question

Challenge

Given a positive integer N, output the sum of the first N reciprocals as an exact fraction, which is represented as a pair of integers in a consistent order representing numerator and denominator.

Rules

• Output must be exact.

• Output should be as a pair of integers in a consistent order representing numerator and denominator.

• Using non-integer numeric types (built-in or library) is forbidden.

  • Clarification/exception: non-integer numeric types are okay if and only if all values used, computed, and returned are integers (i.e. your language uses rational numbers by default, but you only use integer arithmetic in your answer)

• Output should be as reduced as possible. (3/2 is okay, 6/4 is not)

• Standard loopholes are forbidden.

• Submissions should work for inputs at least up to 20, or this meta, whichever is higher.

Test Cases

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

Test-Case Generation (Python 3)

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

Similar to this challenge and this challenge.

Numerators are OEIS A001008, and denominators are OEIS A002805.

Answer 1

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

Try it online!

Prints the numerator and denominator.

Yay! MathJax support!!!! One observes:

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

Then, thinking about recursion, for \$n\$ positive, in the Numerator:

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

and one can't help think of the Denominator \$n!\$ recursively as well; thus the exec.

We must pay the Reduced Fraction Piper with a GCD calculation in the while loop; and then we're done.

Answer 2

Jelly, 10 bytes

!:RS,!:g/$

Try it online!

How it works

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

Answer 3

J, 16 bytes

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

Try it online!

Run examples

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

How it works

!(,%+.)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, using fraction type

1#.1%1+i.

Try it online!

J gives fractions for int-int division if not divisible.

Answer 4

05AB1E, 10 bytes

!DIL÷O)D¿÷

Try it online!

Uses the same method as all other entries. Output is in the form [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. 

Answer 5

Wolfram Language (Mathematica), 30 bytes

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

Try it online!

---

14 bytes if built-in fractional types are allowed

HarmonicNumber

Try it online!

Answer 6

Perl 6, 57 53 bytes

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

Try it online!

An anonymous code block that takes an integer and returns a tuple of denominator, numerator.

If we were allowed to use fractional types, it would be the much simpler 32 byter:

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

Try it online!

Answer 7

JavaScript (ES6), 60 bytes

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

Try it online!

How?

The method is similar to @ChasBrown's Python answer.

We first compute the unreduced numerator \$a\$ and unreduced denominator \$b\$ by starting with \$a=0\$ and \$b=1\$ and recursively doing:

$$a\gets an+b\\ b\gets bn\\ n\gets n-1$$

until \$n=0\$.

We save \$(a,b)\$ into \$(p,q)\$ and then compute \$a\gets \gcd(a,b)\$ with:

$$a\gets b\\ b\gets a \bmod b$$

until \$b=0\$.

We finally return the reduced numerator \$p/a\$ and reduced denominator \$q/a\$.

Answer 8

Pari/GP, 34 bytes

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

Try it online!

---

17 bytes if built-in fractional types are allowed

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

Try it online!

Answer 9

Octave, 29 bytes

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

Try it online!

Answer 10

C++17 (gcc), 108 bytes

Only use integer arithmetic:

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

Try it online!

---

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

Try it online!

Same as below, but use C++17's 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;}

Try it online!

Because C++ doesn't have native bigint support, this will definitely overflow for n>20.

Require:

• gcc's deprecated import statement.
• gcc's std::__gcd.
• -O0 (I think so) otherwise the compiler will optimize out d/=a.
• At least 64-bit long.

Explanation:

• Let \$d=n!, a=H_n\$.
• Round a*d to nearest integer by casting a*d+.5 to long, and assign to n. Now n/d is the output.
• Simplify the fraction with std::__gcd.

Answer 11

MATL, 13 bytes

:tptb/sht&Zd/

Try it on MATL Online

Same method as used in @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.     

(Implicit output, prints denominator first and then the numerator.)

Floating point inaccuracies mean this doesn't work for n = 20, because the intermediate values are too large. Looks like the test case output was a typo, this returns the same answer as the other answers for n=20.

Here's an integer type-preserving version (25 bytes) I tried in the meantime, before finding this out:

25 bytes, input upto 43

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

Try it online!

Casts the numbers to uint64 before operating on them, does the arithmetic explicitly in a loop (without using prod or sum). More importantly, divides the partial numerators and denominators by their GCD every step along the way, at the end of each iteration. This increases the input range to allow n upto 43. Part of the code is based on @Chas Brown's Python answer.

Alternate (original) method using LCM instead of factorial:

16 15 bytes

:t&Zmtb/sht&Zd/

Try it on MATL Online

Answer 12

Excel VBA, 141 bytes

Takes input from [A1] and outputs to the 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)

Ungolfed and Commented

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

Answer 13

dc, 87 bytes

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

Try it online!

This leaves the numerator and denominator on top of the stack in that order, as allowed by this output default. Since dc does not have a gcd built-in, this utilizes the Euclidean algorithm to calculate the gcd.

Answer 14

Stax, 11 bytes

ó╢Δ'åç4}ú┌7

Run and debug it

Explanation:

We want to calculate:

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

We now need a denominator \$b\$ and a list of numerators \$a_i\$:

$$\sum_{i=1}^n{\frac{a_i}b}=\frac{\sum_{i=1}^n{a_i}}{b}$$

We can make \$b=n!\$, then we have:

\begin{align} \frac{a_i}{n!}&=\frac 1 i&|\times n! \\ a_i&=\frac{n!}i \end{align}

So we have:

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

Answer 15

APL(NARS), 56 chars, 112 bytes

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

test:

  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 

In few words reduce "sum function on 2 fraction numbers" (one fraction number is a list 2 integers) on the set:

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

this below seems wrong:

 f 56
74359641471727289 16124934538402170

but if i change the type of input than:

  f 56x
252476961434436524654789 54749786241679275146400 
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000

Answer 16

APL (Dyalog Unicode), 15 12 bytes

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

Try it online!

Tacit function, taking a single argument ⍵. Saves a byte by removing the ⌽ if we're allowed to print the denominator first.

Thanks @dzaima for 3 bytes.

How:

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