CODEWITHSUNDEEP
algorithmmath
douggard
douggard

Reputation: 712

Mathematical Formula For Generating Incresing Sequences

I have two lookup tables that I would like to eliminate with simple math if possible.

The first is a map from indices in an array to the sequence {0} => 1, {1, 2} => 2, {3, 4, 5} => 3, s.t. there is one 1, two 2s, three 3s, etc. Or visually: 

lookup1[N] = { 
    1,
    2, 2,
    3, 3, 3,
    4, 4, 4, 4,
    5, 5, 5, 5, 5,
    6, 6, 6, 6, 6, 6,
    7, 7, 7, 7, 7, 7, 7,
    8, 8, 8, 8, 8, 8, 8, 8,
    ...
}

The second is for increasing sequences, the first sequence is (1), the second (1, 2), the third (1, 2, 3). It's like a modulus cycle, but increasing after each cycle. Visually:

lookup2[N] = {
    1,
    1, 2,
    1, 2, 3,
    1, 2, 3, 4,
    1, 2, 3, 4, 5,
    1, 2, 3, 4, 5, 6,
    1, 2, 3, 4, 5, 6, 7,
    1, 2, 3, 4, 5, 6, 7, 8,
    1, 2, 3, 4, 5, 6, 7, 8, 9,
    ...
}

These need to map from indices. For the second lookup, inputs 5, 4, 3 would map to 3, 2, 1 respectively.

Are there any mathematical formulas that would produce these patterns? I would rather execute a few instructions than do a memory access.

Upvotes: 1

Views: 113

Answers (1)

Salix alba
Salix alba

Reputation: 7824

For lookup1 this looks closely related to Triangular numbers, infact it is the inverse problem. The triangles numbers are the number of items in a triangle with n rows. So you have T1 = 1, T2 = 1+2 = 3, T3 = 1+2+3 = 6, T4 = 1+2+3+4 = 10. Or as a function f(1) = 1, f(2)=3, f(3)=6, f(4)=10.

You want to do the inverse so g(1) = 1, g(3) = 2, g(6) = 3, g(10) = 4. We worry about other values later.

There is a formula for the triangular numbers f(n) = n (n+1) / 2. And a more complex one for the inverse

g(n) = (sqrt(8 * n + 1) - 1) / 2

A little experiment shows that

ceil((sqrt(8*n+1) - 1) / 2 )

gives your desired numbers.

For the second part you can use the function for the inverse triangular number and then find the previous triangular number, and take the difference

X =  ceil((sqrt(8*n+1) - 1) / 2);
T = (X * (X-1))/2 ; 
print(n-T);

A slight cautionary note. At the transition points sqrt(8*n+1) should evaluate to an odd integer value. What might happen for very large n is than rounding errors might pay a part. I've tested this to well over a million and not seen the problem occur.

Upvotes: 3

Related Questions