Three positive integers are chosen at random without replacement from 1,2,....,64. What is the probability that the numbers chosen are in geometric sequence?

Order of choice doesn't matter. For example, 4-1-2 would qualify as numbers in geometric sequence.

Bonus Question:
Generalise this result (in terms of n) covering the situation where three positive integers are chosen at random without replacement from 1,2,.....,n².

For the main case of n = 8; n^2=64, there are 58 positive outcomes out of the C(64,3)=41664 possible combinations of 3 chosen numbers, making the probability 58/41664 = 29/20832 ~= 0.0013920891 or 1/718.3448275862069:

1  2  4
1  3  9
1  4  16
1  5  25
1  6  36
1  7  49
1  8  64
2  4  8
2  6  18
2  8  32
2  10  50
3  6  12
3  9  27
3  12  48
4  6  9
4  8  16
4  10  25
4  12  36
4  14  49
4  16  64
5  10  20
5  15  45
6  12  24
6  18  54
7  14  28
7  21  63
8  12  18
8  16  32
8  20  50
9  12  16
9  15  25
9  18  36
9  21  49
9  24  64
10  20  40
11  22  44
12  18  27
12  24  48
13  26  52
14  28  56
15  30  60
16  20  25
16  24  36
16  28  49
16  32  64
18  24  32
18  30  50
20  30  45
24  36  54
25  30  36
25  35  49
25  40  64
27  36  48
28  42  63
32  40  50
36  42  49
36  48  64
49  56  64

The following program produces a table of probabilities for other n up to 20 (i.e., n^2 up to 400):

DECLARE FUNCTION gcd# (a#, b#)
DECLARE FUNCTION combi# (n#, r#)
DEFDBL A-Z
FOR n = 2 TO 20
  nsq = n * n
  tot = 0
  FOR a = 1 TO nsq - 1
   FOR c = a + 1 TO nsq
     b = INT(SQR(a * c) + .5)
     IF b * b = a * c THEN tot = tot + 1: ' PRINT a; b; c
   NEXT
  NEXT
  c = combi(nsq, 3)
  g = gcd(tot, c)
  tot2 = tot / g: c2 = c / g
  PRINT USING "## ####      ####### /######### #### / ####### #.##########"; n; nsq; tot; c; tot2; c2; tot / c
NEXT n

FUNCTION combi (n, r)
  c = 1
  FOR i = n TO n - r + 1 STEP -1
    c = c * i
  NEXT
  FOR i = 2 TO r
    c = c / i
  NEXT
  combi = c
END FUNCTION

FUNCTION gcd (a, b)
 dnd = a: dvr = b
 DO
  q = INT(dnd / dvr): r = dnd - q * dvr
  dnd = dvr: dvr = r
 LOOP UNTIL dvr = 0
 gcd = dnd
END FUNCTION

produces the following table including the 29 / 20832 probability when n^2 = 64, as in the first part of the puzzle:

 n  n^2         ways     out of         reduced         decimal
                     (combinations)    fraction       probability
 2    4            1 /        4       1 /       4    0.2500000000
 3    9            4 /       84       1 /      21    0.0476190476
 4   16            8 /      560       1 /      70    0.0142857143
 5   25           16 /     2300       4 /     575    0.0069565217
 6   36           27 /     7140       9 /    2380    0.0037815126
 7   49           40 /    18424       5 /    2303    0.0021710812
 8   64           58 /    41664      29 /   20832    0.0013920891
 9   81           80 /    85320       2 /    2133    0.0009376465
10  100          105 /   161700       1 /    1540    0.0006493506
11  121          128 /   287980      32 /   71995    0.0004444753
12  144          158 /   487344      79 /  243672    0.0003242063
13  169          198 /   790244      99 /  395122    0.0002505555
14  196          237 /  1235780     237 / 1235780    0.0001917817
15  225          278 /  1873200     139 /  936600    0.0001484091
16  256          336 /  2763520      21 /  172720    0.0001215841
17  289          382 /  3981264     191 / 1990632    0.0000959494
18  324          435 /  5616324     145 / 1872108    0.0000774528
19  361          502 /  7775940     251 / 3887970    0.0000645581
20  400          574 / 10586800      41 /  756200    0.0000542185

Posted by Charlie on 2013-02-28 12:46:10