Geometric Dot Products and Digit Reversals

For any fixed integer b greater than 1, and any positive integer
N, let N_j denote the greatest integer less than or equal to N/b^j.
For example, if b=10 and N=3781925 we have

              j     N_j
             ---  -------
              0   3781925
              1   378192
              2   37819
              3   3781
              4   378
              5   37
              6   3

Let {N,b} denote the vector with these components, in increasing
order.  For the example given above, with b=10 and N=3781925, we
have the vector

  {3781925,10}  =  [3, 37, 378, 3781, 37819, 378192, 3781925]

On particularly simple case, for any base b, is the number N = b^k,
which has the representation 100..000 (k zeros) in the base b.  In
this case the vector is just the k-term geometric series

          {b^k,b}  =  [1, b, b^2, b^3, ..., b^k]

If we take the dot product of this geometric vector with itself we
have

  {b^k,b}.{b^k,b}  =  1  +  b^2  +  b^4  +  b^6  +  ...  +  b^2k


                            (b^2)^(k+1) - 1        b^(2k+2) - 1
                       =    ---------------   =    ------------
                                b^2 - 1               b^2 - 1

which of course is just the Euclidean formula for the kth partial sum
of the geometric series in b^2.  Suppose we replace one of the vectors
on the left hand side with a more general vector of the form {N,b}
for an arbitrary integer N with k+1 digits in the base b.  It's not 
hard to show that the dot product is given by the formula


  {N,b}.{b^k,b}  =  N_k + N_(k-1) b + N_(k-2) b^2 + ... + N_0 b^k

                     N b^(k+2)  -  N~
                 =   ----------------
                         b^2 - 1

where N~ is the digit-reversal of the base-b representation of N.

To illustrate, let's take N=3781925 with b=10.  In this case we have
k=6 (because N has 7 decimal digits), and the dot product gives the 
sum

 {3781925,10}{10^6,10}

 = 3 + 370 + 37800 + 3781000 + 378190000 + 37819200000 + 3781925000000

 =  3820126209173

Notice that the places of the digits in the summands overlap (by
arbitrarily large spans for large values of k), so this is a non-
trivial sum, with carries, rather than just a juxtaposition of
digits.  Now, the base-10 digit reversal of this N is 5291873, so
the generalized geometric formula for this dot product is

     3781925 10^8  -  5291873
     ------------------------  =  3820126209173
            10^2 - 1

This is a nice little application of the base-b digit reversal.

Return to MathPages Main Menu
Сайт управляется системой uCoz