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

Home > Numbers > Sequences
Given the term, find the number (Posted on 2008-02-15) Difficulty: 3 of 5
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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information