Find sequential smallest sums of the multiples of three different numbers, javascript

Question

On this post I found an algorithm to determine the luminance of an RGB color:

Luminance (standard for certain colour spaces): (0.2126*R + 0.7152*G + 0.0722*B)

I want to use this equation, starting at rgb(0,0,0), to generate all RGB colors in order from lowest to highest luminance and then draw them to a 4096x4096 canvas.

My issue is that with 16.7 million different combinations I can't generate them all and then sort them without either crashing my browser or taking multiple days to complete the render. So I want to find a way to find the multiples of each number that will summate to the next lowest number.

For instance, starting at and rgb of 0,0,0, the luminance would be 0 (0.2126*0 + 0.7152*0 + 0.0722*0 = 0), the next least luminescent rgb value would be 0,0,1 because 0.2126*0 + 0.7152*0 + 0.0722*1 = .0722, and there's no set of multiples that would summate to a smaller number.

The first 19 sequential luminance values would be as follows (I may have missed one or two, because I calculated them manually, but hopefully it helps to make the point):

RGB       =>     Luminence

0,0,0     =>     0
0,0,1     =>     .0722
0,0,2     =>     .1444
1,0,0     =>     .2126
0,0,3     =>     .2166
1,0,1     =>     .2848
0,0,4     =>     .2888
1,0,2     =>     .357
0,0,5     =>     .361
2,0,0     =>     .4252
1,0,3     =>     .4292
0,0,6     =>     .4332
2,0,1     =>     .4974
1,0,4     =>     .5014
0,0,7     =>     .5054
2,0,2     =>     .5696
1,0,5     =>     .5736
0,0,8     =>     .5776
3,0,0     =>     .6378

I can't seem to find any pattern so I was hoping that maybe there was an equation or a coding trick out there that would allow me to find the smallest sum, higher than the previous sum, of the multiples of three numbers, without brute forcing it and checking every possible value.

EDIT: I Did some extra research and it looks like the solution may lie in using linear diophantine equations. If I take each decimal and multiply by 1000, to get 2126, 7152, & 722. Then count 1-by-1 up to 2,550,000 (2126*255 + 7152*255 + 722*255), I can check each number to see if it's a solution to the equation 2126r + 7152g + 722b = n, where n is the current number counted to, and r, g, & b are unknowns. If I could do this, I could figure out all possible rgb values at the next sequential luminance value, without even having to double over any values for duplicate luminance values and I'd only have to do 2.55 million calculations instead of 16.77+ million (one for each color). If anyone has any idea how to code this equation, or if anyone has any better solution, I'd be extremely grateful. Thanks!

Answer 1

Here's an algorithm (have forgotten its name) for your problem: The algorithm can list all color tuples {R,G,B} sorted in some order. In your case it's by luminance ascending: color1 < color2 <==> f(color1) < f(color2), where f(color) = 0.2126*R + 0.7152*G + 0.0722*B

• Initialize: arr = [{r:0, g:0, b:0}] (the minimum color)
• Repeat:
  • Select min(iR): a[iR] = {rR < 255, gR, bR}, and cR = {rR + 1, gR, bR} > arr[i] for every i. (Select the first color in arr such that if we add 1 to its r component, we get a new color that is greater than every colors currently in arr)
  • Similar for iG and iB => also get cG = {rG, gG + 1, bG} and cB = {rB, gB, bB + 1}
  • Among cR, cG and cB select the minimum color c
  • Append c to the array arr

The algorithm stops when no such iR, iG, or iB could be found.

Notes:

• arr is always in sorted (ascending) order, because every time a new color is appended to arr, it is always greater than every elements currently in arr.
• Because arr is in ascending order, we only have to compare cR/cG/cB with the last element of arr to check if it's greater than every elements of arr
• iR, iG and iB increase through out the algorithm
• The complexity is O(N) with N the number of colors (2^24) ~ 16M. With heap-based algorithm the complexity is about O(NlogN).

Here is my implementation (Tested in nodejs 6)

//  use integer to avoid floating point inaccuracy
const lumixOf = {r: 2126, g: 7152, b: 722};

const maxValue = 256;
const components = ['r', 'g', 'b'];

class Color {
  constructor(r, g, b, lum) { 
    this.r = r;
    this.g = g;
    this.b = b;
    this.lum = lum;
  }

  add(component) { 
    const ans = new Color(this.r, this.g, this.b, this.lum);
    if (++ans[component] >= maxValue) return null; // exceed 255
    ans.lum += lumixOf[component];
    return ans;
  }

  greater(color2) {
    // return this.lum > color2.lum;
    if (this.lum !== color2.lum) return this.lum > color2.lum;
    if (this.r !== color2.r) return this.r > color2.r;
    if (this.g !== color2.g) return this.g > color2.g;
    return this.b > color2.b;        
  }
}

let a = [new Color(0, 0, 0, 0)];  //  R, G, B, lumix
let index = {r: 0, g: 0, b: 0};

console.log('#0:', a[0]);
// Test: print the first 100 colors
for (let count = 1; count < 100; ++count) {
  let nextColor = null;
  const len = a.length;
  const currentColor = a[len - 1];
  components.forEach(component => {
    let cIndex = index[component];
    for (; cIndex < len; ++cIndex) {
      const newColor = a[cIndex].add(component);
      if (!newColor || !newColor.greater(currentColor)) continue;

      //  find the minimum next color
      if (nextColor == null || nextColor.greater(newColor)) {
        nextColor = newColor;
      }
      break;
    }
    index[component] = cIndex;
  });

  if (!nextColor) break;  //  done. No more color
  a.push(nextColor);
  console.log('#' + count + ':', nextColor);
}
console.log(a.length);

This implementation list all 2^24 = 16777216 colors (once you remove the count < 100 condition in the main loop, but you wouldn't want to print out so many lines). If some colors have the same luminance value, they are then sorted by their R value, then G value, then B value. If you just need one color for each luminance value, uncomment the first line in greater() function - then you get 1207615 colors with distinct luminance