9 replies to this topic

[lomateron]

I have this relation of numbers
0 - 1 ---> 0
1 - 2 ---> 1
0 - 2 ---> 2
2 - 3 ---> 3
1 - 3 ---> 4
0 - 3 ---> 5
3 - 4 ---> 6
2 - 4 ---> 7
1 - 4 ---> 8
0 - 4 ---> 9
4 - 5 ---> 10
3 - 5 ---> 11
2 - 5 ---> 12
1 - 5 ---> 13
0 - 5 ---> 14
...
...
...

Finally
a - b ---> x
so i want an equation were i put the values 'a' and 'b' and it gets me x, I know how to solve this using loops but i am dealing with x numbers of 500,000 so my loop will have to do 500,000 loops and you know that's not good.
I can't find the recurrence relation too.

Edited by lomateron, 16 October 2012 - 08:43 AM.

[Álvaro]

x = b*(b+1)/2 -a -1;

[lomateron]

SOLVED:
Having 'a' and 'b', I compare who is the biggest, then I put the biggest in the equation (n^2+n)/2=h
then i take h put it in this other equation: h-'the smallest between and b'-1 = x
thats all.

[lomateron]

Alvaro i am curious of how you solved it, i was posting my solution when you posted yours.

Edited by lomateron, 16 October 2012 - 09:22 AM.

[Álvaro]

Let's call F(a,b) = x. I put your examples into a table, I observed that F(n-1,n) are triangular numbers, and it was simple manipulation from there. I verified the result with this command line:

> perl -e 'for ($b=1; $b<6; ++$b) {for ($a=$b-1; $a>=0; $a--){$x = $b*($b+1)/2-$a-1; print "$a - $b ---> $x\n"}}'
0 - 1 ---> 0
1 - 2 ---> 1
0 - 2 ---> 2
2 - 3 ---> 3
1 - 3 ---> 4
0 - 3 ---> 5
3 - 4 ---> 6
2 - 4 ---> 7
1 - 4 ---> 8
0 - 4 ---> 9
4 - 5 ---> 10
3 - 5 ---> 11
2 - 5 ---> 12
1 - 5 ---> 13
0 - 5 ---> 14

Edited by alvaro, 16 October 2012 - 09:32 AM.

[Emergent]

Hah! So now we all know how to index upper-triangular matrices. Or store edge weights for undirected graphs. Same difference. :-)

[lomateron]

now i wanna know the opposite way, now i have "x" and i want "a" and "b"

I have a solution, want to know if there is a faster way

 

v=sqrt(2*(x+1)-0.25)+0.5

take out the decimals of that "v" and its the correct "b"

a= (b*(b+1)/2) - (x+1)

Edited by lomateron, 18 February 2013 - 07:09 AM.

[Álvaro]

Nevermind, I am not sure of what I wrote. I'll check more carefully before posting again.

Edited by Álvaro, 17 February 2013 - 09:20 PM.

[lomateron]

I edited my last post thinking i was wrong, now i want to know what it says

[Álvaro]

I edited my last post thinking i was wrong, now i want to know what it says

There is a `History' button below the post. Doesn't that work?