For any positive integer n let f(n) denote the integer given by the recurrence f(n) = 10 f(n-1) + n with the initial value f(0) = 0. Thus we have f(1)=1, f(2)=12, f(3)=123, and so on. The square roots of f(n) for odd integers n give a persistent pattern, appearng to be rational for periods, and then disintegrating into irrationality. This is illustrated by the first 500 digits of sqrt[f(49)] below. sqrt[f(49)] = 1111111111111111111111111.1111111111111111111111 0860 555555555555555555555555555555555555555555555 2730541 66666666666666666666666666666666666666666 0296260347 2222222222222222222222222222222222222 0426563940928819 4444444444444444444444444444444 38775551250401171874 9999999999999999999999999999 808249687711486305338541 66666666666666666666666 5987185738621440638655598958 33333333333333333333 0843460407627608206940277099609374 99999999999999 0642227587555983066639430321587456597 222222222 1863492016791180833081844..... Notice how the sequence of digits consists of strings of repeated digits alternating with "scrambled" strings. The repeating strings become progressively smaller and the scrambled strings become larger until eventially the repeating strings disappear. However, by increasing n we can forstall the disappearance of the repeating strings as long as we like. The repeating digits are always 1, 5, 6, 2, 4, 9, 6, 3, 9, 2, ... To determine this sequence of digits directly, recall that for any positive integer k the sum of (n^t)(x^n) can be expressed in terms of a polynomial of degree k whose coefficients are a row of the Eulerian numbers. In the present case we just have t=1 so it we immediately have f(n) = (10^(n+1) - 9n - 10)/81 Setting n=2k-1 (because n must be odd) and factoring gives 10^(2k) / 18k+1 \ f(2k-1) = --------- ( 1 - ------- ) 81 \ 10^(2k) / The square root of this number is _________ 10^k / 18k+1 \1/2 / f(2k-1) = ---- ( 1 - ------- ) 9 \ 10^(2k) / Expanding the square root gives _ _ _________ 10^k | 1 / 18k+1 \ 1 / 18k+1 \2 | / f(2k-1) = ---- | 1 - - ( ------- ) - - ( ------- ) - ... | 9 |_ 2 \10^(2k)/ 8 \10^(2k)/ _| The repeated digits can be inferred from the k=0 case, which implies that each term contributes a negative digit equal to the ultimate repeating digit of (c_t)/9, where c_t is the coefficient of ((18k+1)/(10^(2k)))^t in the binomial expansion. Beginning with the first repeating digit a_0 = d_0 = 1, we have c_1 = 1/2 and so the 1st order term contributes (-1/2)/9 = -.05555555. Accordingly we set a_1 = 5 and subtract this from the initial repeating digit d_0 = 1. Thereafter we set d_j to the least positive (non-zero) residue (mod 9) of d_(j-1) - a_j. For example, since a_1 = 5 and d_0 = 1 we compute d_0 - a_1 = 1 - 5 = -4, and so we set d_1 = 5. In this way we can compute the successive digits that will appear in strings just by examining the ultimate repeating digits of the binomial expansion coefficients divided by 9. This gives the values i c_i a_i d_i --- ----- ----- ----- 0 1 1 1 1 1/2 5 5 2 1/8 8 6 3 1/16 4 2 4 5/128 7 4 5 7/256 4 9 6 21/1024 3 6 7 33/2048 3 3 8 429/2^15 3 9 9 715/2^16 7 2 etc. To more efficiently generate the terms of this sequence, notice that binomial expansion coefficients are the partial products (up to sign) of 1 1 3 5 7 9 11 13 15 17 19 21 23 - - - - -- -- -- -- -- -- -- -- -- ... 2 4 6 8 10 12 14 16 18 20 22 24 26 Since every odd factor appears in the numerator no later than it appears in the denominator, the denominators of the partial sums are necessarily pure powers of 2. Also, since the numerators are all odd, the denominator has exactly the powers of 2 cumulatively of the first k integers, given by the sequence 0,1,3,4,7,8,10,11,15,16,... whose terms can be generated by E(n) = n + E([n/2]). Since 1/2 = 5 mod 9, the effect of the denominators on the partial products mod 9 is to multiply by 5^E(n) (mod 9). The cycle of powers of 5 (mod 9) is 1,5,7,8,4,2,1,..., which a period of 6. Therefore, if we let p[j] with j=0,1,..,5 denote the array [1,5,7,8,4,2], the nth denominator contributes a factor of p[E(n) mod 6]. This already gives a non-periodic sequence, and explains why every expansion of one of these coefficients divided by 9 ends in a single repeating digit (which would not be the case if the coefficients could have factors other than 2 in the denominator). To properly account for the numerators as well as the denominators, we need to keep track of the cumulative powers of 3 in the fraction (taking numerator powers as positive and denominator powers as negative), since we are working modulo 9. Given the value of a_j representing the jth partial product (mod 9) and the cumulative powers of 3 in this product, and given the (j+1)th fractional factor N/D, we first factor out the powers of 3 from N and D, and increment/decrement the cumulative total accordingly, to give the new total p_3(j) and the fraction n/d where n and d represent the 3-free parts of N and D respectively. Then we can reduce these (mod 9) and take the reciprocal of d (mod 9) to form the multiplier. The products of these 3-free fractions gives a sequence f_j of positive non-zero integers (mod 9). Then the value of a_j is defined as / f_j if P_j = 0 / a_j = ( 3 f_j mod 9 if P_j = 1 \ \ 0 if P_j > 1 It's not hard to see that the sequence a_j contains infinitely many zeros, because a_{3^k - 1} = 0 for all k. Also, since a_{3^k} = k-1, it's clear that a_j attains arbitrarily large ranges consisting of nothing but zeros. This gives another demonstration of the fact that a_j (and therefore d_j) is not periodic. Here's a simple BASIC program for computing arbitrarily many values of a_j: DEFDBL A-Z DIM recip(8) FOR i = 0 TO 8: READ recip(i): NEXT i DATA 0,1,5,0,7,2,0,4,8 f = 5: sum3 = 0 FOR nn = 1 TO 5000 STEP 2 n = nn d = nn + 3 DO WHILE ((n MOD 3) = 0) n = n \ 3 sum3 = sum3 + 1 LOOP DO WHILE ((d MOD 3) = 0) d = d \ 3 sum3 = sum3 - 1 LOOP n = n MOD 9 d = d MOD 9 f = (f * n * recip(d)) MOD 9 IF sum3 = 0 THEN fout = f IF sum3 = 1 THEN fout = (f * 3) MOD 9 IF sum3 > 1 THEN fout = 0 PRINT nn, f, fout INPUT tttt NEXT nn Here are the first 502 values of a_j: 158474333717525000333666000 717858666282474000000000000 333666000666333000000000000 717858666525141000666333000 282141333717525000000000000 000000000000000000000000000 333666000666333000000000000 666333000333666000000000000 000000000000000000000000000 717858666525141000666333000 525717333474858000000000000 666333000333666000000000000 282141333474858000333666000 717858666282474000000000000 000000000000000000000000000 000000000000000000000000000 000000000000000000000000000 000000000000000000000000000 3336660006663330... Here are the corresponding 502 values of d_j, which are the digits that repeat for progresively smaller bursts in our original "mock-rational numbers": 156249639213759999639369999 213489369786249999999999999 639369999369639999999999999 213489369426519999369639999 786519639213759999999999999 999999999999999999999999999 639369999369639999999999999 369639999639369999999999999 999999999999999999999999999 213489369426519999369639999 426879639573489999999999999 369639999639369999999999999 786519639573489999639369999 213489369786249999999999999 999999999999999999999999999 999999999999999999999999999 999999999999999999999999999 999999999999999999999999999 6393699993696399... Interestingly, if we take these as the digits of a single number, it gives another example of what might be called a "mock-rational number", because it has arbitrarily long ranges of pure 9's, but infinitely many non-9 digits. In some respects, the most interesting sequence is f_j, which is the same as a_j above, except that we simply discard the effects of the powers of 3 in the binomial expansion coefficients. Here are the first 502 values of the f_j sequence, arranged in blocks of 27: 158474141717525525717282474 717858525282474474858141858 717858858858717858141858474 717858282525141717858141282 282141474717525525141858141 858474474474858717282717858 717858282525141474282717525 858474717141282141282717282 141525525525141858141858474 717858282525141141525474858 525717141474858282474525474 858474474474858474525474282 282141717474858282141858717 717858525282474474858141858 141525525525141282717282141 858474141717525282141858717 474282858525141282474525474 282141141141282717282717858 7178582825251411... This highlights the quasi-periodicity of the digits when taken in blocks of 3^k. I wonder if there are plane-tiling patterns of simple shapes that correspond to this quasi-periodic 3^k pattern. Each of the digits 1,2,4,5,7,8, appears (asymptotically) an equal number of times in this pattern. One way of visualizing this peculiar sequence is to assign each of the six possible digits to one of six directions in the plane, and then plot the visited locations reached by a "pseudo-random" walk produced by this sequence. The first 50 million digits lead to the locus of points shown below in blue. The red circle was the starting point, and the red dot was the ending point (i.e., the 50 millionth step). It's fascinating to watch this "pseudo-random" walk progress, noting that it carefully retraces its steps at various stages, which explains why it has branches that appear to lead nowhere. The figure below shows the orbit extended to cover the first 100 million digits, with the color changing every 5 million digits.

Return to MathPages Main Menu