The sequence of numbers {Q(m)} is defined recursively by the following relationships:
Q(1) = 1, and:
Q(m) = 1 + Q(m/2), whenever m is ≥ 2 and even, and:
Q(m) = 1/Q(m-1), whenever m is ≥ 3 and odd.
Determine the value of d, given that Q(d) = 19/87
All the terms are positive, so all the even terms will be greater than 1, as you're adding 1 to a positive number.
The odd terms higher than the first are reciprocals of even terms, and so will be smaller than 1.
Therefore you can trace backward from 19/87, which must be an odd term. Whenever you have a number smaller than 1, subtract 1 from the term number and take the reciprocal of the term, in this backward trip. When you see a number greater than 1, halve the term number and subtract 1 from the term:
term number term
(d - 1) 87 / 19
(d - 1) / 2 68 / 19
(d - 1) / 4 49 / 19
(d - 1) / 8 30 / 19
(d - 1) / 16 11 / 19
(d - 17) / 16 19 / 11
(d - 17) / 32 8 / 11
(d - 49) / 32 11 / 8
(d - 49) / 64 3 / 8
(d - 113) / 64 8 / 3
(d - 113) / 128 5 / 3
(d - 113) / 256 2 / 3
(d - 369) / 256 3 / 2
(d - 369) / 512 1 / 2
(d - 881) / 512 2
(d - 881) / 1024 1
So (d - 881) / 1024 = 1, as 1 is the first term (term 1).
Therefore d = 1024 + 881 = 1905.
I first tried doing the above procedure by hand, but lost track of the arithmetic, so let my computer do the grunt work:
DEFDBL A-Z
currnum = 19: currden = 87
subtVal = 0: divVal = 1
DO
IF currnum > currden THEN
currnum = currnum - currden
divVal = 2 * divVal
ELSE
SWAP currnum, currden
subtVal = subtVal + divVal
END IF
PRINT "(d -"; subtVal; ") /"; divVal; " "; currnum; "/"; currden
LOOP UNTIL currnum = 1 AND currden = 1
A more brute force method verifies the above answer by starting at 1 and finding all the terms until the appropriate one is found:
DECLARE FUNCTION gcd% (a%, b%)
DEFINT A-Z
DIM qnum(2000), qden(2000)
qnum(1) = 1: qden(1) = 1
FOR m = 2 TO 2000
IF m MOD 2 = 0 THEN
qden(m) = qden(m / 2)
qnum(m) = qnum(m / 2) + qden(m / 2)
g = gcd(qnum(m), qden(m))
qnum(m) = qnum(m) / g
qden(m) = qden(m) / g
ELSE
qden(m) = qnum(m - 1): qnum(m) = qden(m - 1)
END IF
IF qnum(m) = 19 AND qden(m) = 87 THEN PRINT m
NEXT
END
FUNCTION gcd (a, b)
x = a: y = b
DO
q = INT(x / y)
r = x - y * q
x = y: y = r
LOOP UNTIL r = 0
gcd = x
END FUNCTION
|
|
Posted by Charlie
on 2008-02-15 13:12:30 |
solution
