Determine the total number of pairs (x, y) of positive integers such that the least common multiple (LCM) of x and y is 2³*5⁷*11¹³.

For choosing the powers-of-2 components of the two numbers, each can have from 0 to 3 as its power of 2 (4 choices each) but they can't both have from 0 to 2 as each one's power of 2 (3 choices each). So the choices for power of 2 are (4^2 - 3^2), and similarly for the larger powers for the other primes listed:

(4*4-3*3)*(8*8-7*7)*(14*14-13*13) = 2835

FOR x2 = 0 TO 3
 FOR y2 = 0 TO 3
  FOR x5 = 0 TO 7
   FOR y5 = 0 TO 7
    FOR x11 = 0 TO 13
     FOR y11 = 0 TO 13
      IF (x2 = 3 OR y2 = 3) AND (x5 = 7 OR y5 = 7) AND (x11 = 13 OR y11 = 13) THEN ct = ct + 1
     NEXT
    NEXT
   NEXT
  NEXT
 NEXT
NEXT
PRINT ct

confirms the result.

Posted by Charlie on 2013-10-14 10:38:52