wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Triangle Test
        
(Message started by: Sir Col on Sep 7th, 2003, 11:25am)
Title: Triangle Test
Post by Sir Col on Sep 7th, 2003, 11:25am
Given a number, N, what is the most efficient way to test if it is a triangle number?
Title: Re: Triangle Test
Post by towr on Sep 7th, 2003, 1:05pm
the best I can do on short notice is
[hide]floor([sqrt](2*N)) * (floor([sqrt](2*N)) +1) == 2*N[/hide]
Title: Re: Triangle Test
Post by Sir Col on Sep 7th, 2003, 1:24pm
That is very clever, towr, and I know that you said you did it on short notice, but I believe there is a more efficient way. One which I found very interesting, in that it is both a necessary and sufficient condition.
Title: Re: Triangle Test
Post by Icarus on Sep 7th, 2003, 2:06pm
I came up with [hide]8N+1 is a perfect square[/hide].

This comes from [hide]Applying the quadratic formula to the equation n(n+1) = 2N, and figuring out what it required for n to be an integer.[/hide]
Title: Re: Triangle Test
Post by towr on Sep 7th, 2003, 2:17pm
What kind of efficiency are we looking for? CPU-cycle wise?

And how long does it take to check if something is a perfect square?
floor([sqrt]x)2==x costs 5 operations
and [sqrt]x - floor([sqrt]x) > 0 still costs 4
putting the total at 6 operations, like mine (storing in variables can be done in the same cycle as calculating it if I recall correctly)
Title: Re: Triangle Test
Post by Sameer on Sep 8th, 2003, 8:37am
what is a triangle number? ???
Title: Re: Triangle Test
Post by Sir Col on Sep 8th, 2003, 8:44am
The sequence 1, 3, 6, 10, 15, ..., defined by tn=n(n+1)/2, or the recrurrence relation, tn=tn-1+n: 1, 3=1+2, 6=3+3, 10=6+4, 15=10+5, ...

They are called triangle numbers because it is possible to form triangle shapes with 1, 3, 6, 10, ... blocks:

o

o
oo

o
oo
ooo

o
oo
ooo
oooo


Familiar contexts would be the arrangement of (the fifteen) balls on a pool table, or, of course, 10-pin bowling
Title: Re: Triangle Test
Post by towr on Sep 8th, 2003, 11:58am
In general, if there's ever a mathematical term anyone here uses which is confusing, you can try looking it up at www.mathworld.com
(it allways helps me)
Title: Re: Triangle Test
Post by Sir Col on Sep 8th, 2003, 12:34pm
Good idea, towr. I keep forgetting about that excellent resource.

If we count the operation efficiency during the decision phase for towr's and Icarus' methods using the pseudo code...
::[hide]
towr:
a=2*N [1]
b=sqrt(a) [1]
c=floor(b)*floor(b+1) [4]
if ( c==a ) then print "triangle!" [1] ignoring output as an operation
total operations = 7

Icarus:
a=sqrt(8*N+1) [3]
if ( a==int(a) ) then print "triangle!" [2]
total operations = 5

Having said, that I am still impresed with your original approach, towr.
[/hide]::

I used your approach, Icarus, which leads on to the next challenge which I hinted at on my 2nd post...

Prove that 8N+1 is a perfect square iff (if and only if) N is a triangle number.
Title: Re: Triangle Test
Post by towr on Sep 8th, 2003, 1:10pm

on 09/08/03 at 12:34:56, Sir Col wrote:
If we count the operation efficiency during the decision phase for towr's and Icarus' methods using the pseudo code...
towr:
<snip>
total operations = 7

hardly fair to use floor twice when it's not needed, floor(a+1) = floor(a) +1, and we allready had floor(a).

So as I said, 6

Depending on the chip there may also be differences per operation. Possibly *8 can be substituted for  << 3 and *2 by << 1 in the same cycle as another calculation (so both take 1 operation instead of two), and +1, or rather ++ might also be done in the same operation.
But overall Icarus' solution is probably faster.
Title: Re: Triangle Test
Post by Sir Col on Sep 8th, 2003, 1:25pm

on 09/08/03 at 13:10:18, towr wrote:
hardly fair to use floor twice when it's not needed, floor(a+1) = floor(a) +1, and we allready had floor(a).

Silly me, sorry about that!  :-[

So how about the proof... ?
Quote:
Prove that 8N+1 is a perfect square iff (if and only if) N is a triangle number.
Title: Re: Triangle Test
Post by wowbagger on Sep 8th, 2003, 1:42pm

on 09/08/03 at 12:34:56, Sir Col wrote:
Prove that 8N+1 is a perfect square iff (if and only if) N is a triangle number.

Er, [hide]8N+1 = 4n(n+1)+1 = 4n2+4n+1 = (2n+1)2[/hide].
Well, at least one implication is obvious.
Title: Re: Triangle Test
Post by Sir Col on Sep 8th, 2003, 1:47pm
Okay, you've done half the proof (if): you've shown that if N is a triangle number then 8N+1 is a perfect square. Now you need to do the other half (only if): show that if 8N+1 is a perfect square, then N is a triangle number.
Title: Re: Triangle Test
Post by Icarus on Sep 8th, 2003, 3:47pm
I'm sorry. I thought the brief description I gave was sufficient to see the relation both ways:
For n >=0,

n = ([sqrt](8N+1) - 1)/2 iff
(2n+1)[sup2] = 8N+1 iff
4n[sup2] + 4n = 8N iff
n(n+1)/2 = N

Thus N is a triangular number iff n is an integer iff 8N+1 is a perfect square.

As for my solution vs Towr's. I was not thinking in terms of computer efficiency when I gave mine.
Title: Re: Triangle Test
Post by Sameer on Sep 8th, 2003, 3:51pm
I agree a computer chip's architecture will be the deciding factor in the efficiency part. So Sir Col has to decide which processor we are using and then we will come up with an efficient algorithm  ;D
Title: Re: Triangle Test
Post by Sir Col on Sep 8th, 2003, 4:01pm
Certainly applying the quadratic formula to N=n(n+1)/2 tells us that 8N+1 must be a perfect square, but does it guarantee that for all perfect squares of the form 8N+1, N will be a triangle numbers?

Anyway, your demonstration in the last post was very slick.

For your information, I stumbled on this result geometrically; at least in one direction.

As tn=n(n+1)/2, it follows that 2tn=n(n+1) can be interpreted as an n by (n+1) rectangle. We can then place four of these rectangles in the following way:

A A A A B B B
A A A A B B B
A A A A B B B
C C C X B B B
C C C D D D D
C C C D D D D
C C C D D D D

It can be seen that we form a square and there will always by a 1 by 1 square in the middle. In other words, 8tn+1 is a perfect square.
Title: Re: Triangle Test
Post by Icarus on Sep 8th, 2003, 4:05pm
That's nice. I always like a good geometric proof of combinatorial, or other algebraic equations!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board