Mock-Rational Numbers

In 1997 I posted the following in the sci.math newsgroup, under
the title of Schizophrenic Numbers:  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