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

\$\endgroup\$
  • \$\begingroup\$ Sandbox post (deleted) \$\endgroup\$ – pizzapants184 Jul 17 '18 at 0:18
  • \$\begingroup\$ related \$\endgroup\$ – Leaky Nun Jul 17 '18 at 1:33
  • \$\begingroup\$ Is gcd a "built-in function" if your language provides it? \$\endgroup\$ – Chas Brown Jul 17 '18 at 1:49
  • \$\begingroup\$ @ChasBrown gcd and other built-in functions are fine. Rational/fractional types are not allowed. \$\endgroup\$ – pizzapants184 Jul 17 '18 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\$ – pizzapants184 Jul 17 '18 at 5:54

14 Answers 14

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

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

\$\endgroup\$
4
\$\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. 
\$\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!

\$\endgroup\$
  • \$\begingroup\$ InputForm@HarmonicNumber (24 bytes) gives output in the format given by OP. \$\endgroup\$ – Eric Towers Jul 17 '18 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\$.

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

\$\endgroup\$
2
\$\begingroup\$

Octave, 29 bytes

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

Try it online!

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

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

\$\endgroup\$
1
\$\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.
\$\endgroup\$
  • \$\begingroup\$ Can't you use auto a=0. instead of double a=0 (1 char less)? \$\endgroup\$ – Dan M. Jul 18 '18 at 12:42
1
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.