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.

Is gcd a "built-in function" if your language provides it? — Chas Brown, Commented Jul 17, 2018 at 1:49
@ChasBrown gcd and other built-in functions are fine. Rational/fractional types are not allowed. — pizzapants184, Commented Jul 17, 2018 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, Commented Jul 17, 2018 at 5:54

Dennis · Accepted Answer · 2018-07-17 02:06:53Z

9

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

Dennis

210k41 gold badges370 silver badges824 bronze badges

Add a comment |

Chas Brown · Accepted Answer · 2018-07-17 05:24:38Z

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.

Bubbler · Accepted Answer · 2018-07-17 02:13:16Z

5

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

Bubbler

78.2k5 gold badges149 silver badges466 bronze badges

\$\begingroup\$ Only if one of the parameters are bigint. \$\endgroup\$
– DELETE_ME
Commented Jul 17, 2018 at 6:45
\$\begingroup\$ You can use wrapper like this \$\endgroup\$
– DELETE_ME
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\$
– cole
Commented Jul 17, 2018 at 13:14

Add a comment |

Mr. Xcoder · Accepted Answer · 2018-07-17 05:05:14Z

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.

alephalpha · Accepted Answer · 2018-07-17 09:02:22Z

4

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

alephalpha

49.4k7 gold badges65 silver badges181 bronze badges

\$\begingroup\$ InputForm@HarmonicNumber (24 bytes) gives output in the format given by OP. \$\endgroup\$
– Eric Towers
Commented Jul 17, 2018 at 19:46

Add a comment |

Arnauld · Accepted Answer · 2018-07-17 09:17:10Z

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

Jo King · Accepted Answer · 2018-07-18 01:57:18Z

3

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!

edited Jul 18, 2018 at 1:57

answered Jul 17, 2018 at 5:29

Jo King♦

47.4k5 gold badges124 silver badges184 bronze badges

Add a comment |

Luis Mendo · Accepted Answer · 2018-07-17 06:36:07Z

2

Octave, 29 bytes

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

Try it online!

answered Jul 17, 2018 at 6:36

Luis Mendo

105k9 gold badges133 silver badges371 bronze badges

Add a comment |

DELETE_ME · Accepted Answer · 2018-07-17 08:19:53Z

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.

Can't you use auto a=0. instead of double a=0 (1 char less)? — Dan M., Commented Jul 18, 2018 at 12:42

alephalpha · Accepted Answer · 2018-07-17 08:56:10Z

2

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!

edited Jul 17, 2018 at 8:56

answered Jul 17, 2018 at 5:08

alephalpha

49.4k7 gold badges65 silver badges181 bronze badges

Add a comment |

wastl · Accepted Answer · 2018-07-18 13:48:31Z

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

J. Sallé · Accepted Answer · 2019-07-04 13:23:24Z

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.

Suever · Accepted Answer · 2022-09-04 02:48:12Z

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

Taylor Raine · Accepted Answer · 2018-07-17 15:02:03Z

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

R. Kap · Accepted Answer · 2018-07-18 01:01:48Z

1

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

R. Kap

4,9082 gold badges15 silver badges37 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Kip the Malamute · Accepted Answer · 2023-02-26 14:44:30Z

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

Challenge

Rules

Test Cases

17 Answers 17

Jelly, 10 bytes

How it works

Python 2, 80 79 bytes

J, 16 bytes

Run examples

How it works

J, 9 bytes, using fraction type

05AB1E, 10 bytes

Wolfram Language (Mathematica), 30 bytes

14 bytes if built-in fractional types are allowed

JavaScript (ES6), 60 bytes

How?

Perl 6, 57 53 bytes

Octave, 29 bytes

C++17 (gcc), 108 bytes

C++17 (gcc), 108 bytes

C++ (gcc), 109 bytes

Pari/GP, 34 bytes

17 bytes if built-in fractional types are allowed

Stax, 11 bytes

APL (Dyalog Unicode), 15 12 bytes

How:

MATL, 13 bytes

25 bytes, input upto 43

16 15 bytes

Excel VBA, 141 bytes

Ungolfed and Commented

dc, 87 bytes

APL(NARS), 56 chars, 112 bytes

Pyt, 14 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Not the answer you're looking for? Browse other questions tagged
code-golf
math
rational-numbers
or ask your own question.