Prime Factorization

2018-09-08

This visualization is inspired by the works of Stephen Von Worley, which in turn is based on the original factorization diagrams idea by Brent Yorgey. Primes are visualized by a single unique pattern (circle) while non-primes are visualized by groups of prime patterns.

1

Intuition for Viz

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime itself or a product of prime numbers.1

The fundamental theorem of arithemetic is the basis for this visualization. Given a number n, we are guaranteed an array of prime factors [p1, p2, p3, ... pn], which we use for iteratively rendering subgroups of points in the visualization.

An implementation for getPrimeFactors could look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Return array of prime factors (in ascending order) of n.
 *
 * Examples:
 *  getPrimeFactors(1) // []
 *  getPrimeFactors(10) // [5, 2]
 *  getPrimeFactors(5) // [5]
 *  getPrimeFactors(60) // [5, 3, 2, 2]
 *  getPrimeFactors(120) // [5, 3, 2, 2, 2]
 *  getPrimeFactors(240) // [5, 3, 2, 2, 2, 2]
 */
const getPrimeFactors = memoize(n => {
  const result = [];
  while (n > 1) {
    const factor = getPrimeFactor(n);
    result.push(factor);
    n /= factor;
  }
  return result.reverse();
});

/**
 * Return smallest prime factor of n.
 */
const getPrimeFactor = memoize(n => {
  if (n % 2 === 0) {
    return 2;
  }
  for (let i = 3; i <= Math.floor(Math.sqrt(n)); i += 2) {
    if (n % i === 0) {
      return i;
    }
  }
  return n;
});

For example, getPrimeFactors(120) returns an array of prime factors [5, 3, 2, 2, 2]. If we set the number in the viz to be 120, we notice that the outer patterns are nested inwards with an ordering of 5, 3, 4 and 2. This is very similar to the prime factorization of 120 with the observation that we try to merge consequetive groups of 2 into of 4, which leads to a more aesthetically pleasing distribution of points.

We can implement a simple method mergePrimeFactors that receives an array of prime factors and merges 2 into 4 whenever possible:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Merge consequtive '2's into '4' to support better visualization of points
 * Examples:
 *  mergePrimeFactors([2, 2, 2, 2]) // [4, 4]
 *  mergePrimeFactors([2, 4, 4, 2]) // [2, 4, 4, 2]
 *  mergePrimeFactors([2, 2, 2, 4]) // [4, 2, 4]
 */
const mergePrimeFactors = primeFactors => {
  return primeFactors.reduce((a, x) => {
    const last = a.length - 1;
    if (a[last] === 2 && x === 2) {
      a[last] = 4;
      return a;
    }
    return [...a, x];
  }, []);
};

Feel free to pause the viz and plug in some of the interesting numbers provided above to study their respective prime factorization diagrams, or browse through the d3 source code for details of the implementation.