Suppose you are looking for a rational that yields a string of squares: v = .001004009016025036... If you start with long enough initial snippet of v and apply Euclid's algorithm, you will undoubtedly at some point arrive at 1001000/997002999 However, Euclid will not tell you outright how big your initial snippet must be to yield "the answer" as a convergent, or which convergent is "the answer". Furthermore, it is a bit of computational work to arrive at "the answer". The "generating function" approach is really a series evaluation approach, where we evaluate SUM(n = 1..inf; p(n)/(b^d)^n) with polynomial p(n) or order k, base b and d digits per block, as a rational function of n. The results tells you that the denominator must divide (b^d-1)^(k+1). In the original example, the base is 10, the blocks are 3 digits long, the block values are given by polynomial f(n) = n^2, which is order k = 2, so we use denominator (10^3-1)^(2+1) = 997002999, from which it is straightforward to obtain and simplify the rational given above. The polynomial function can be generalized to a linear recurrence while still evaluating to a rational. The denominator in this case will be related to block value recurrence. For example, with v = .001002004008016032... (powers of 2) The recurrence for the block value recurrence is f(n+1) - 2f(n). The finite linear recurrence SUM(a_i f(n+i)) = 0 has the associated polynomial p(x) = SUM(a_i x^i) = 0, so our associate polynomial is p(x) = x - 2. Our denominator will then be p(b^d), in this case p(10^3) = p(1000) = 1000 - 2 = 998, and indeed v = 1/998. Or take v = .001001002003005008... (Fibonacci numbers) In this case, the block value recurrence if f(n+2) - f(n+1) - f(n) = 0, yielding polynomial p(x) = x^2 - x - 1, so that p(b^d) = p(1000) = 1000^2 - 1000 - 1 = 998999, and again v = 1000/998999. In the case where f is a polynomial of order k, we get associated polynomial p(x) = (x-1)^(k+1), yielding denominator (b^d-1)^(k+1) as given above. Also, the series approach tells you something that Euclid does not, specifically, that your blocks will eventually carry and bleed over into previous blocks and spoil your nice pattern. On 1/29/2012 9:19 AM, Warren Smith wrote:
The idea that we can identify numbers like 1.004009016025036... by use of "generating functions" is silly in comparison with the much better and simpler idea that you can find the optimum rational approximations to ANY decimal X by use of (Euclid's) continued fraction expansion of X: 1.004009016025036049064081100 = [1, 249, 2, 3, 1, 1, 14, 7, 4, 2, 4, 7, 7, 1, large] then 1 + 1/(249+1/(2+1/(3+1/(1+1/(1+1/(14+1/(7+1/(4+1/(2+1/(4+1/(7+1/(7+1)))))))))))); = 1001000000 / 997002999 = 1.004009016025036049064081100121144169196225256289324361...