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

 Given the term, find the number (Posted on 2008-02-15)
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

 See The Solution Submitted by K Sengupta Rating: 4.0000 (3 votes)

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

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

 Search: Search body:
Forums (0)