All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Special Ordered Pairs (Posted on 2007-12-28)
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(xk)*d(yk))2p with p substituting for n(yk / xk),
if (xk,yk) 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

 See The Solution Submitted by Praneeth Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Heuristics for part 1 Comment 1 of 1

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 20pwr     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 5510  6 12 12 18 18 24 24 30 30 36 36 42 42 48 48 54 54 60 60 6611  6 12 12 18 18 24 24 30 30 36 36 42 42 48 48 54 54 60 60 6612  7 14 14 21 21 28 28 35 35 42 42 49 49 56 56 63 63 70 70 7713  7 14 14 21 21 28 28 35 35 42 42 49 49 56 56 63 63 70 70 7714  8 16 16 24 24 32 32 40 40 48 48 56 56 64 64 72 72 80 80 8815  8 16 16 24 24 32 32 40 40 48 48 56 56 64 64 72 72 80 8016  9 18 18 27 27 36 36 45 45 54 54 63 63 72 72 81 8117  9 18 18 27 27 36 36 45 45 54 54 63 63 72 72 8118 10 20 20 30 30 40 40 50 50 60 60 70 70 8019 10 20 20 30 30 40 40 50 50 60 60 70 7020 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  22,1,1  2    2,2,1  4    2,3,1  43,1,1  2    3,2,1  4    3,3,1  44,1,1  3    4,2,1  6    4,3,1  6  1,1,2  2    1,2,2  4    1,3,2  42,1,2  4    2,2,2  8    2,3,2  83,1,2  4    3,2,2  8    3,3,2  84,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

 Search: Search body:
Forums (0)