Author |
Topic: Triangle Test (Read 588 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Triangle Test
« on: Sep 7th, 2003, 11:25am » |
 Quote  Modify
|
Given a number, N, what is the most efficient way to test if it is a triangle number?
|
|
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Triangle Test
« Reply #1 on: Sep 7th, 2003, 1:05pm » |
Quote Modify
|
the best I can do on short notice is
floor([sqrt](2*N)) * (floor([sqrt](2*N)) +1) == 2*N
|
| « Last Edit: Sep 7th, 2003, 1:10pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Triangle Test
« Reply #2 on: Sep 7th, 2003, 1:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Triangle Test
« Reply #3 on: Sep 7th, 2003, 2:06pm » |
Quote Modify
|
I came up with 8N+1 is a perfect square.
This comes from Applying the quadratic formula to the equation n(n+1) = 2N, and figuring out what it required for n to be an integer.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Triangle Test
« Reply #4 on: Sep 7th, 2003, 2:17pm » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Triangle Test
« Reply #5 on: Sep 8th, 2003, 8:37am » |
Quote Modify
|
what is a triangle number? 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Triangle Test
« Reply #6 on: Sep 8th, 2003, 8:44am » |
Quote Modify
|
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
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Triangle Test
« Reply #7 on: Sep 8th, 2003, 11:58am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Triangle Test
« Reply #8 on: Sep 8th, 2003, 12:34pm » |
Quote Modify
|
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...
::
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.
::
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.
|
| « Last Edit: Sep 8th, 2003, 12:36pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Triangle Test
« Reply #9 on: Sep 8th, 2003, 1:10pm » |
Quote Modify
|
on Sep 8th, 2003, 12:34pm, 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.
|
| « Last Edit: Sep 8th, 2003, 1:17pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Triangle Test
« Reply #10 on: Sep 8th, 2003, 1:25pm » |
Quote Modify
|
on Sep 8th, 2003, 1:10pm, 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. |
|
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Triangle Test
« Reply #11 on: Sep 8th, 2003, 1:42pm » |
Quote Modify
|
on Sep 8th, 2003, 12:34pm, Sir Col wrote:| Prove that 8N+1 is a perfect square iff (if and only if) N is a triangle number. |
|
Er, 8N+1 = 4n(n+1)+1 = 4n2+4n+1 = (2n+1)2.
Well, at least one implication is obvious.
|
| « Last Edit: Sep 8th, 2003, 1:44pm by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Triangle Test
« Reply #12 on: Sep 8th, 2003, 1:47pm » |
Quote Modify
|
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.
|
| « Last Edit: Sep 8th, 2003, 1:47pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Triangle Test
« Reply #13 on: Sep 8th, 2003, 3:47pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Triangle Test
« Reply #14 on: Sep 8th, 2003, 3:51pm » |
Quote Modify
|
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 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Triangle Test
« Reply #15 on: Sep 8th, 2003, 4:01pm » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Triangle Test
« Reply #16 on: Sep 8th, 2003, 4:05pm » |
Quote Modify
|
That's nice. I always like a good geometric proof of combinatorial, or other algebraic equations!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print