pythagorean triplets in go
sobriquet
How many possible distances can we have in go between 2 stones on the
standard 19x19 board (lets
include the trivial case of a distance of 0 between a stone and
itself)?
At first you might think that the answer is simply the 19th triangular
number (190), but that fails to take pythagorean triplets into
account.
http://en.wikipedia.org/wiki/Triangular_numbers
http://img706.imageshack.us/img706/3491/pythagorean.jpg
Hence, pythagorean triplets reduce the number of possible distances by
3 and we end up with 187 possible unique distances between individual
stones on a standard go board.
Corrections or suggestions are welcome.
PSmith
There are some other distances that coincide, which don't correspond
to Pythagorean triples.
For example, |(4,7)| = |(8,1)| and |(6,7)|=|(9,2)| .
(that's because the sums of the squares are the same: 4*4 + 7*7 = 65 =
8*8 + 1*1, etc)
Peter
sobriquet
Right, I see that I forgot to take multiples of 5 into account as well
as some other duplicates.
Prolog yields the following list of 151 sums of squares (of numbers
from 1 to 18):
[2,5,8,10,13,17,18,20,25,26,29,32,34,37,40,41,45,50,52,53,58,61,65,68,72,73,74,80,82,85,89,90,97,98,100,101,104,106,109,113,116,117,122,125,128,130,136,137,145,146,148,149,153,157,160,162,164,169,170,173,178,180,181,185,193,194,197,200,202,205,208,212,218,221,225,226,229,232,233,234,241,242,244,245,250,257,260,261,265,269,272,274,277,281,288,289,290,292,293,296,298,305,306,313,314,317,320,325,328,333,337,338,340,346,349,353,356,360,365,369,370,373,377,388,389,392,394,400,405,410,421,424,425,433,445,450,452,458,468,481,485,493,512,514,520,545,549,578,580,613,648]
Of those, [25,100,169,225,289] are squares of integers.
So we end up with 146+19=165 possible unique distances (including the
trivial distance of 0).
I overcounted initially because sums of squares are not unique.
18 of them can be formed in two ways and one even in three ways.
50 = 1 + 49 = 25 + 25
65 = 1 + 64 = 16 + 49
85 = 4 + 81 = 36 + 49
125 = 4 + 121 = 25 + 100
130 = 9 + 121 = 49 + 81
145 = 1 + 144 = 64 + 81
170 = 1 + 169 = 49 + 121
185 = 16 + 169 = 64 + 121
200 = 4 + 196 = 100 + 100
205 = 9 + 196 = 36 + 169
221 = 25 + 196 = 100 + 121
250 = 25 + 225 = 81 + 169
260 = 4 + 256 = 64 + 196
265 = 9 + 256 = 121 + 144
290 = 1 + 289 = 121 + 169
305 = 16 + 289 = 49 + 256
338 = 49 + 289 = 169 + 169
340 = 16 + 324 = 144 + 196
325 = 1 + 324 = 36 + 289 = 100 + 225
sobriquet
>
> Of those, [25,100,169,225,289] are squares of integers.
>
> So we end up with 146+19=165 possible unique distances (including the
> trivial distance of 0).
>
> I overcounted initially because sums of squares are not unique.
> 18 of them can be formed in two ways and one even in three ways.
>
> 50 = 1 + 49 = 25 + 25
> 65 = 1 + 64 = 16 + 49
> 85 = 4 + 81 = 36 + 49
> 125 = 4 + 121 = 25 + 100
> 130 = 9 + 121 = 49 + 81
> 145 = 1 + 144 = 64 + 81
> 170 = 1 + 169 = 49 + 121
> 185 = 16 + 169 = 64 + 121
> 200 = 4 + 196 = 100 + 100
> 205 = 9 + 196 = 36 + 169
> 221 = 25 + 196 = 100 + 121
> 250 = 25 + 225 = 81 + 169
> 260 = 4 + 256 = 64 + 196
> 265 = 9 + 256 = 121 + 144
> 290 = 1 + 289 = 121 + 169
> 305 = 16 + 289 = 49 + 256
> 338 = 49 + 289 = 169 + 169
> 340 = 16 + 324 = 144 + 196
>
> 325 = 1 + 324 = 36 + 289 = 100 + 225
One last picture to visualize these duplicates:
wilemien
(never sure)
they are
sum 1st pair 2nd pair 3rd pair
25 0 + 25 9 + 16
50 1 + 49 25 + 25
65 1 + 64 16 + 49
85 4 + 81 36 + 49
100 0 + 100 36 + 64
125 4 + 121 25 + 100
130 9 + 121 49 + 81
145 1 + 144 64 + 81
169 0 + 169 25 + 144
170 1 + 169 49 + 121
185 16 + 169 64 + 121
200 4 + 196 100 + 100
205 9 + 196 36 + 169
221 25 + 196 100 + 121
225 0 + 225 81 + 144
250 25 + 225 81 + 169
260 4 + 256 64 + 196
265 9 + 256 121 + 144
289 0 + 289 64 + 225
290 1 + 289 121 + 169
305 16 + 289 49 + 256
325 1 + 324 36 + 289 100 + 225
338 49 + 289 169 + 169
340 16 + 324 144 + 196
365 4 + 361 169 + 196
370 9 + 361 81 + 289
377 16 + 361 121 + 256
410 49 + 361 121 + 289
425 64 + 361 169 + 256
sobriquet
You've included sums of 19*19 (=361), while the maximum length along a
line on the go board (so either horizontal or vertical) is of length
18.
So you've overcounted slightly.
The sums I've listed just excluded the Pythagorean triples, so the
complete list is:
25 = 0 + 25 = 9 + 16
50 = 1 + 49 = 25 + 25
65 = 1 + 64 = 16 + 49
85 = 4 + 81 = 36 + 49
100 = 0 + 100 = 36 + 64
125 = 4 + 121 = 25 + 100
130 = 9 + 121 = 49 + 81
145 = 1 + 144 = 64 + 81
169 = 0 + 169 = 25 + 144
170 = 1 + 169 = 49 + 121
185 = 16 + 169 = 64 + 121
200 = 4 + 196 = 100 + 100
205 = 9 + 196 = 36 + 169
221 = 25 + 196 = 100 + 121
225 = 0 + 225 = 81 + 144
250 = 25 + 225 = 81 + 169
260 = 4 + 256 = 64 + 196
265 = 9 + 256 = 121 + 144
289 = 0 + 289 = 64 + 225
290 = 1 + 289 = 121 + 169
305 = 16 + 289 = 49 + 256
338 = 49 + 289 = 169 + 169
325 = 1 + 324 = 36 + 289 = 100 + 225
340 = 16 + 324 = 144 + 196
Visually:
sobriquet
> [..] so the complete list is:
>
> 25 = 0 + 25 = 9 + 16
> 50 = 1 + 49 = 25 + 25
> 65 = 1 + 64 = 16 + 49
> 85 = 4 + 81 = 36 + 49
> 100 = 0 + 100 = 36 + 64
> 125 = 4 + 121 = 25 + 100
> 130 = 9 + 121 = 49 + 81
> 145 = 1 + 144 = 64 + 81
> 169 = 0 + 169 = 25 + 144
> 170 = 1 + 169 = 49 + 121
> 185 = 16 + 169 = 64 + 121
> 200 = 4 + 196 = 100 + 100
> 205 = 9 + 196 = 36 + 169
> 221 = 25 + 196 = 100 + 121
> 225 = 0 + 225 = 81 + 144
> 250 = 25 + 225 = 81 + 169
> 260 = 4 + 256 = 64 + 196
> 265 = 9 + 256 = 121 + 144
> 289 = 0 + 289 = 64 + 225
> 290 = 1 + 289 = 121 + 169
> 305 = 16 + 289 = 49 + 256
> 338 = 49 + 289 = 169 + 169
> 340 = 16 + 324 = 144 + 196
>
(slightly re-ordered)