Nice Vectors

2025-12-10. Filed in public, math.

I wanted to be nice this semester in computer graphics. In my exercises, I ask students to do a lot of 3D vector math. These vectors must often be normalized, which means their magnitude is 1:

$$\begin{align} \sqrt{a^2 + b^2 + c^2} &= 1 \\ \end{align}$$

If that's the case, so is their squared magnitude:

$$\begin{align} a^2 + b^2 + c^2 &= 1 \\ \end{align}$$

I needed vectors for which this equation is true, but I didn't want to have a lot of digits in \(a\), \(b\), and \(c\). The more digits, the greater the chance for transcription and roundoff errors. If we lose some of those digits, the vectors lose their normality.

One way to generate nice vectors is to guess short values for \(a\), \(b\), and \(c\) and see if they satisfy the magnitude equation. But this is scattershot. Suppose I choose \(a = 0.5\) and \(b = 0.6\). Then I end up with \(c \approx 0.6244997998398398\), which is not nice at all.

I decided instead to iterate through all triplets of integers of a small magnitude, plug them into the equation, and keep the good ones. For instance, all single-digit triplets would have \(1 \leq a, b, c \leq 9\). These integers need to be normalized when plugging them in:

$$\begin{align} 1 &= \left(\frac{a}{10}\right)^2 + \left(\frac{b}{10}\right)^2 + \left(\frac{c}{10}\right)^2 \\ \end{align}$$

We can manipulate the equation to stick with integers throughout. For single-digit numbers, this is the equation we need to satisfy:

$$\begin{align} 1 &= \frac{a^2}{100} + \frac{b^2}{100} + \frac{c^2}{100} \\ 100 &= a^2 + b^2 + c^2 \\ \end{align}$$

As it turns out, there are no integer triplets that satisfy this equation. For two-digit numbers, this is the equation we need to satisfy:

$$\begin{align} 1 &= \left(\frac{a}{100}\right)^2 + \left(\frac{b}{100}\right)^2 + \left(\frac{c}{100}\right)^2 \\ &= \frac{a^2}{10000} + \frac{b^2}{10000} + \frac{c^2}{10000} \\ 10000 &= a^2 + b^2 + c^2 \\ \end{align}$$

Exactly two vectors satisfy this equation. In normalized form, they are \([0.36, 0.48, 0.8]\) and \([0.48, 0.6, 0.64]\). Those are nice and tidy. But there are only two of them. To get more, I needed some code to generate all possible triplets with an arbitrary number of digits. This just felt like a job for Haskell. Here was my first draft solution:

Haskell
magnitudeTriplets :: Int -> [[Int]]
magnitudeTriplets digitCount = roots
  where
    -- For 1 digit, the divisor is 10. For 2, 100.
    -- For 3, 1000. But we really need its square.
    divisor = 10 ^ digitCount
    divisor2 = divisor ^ 2

    -- What values can a^2, b^2, and c^2 take on?
    -- Any perfect square less than divisor2.
    squares = takeWhile (< divisor2) perfectSquares

    -- Let's find all possible 3-combinations of
    -- these squares and filter out the ones that
    -- sum to divisor2.
    triplets = combos 3 squares
    matches = sumTriplets divisor2 triplets

    -- Turn each [a^2, b^2, c^2] into [a, b, c].
    roots = map (map sqrtFloor) matches
magnitudeTriplets :: Int -> [[Int]]
magnitudeTriplets digitCount = roots
  where
    -- For 1 digit, the divisor is 10. For 2, 100.
    -- For 3, 1000. But we really need its square.
    divisor = 10 ^ digitCount
    divisor2 = divisor ^ 2

    -- What values can a^2, b^2, and c^2 take on?
    -- Any perfect square less than divisor2.
    squares = takeWhile (< divisor2) perfectSquares

    -- Let's find all possible 3-combinations of
    -- these squares and filter out the ones that
    -- sum to divisor2.
    triplets = combos 3 squares
    matches = sumTriplets divisor2 triplets

    -- Turn each [a^2, b^2, c^2] into [a, b, c].
    roots = map (map sqrtFloor) matches

This function relies on the utilities below. Haskell probably has some module that can generate combinations, but I enjoy writing these.

Haskell
-- [1, 4, 9, 16, 25, ...]
perfectSquares = map (^ 2) [1..]

-- Select all the triplets that sum to the target n.
-- For example:
--   sumTriplets 100 [(36, 48, 80), (30, 40, 50)] == [(36, 48, 80)]
sumTriplets n triplets = filter ((n ==) . sum) triplets

-- Find all the n-combinations of a list. Take each element
-- and prepend it on all the (n - 1)-combinations of its
-- successors. For example:
--   combos 1 [1, 2, 3] = [[1], [2], [3]]
--   combos 3 [1, 2, 3, 4] == [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
combos 0 _ = []
combos 1 xs = map singleton xs
combos _ [] = []
combos n (x : xs) = map (x :) (combos (n - 1) xs) ++ combos n xs

-- Compute the integral floor of the square root of
-- a number. For example:
--   sqrtFloor 25 == 5
--   sqrtFloor 103 == 10
sqrtFloor :: Int -> Int
sqrtFloor = floor . sqrt . fromIntegral
-- [1, 4, 9, 16, 25, ...]
perfectSquares = map (^ 2) [1..]

-- Select all the triplets that sum to the target n.
-- For example:
--   sumTriplets 100 [(36, 48, 80), (30, 40, 50)] == [(36, 48, 80)]
sumTriplets n triplets = filter ((n ==) . sum) triplets

-- Find all the n-combinations of a list. Take each element
-- and prepend it on all the (n - 1)-combinations of its
-- successors. For example:
--   combos 1 [1, 2, 3] = [[1], [2], [3]]
--   combos 3 [1, 2, 3, 4] == [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
combos 0 _ = []
combos 1 xs = map singleton xs
combos _ [] = []
combos n (x : xs) = map (x :) (combos (n - 1) xs) ++ combos n xs

-- Compute the integral floor of the square root of
-- a number. For example:
--   sqrtFloor 25 == 5
--   sqrtFloor 103 == 10
sqrtFloor :: Int -> Int
sqrtFloor = floor . sqrt . fromIntegral

Unfortunately, this strategy is really slow. We are generating all possible triplets, making this an \(O(n^3)\) algorithm, where \(n\) is the number of possible values of each component. With 3 digits, \(n = 1000\) and \(n^3 = 1,000,000,000\).

A faster stategy is to generate all possible combinations of just \(a\) and \(b\). That's an \(O(n^2)\) algorithm. For each combination, we calculate \(c\) to satisfy the magnitude equation. If \(c\) is an integer, then we found a triplet. This solution runs much faster:

Haskell
magnitudeTriplets :: Int -> [[Int]]
magnitudeTriplets digitCount = foldr mix [] pairs
  where
    divisor = 10 ^ digitCount
    divisor2 = divisor * divisor
    squares = takeWhile (< divisor2) perfectSquares
    pairs = combos 2 squares
    mix ([a, b]) accum
      | c > b && isSquare c = [sqrtFloor a, sqrtFloor b, sqrtFloor c] : accum
      | otherwise = accum
      where
        c = divisor2 - a - b
magnitudeTriplets :: Int -> [[Int]]
magnitudeTriplets digitCount = foldr mix [] pairs
  where
    divisor = 10 ^ digitCount
    divisor2 = divisor * divisor
    squares = takeWhile (< divisor2) perfectSquares
    pairs = combos 2 squares
    mix ([a, b]) accum
      | c > b && isSquare c = [sqrtFloor a, sqrtFloor b, sqrtFloor c] : accum
      | otherwise = accum
      where
        c = divisor2 - a - b

Our combination generator yields combinations that are in sorted order, like \([48, 60, 64]\). Since c is derived separately, we add in the c > b check. Without it, we get vectors like \([36, 80, 48]\). This is a duplicate of \([36, 48, 80]\), which we will also generate. We don't need both.

We need one additional utility to check if \(c\) is a square:

Haskell
-- Determine whether a number is a square. For example:
--   isSquare 36 == true
--   isSquare 42 == false
isSquare :: Int -> Bool
isSquare x = (sqrtFloor x) ^ 2 == x
-- Determine whether a number is a square. For example:
--   isSquare 36 == true
--   isSquare 42 == false
isSquare :: Int -> Bool
isSquare x = (sqrtFloor x) ^ 2 == x

This new function finds these 14 vectors with 3-digit components:

And these 76 vectors with 4-digit components:

There are 388 normalized vectors with 5-digit components. I won't list them here.

The faster version of magnitudeTriplets takes 11 seconds on my MacBook Pro to find the vectors with 4-digit components. I gave up on the slower solution after five minutes.