15
\$\begingroup\$

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.

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

17 Answers 17

9
\$\begingroup\$

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.
answered Jul 17, 2018 at 2:06
\$\endgroup\$
9
\$\begingroup\$

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.

answered Jul 17, 2018 at 1:22
\$\endgroup\$
0
5
\$\begingroup\$

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.

answered Jul 17, 2018 at 2:13
\$\endgroup\$
3
  • \$\begingroup\$ Only if one of the parameters are bigint. \$\endgroup\$ Commented Jul 17, 2018 at 6:45
  • \$\begingroup\$ You can use wrapper like this \$\endgroup\$ Commented Jul 17, 2018 at 8:15
  • \$\begingroup\$ Would 2 x:1#.1%1+i. count as a valid answer, or is this an invalid use of a rational type? \$\endgroup\$ Commented Jul 17, 2018 at 13:14
5
\$\begingroup\$

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.
answered Jul 17, 2018 at 5:05
\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

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

Try it online!

14 bytes if built-in fractional types are allowed

HarmonicNumber

Try it online!

answered Jul 17, 2018 at 9:02
\$\endgroup\$
1
  • \$\begingroup\$ InputForm@HarmonicNumber (24 bytes) gives output in the format given by OP. \$\endgroup\$ Commented Jul 17, 2018 at 19:46
3
\$\begingroup\$

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

answered Jul 17, 2018 at 8:44
\$\endgroup\$
3
\$\begingroup\$

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!

answered Jul 17, 2018 at 5:29
\$\endgroup\$
2
\$\begingroup\$

Octave, 29 bytes

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

Try it online!

answered Jul 17, 2018 at 6:36
\$\endgroup\$
2
\$\begingroup\$

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.
answered Jul 17, 2018 at 7:52
\$\endgroup\$
2
  • \$\begingroup\$ Can't you use auto a=0. instead of double a=0 (1 char less)? \$\endgroup\$ Commented Jul 18, 2018 at 12:42
  • \$\begingroup\$ Yes he can. And one more byte from the loop: 106 bytes \$\endgroup\$ Commented Jul 3, 2019 at 22:49
2
\$\begingroup\$

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!

answered Jul 17, 2018 at 5:08
\$\endgroup\$
2
\$\begingroup\$

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
answered Jul 18, 2018 at 13:25
\$\endgroup\$
2
\$\begingroup\$

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.
answered Jul 3, 2019 at 22:22
\$\endgroup\$
2
\$\begingroup\$

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

Suever
11.2k1 gold badge24 silver badges52 bronze badges
answered Jul 17, 2018 at 19:41
\$\endgroup\$
1
\$\begingroup\$

Excel VBA, 141 bytes

Takes input from [A1] and outputs to the console. 

s="=If(Row()>A1,ドル":[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()>A1,ドル" '' 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
answered Jul 17, 2018 at 15:02
\$\endgroup\$
1
\$\begingroup\$

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.

answered Jul 18, 2018 at 1:01
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 56 chars, 112 bytes

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

test:

 f←{⍵=1:⊂1 1⋄{(r s)←⍺⋄(i j)←⍵⋄m÷∨/m←((×ばつ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
answered Jul 3, 2019 at 8:32
\$\endgroup\$
1
\$\begingroup\$

Pyt, 14 bytes

Đ!⇹ř/Đ↑⇹ƩáĐÁǤ/

Try it online!

Outputs [denominator, numerator].

Đ implicit input; Đuplicate
 ! factorial
 ⇹ swap top two on stack
 ř řangify
 / divide
 Đ↑ Đuplicate; get max
 ⇹ swap top two on stack
 Ʃ Ʃum
 á push stack to árray
 Đ Đuplicate
 Á push contents of Árray to stack
 Ǥ get ǤCD
 / divide; implicit print
answered Feb 26, 2023 at 14:44
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.