Henry
Newbie
Joined: 02 Jun 2010
Posts: 7
|
 Posted: 06 Jun 2010 11:24:04 pm Post subject: |
|
|
Reference: http://www.cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html and (long url) and http://www.research.att.com/~njas/sequences/A006600
The formula is based off of the divisibility of n, and thus a universal formula is quite complicated, if not impossible - so using all those divisibility tricks, here is a program that can find the number of triangles formed by a fully connected graph (complete).
I read a book once where it solved the problem through combinatorics, but it was wrong! There is a correction factor after a certain point, where the triangles overlap, and thus the divisibility of n.
So as everyone always wonders how many triangles there are in complete graphs every day, here is the program:
Code:
ClrHome
Disp "VERTICES"
Prompt N
If (N/2)=iPart(N/2)
Then
1→A
Else
0→A
End
If (N/4)=iPart(N/4)
Then
1→B
Else
0→B
End
If (N/6)=iPart(N/6)
Then
1→C
Else
0→C
End
If (N/12)=iPart(N/12)
Then
1→D
Else
0→D
End
If (N/18)=iPart(N/18)
Then
1→E
Else
0→E
End
If (N/24)=iPart(N/24)
Then
1→F
Else
0→F
End
If (N/30)=iPart(N/30)
Then
1→G
Else
0→G
End
If (N/42)=iPart(N/42)
Then
1→H
Else
0→H
End
If (N/60)=iPart(N/60)
Then
1→I
Else
0→I
End
If (N/84)=iPart(N/84)
Then
1→J
Else
0→J
End
If (N/90)=iPart(N/90)
Then
1→K
Else
0→K
End
If (N/120)=iPart(N/120)
Then
1→L
Else
0→L
End
If (N/210)=iPart(N/210)
Then
1→M
Else
0→M
End
(((N)(N-1)(N-2)((N^3+18N^2-43N+60)/720)-A(N-2)(N-7)N/8-B(3N/4)-C(18N-106)N/3+D33N+E36N+F24N-G96N-H72N-I264N-J96N-K48N-L96N-M48N))→O
Disp O
Last edited by Guest on 07 Jun 2010 01:32:34 pm; edited 1 time in total |
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 07 Jun 2010 06:25:56 am Post subject: |
|
|
This...
If (N/2)=iPart(N/2)
Then
1→A
Else
0→A
End
...may be turned into this:
N/2=iPart(N/2→A
...which in turn becomes:
not(fPart(N/2→A
All of them together:
not(fPart(N/2→A
not(fPart(N/4→B
not(fPart(N/6→C
...
not(fPart(N/210→M
...are now converted to a list:
not(fPart(N/{2,4,6,12,18,24,30,42,60,84,90,120,210
Consider the bijection of the factors for each variable:
A → -(N-2)(N-7)N/8
B → -(3N/4)
C → -(18N-106)N/3
D → 33N
E → 36N
F → 24N
G → -96N
H → -72N
I → -264N
J → -96N
K → -48N
L → -96N
M → -48N
Make this into its own list and then simplify, reducing the token count:
-12N{(N-7)(N-2)/96,16‾¹,.5N-53/18,-2.75,-3,-2,8,6,22,8,4,8,4
(The sign is extracted because most of the elements are negative.)
Multiplying two lists together will multiply each pair of elements that are parallel to one another from both lists – in effect, each addend is considered only if the corresponding binary element is nonzero. Afterward, the sum is taken as part of the evaluation.
Note that the result of the most recent calculation is automatically stored into Ans, and that any such result produced by a line at the end of a program is automatically displayed on the home screen.
PROGRAM:VERTICES
:Ans(Ans-1)(Ans-2)(Ans[font=verdana]³+18Ans[font=verdana]²-43Ans+60)/6!-sum(12Ans{(Ans-7)(Ans-2)/96,16‾¹,.5Ans-53/18,…
…-2.75,-3,-2,8,6,22,8,4,8,4}not(fPart(Ans/{2,4,6,12,18,24,30,42,60,84,90,120,210
Run the input like so:
12:prgmVERTICES
70:prgmVERTICES
...
You'll find that this program gives the same outputs as its ancestor, and that it employs 392 fewer bytes, 15 fewer variables, and all-but-one fewer lines to do so.
Last edited by Guest on 07 Jun 2010 07:04:23 am; edited 1 time in total |
|
Math and Science => Technology & Calculator Open Topic
