Call the ordered pairs (x,y), where x, y are positive integers such that x*y=A and y is a multiple of x, "special ordered pairs" of A.

1) Find an expression for the number of special ordered pairs of a given A.

2) Show that:
π_i|Ad(i) = π (d(x_k)*d(y_k))^2p with p substituting for n(y_k / x_k),
if (x_k,y_k) for {k=1,2,..} are all possible special ordered pairs of A.

Note: i|A means i is a divisor of A, d(i) is the number of positive divisors of i, n(i) is the number of prime divisors of i and π determines the product

The number of special ordered pairs of A should depend only on the structure of powers of primes that go into the prime factorization of A. That is, the number for p1^n1*p2^n2*...*pz^nz, for distinct primes p, depends solely on the numbers n1, n2, ... nz, and not on the identities of the primes.

The following program, therefore, uses powers of 2 and 3 to stave off overflow or numbers too large to fit well on the table produced.

DEFDBL A-Z

PRINT

PRINT "  ";
FOR pwr2 = 1 TO 20
 PRINT USING "###"; pwr2;
NEXT
PRINT
FOR pwr3 = 0 TO 20
 PRINT USING "##"; pwr3;
 FOR pwr2 = 1 TO 20
   n = INT(2 ^ pwr2 * 3 ^ pwr3 + .5)
   IF n < 1E+13 THEN
    sct = 0
    FOR i = 1 TO SQR(n)
      q = INT(n / i + .5)
      IF q * i = n THEN
       q2 = INT(q / i + .5)
       IF q2 * i = q THEN
        sct = sct + 1
       END IF
      END IF
    NEXT
    PRINT USING "###"; sct;
   END IF
 NEXT
 PRINT
NEXT

The resulting table of special ordered pairs by powers of two primes follows:

pwr 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
pwr    
 0  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  9  9 10 10 11
 1  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  9  9 10 10 11
 2  2  4  4  6  6  8  8 10 10 12 12 14 14 16 16 18 18 20 20 22
 3  2  4  4  6  6  8  8 10 10 12 12 14 14 16 16 18 18 20 20 22
 4  3  6  6  9  9 12 12 15 15 18 18 21 21 24 24 27 27 30 30 33
 5  3  6  6  9  9 12 12 15 15 18 18 21 21 24 24 27 27 30 30 33
 6  4  8  8 12 12 16 16 20 20 24 24 28 28 32 32 36 36 40 40 44
 7  4  8  8 12 12 16 16 20 20 24 24 28 28 32 32 36 36 40 40 44
 8  5 10 10 15 15 20 20 25 25 30 30 35 35 40 40 45 45 50 50 55
 9  5 10 10 15 15 20 20 25 25 30 30 35 35 40 40 45 45 50 50 55
10  6 12 12 18 18 24 24 30 30 36 36 42 42 48 48 54 54 60 60 66
11  6 12 12 18 18 24 24 30 30 36 36 42 42 48 48 54 54 60 60 66
12  7 14 14 21 21 28 28 35 35 42 42 49 49 56 56 63 63 70 70 77
13  7 14 14 21 21 28 28 35 35 42 42 49 49 56 56 63 63 70 70 77
14  8 16 16 24 24 32 32 40 40 48 48 56 56 64 64 72 72 80 80 88
15  8 16 16 24 24 32 32 40 40 48 48 56 56 64 64 72 72 80 80
16  9 18 18 27 27 36 36 45 45 54 54 63 63 72 72 81 81
17  9 18 18 27 27 36 36 45 45 54 54 63 63 72 72 81
18 10 20 20 30 30 40 40 50 50 60 60 70 70 80
19 10 20 20 30 30 40 40 50 50 60 60 70 70
20 11 22 22 33 33 44 44 55 55 66 66

So, for example, A = p1^5 * p2^6 has 12 special ordered pairs. The program calculated this based on 2^5 * 3^6 =  23328, whose twelve special ordered pairs are (1,23328) (2,11664) (3,7776) (4,5832) (6,3888) (9,2592) (12,1944) (18, 1296) (27,864) (36,648) (54,432) (108,216).

The structure in blocks of four equal values indicates the likelihood that a ceiling or floor function is used in the formula after dividing each power by 2.  Fiddling around with the values shows a match when the formula

ceil((a+1)/2) ceil((b+1)/2) ... ceil((z+1)/2)

is used, where a, b, etc. are the powers of the primes.

As the above table only shows the involvement of powers of two primes, manual entry of some powers of three primes further verifies the formula:

1,1,1  1    1,2,1  2    1,3,1  2
2,1,1  2    2,2,1  4    2,3,1  4
3,1,1  2    3,2,1  4    3,3,1  4
4,1,1  3    4,2,1  6    4,3,1  6
  
1,1,2  2    1,2,2  4    1,3,2  4
2,1,2  4    2,2,2  8    2,3,2  8
3,1,2  4    3,2,2  8    3,3,2  8
4,1,2  6    4,2,2 12    4,3,2 12

where the triplets are the powers of three primes and the number to the right of each triplet is the number of special ordered pairs for that combination. For example, 2^4 * 3^3 * 5^2 = 10800 has 12 special ordered pairs:  (1,10800) (2,5400) (3,3600) (4,2700) (5,2160) (6,1800) (10,1080) (12,900) (15,720) (20,540) (30,360) (60,180), and ceil(5/2)*ceil(4/2)*ceil(3/2) = 3*2*2 = 12.

The manual entry was made, one number at a time, into:

DEFDBL A-Z

DO
  INPUT n
  sct = 0
  PRINT n;
  FOR i = 1 TO SQR(n)
    q = INT(n / i + .5)
    IF q * i = n THEN
     q2 = INT(q / i + .5)
     IF q2 * i = q THEN
      sct = sct + 1
      PRINT "("; LTRIM$(STR$(i)); ","; LTRIM$(STR$(q)); ") ";
     END IF
    END IF
  NEXT
  PRINT TAB(44); : PRINT USING "###### ###"; n; sct
LOOP

Edited on December 28, 2007, 6:14 pm

Posted by Charlie on 2007-12-28 18:12:47