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

One fact you can make use of is that each triplet in the sequence will have an R, G or B value only one greater than a triplet that has already been output.

So, you could maintain a BinaryHeap (sorted by luminance) containing all the triplets that are 1 greater in R, G or B than a triplet that has already been output, and do this in a loop:

• Remove the smallest element (r, g, b) from the heap
• Output it
• Add (r+1, g, b), (r, g+1, b) and (r, g, b+1) to the heap, but only if they are valid triplets (all values less than or equal to 255), and only if they are not already in the heap. A triplet will not already be in the heap if the alternative triplets that it could have been generated from (1 less in either r, g, or b, within allowed bounds) have a higher luminance than (r, g, b).

For example only add (r+1, g, b) if (r+1, g-1, b) has a higher luminance than (r, g, b) or (r+1, g-1, b) is invalid. Since the factors for computing luminance based on r, g, b are fixed, (r+1, g-1, b) will always have a lower luminance, and you should only add (r+1, g, b) if (r+1, g-1, b) is invalid, which is when g is 0.

In pseudo-code the rules are like this:

function addTriplets(r, g, b)
{
    if(g < 255)
       pushTripletToHeap(r, g + 1, b);
    if((g == 0) && (r < 255))
       pushTripletToHeap(r + 1, g, b);
    if((g == 0) && (r == 0) && (b < 255))
       pushTripletToHeap(r, g, b + 1);
}

Push the (0, 0, 0) triplet onto the heap before starting the loop and stop the loop when the heap is empty.

Answer 2

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

Answer 3

Sorry but i have to say that you are doing some wasteful work.

8 bit quantization of RGB would yield 16.7M colors at 256 luminance levels (black and white included) However you haven't got enough pixels to display them all on a 4K monitor which would have like 3840 x 2160 = 8294400 pixels on 4K TV standard or like 4096 x 2160 = 8847360 on 4K movie standard. Besides what's the meaning of 1 pixel color sample to an eye especially on 4K display..?

I would recommend you to use 7 bits quantization instead of 8 bits. This will give you 2^21 => 2097152 color samples and they will be mapped as single pixel on an HD monitor/TV and 2x2 pixels on a 4K monitor/TV. Beautiful.

The code would be as follows;

"use strict";
var allColors = Array(Math.pow(2,21)),           // All 2^21 colors
         cgbl = Array(128).fill().map(e => []);  // Colors gropuped by luminance
for (var i = 0, len = allColors.length; i < len; i++) allColors[i] = [i>>14, (i&16256)>>7, i&127];
allColors.reduce((g,c) => (g[Math.round(c[0]*0.2126 + c[1]*0.7152 + c[2]*0.0722)].push(c),g), cgbl);
cgbl.forEach((y,i) => console.log(y.length,"Colors at luminance level:",i));

However remember that your RGB values are now in 7 bit quantization. Since we have already grouped them into 128 luminance levels I would also advise you to map each RGB values in the luminance groups (sub arrays) back into 8 bits by shifting their values left by 1 bit (r << 1; g << 1; b << 1;) before displaying them. By using the .map() functor it's a trivial job.

Answer 4

Because my original answer is already long, I'm making this answer to clarify the algorithm, as OP has requested

Let's consider a similar problem (but easier to reason about):

• Let A the set of numbers, in ascending order, which have no other prime factor than 2, 3 and 5 (Ai = 2^x * 3^y * 5^z)
• Find the n-th number of A

Sure A1 = 1 = 2^0 * 3^0 * 5^0

Let's assume at some step, we have calculated A1..An and we need to find A[n+1]

• If A[n+1] is divisible by 2, then A[n+1] = A[i2]*2 with 1 <= i2 <= n
• If A[n+1] is divisible by 3, then A[n+1] = A[i3]*3 with 1 <= i3 <= n
• If A[n+1] is divisible by 5, then A[n+1] = A[i5]*5 with 1 <= i5 <= n

(and obviously A[n+1] is divisible by at least one of those)

Proof: A[n+1] = 2^x * 3^y * 5^z. If A[n+1] is divisible by 2 then x > 0, so B = A[n+1]/2 = 2^(x-1) * 3^y * 5^z must be in A. And because B < A[n+1], it must come before A[n+1] in A, so B = A[i2], with 1 <= i2 <= n.

So to find A[n+1], we can:

• Find the minimum i2 that A[i2]*2 > A[n]
• Similar for i3 and i5
• ==> A[n+1] = min(A[i2]*2, A[i3]*3, A[i5]*5)

Having A1 = 1, run these steps (n - 1) times and we find the n-th number of A

Now, if at every iteration finding A[n+1], we use 3 for loops from 1 to n to calculate i2, i3 and i5, the time complexity would be O(N^2). But you can see i2, i3 and i5 for each iteration never decrease ( be less than those value for previous iteration, respectively ). So we can save those i2, i3 and i5 values, and at each iteration we just need to:

while (A[i2]*2 <= A[n]) ++i2;
while (A[i3]*3 <= A[n]) ++i3;
while (A[i5]*5 <= A[n]) ++i5;

Now the time complexity becomes O(N): while the while loops are still nested in the main for 1->n loop, there are only 4 variables increasing from 1 -> n, and can be considered 4 independent loops. You can verify the O(N) property by using a clock and measure the run time for different N s

Applying this algorithm to your problem:

• 2, 3 and 5 becomes R, G and B
• Integer comparison becomes a color comparison function you define
• If you need to list all 2^24 colors, define the comparison function so that no 2 different colors are "equal" (if C1 and C2 are 2 different colors then either C1 < C2 or C2 < C1) - like I did in the original answer