Equilateral triangles in lattice cube
Pfoertner, Hugo
Hugo.Pfoertner at muc.mtu.de
Mon Feb 7 17:27:23 CET 2005
-----Original Message-----
From: Joshua Zucker [mailto:joshua.zucker at gmail.com]
Sent: Friday, February 04, 2005 23:01
To: seqfan at ext.jussieu.fr
Subject: Equilateral triangles in lattice cube
Hi folks,
I just submitted the following to OEIS.
My algorithm for calculating the terms is complete brute force and
will take a while to run to get even 1 more term ...
can anyone help me with more terms, or with an idea for a faster algorithm?
Thanks,
--Joshua Zucker
%S A000001 8, 80, 368, 1264, 3448, 7792
%N A000001 Equilateral triangles in the lattice cube of side length n.
%D A000001 Inspired by problem 25 on the 2005 AMC-12A mathematics
competition, which asked for a(2).
%e A000001 a(1) = 8 because in the unit cube, equilateral triangles
are formed by cutting off any one of the 8 corners.
a(2) = 80 because there are 8 unit cubes with 8 each, 8 larger
triangles (analogous to the 8 in the unit cube, but twice as big), and
also 8 triangles of side length sqrt(6).
%O A000001 1
%K A000001 ,more,nonn,
%A A000001 Joshua Zucker (joshua.zucker at stanfordalumni.org), Feb 04 2005
Within a few minutes I got:
8, 80, 368, 1264, 3448, 7792, 16176, 30696, 54216, 90104, 143576,
220328, 326680, 471232
Why not also count other kinds of triangles? I've extended my program by a
few more counts.
All possible triangles, isosceles, equilateral, acute, obtuse, right:
n= 1
alltri: 56 /4= 14
isoscl: 32 /4= 8
equila: 8 /8= 1
acute: 8 /4= 2
obtuse: 0 /4= 0
righta: 48 /12= 4
n= 2
alltri: 2876 /4= 719
isoscl: 776 /4= 194
equila: 80 /8= 10
acute: 776 /4= 194
obtuse: 744 /4= 186
righta: 1356 /12= 113
n= 3
alltri: 41288 /4= 10322
isoscl: 6440 /4= 1610
equila: 368 /8= 46
acute: 13736 /4= 3434
obtuse: 15240 /4= 3810
righta: 12312 /12= 1026
n= 4
alltri: 315892 /4= 78973
isoscl: 33628 /4= 8407
equila: 1264 /8= 158
acute: 117424 /4= 29356
obtuse: 135192 /4= 33798
righta: 63276 /12= 5273
n= 5
alltri: 1650592 /4= 412648
isoscl: 128008 /4= 32002
equila: 3448 /8= 431
acute: 648760 /4= 162190
obtuse: 759792 /4= 189948
righta: 242040 /12= 20170
n= 6
alltri: 6649600 /4= 1662400
isoscl: 392764 /4= 98191
equila: 7792 /8= 974
acute: 2718616 /4= 679654
obtuse: 3200112 /4= 800028
righta: 730872 /12= 60906
n= 7
alltri: 22191264 /4= 5547816
isoscl: 1017144 /4= 254286
equila: 16176 /8= 2022
acute: 9295512 /4= 2323878
obtuse: 10978176 /4= 2744544
righta: 1917576 /12= 159798
n= 8
alltri: 64186416 /4= 16046604
isoscl: 2386860 /4= 596715
equila: 30696 /8= 3837
acute: 27358380 /4= 6839595
obtuse: 32372892 /4= 8093223
righta: 4455144 /12= 371262
n= 9
alltri: 165900888 /4= 41475222
isoscl: 5068512 /4= 1267128
equila: 54216 /8= 6777
acute: 71639688 /4= 17909922
obtuse: 84809520 /4= 21202380
righta: 9451680 /12= 787640
n= 10
alltri: 391539788 /4= 97884947
isoscl: 10025144 /4= 2506286
equila: 90104 /8= 11263
acute: 170702204 /4= 42675551
obtuse: 202227828 /4= 50556957
righta: 18609756 /12= 1550813
n= 11
alltri: 857341952 /4= 214335488
isoscl: 18586664 /4= 4646666
equila: 143576 /8= 17947
acute: 376501424 /4= 94125356
obtuse: 446244600 /4= 111561150
righta: 34595928 /12= 2882994
n= 12
alltri: 1762885484 /4= 440721371
isoscl: 32959628 /4= 8239907
equila: 220328 /8= 27541
acute: 778772960 /4= 194693240
obtuse: 923116344 /4= 230779086
righta: 60996180 /12= 5083015
n= 13
alltri: 3435925528 /4= 858981382
isoscl: 55781800 /4= 13945450
equila: 326680 /8= 40835
acute: 1524857800 /4= 381214450
obtuse: 1807742040 /4= 451935510
righta: 103325688 /12= 8610474
Without web access today I didn't look up anything in the OEIS, so we have
to check if some or all of this stuff is already in the database. I don't
know if the preferred form is to remove common factors as indicated in the
last column.
My algorithm is also "brute force". The only "trick" is the usual
"equivalence" construct between the 3-d and 1-d addressing of the lattice
points, which allows an easy traversal through all 3-tuples of distinct
points. There seem to be gradations in brutality ;-).
The Fortran program is attached at the end of this e-mail.
Hugo Pfoertner
-------------------------
C Count number of different sorts of triangles that can be formed
C using the points in an (n+1) X (n+1) X (n+1) lattice cube.
C Problem by Joshua Zucker in Seqfan mailing list
C (for equilateral triangles)
C
C Hugo Pfoertner http://www.pfoertner.org/
C Feb 7, 2005
C
implicit integer (a-z)
logical needle
integer*8 alltri, isoscl, equila, acute, obtuse, righta
parameter (n=13,n3=(n+1)*(n+1)*(n+1))
C
dimension x(n3), y(n3), z(n3),
& xx(0:n,0:n,0:n),
& yy(0:n,0:n,0:n),
& zz(0:n,0:n,0:n)
C
equivalence (x,xx),(y,yy),(z,zz)
C set coordinates
do 10 ix = 0, n
do 10 iy = 0, n
do 10 iz = 0, n
xx(ix,iy,iz) = ix
yy(ix,iy,iz) = iy
zz(ix,iy,iz) = iz
10 continue
C Preset counters for different kinds of triangles
alltri = 0
isoscl = 0
equila = 0
acute = 0
obtuse = 0
righta = 0
C
C Loop over all combinations of 3 points
do 100 k1 = 1, n3-2
x1 = x(k1)
y1 = y(k1)
z1 = z(k1)
do 200 k2 = k1+1, n3-1
x2 = x(k2)
y2 = y(k2)
z2 = z(k2)
d12 = (x2-x1)**2 + (y2-y1)**2 + (z2-z1)**2
do 300 k3 = k2+1, n3
x3 = x(k3)
y3 = y(k3)
z3 = z(k3)
d23 = (x2-x3)**2 + (y2-y3)**2 + (z2-z3)**2
d31 = (x1-x3)**2 + (y1-y3)**2 + (z1-z3)**2
C will later be corrected to eliminate "3 aligned points"
alltri = alltri + 1
C Sort side lengths such that dmi<=dmid<=dma
dsum = d12 + d23 + d31
dmi = min ( d12, d23, d31 )
dma = max ( d12, d23, d31 )
dmid = dsum - dmi - dma
C sum of squares of 2 shortest sides
dcom = dmi + dmid
C compare with square of longest side
if ( dma .ge. dcom ) then
C Triangle is either obtuse or right angle
C logical needle indicates the degenerate case "3 in a line"
needle = .false.
if ( dma .eq. dcom ) then
righta = righta + 1
else
C Check for 3 points in a line
needle = abs(( sqrt(float(dma)) -
& sqrt(float(dmi)) - sqrt(float(dmid)) )) .lt. 0.01
if ( .not. needle ) obtuse = obtuse + 1
endif
if ( needle ) then
C not counted as triangle
alltri = alltri - 1
elseif ( dmi .eq. dmid ) then
isoscl = isoscl + 1
endif
else
acute = acute + 1
if ( dma .eq. dmid ) isoscl = isoscl + 1
endif
if ( dma .eq. dmi ) equila = equila + 1
300 continue
200 continue
100 continue
write(*,*) ' n=', n
write(*,*) ' alltri:', alltri, ' /4=', alltri/4.0D0
write(*,*) ' isoscl:', isoscl, ' /4=', isoscl/4.0D0
write(*,*) ' equila:', equila, ' /8=', equila/8.0D0
write(*,*) ' acute: ', acute, ' /4=', acute/4.0D0
write(*,*) ' obtuse:', obtuse, ' /4=', obtuse/4.0D0
write(*,*) ' righta:', righta, ' /12=', righta/12.0D0
end
More information about the SeqFan
mailing list