(2006-02-06) What integers become if they're allowed infinitely many radix-p digits.
Motivation :
The so-called "two's complement" binary numeration allows a representationof 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 cancelsinfinitely many bits from the firstaddend.
...111111111111111111111111111111010+ 110= 0
As the second addend is the binary representationof the integer 6, the first addend mustrepresent -6. A finite version of this is used in computers,where a predetermined number of bits (e.g.,32 bits) make up aword, with the conventionthat the leftmost bit in a word stands for infinitely many like bits to the left.
Similarly, here are three identical terms which add up to 1, in radix 5:
If this makes any sense at all, "...13131313132" should thus be one third of unity in radix 5. Well, a sensible definition of such things exists:
Definition & Basic Properties :
Fortechnical 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 anmodulo pn (n > 0) in which an+1 is congruent to an modulo pn.
The quantity an 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 ofa p-adic integer, whose order-n residue is simply N mod pn.
The sum (or the product) of two p-adic integers is definedas the p-adic integer whose order-n residue is the sum (or the product) of theorder-n residues of both operands. Modular arithmetic then establishes thatp-adic integers form aring.
Invertible p-adic Integers :
The primality of p ensures that thereare no zero-divisors in this ring(i.e., the product of two nonzero p-adic integers cannot be zero). If a1 is nonzero,the p-adic integer A = (an) is said to be invertible because ithas a reciprocal which is also a p-adic integer. (: In this case,an has an inverse modulo pn.)
(2006-02-11)
When considering a composite radix (or one which is not assumed to be prime) someauthors prefer to use the symbol g for the radix and talk about g-adic integers. The usual Greekscientific prefixes may be used:
g (or p)
2
3
5
6
7
10
11
g-adic
dyadic
triadic
pentadic
hexadic
heptadic
decadic
hendecadic
There's no need for a name when g is thepower of a prime p (4, 8, 9, 16, 25 ... ) since the corresponding set is isomorphic to the one obtained for p.
When the value of p is irrelevant, it would be better to speakof polyadic integers rather than p-adic integers (or also polyadic numbers rather than p-adicnumbers). Likewise, we speak of polygons rather than n-gonsunless the value of n is explicitely used in a neighboring expression.
So far, mathematicians have ignored this proper usage. Unfortunately, I am still occasionally guilty of that myself: A propertitle for this collection of articlesshould have been Polyadic Arithmetic.
(2006-02-09) . Decimal examples appear in thenext article,which may be read first.
With a prime radix p, the product of nonzerop-adic integers is neverzero (that's what makes the construction ofthep-adic numbers possible).
With a composite radix (g) which is not the power of a prime(includingdecimal numeration)we have no such luck: The existence of zero-divisors has to be kept in mind constantly (in a ring, a zero-divisor is,by definition, a nonzero element whose product by some nonzero element is zero). Here are explicit examples of zero-divisors among g-adic integers.
If the radix is not the power of a prime, it can be expressedas the product of two factors (p and q) neither of which divides the other. The following residue sequencesthen define two nonzero g-adic integers (u & v) whose product is 0:
un = qpn mod (pq)n [ note that up = u ] vn = pqn mod (pq)n [ note that vq = v ]
Both of these are also introduced in thenext article,with consistent notations, in the decimal case (p=2,q=5) usinga more practical approach which makes it easyto establish that both sequences properly define pq-adic integers (in theabove sense). We may then see that uv = 0 although neither factor vanishes.
As shownnext in the decimal case (g=10)even simple quadratic equations may have "extra" solutions when there arezero-divisors around...
x2 = 0 never has anynonzero solution in g-adic integers (thus, the equation (x-a)2 = 0 has only one solution). There are no (nonzero) nilpotent g-adics;a power of a nonzero g-adic integer is never 0 (: gkn | xnk implies gn | xn ).
More generally, P(x)Q(x) and P(x)kQ(x) have the same roots in g-adic integers (: The latter divides [P(x)Q(x)]k ).
(2006-02-09) (decadic integers, ordecadics) Some recreational decimal arcana... Fun with zero-divisors.
Let's consider a recursively-defined sequence of decimal residues (5, 25, 625, 0625...A007185) which determines a 10-adic (ordecadic) integer u :
u1 = 5 un+1 = (un) 2 mod 10 n+1
An induction on n would show that un+1 is, indeed, of the form k 10n + un (: 2kun is a multiple of 10). Also, since all of its successive decimal residues verify the followingequation, so does u itself; u is idempotent.
x 2 = x
In aunital ring,that equation factors as x (x-1) = 0. So, if there were nozero-divisors,it would have only two solutions (0 and 1). Actually,there are four 10-adic solutions. If x is a solution, so is (1-x). (A016090)
To verify this,grab your calculator and punch in the last n digits of either nontrivial solution. Square that to obtain a numberwhose last n digits are the same. Alternately, multiply the thing by its "predecessor" (ending witheither ...890624 or ...109375) and you obtain a number ending with n zeroes.
Similarly, although the equation x2 = 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:
The decadic solutions of x 3 = x. are calledtrimorphic. There are 9 of those, including all of the above: 0, 1, 1-2u, u-1, u, -u, 1-u, 2u-1, -1.
x2+1 = 0 has no solutions (as there are nonemodulo 100) but x (x2+1) = 0 has two solutions (beside 0) in decadic integers :
Each such solution verifies x5 = x (as it makes x(x2+1)(x2-1) vanish). This suggests the following recursive definition of the order-n residuesof v (a proper definition of a decadic integer, which "works" wheneverv1 is even).
v1 = 2 vn+1 = (vn) 5 mod 10 n+1
We may remark that uv = 0 and u = 1 + v 2. In the jargon of recreational mathematicians, the solutions of x 5 = x are calledpentamorphic. There are 15 pentamorphic decadic integers,including alltrimorphic decadics:
If xn = x for some integer n greater than 1, x is called polymorphic. Surprisingly, 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 toprove that an ordinary integer is never a zero-divisor amongpolyadic integers) an equivalent of the above is obtained by multiplying into 4 and rearranging:
[ 2x - (a+b) ] 2 = (a-b) 2
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 2from both sides (we may do so because 2 is not a divisor of zeroamong 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 valuesin special cases like b = a+ku).
a , b , ua + (1-u)b , (1-u)a + ub
For example, x2+ x + 8 = 0 has no real solutions,but four decadic ones:
The above approach fails for quadratic equationswhose leading coefficient is notinvertible. For example, x (5x-1) = 0 has only one nonzero solution:
Note that u is divisible by any power of 5 (since (u/5)n = u/5n ) just like 1-u is divisible by any power of 2 (since ((1-u)/2)n = (1-u)/2n ).
To solve the equation x (5x-1) = 0 we may remarkthat it's equivalent to 5x (5x-1) = 0 (as 5 isn't a decadic divisor of zero). So, we have 5x = y where y is one of the 4 solutions (0,1,u,1-u) of theaforementioned equation y (y-1) = 0. As only two of those are divisible by 5, the originalequation only has the two advertised solutions (0 and u/5). In therealm of decadic numbers (introducedbelowfor the usual case of a prime radix) 5 has a reciprocal (namely: 0.2) and x (5x-1) = 0 does have 4 solutions:
The nonzero (10-adic) solutions of n x2 = x are called n-automorphic. If defined, each expression 1/n, u/n and (1-u)/n gives one of those. That's 0, 1 or 3 n-automorphic 10-adic integers, depending on what (n,10) is:
(n,10)
1
2
5
10
n-automorphic decadic integers
1 / n u / n (1-u) / n
(1-u) / n
u / n
none
In thebroader realm of decadic numbers (allowing finitely many digits to the right of the decimal point)every nonzero [ordinary] integer n has a reciprocal (1/n) and the equation n x 2 = x always has 4 distinct solutions:
0 , 1/n , u/n and (1-u)/n
Such extra solutions to polynomial equations are entertaining but unwieldy. They are shunned by considering only the case of a prime radix p. Period.
(2011-09-15) 10-adic equations have inspired many recreational mathematicians...
Theabove can be used to make sense of the following pattern:
This example iscredited to the mathematical columnistJ.A.H. Hunter (1902-1986). It's just an embodiment of one decadic solution to the equation:
x = 2 x 2 - 1
That equation has two solutionsmodulo 10 (namely, 1 and 7) whichseedtwo different solutions in decadic integers, namely 1 and anontrivial solution h consistent with the above. In the broader context of decadic numbers, there are two other solutions... (although p-adic numbers arenormally introduced only whenthe radix p is prime ). The 4 solutions are:
Although h may have presented the best recreational valuefor J.A.H. Hunter, (½ - h) is a close second that's easily overlooked! For example:
(2006-02-06) p-adic numbers were invented in 1897 byKurt Hensel (1861-1941).
Thefield of p-adic numbers is to thering of p-adic integers whatthe field of rationals is to the ring of ordinary integers: More precisely, the p-adic numbers form thequotient field of the ring of p-adic integers.
Any nonzero p-adic integer is of the form A pm ,where A is an invertible p-adic integer (m being zero for invertible p-adic integers themselves). The quotient construct introduces inverses for power of p which we may call negative powers of p.
The inverse of a noninvertible p-adic integer is thus the product of an invertiblep-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 whereq 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 presentedbelow,which makes the field Qp complete (i.e., everyCauchy sequence converges in it).
Assuming qm is nonzero, the p-adic metric of the above p-adic sumis p-m.
(2006-02-17) It's just like ordinarylong division, only backwards...
Let's give a step-by-step computation for the decadic division of 7 into 1:
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 yielda new remainder for the next step...
Remainder(s):1 21 = 7 x 3...99999999980 28 = 7 x 4 <-+...999999997007 = 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 = ...2857143 = ...2857142857142857143
By convention, a string of digits with avinculum over it stands forinfinitely many repetitions of that string.
Note that a satisfactory "next digit" may not always be foundin decimal (zero-divisors, like the multiples of theaforementioned u and v,do not have a multiplicative inverse). However, it's uniquely determined when the radix is prime,which is what we normally assume.
There's a faster way to computethe reciprocal of a p-adic integer, which isbest understood in terms of the p-adic metric that we'll introduce later.
(2012-10-29) For p-adic and rational numbers alike.
As examplified in theprevious section,an overbar may be used in the expansion of p-adic numbers tostand for infinitely many repetitions of the string of digits it binds.
This is exactly the same meaning as what istraditionally usedfor ordinary fractions. We merely distinguish between p-adic numbers andrational numbers by putting an ellipsis (...) to the leftof the repeated strings in the former case. An ellipsis to the right of the overbaris optional for rational numbers, but's is recommended (for readability) in any discussion, like this one, where p-adics and rational numbers coexist. Examples:
1/7 = ...2857143 1/7 = 0.142857...
An overbar may straddle the decimal point:
100/7 = 14.2857...
The only pocket calculators I've found which display results with overbarsare Casio'sES calculators. Casio has decided to avoid overbars straddling the decimal point, at the cost of not always displaying the shortest possible expression. In our last example, the result displayed by Casio is therefore:
100/7 = 14.285714...
To save space, the pocket calculators don't display the terminating ellipsis, whichis redundant in a context where p-adic numbers are ruled out...
The rationals are notcomplete with respect to this metric. The completion of the rationals with respect to the p-adic metric (based on equivalence-classesof Cauchy sequences) is the aforementioned field of p-adic numbers.
This approach may be construed as an analytical definition of the p-adic numbers,which we've already introduced algebraically as thequotient field of the p-adic integersand formally as objects expressed inpositional numeration of radix p if infinitely many digits are allowed to the left of the radix pointbut only finitely many nonzero digits to the right of it...
Metric and Topological Properties :
In a field or a ring, a scalar norm (orvaluation) is a nonnegative [real] function |.| vanishing only at zero, which is multiplicative (i.e., |x.y| = |x|.|y|) and obeys the triangular inequality |x+y| ≤ |x|+|y|. The above p-adic metric is such a norm.
Adistance is a nonnegative [real] symmetricfunction of two variables vanishing onlywhen 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.
A [closed] ball of radius R is the set of all points that areat a distance at most equal to R from a given point. With the p-adic metric, two balls of the same radius areeither disjoint or identical !
In 1916,Alexander Ostrowski(1893-1986) showed that there are only three ways to define an absolute value on the fieldof rational numbers:
The trivial absolute value (0 for a zero argument, 1 otherwise).
Raising to a positive exponent less than or equal to unity the standard absolute value (itself equal to the nonnegative number that match eitherthe argument or its opposite).
Raising to the power of a fixed positive exponent somep-adic metric.
(2006-02-19) A p-adic multiplicative inverse is the limit of a simple sequence,whose convergence is best analyzed in terms of thep-adic metric.
Consider ap-adic numberin the standard form a pm, wherea is an invertible p-adicinteger, its reciprocal (multiplicative inverse) is (1/a) p-m, where 1/a can be computed efficientlyby successive approximations:
| 1/a - x1 | p < 1 and xn+1 = ( 2a xn) xn
This is the simplest case (k = 2) of the following sequence of approximations (for a positive integer k) where the right-hand side is actually a polynomial functionof a and xn (theminuend cancelsthesubtrahend's first term).
| 1/a - x1 | p < 1 and xn+1 = (1/a) -ak-1(1/a - xn) k
Let's analyze this algorithm. First, since a isaninvertible p-adic integer, the initial conditionsimply 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 reciprocalsmodulo p (for a single shot, use trial and error). For a large p, the multiplicative inverse of a modulo p can beobtained efficiently as aBezout coefficient (one method is to trace back the steps of Euclid's algorithm).
Now, observe that (since |ak-1|p= 1) the quantity | 1/a - xn |p gets precisely raised to the power of k with each iterationthat increments n.
Therefore, the number of correct digitsis multiplied by k at each step... In the simplest process (k = 2, as presented first) thenumber of correct digits doubles with each iteration,for little more than the cost of two modular multiplications !
If an and bn are the residues modulo pn of a and its reciprocal, then :
1 = a1b1 mod p b 2n = ( 2a 2n bn) bn mod p2n
(2012-10-30) Rational numbers also exist as p-adic numbers.
Let's go back to previous "coincidences" that I promised to elucidate:
In the (ordinary) realm of rational numbers, the decimal expansion of 1/q (where q is a positiverational integer) form a periodic string whoseelementary period is an integer P of n digits. n is the smallest positive integer which makes 10n-1 a multiple of q. UsingCarmichael's lambda function, we may state that the length n is a divisor of (q) which itself divides (q), the Euler totient of q. The period P is then given by:
P = (10n-1)/ q which does yield: 1/ q = P/ (10n-1) = 0.P...
On the other hand, in the realm of decadic integers ...P stands for:
P ( 1 + 10n + 102n + 103n + 104n + ... )
The decadic metric makes the bracketed series converge to 1/(1-10n ).
-1/ q = P/ (10n-1) = ...P
(2011-09-20) How to turn a root modulo p into a p-adic root.
Example: Solving x2 + 1 = 0 in p-adic integers.
That equation has a root modulo an odd prime p if and only if p is congruent to 1 modulo 4. One way to establish this is to partition all p-1 nonzero elements intosets of the form {x,-x,1/x,-1/x}.
There are k such disjoint sets with 4 distinct elements and one set consisting of thetwo roots {-1,+1} of x2-1. There may also be anotherset of two elements, formed by the roots of x2+1. If p-1 is 4k+4, such roots must therefore exist, otherwise (p-1 = 4k+2) they cannot.
In particular, the roots modulo 5 of x2+1 are the two residues 2 and 3. The general reasoning presented below shows that one root is the pentadic integer i whose residue in modulo 5n is iteratively defined asfollows (the other pentadic root is, of course, -i):
i1 = 2 in+1 = { in + [ (in) 2 + 1 ] } mod 5 n+1
In base thirteen, the two roots are ...A67B41505474036C688101550155 and ...26518B7C7858C960644BCB77CB78. (the letters A, B, C stand, respectively, for the digits ten, eleven, twelve).
The first of the above is called the "ABC" 13-adic integer, becauseof the somewhat unlikely fact (a priori, one chance in 27) that, at some precision (here, 28 digits) A, B and Cappear only once and in alphabetical order. Theprobability that this happens at a precision of 28 digitswith a prescribed (nonalphabetical) rightmost digit isless than one chance in 400 (precisely, C(27,3) 1024/1327 ). The pattern holds for 5 more digits (there was less than 1 chance in 892.7 for that):
ABC = ...6A69555A67B41505474036C688101550155
That 13-adic integer may be defined as follows:
i1 = 5 in+1 = { in + 9 [ (in) 2 + 1 ] } mod 13 n+1
To prove that this is a convergent definition of a 13-adic integer, we only needto observe that the right-hand-side of the recurrence is unchanged if we replace in by in + k 13n for any k. Indeed, that substitution transforms the above curly bracket into:
in+1 = in + 9 [ (in) 2 + 1 ] + k 13n[ 1 + 18 in + k 13n]
The second bracket is divisible by 13, since it's congruent, modulo 13, to:
1 + 18 i1 = 1 + 18 . 5 = 91 = 7 . 13
More generally, if i1 is a root modulo p of x2+1,the n-th residue of a root of that polynomial in p-adic integers can berecursively defined as follows:
in+1 = { in + b [ (in) 2 + 1 ] } mod p n+1 where b = bezout (-2 i1 , p )
Needless to say that the p-adic integer so defined verifies the following equation,so that the bracket (our original equation) does vanish:
x = x + b [ x2 + 1 ]
Conversely, any p-adic root is obtained that way. So, there are as many p-adicroots as there are roots modulo p (namely 0 or 2, as discussed above).
(2012-08-18) There are no (nontrivial) continuous linear maps between the two.
Thefield of the rational numbers (consisting of ratios of ordinary integers) is a subfield of the field of real numbers. is also a subfield of the field Qp of thep-adic numbers introduced above. Both of those can also be consideredvector spacesover the field (i.e., rationals are scalars, nothing else is). Thedimension of either space is infinite.
With respect to the scaling by rationals, let's consider a linear function f from the p-adic numbers to the reals. As zero is the image of zero by any linearfunction, continuity about zero means that:
> 0, > 0, xQp , ( | x |p < ) ( |f (x) | < )
This fails with x = y pn for a large enough n, unlessf (y) = 0. HINT:
| x |p = | y |p/ pn and f (x) = pnf (y) (by linearity over )
Therefore, f (y) = 0 for every p-adic number y.
Conversely, the continuity at 0 of a linear function g from the reals to the p-adic numbers means that:
> 0, > 0, x , ( | x | < ) ( |g (x) |p < )
By considering x = y / pn for a large enough n, we can establish that g (y) = 0 for every real y. Here is a summary of the awful truth:
Any linear map (with respect to the rationals) between the p-adic numbers and the real numbers is either discontinuous everywhereor zero everywhere.
We're using the fact that a linear map on a normed space is continuous atany prescribed point if and only if it's continuous at point zero (the origin).
(2006-02-07) What's true of reals numbers and ofall p-adic fields is true of rationals.
A given type of equation is said to obey the Hasse principle when everyinstance has a solution over the rationals if and only if it has a real solutionand a solution in p-adic numbers for any prime p.
In October 1920, Helmut Hasse (1898-1979)working underKurt Hensel,the inventor of p-adic numbers, showed that this principle holds for quadratic equations, not only for rational numbers and p-adic numbers but also for any "global" fieldrelated tolocal fields (the Hasse-Minkowski theorem).
If something like that was true of cubic equations, we could make mincemeatof the Birch and Swinnerton-Dyer conjecture forwhich the Clay Mathematical Institute has posted a bounty of one million dollars!
S N Roy from India (2006-05-08; e-mail) Is there a positive integer which doubles in value when its leading digitis transferred to its right end? [Like when 12345 becomes 23451.]
No. Such an n-digit integer (n>1) would be of the form d 10n-1 + y where d would be a single-digit nonzero number,and y an (n-1)-digit number such that:
2 (d 10n-1 + y ) = 10 y + d Which is to say: [210n-1-1] d = 8 y = 23 y
Since the square bracket is an odd number, 23 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 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).
Great help, and what a short response time! I am amazed and grateful forthe clarity of the exposition... [continuedbelow]
General discussion, for any base of numeration...
There are no solutions in base 2, sinceputting 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 2k+2 (because of the argument given above in the decimal case,which corresponds to k=3). As we'll seelater, those bases are theonlyones 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 byduplicating 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 integerwhich is the solutionof 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 nonzerosolutions. Also, the larger leading digits (3 and 4) need not be consideredat 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, correspondingto the family of solutions already described (a finite number of repetitions of the two digits "13") which is thus establishedto include all solutions in base 5 for ordinary integers.
More generally, this g-adic approach reduces the problem in base g to the simple examinationof only (g-1)/2 g-adic cases. Here are the results for small bases:
Integers which are doubled by rotating their digits one place to the left.
Base
Elementary Digit Patterns (each may be duplicated several times)
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 = 32k+2 (i.e., 5, 8, 14, 26, 50, 98, 194, 386, 770, 1538, 3074, 6146, ...) because the argument given in thedecimal casecan be modified to provethat the leading digit d must be 2k.
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 solutionsif u = 2k. (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 solutionsif u = 2k. (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 = 2k. (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 thereofwhich 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.
First, we remark that an argument similar to the one we gave for thedecimal case easily establishes that there cannot beany other leading digits:
Conversely, there can only be one solution for each such i, corresponding to x = -i/(2m+1) which is indeeda (periodic) g-adic integer because g and 2m+1 arecoprime. The tricky part is to check that this potential solutionalways has the correct "leading digit". To do this, we'll establish an interesting explicit formulafor the digits in a "unit" pattern (from which all others solutions are derived)...
Without loss of generality, we may assume i = 1, sincethe g-adic integers for the other cases are obtained by multiplying this basic oneby i.
Let u be 2k. 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 involvedin the doubling of the rightmost digit, the pattern rotated right would bea solution with a smaller power of two in the leading position). Therefore, the rightmost digit is d0 = (m+1)u+1. The periodic pattern is:
d = dn-1 = u + 0 , ... dj =aju +j ... d0 = (m+1)u + 1
In this, j is either 0 or 1 (n-1 is zero and so is n-2 unless g = 5). The key observation is that aj is simply congruentto 2aj+1 modulo (2m+1) whereas j isequal to 1 if and only if aj 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 d0.
Checking the validity of the above explicit formula :
Calling cj the "carry" (0 or 1) injected at rank j inthe doubling operation, we'll have proved that the value is doubled by the properrotation of the digits if we establish the following relation (valid for j = 0 if we put d-1 = d andc0 = 0 ).
2 dj + cj = dj-1 + g cj+1
Since cj+1 =j this very relation results from the following case-splitting:
If aj is greater than m, then aj-1 is not: j = 1 = cj+1 and j-1 = 0 = cj 2aju + 2j + cj = (aj-1 + 2m+1 ) u + 2 = aj-1 u +j-1 + g cj+1
Otherwise,j = 0 = cj+1 and j-1 = cj. Therefore: 2aju + 2j + cj = aj-1 u+j-1 = aj-1 u+j-1+ g cj+1
The final check was easy, but deriving this simple formula was murder!
On 2006-05-08,S N Roy wrote: [continued fromabove]
What about decimal numbers which the same transformation cuts in half? I believe there are only 9 such numbers. Am I right?
In periodicdecadic integers, there are clearly 10solutions (9 of which are nonzero) to the corresponding set of equations (where d is a singledecimal digit):
x = 2 (10 x + d)
The solutions for x are equal to the (nonzero)digit d multiplied by :
The periodic decimal pattern 105263157894736842 yields a solution in ordinaryintegers, as do its first nine nonzero multiples (there's no "overflow" becausethe pattern starts with "10").
For each such 18-digit solution, we have infinitely manysolutions of 18 n digits, like 105263157894736842105263157894736842. (A217592)
Again, since any solution in ordinary integers would yield aperiodic 10-adic integer satisfying a linear equation of the above type,we know that there are no nonzero solutions in ordinary integersoutside 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.
(2012-10-28) Epilog:
In April 2009, N.J.A. Sloane et al. (seeA146088) considered the related problem of doubling a decimal number by rotating it tothe right (12345 would become 51234).
The solutions of that problem are clearly obtained by rotatingour 9 previous patterns one place to the left, except when this yields a leading zero digits (052631578947368421 is disallowed).
Therefore, there are only eight 18-digit solutions (and thus only 8 infinite families of solutions obtainedby repeating each such decimal pattern any number of times).
Sorting those in increasing order hides some of the regularitywhich we found in the "reverse" problem discussed above (arguably, the better one). The consecutive digits 2,3,4,5,6,7,8,9 do appearconsecutively in that sorted list but they are now in the leftmostposition and "1" is missing (both remarks are trivial with the way we obtained thesolutions, they might not be with a more "direct" approach). Again, the true regularity comes from the decadic discussion. Obtaining decimals from decadics destroys the utter simplicity.
(2012-10-29) For example 102564 becomes 025641 which is exactly one fourth of it.
For any k, the solutions have the structure, discussedabove for k = 2. The decadic equations to solve, for any digit d from 0 to 9, are:
x = k (10 x + d)
Each of the 10 decadic solutions, x = -d k / (10k-1) yieldssolutions in rational integers (infinitely many for thenonzero values of d).
If P is the decadic period of -k/(10k-1) (which is the decimal period of the ordinary fraction k/(10k-1) incidentally) then the first 10 solutions are the first ten multiples of P (nP for n between 0 and 9). These form ten families of solutions: The singleton {0} and 9 infinite families obtained by repeatingumber of times" may, arguably, include "zero times"which yields the empty string... The empty string is the proper decimalrepresentation of zero if you strictly enforce the rule that 0 cannot be a leading digit. Needless to say that we usually use a single "0" digit when there's a need towrite something down. However, some decimal or binary computer representations of long integers mayaccurately reflect the fact that zero has no significant digits (and/or zero significant bits).
For example, the numbers that are divided by 4 in a single left-rotation of their decimal digitsinclude 0, the number 102564 multiplied into 1,2,3,4,5,6,7,8,9 and any of those multipliedinto (106k-1)/(106-1) for any positive k. So, all the solutions are easy to derive from the smallest positive one, tabulated below:
n-digit Decimal Period P of k/ (10k-1) = P/ (10n-1)
The table is infinite. It goes on (k=11) with the 108-digit period of 11/109:
Then we have:
12/119 = 0.100840336134453781512605042016806722689075630252... 13/129 = 0.100775193798449612403... 14/139 = 0.1007194244604316546762589928057553956834532374... etc. (The next one has 148 digits.)
The length (n) of the decimal period of k/ (10k-1) is A128858(k):
-
and Q are discontinuous at every point.
