1419. The Harmonic Sum, Exactly

Print 1 + 1/2 + 1/3 + ... + 1/n as an exact reduced fraction.

n = 1 -> 1/1 n = 2 -> 3/2 n = 3 -> 11/6 n = 4 -> 25/12 n = 6 -> 49/20

Look at n = 6: the denominator is 20, not 720 and not even 60. The common denominator and the reduced denominator are different things, and the problem is only interesting because of that.

## The sign rule, pinned before anything is asserted

A fraction has more than one reduced spelling unless the sign is placed by a rule: -1/2 and 1/-2 are the same number. So this problem requires

• the denominator positive,
• the sign carried by the numerator,
• zero written exactly 0/1.

Without that sentence the five reference languages would disagree and the problem would be unanswerable rather than hard.

## What most people try first

Add the terms as double values. The sum is irrational-looking and never exactly representable, so the printed digits are rounding noise and the five reference languages disagree in the last places. The point of asking for a fraction is to remove that entirely.

The second attempt uses n! as the common denominator. For n = 40 that is about 8 * 10^47, which no integer type holds. Even the much smaller product of the denominators as they arrive overflows long before n = 40.

## Accumulate over the lcm, reducing as you go

Keep a running num/den and add 1/i to it using the least common multiple of den and i:

g = gcd(den, i) step = i / g so lcm(den, i) = den * step num = num * step + den / g since lcm/den = step and lcm/i = den/g den = den * step reduce num/den by their gcd

The reduction after each step is what keeps the numbers small. Without it the denominator is lcm(1..n), which for n = 40 is 485721041551200, about 4.9 * 10^14; with it the denominator is still at most that, because the reduced denominator always divides the lcm.

## Why it is correct

lcm(den, i) = den * (i / gcd(den, i)) is the standard identity, and dividing before multiplying keeps it from overflowing. The rewrite num/den = num * step / (den * step) is exact, as is 1/i = (den/g) / (den * step), because den * step = lcm is a multiple of i with quotient den/g. So the addition is a genuine addition of numerators over a shared denominator, and reducing afterwards does not change the value.

By induction the invariant is that num/den equals the partial sum in lowest terms at every step, so the final pair is the answer.

## Why the answer stays inside 64 bits

The reduced denominator divides lcm(1, 2, ..., n), which for n = 40 is 485721041551200. The sum itself is below 1 + ln 40 < 5, so the numerator is below 5 * 4.9 * 10^14, about 2.5 * 10^15. Both fit a signed 64-bit integer comfortably. That bound is the reason the constraint stops at 40 rather than somewhere larger: at n = 50 the lcm already passes 3 * 10^21.

## Overflow

The final numerator for n = 40 is 2078178381193813, about 2.1 * 10^15, which needs 64 bits: a signed 32-bit integer stops at 2147483647 and a 32-bit build answers 1497128983/1982909216. Note what does not overflow: n = 20 gives 55835135/15519504, and both of those fit 32 bits, so a 32-bit build answers n = 20 correctly. The declared tests say which is which rather than claiming every large case breaks.

In JavaScript the final numerator is below 2^53, but the intermediate num * step reaches about 8 * 10^16, which is not, so BigInt is still required.

## Cost

O(n log n).

Constraints - `1 ≤ n ≤ 40`