New: 201 pattern programs with tested code in C, C++, Java and Python Explore patterns

Leibniz Harmonic Triangle

Read summary with AI tools

The Leibniz harmonic triangle is a triangle of fractions. The edges are 1, 1/2, 1/3, 1/4, 1/5, and each fraction equals the sum of the two fractions below it, which is Pascal’s rule turned upside down.

Quick answer: Every entry has 1 on top, so only the bottom number has to be worked out: the denominator in row i, position j (from 0) is (i + 1) × C(i, j), where C is the binomial coefficient from Pascal’s triangle. Build C with c = c × (i − j) / (j + 1), print 1 or 1/den, and move on.

This program is part of the Series Patterns collection.

Table of contents8 sections
  1. Output
  2. How the leibniz harmonic triangle works
  3. Program in C
  4. Program in C++
  5. Program in Java
  6. Program in Python
  7. Time and space complexity
  8. Frequently asked questions

Leibniz Harmonic Triangle output

Output (n = 5):

1
1/2 1/2
1/3 1/6 1/3
1/4 1/12 1/12 1/4
1/5 1/20 1/30 1/20 1/5
Leibniz Harmonic Triangle layout diagram, row by row (n = 5)
The fractions of the leibniz harmonic triangle laid out row by row (n = 5).

How the leibniz harmonic triangle works

The German mathematician Gottfried Leibniz used this triangle in the 1670s to add up series of fractions. Its link with Pascal’s triangle makes the code short: take row i of Pascal’s triangle, multiply every number by i + 1, and put each result under a 1. The program creates the binomial coefficients one after another with the same update used for Pascal’s triangle, so it never needs factorials.

  1. Run the outer loop for i from 0 to n − 1.
  2. Set c = 1, which is C(i, 0).
  3. For j from 0 to i: work out den = (i + 1) × c; print 1 if den is 1, otherwise 1/den; then update c = c × (i − j) / (j + 1).
  4. Move to the next line.

Key takeaways

  • Every entry is a unit fraction, so the program only computes denominators.
  • The denominators are Pascal’s numbers times i + 1.
  • Each fraction is the sum of the two below it: 1/2 = 1/3 + 1/6.
  • Multiplying before dividing in the update keeps c a whole number at every step.

Leibniz Harmonic Triangle in C

#include <stdio.h>

int main(void) {
    int n = 5;

    for (int i = 0; i < n; i++) {
        int c = 1;                         /* C(i, j), starting with C(i, 0) */
        for (int j = 0; j <= i; j++) {
            int den = (i + 1) * c;
            if (den == 1)
                printf("1 ");
            else
                printf("1/%d ", den);
            c = c * (i - j) / (j + 1);
        }
        printf("\n");
    }
    return 0;
}

Leibniz Harmonic Triangle in C++

#include <iostream>
using namespace std;

int main() {
    int n = 5;

    for (int i = 0; i < n; i++) {
        int c = 1;                         // C(i, j), starting with C(i, 0)
        for (int j = 0; j <= i; j++) {
            int den = (i + 1) * c;
            if (den == 1)
                cout << "1 ";
            else
                cout << "1/" << den << " ";
            c = c * (i - j) / (j + 1);
        }
        cout << endl;
    }
    return 0;
}

Leibniz Harmonic Triangle in Java

public class LeibnizHarmonicTriangle {
    public static void main(String[] args) {
        int n = 5;

        for (int i = 0; i < n; i++) {
            int c = 1;                         // C(i, j), starting with C(i, 0)
            for (int j = 0; j <= i; j++) {
                int den = (i + 1) * c;
                if (den == 1)
                    System.out.print("1 ");
                else
                    System.out.print("1/" + den + " ");
                c = c * (i - j) / (j + 1);
            }
            System.out.println();
        }
    }
}

Leibniz Harmonic Triangle in Python

n = 5

for i in range(n):
    c = 1                              # C(i, j), starting with C(i, 0)
    for j in range(i + 1):
        den = (i + 1) * c
        print("1" if den == 1 else f"1/{den}", end=" ")
        c = c * (i - j) // (j + 1)
    print()

Time and space complexity

Each fraction costs a few multiplications and one division, so the program runs in O(n²) time with O(1) extra memory.

Frequently asked questions

How can 1/2 equal 1/3 + 1/6?

Put both on a denominator of 6: 1/3 = 2/6, and 2/6 + 1/6 = 3/6 = 1/2. Every entry in the triangle works the same way with the two entries directly below it.

Why not print the fractions as decimals?

Most of them repeat forever: 1/3 is 0.333…, 1/6 is 0.1666…. Printing 1/den keeps the values exact and makes the pattern easier to see.

How far can the triangle go?

The largest denominator in row i is in the middle, and it grows quickly. With int the program is safe for about 15 rows; with a 64-bit type it goes much further.

Authored by

Ghanendra Yadav runs Pattern Programs from Bangalore, India. The site started in 2020 to help students practise loops and logic through pattern programs in C, C++, Java and Python. Every program published here is compiled and run before it goes live, and the output shown is the real output.

Latest articles

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.