Related Links (Outside this Site)

---

(2006-02-06)   Z_p :  The Ring of p-adic Integers
What integers become if they're allowed infinitely many radix-p digits.

Motivation :

The so-called "two's complement" binary numeration allows a representation of negative integers compatible with the rules of addition for positive numbers.  For example, consider the following sum, where the propagation of the bit "carried" from right to left cancels infinitely many bits from the first addend.

  ...111111111111111111111111111111010
+                                  110
=                                    0

As the  second  addend is the binary representation of the integer 6,  the  first  addend is the representation of -6...  A finite version of this is used in computers, where a predetermined number of bits make up a word, with the convention that the leftmost bit in a  word  stands for infinitely many like bits to the left.

Another example is the sum of three identical terms adding up to 1, in radix 5:

  ...131313131313131313131313131313132
+ ...131313131313131313131313131313132
+ ...131313131313131313131313131313132
=                                    1

If this makes any sense at all, the "integer" ...13131313132 should be "one third" of unity in radix 5.  Well, a sensible definition of such things can be given:

Definition & Basic Properties :

For technical reasons, the numeration radix is normally chosen to be a prime number  p.  Objects like the above are thus called  p-adic integers :

A  p-adic integer  is a sequence of residues  an  modulo  pn   (n > 0)   in which  an+1  is congruent to  an  modulo  pn.

The quantity  a_n  is called the  order-n residue  of such a p-adic integer.  An ordinary integer  N  (also called a  rational integer  in this context)  is a special case of a p-adic integer, whose order-n residue is simply  N mod pⁿ.

The sum (or the product) of two p-adic integers is defined as the p-adic integer whose order-n residue is the sum (or the product) of the order-n residues of both operands.  Modular arithmetic then establishes that p-adic integers form a ring.

The ring of p-adic integers is  not  countable.  (Each radix-p expansion of a real between 0 and 1 corresponds to a p-adic integer.  Most of those reals have only  one  such expansion, although a few have  two.)

Invertible p-adic Integers :

The primality of p ensures that there are no divisors of zero in this ring  (i.e., the product of two nonzero p-adic integers cannot be zero).  If  a₁  is nonzero, the p-adic integer  A = (a_n )  is said to be  invertible  because it has a reciprocal which is also a p-adic integer.  (HINT:  In this case, a_n  has an inverse modulo pⁿ.)

---

(2006-02-11)   Nomenclature: "Polyadic" Integers

When considering a composite radix (or one which is not assumed to be prime) some authors prefer to use the symbol  g  for the radix and talk about  g-adic  integers.  The usual Greek scientific prefixes may be used:

There's no need for a name when g is the power of a prime p (4, 8, 9, 16, 25 ... ) since the corresponding set is isomorphic to the one obtained for the prime  p.

---

(2006-02-09)   What if p isn't prime?  Dealing with "divisors of zero".
Decimals example appear in the next article, which may be read first.

With a prime radix p, the product of two nonzero p-adic integers is never zero  (this is what allows the construction of their quotients, the p-adic numbers).

With a composite radix (g) which is not the power of a prime (including decimal numeration) we have no such luck:  The existence of divisors of zero has to be kept in mind constantly  (in a ring, a "divisor of zero" is, by definition, a nonzero element whose product by some nonzero element is zero).  Here are explicit examples of divisors of zero among g-adic integers.

If the radix is not the power of a prime, it can be expressed as the product of two factors (p and q)  neither of which divides the other.  The following residue sequences then define two nonzero g-adic integers (u & v) whose product is 0:

u_n   =   q^pn mod (pq)ⁿ                     [ note that   u^p = u ]
v_n   =   p^qn mod (pq)ⁿ                     [ note that   v^q = v ]

Both of these are also introduced in the next article, with consistent notations, in the decimal case (p=2,q=5) using a more practical approach which makes it easy to establish that both sequences properly define pq-adic integers  (in the above sense).  We may  then  see that  uv = 0  although neither factor vanishes.

As demonstrated next in the decimal case (g=10) even simple quadratic equations may have "extra" solutions when there are divisors of zero around...

However,  x² = 0  doesn't have any nonzero solution in g-adic integers  (therefore,  (x-a)² = 0  has only one solution).  There are no  nilpotent  g-adics; a power of a nonzero g-adic integer is never 0  (HINT:  g^kn | x_n^k  implies  gⁿ | x_n ).

More generally,  P(x)Q(x)  and  P(x)^kQ(x)  have the same roots in g-adic integers  (HINT:  The latter divides [P(x)Q(x)]^k ).

---

(2006-02-09)   10-adic Integers   (decadic integers, or decadics)
Some recreational  decimal  arcana...  Fun with  divisors of zero.

Let's first consider a recursively-defined sequence of decimal residues  (5, 25, 625, 0625... A007185)  which determines a 10-adic (or decadic) integer u :

u₁ = 5             u_n+1   =   (u_n ) ²  mod 10 ⁿ⁺¹

An induction on  n  would show that  u_n+1  is, indeed, of the form   k 10ⁿ + u_n  (HINT:  2ku_n is a multiple of 10).  Also, since all of its successive decimal residues verify the following equation, so does  u  itself;  u is  idempotent.

x ²   =   x

In a unital ring, that equation may be factored  x (x-1) = 0.  So, if there were no divisors of zero, it would have only  two  solutions  (0 and 1).  Actually though, there are  four  10-adic solutions.  If  x  is a solution, so is (1-x).

0 = ...00000000000000000000000000000000000000000000000000000000000000000000000
1 = ...00000000000000000000000000000000000000000000000000000000000000000000001
u = ...62166509580863811000557423423230896109004106619977392256259918212890625
1-u = ...37833490419136188999442576576769103890995893380022607743740081787109376

To verify this, grab your calculator and punch in the last n digits of either nontrivial solution.  Square  that  and you obtain a number whose last n digits are unchanged.  Alternately, multiply the thing by its "predecessor"  (ending with either ...890624 or ...109375)  and you obtain a number ending with n zeroes.

Similarly, although the equation  x² = 1  can be factored as   (x-1)(x+1) = 0   it has   four  decadic solutions as well  (if  x  is a solution, so is -x )  namely:

1 = ...00000000000000000000000000000000000000000000000000000000000000000000001
1-2u = ...75666980838272377998885153153538207781991786760045215487480163574218751
2u-1 = ...24333019161727622001114846846461792218008213239954784512519836425781249
-1 = ...99999999999999999999999999999999999999999999999999999999999999999999999

The so-called  trimorphic  decadic integers are the solutions of  x ³ = x.  There are 9 of them, including  all  of the above:   0, 1, 1-2u, u-1, u, -u, 1-u, 2u-1, -1.

x²+1 = 0  has no solutions  (as there are none modulo 100)  but  x (x²+1) = 0  has two solutions  (beside 0)  in decadic integers :

v = ...06862593839649523223304553032451441224165530407839804103263499879186432
-v = ...93137406160350476776695446967548558775834469592160195896736500120813568

Each such solution verifies  x⁵ = x  (since it makes  x(x²+1)(x²-1)  vanish).  This suggests the following recursive definition of the order-n residues of  v  (a proper definition of a decadic integer, which "works" whenever v₁ is even).

v₁ = 2             v_n+1   =   (v_n ) ⁵  mod 10 ⁿ⁺¹

We may remark that   uv = 0   and   u = 1 + v ².  In the jargon of recreational mathematicians, the solutions of   x ⁵ = x   may be called pentamorphic  (these include all trimorphic decadics).  There are 15 pentamorphic decadic integers :

0 = ...00000000000000000000000000000000000000000000000000000000000000000000000
1 = ...00000000000000000000000000000000000000000000000000000000000000000000001
1-2u = ...75666980838272377998885153153538207781991786760045215487480163574218751
v = ...06862593839649523223304553032451441224165530407839804103263499879186432
-u-v = ...30970896579486665776138023544317662666830362972182803640476581907922943
u-v = ...55303915741214287777252870390779454884838576212137588152996418333704193
u-1 = ...62166509580863811000557423423230896109004106619977392256259918212890624
u = ...62166509580863811000557423423230896109004106619977392256259918212890625
-u = ...37833490419136188999442576576769103890995893380022607743740081787109375
1-u = ...37833490419136188999442576576769103890995893380022607743740081787109376
-u+v = ...44696084258785712222747129609220545115161423787862411847003581666295807
u+v = ...69029103420513334223861976455682337333169637027817196359523418092077057
-v = ...93137406160350476776695446967548558775834469592160195896736500120813568
2u-1 = ...24333019161727622001114846846461792218008213239954784512519836425781249
-1 = ...99999999999999999999999999999999999999999999999999999999999999999999999

If   xⁿ = x   for  some  integer  n  greater than 1, we may call  x  polymorphic.  A surprising fact is that  all  polymorphic 10-adic integers are pentamorphic...  The only polymorphic 10-adic integers are thus the 15 decadics listed above !

---

Let's now consider a factored  monic  quadratic equation in decadic integers:

(x - a) (x - b)   =   0

Since 4 is not a divisor of zero among decadic integers  (the reader may want to prove that an ordinary integer is never a divisor of zero among g-adic integers)  an  equivalent  of the above is obtained by multiplying by 4 and rearranging:

[ 2x - (a+b) ] ²   =   (a-b) ²

A  sufficient  condition for this to hold is that   2x = (a+b) + y (a-b)   where  y  is one of the four "square roots of unity" listed above  (i.e., 1, -1, 1-2u, 2u-1).  This yields four equations, in which we may cancel the factor 2 from both sides  (we may do so because 2 is not a divisor of zero among decadic integers).  This way, we obtain the following four solutions for x, which are usually distinct  (they're all equal if  a=b  and may yield only two values in special cases like  b = a+ku).

a ,         b ,         u a + (1-u) b ,         (1-u) a + u b

For example,  x² + x + 8 = 0  has no real solutions, but four decadic ones:

w = ...56389846001309162982116098126825854038627744656299971933409202632873031
u-1+(2u-1)w = ...54359819351433154332034684514552613602518954295770465438321601810486343
-u +(1-2u)w = ...45640180648566845667965315485447386397481045704229534561678398189513656
-1-w = ...43610153998690837017883901873174145961372255343700028066590797367126968

The above approach  fails  for quadratic equations whose leading coefficient is  not  invertible.  For example,  x (5x-1) = 0  has only one nonzero solution:

u/5 = ...12433301916172762200111484684646179221800821323995478451251983642578125

Note that  u  is divisible by any power of 5  (since  (u/5)ⁿ = u/5ⁿ )  just like
1-u  is divisible by any power of 2  (since  ((1-u)/2)ⁿ = (1-u)/2ⁿ ).

The nonzero (10-adic) solutions of   n x² = x   have been called  n-automorphic:

All those extra solutions of polynomial equations are entertaining but  unwieldy.  They are shunned by considering only the case of a  prime  radix  p.  Period.

---

(2006-02-06)   Q_p :  The Field of p-adic Numbers  (for any  prime  p )
p-adic numbers were invented in 1897 by Kurt Hensel (1861-1941).

The field of p-adic numbers is to the ring of p-adic integers what the field of rationals is to the ring of ordinary integers:  More precisely, the p-adic numbers form the quotient field of the ring of  p-adic integers.

Quotient Field:  In a ring where the product of two nonzero elements is never zero, consider couples with a nonzero second element...  We say that two such couples (a,b) and (c,d) are equivalent if ad = bc.  The equivalence-class of (a,b) is then called the quotient of a and b.  The set of all such quotients form the ring's  quotient field.  Modulo the equivalence defined above, the sum and product of (a,b) and (c,d) are respectively (ad+bc,bd) and (ac,bd).

Any nonzero p-adic integer is of the form  A p^m , where A is an invertible p-adic integer  (m being zero for invertible p-adic integers themselves).  The inverse of a noninvertible p-adic integer is thus the product of an invertible p-adic integer by a  negative  power of p.  Therefore, as quotients of p-adic integers,  all  p-adic numbers are simply of the following form, where  m  may  be negative:

¥
å	q i pi         where q i is in { 0, 1, 2 ... p-1 }
i = m

When it has infinitely many nonzero terms, this sum converges only according to a metric for which high powers of  p are  small.  Such a metric is presented below, which makes the field Q_p complete  (i.e., every Cauchy sequence converges in it).

Assuming q_m to be nonzero, the p-adic metric of the above p-adic sum is  p^-m.

---

(2006-02-17)   Elementary division of two p-adic numbers
It's just like ordinary long division, only backwards...

Let's give a step-by-step computation of the division of 1 by 7 in decadic integers.

1/7 = ...57142857142857142857142857142857142857142857142857142857142857142857143

At each of the steps listed below, we're faced with a "remainder".  A new digit must be found whose product by the divisor (7 in this example) has a last digit matching the last nonzero digit of the remainder (underlined).  This product is then subtracted from the remainder to yield a new remainder for the next step...

Remainder(s):
             1         21 = 7 x 3
...99999999980         28 = 7 x 4   <-+
...99999999700          7 = 7 x 1     |
...99999999000         49 = 7 x 7     |
...99999950000         35 = 7 x 5     |
...99999600000         56 = 7 x 8     |
...99994000000         14 = 7 x 2     |
...99980000000         28 = 7 x 4   --+

Quotient = ...2857142857142857143

Note that a satisfactory "next digit" may not always be found in decimal  (some decadic numbers do not have a multiplicative inverse)  but it's uniquely determined when the radix is prime, which is what we normally assume. 

When the radix is not a prime power, the above algorithm ambiguously divides a divisor of zero into one of its multiples  (if uv=0, dividing ux by u could yield many values, including x+yv for any y).

There's a  faster way to compute the multiplicative inverse of a p-adic integer, which is best understood in terms of the p-adic metric we introduce next.

---

(2006-02-06)   The p-adic Metric  | x |_p  of a Rational Number  x :
If a nonzero rational number is expressed in lowest terms as  x = pⁿ (a/b)  then, by definition,  | x |_p  =  p^-n.  (We also define  | 0 |_p = 0 .)

This valuation was introduced in 1913 by József Kürschák (1864-1933).

For example:     | ¹²/₇ | ₂  =  ¼       | ¹²/₇ | ₇  =  7       | ¹²/₇ | ₅  =  1

The rationals are not complete with respect to this metric.  The completion of the rationals with respect to the p-adic metric  (based on equivalence-classes of Cauchy sequences)  is simply the aforementioned  field of p-adic numbers.

This approach may be construed as an  analytic  definition of the p-adic numbers, which we've introduced  algebraically  as the quotient field of p-adic integers.

Metric and Topological Properties :

In a field or a ring, a  [scalar]  norm  (or valuation)  is a nonnegative function  |.|  vanishing only at zero, which is multiplicative  (i.e., |x.y| = |x|.|y|)  and obeys the  triangular inequality  |x+y| ≤ |x|+|y|.  The p-adic metric is such a norm.

A "vectorial" norm ||.|| on a vector space over a field endowed with a valuation |.| must satisfy the relation  ||x V|| = |x|.||V||.

A distance is a nonnegative symmetric function of two variables vanishing only when its arguments are equal, which satisfies the  triangular inequality:

d(x,z)   ≤   d(x,y) + d(y,z)

A distance is said to be  ultrametric  if it obeys the stronger inequality:

d(x,z)   ≤   max ( d(x,y) , d(y,z) )

The p-adic distance  (and/or the p-adic norm)  happens to be ultrametric.

Distances are commonly derived from norms  (although they need not be)  via the relation  d(x,y)=|x-y|  (or d(x,y)=||x-y||).  In that case, the terms "distance", "norm" and "metric" refer essentially to the same thing and are used somewhat interchangeably.

A  [closed]  ball of radius R is the set of all points that are at a distance at most equal to R from a given point.  With the p-adic metric, two balls of the same radius are either disjoint or identical !

---

(2006-02-19)   Quick and easy computation of a p-adic reciprocal :
A p-adic multiplicative inverse is the limit of a simple sequence, whose convergence is best analyzed in terms of the p-adic metric.

Consider a p-adic number in the standard form  a p^m, where a is an  invertible  p-adic integer,  its reciprocal (or multiplicative inverse) is  (1/a) p^-m, where  1/a  can be computed efficiently by successive approximations :

| 1/a - x₁ | _p  < 1         and         x_n+1   =   ( 2 - a x_n )  x_n

This is the simplest case (k = 2) of the following sequence of approximations  (for any positive integer k)  where the right-hand side is actually a polynomial function of  a  and  x_n  (since the minuend cancels the subtrahend's first term).

| 1/a - x₁ | _p  < 1         and         x_n+1   =   (1/a) - a^k-1 (1/a - x_n ) ^k

Let's analyze this algorithm.  First, since  a  is an invertible p-adic integer, the initial condition simply means that the last p-adic digit of our initial approximation  must  be correct.  For a small radix p, it's easy to make it so by building a table of reciprocals modulo p  (for a single shot, use trial and error).  For a large p, the multiplicative inverse of  a  modulo p can be obtained efficiently as a Bezout coefficient  (one method is to trace back the steps of Euclid's algorithm).

Now, observe that  (since  | a^k-1 |_p = 1)  the quantity  | 1/a - x_n |_p  gets precisely raised to the power of  k  with each iteration that increments  n.

Therefore, the number of correct digits is multiplied by  k  at each step...  In the simplest process  (k = 2, as presented first)  the number of correct digits doubles with each iteration, for little more than the cost of two modular multiplications !

If  a_n  and  b_n are the residues modulo  pⁿ  of  a  and its reciprocal, then :

1   =   a₁ b₁   mod  p               b _2n    =    ( 2 - a _2n  b_n )  b_n   mod   p²ⁿ

---

(2006-02-07)   Helmut Hasse's  Local-Global  Principle
What's true of reals numbers and of all p-adic fields is true of rationals.

The so-called  Hasse principle  is the statement that a particular type of equation (to be specified) has a solution over the rationals if and only if it has a real solution and a solution in p-adic numbers for any prime p.

In October 1920, Helmut Hasse (1898-1979) working under Kurt Hensel, the inventor of p-adic numbers,  showed that this principle holds for  quadratic  equations, not only for rational numbers and p-adic numbers (the Minkowski-Hasse theorem) but, more generally, for a "global" field and related "local" fields.

---

S N Roy from India (2006-05-08; e-mail)   Rotating Digits
Is there a positive integer which doubles in value when its leading digit is transferred to its right end?   [Like when 12345 becomes 23451.]

No.  Such an n-digit integer  (n>1)  would be of the form   d 10^n-1 + y  where  d  would be a single-digit number, and  y  an (n-1)-digit number such that:

2 (d 10^n-1 + y )   =   10 y  +  d
Which is to say:   [2´10^n-1-1] d   =   8 y   =   2³ y

Since the square bracket is an odd number,  2³  must divide the other factor (d).  Being a nonzero single-digit number, d  must be equal to 8.  Therefore, y is equal to the bracket and  cannot  be an (n-1)-digit number, as required.  (The bracket has n digits; it's equal to 19 for n=2, 199 for n=3, 1999 for n=4, etc.) 

Solutions may exist in  nondecimal  numeration.  The simplest example is in base 5, where  31 is twice 13  (in other words, sixteen is two times eight).

On 2006-05-08, S N Roy wrote:       [edited summary] Great help, and what a short response time!  I am amazed and grateful for the clarity of the exposition...  [continued below]

General discussion, for any base of numeration...

Let's use this opportunity to present a complete example of the mathematical discovery process, where a regular pattern is ultimately found by studying apparent chaos and generalizing particular cases.  For educational purposes, we've left in place  all  the scaffolds that we actually used in the process, including the numerical examples...

There are no solutions in base 2, since putting a nonzero bit rightmost yields an  odd  number, which can't be the double of anything.  There are no solutions either for bases of the form 2^k+2  (because of the argument given above in the decimal case, which corresponds to k=3).  As we'll see later, those bases are the only ones for which there are no solutions  (2, 3, 4, 6, 10, 18, 34, 66 ... A056469).

Now, observe that if we have a solution (like 13 in base 5) we obtain  another  solution by duplicating the digits in that solution several times consecutively:  13, 1313, 131313, etc.  Thus, beyond ordinary integers, another solution is clearly the periodic 5-adic integer ...13131313131313.  To any finite solution in base g would correspond such a periodic g-adic integer which is the solution of a  linear  equation in x, involving only one parameter, namely the "leading" digit  d  of the periodic pattern  (d = 1 in the above example)  irrespective of its length:

2 x   =   g x + d

With  g = 5,  we have only 5 possibilities for  d  (namely:  0,1,2,3,4).  Each yields a unique solution in 5-adic integers, namely 0, -1/3, -2/3, -1 and -4/3.  However, we may rule out  d = 0  if we're only interested in nonzero solutions.  Also, the larger leading digits  (3 and 4)  need not be considered at all, since they make the double of an ordinary integer have an additional digit...  Now, the case  d = 2  yields the pentadic number  -2/3 = ...31313131  for which "2" is not the leading digit of the period  (it's  nowhere  in the period).  Therefore, only the possibility  d = 1  remains, corresponding to the family of solutions already described  (a finite number of repetitions of the two digits "13")  which is thus established to include all solutions in base 5 for ordinary integers.

More generally, this g-adic approach reduces the problem in base g to the simple examination of only  (g-1)/2  g-adic cases.  Here are the results for small bases:

There's a two-digit solution (namely, ug+2u+1) only for bases g of the form  3u+2.

This two-digit pattern is the  only  solution when  g = 3´2^k+2  (i.e., 5, 8, 14, 26, 50, 98, 194, 386, 770, 1538, 3074, 6146, ...) because the argument given in the decimal case can be modified to prove that the leading digit  d  must be  2^k.

For g = 5 u + 2, we find 2 four-digit patterns:  (u,2u,4u+1,3u+1) and (2u,4u+1,3u+1,u) which are the only solutions if  u = 2^k.  (g = 7, 12, 22, 42...)

For g = 7 u + 2, there are 3 three-digit patterns:  (u,2u,4u+1),  (2u,4u+1,u) and (3u,6u+1,5u+1).  These are the only solutions if  u = 2^k.  (g = 9, 16, 30...)

For g = 9 u + 2, we find the aforementioned two-digit solution  (3u,6u+1) and 3 other six-digit patterns:  (u,2u,4u,8u+1,7u+1,5u+1), (2u,4u,8u+1,7u+1,5u+1,u), (4u,8u+1,7u+1,5u+1,u,2u).  That's all there is if  u = 2^k.  (g = 11, 20, 38, 74...)

With g = 11 u + 2, we have:  (u,2u,4u,8u+1,5u,10u+1,9u+1,7u+1,3u,6u+1)  and the rotations thereof which put a "multiple of u" in the lead...

Let's generalize all this to draw the complete picture:

Number of basic digit patterns whose value doubles with a left rotation  :

In base  g = (2m+1) 2k + 2,  there are  exactly  m  nonzero solutions, each corresponding to a leading digit  d = i 2k,  for i between 1 and m.

Proof :   First, we remark that an argument similar to the one we gave for the decimal case easily establishes that there cannot be any other leading digits:

We must solve   2 (d g^n-1 + y )  =  g y  +  d   for an integer  y < g^n-1.  This means that   [2 g^n-1-1] d  =  (2m+1) 2^k y   which implies  d = i 2^k  (since the square bracket is odd).  As the positive integer  i  is no more than the expression   (2m+1) (g^n-1-1) / [2 g^n-1-1]  it's between 1 and m.

Conversely, there can only be one solution for each such i,  corresponding to  x = -i/(2m+1)  which is indeed a (periodic) g-adic integer because g and 2m+1 are coprime.  The tricky part is to check that this potential solution always has the correct "leading digit".  To do this, we'll establish an interesting  explicit  formula for the digits in a "unit" pattern  (from which all others solutions are derived)...

Without loss of generality, we may assume  i = 1, since the g-adic integers for the other cases are obtained by multiplying this basic one by  i.

Incidentally, such products may feature a shorter period, as with the case  g = 11, i = 3  (this can't happen if  2m+1  is prime, though).

Let  u  be  2^k.  We have  g  =  (2m+1)u+2.  The leading digit (d) is u.  Twice the rightmost digit is thus either  u  or  g+u,  but the former is ruled out (even if k > 0) as we consider only  i = 1, which puts the  least possible power of two in the lead  (if a carry wasn't involved in the doubling of the rightmost digit, the pattern rotated right would be a solution with a smaller power of two in the leading position).  Therefore, the rightmost digit is  d₀ = (m+1)u+1.  The periodic pattern is:

d = d_n-1 = u + 0 ,     ...     d_j = a_j u + b_j     ...     d₀ = (m+1)u + 1

In this,  b_j  is either 0 or 1   (b_n-1  is zero and so is  b_n-2  unless  g = 5).  The key observation is that  a_j  is simply congruent to  2a_j+1   modulo (2m+1)  whereas  b_j  is equal to 1 if and only if  a_j  is greater than m  (yeah, same subscript  j ).

Using this formula, whose validity is established below, we may remark that the length  n  of this "unit" pattern (the longest in base g) is simply the multiplicative order of  2  modulo (2m+1)  which implies (incidentally) that the period  n  is at most equal to g-3.  Note that the reciprocal of 2 modulo (2m+1)  is the coefficient (m+1)  which appears in the expression of the rightmost digit  d₀.

Checking the validity of the above explicit formula :

Calling  c_j  the "carry" (0 or 1) injected at rank  j  in the doubling operation, we'll have proved that the value is doubled by the proper rotation of the digits if we establish the following relation  (valid for  j = 0  if we put  d_-1 = d  and c₀ = 0 ).

2 d_j + c_j   =   d_j-1 + g c_j+1

Since  c_j+1 = b_j  this very relation results from the following case-splitting:

If  a_j  is greater than m, then  a_j-1  is not:   b_j = 1 = c_j+1  and  b_j-1 = 0 = c_j
2 a_j u + 2 b_j + c_j   =   (a_j-1 + 2m+1 ) u + 2   =   a_j-1 u + b_j-1 + g c_j+1

Otherwise, b_j = 0 = c_j+1  and  b_j-1 = c_j.  Therefore:
2 a_j u + 2 b_j + c_j   =   a_j-1 u + b_j-1   =   a_j-1 u + b_j-1 + g c_j+1

The final check was easy, but  deriving  this simple formula was murder!  

On 2006-05-08, S N Roy wrote:       [continued from above] What about decimal numbers which the same transformation cuts in half?  I believe there are only 9 such numbers. Am I right?

In  periodic  decadic integers, there are clearly 10 solutions  (9 of which are nonzero) to the corresponding set of equations (where d is a single decimal digit):

x   =   2 (10 x + d)

The solutions for  x  are equal to the (nonzero) digit  d  multiplied by :

-2/19 = ...05263157894736842105263157894736842105263157894736842105263157894736842

The periodic decimal pattern  105263157894736842  yields a solution in ordinary integers, as do its first nine nonzero multiples  (there's no "overflow" because the pattern starts with a "1").  For each such 18-digit solution, we have infinitely many solutions of  18 n  digits, like  105263157894736842105263157894736842.

Again, since any solution in ordinary integers would yield a periodic 10-adic integer satisfying a linear equation of the above type, we  know  that there are no nonzero solutions in ordinary integers outside of those 9 infinite families.

The g-adic approach does solve this type of specific puzzles very quickly.  As illustrated above, it's also a solid foundation for general discussions.