# Exact Partial Sum of Harmonic Series

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

• Sandbox post (deleted) – pizzapants184 Jul 17 '18 at 0:18
• related – Leaky Nun Jul 17 '18 at 1:33
• Is gcd a "built-in function" if your language provides it? – Chas Brown Jul 17 '18 at 1:49
• @ChasBrown gcd and other built-in functions are fine. Rational/fractional types are not allowed. – pizzapants184 Jul 17 '18 at 2:02
• @JoKing That's fine if the numbers are rational type as long as only integers are used. I'll update the question. – pizzapants184 Jul 17 '18 at 5:54

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

# 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. # 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. • – user202729 Jul 17 '18 at 6:45 • You can use wrapper like this – user202729 Jul 17 '18 at 8:15 • Would 2 x:1#.1%1+i. count as a valid answer, or is this an invalid use of a rational type? – cole Jul 17 '18 at 13:14 # 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. # Wolfram Language (Mathematica), 30 bytes #/GCD@@#&@{Tr[#!/Range@#],#!}& Try it online! ## 14 bytes if built-in fractional types are allowed HarmonicNumber Try it online! • InputForm@HarmonicNumber (24 bytes) gives output in the format given by OP. – Eric Towers Jul 17 '18 at 19:46 # 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$. # 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:

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

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

# 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

# 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

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