|
When looking at mathematical sequences some might find cycles in these
sequences only interesting when whole numbers return again and again
after a fixed number of terms (the loop length).
In practice, however, such sequences are the exceptions.
What sequences usually show is a digital cycle in which only the
final digits are repeated in loops of, say, 4, 6, 8, 12 or 20 terms long,
dependent on the numeral system used.
A sequence of whole numbers may even display a final digit cycle in one
numeral system and an initial digit cycle in another.
(For an example, see my
The Powers of Two in Number Theory, which
also discusses digit sum cycles in the different notations of the powers of
2.)
In sequences in which the numerical notations grow longer the number of
final digits which become part of a cycle will also grow larger.
In a binary system, for instance, a 3-term final one-digit
cycle will then be superceded by a 6-term final two-digit
cycle, this one in turn by a 12-term final three-digit cycle, this one in
turn by a 24-term final four-digit cycle, this one in turn by a 48-term
final five-digit cycle, and so on and so forth.
Of course, the five-digit cycle was there from the very beginning, but it
will take some time to detect it.
Now, almost everyone familiar with numbers in the base-10, denary or
'decimal' system will know that a number of which the final digit is 0 is
divisible by 10 (and 5), that a number of which the final digit is 5 (or 0)
is divisible by 5 and that an even number (ending in 0, 2, 4, 6, or 8) is
divisible by 2.
These facts demonstrate that single final digits do or can contain
information, regardless of the total length of the number in digits.
But what other information about divisibility do or can final digits
contain, not only in the denary system, but also in numeral systems with a
different base number?
The following table should give an answer to this question for 10 and the
smaller base numbers among natural numbers:
FACTUAL INFORMATION CONTAINED
IN FINAL DIGIT(S)
| SYSTEM |
WHOLE NUMBER
DIVISIBLE BY |
| 2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| Base 10 |
0, 2, 4,
6, 8 |
- |
00, 04,
..., 96 |
0, 5 |
- |
- |
000, 008,
..., 992 |
- |
0 |
| Base 9 |
- |
0 |
- |
- |
- |
- |
- |
0 |
- |
| Base 8 |
0, 2,
4, 6 |
- |
0, 4 |
- |
- |
- |
0 |
- |
- |
| Base 7 |
- |
- |
- |
- |
- |
0 |
- |
- |
- |
| Base 6 |
0, 2, 4 |
0, 3 |
- |
- |
0 |
- |
- |
- |
- |
| Base 5 |
- |
- |
- |
0 |
- |
- |
- |
- |
- |
| Base 4 |
0, 2 |
- |
0 |
- |
- |
- |
00 |
- |
- |
| Base 3 |
- |
0 |
- |
- |
- |
- |
- |
00 |
- |
| Base 2 |
0 |
- |
00 |
- |
- |
- |
000 |
- |
- |
Note: in the base-10 system any number of which the last two digits
interpreted as a number in itself (4, 8, 12, 16 until 96) are divisible by
4 is itself divisible by 4, because 100 and multiples of 100 are divisible
by 4; and any number of which the last three digits interpreted as a
number in itself (8, 16, 24 until 96, and 104 until 992) are divisible by
8 is itself divisible by 8, because 1000 and multiples of 1000 are
divisible by 8.
You may wonder why one cannot even see whether a number is odd or even in
the base-3, the base-5, the base-7 and the base-9 systems, the odd-numbered
ones.
To explain this we should first have a closer look at the final one-digit
cycles in the sequences which are used in the place-value notations of
numbers.
They are of the following form, in which a is a coefficient and
b the base number:
xn = a·bn,
n≥0, b0 = 1, b1 = b
The positional notation itself turns the sequence into a finite series
with a separate coefficient for each power term, while putting the largest
quantity on the left, the smaller ones in descending order on the right:
s = a0bn +
a1bn-1+...+
an-1b1 +
anb0
As usual, the value for n=0 in the sequence may or may not play a
role in the (legitimate) detection of cycles.
The value 1 for n=0 is fully acceptable for b=3, b=7
and b=9, but it distorts the picture for the other base numbers and
we shall leave it out.
We shall also leave out here the power sequence of a base-number raised to
a power n and expressed in itself.
The sequence of the denary 10 raised to the power 1, 2, 3, 4 et cetera,
which gives 10, 100, 1000, 10000, et cetera in the denary system, is such
a rather uninteresting example.
(The Powers of Two in Number Theory
shows that n=0 has to be left out to distinguish a final digit
cycle in the radix- or 'base'-10 notation of the powers of 2, whereas it
must be included to distinguish an initial digit cycle in the
radix-16 notation of the same numbers.)
A rational proof of cyclicity does, of course, not depend on any
limited number of cycles, but one might argue that the minimum
empirical evidence of cyclicity is two full cycles, or perhaps
even two cycles plus the first term of the third one.
Therefore, we should not stop before having seen the first nine terms of
these base-number sequences:
Note: all numbers are in denary notation.
Sets of one, two or four numbers between horizontal lines and with their
last digits in red denote second final one-digit cycles.
The above table clearly shows that the powers of the even base numbers are
always even, those of the odd base numbers always odd themselves.
But while the sum of any number of even numbers is always even too, the
sum of an even number of odd numbers is even, whereas the sum of an odd
number of odd numbers remains odd.
So the final digit of an unknown number longer than one digit does not tell
us anything in this respect, that is, if it is expressed in a numeral
system with an odd base number.
Since the digital cyclicity of a sequence does not provide us with the
entire number, we cannot apply a whole lot of divisibility rules either
(such as that an integer is divisible by 7 if the number obtained by
multiplying the value of its last digit by 2 and subtracting the result
from the number formed by the remaining digits can be evenly divided by
7).
And then, we cannot afford to apply a rule which makes use of one or more
final digits to a number in a different numeral system than the rule is
made for.
Thus, the number 5 is 101 in the binary system and therefore a
number ending in (0)101 in the binary system may have the looks of
a denary number ending in 5, and may seduce us into believing that it is
divisible by 5 or 101.
As as matter of fact, however, a number ending in 101 can only in a
minority of cases be divided by 101.
It can only be divided by 101 if the entire binary number notation
consists of two disjoint sets of digits which interpreted as numbers are
themselves divisible by 101, such as 0 (0), 101 (5),
1010 (10) and 1111 (15).
The reason is that if z can divide both x and y
—y being the value of the 101 part in this case—
it can divide the sum x+y.
The reverse is not necessarily true: just think of 15=9+6, in which 9 and
6 are not divisible by 5.
But once z can divide x+y, and also y,
then z can divide x too, as in 15=10+5.
The table below should illustrate all this for the first thirty-three
multiples of 101:
SEQUENCE OF MULTIPLES
OF
5 OR 101 |
| n |
|
BASE USED |
|
n |
|
BASE USED |
| 10 |
|
2 |
10 |
|
2 |
| 0 |
|
0 |
|
0 |
|
16 |
|
80 |
|
1010000 |
| 1 |
|
5 |
|
101 |
|
17 |
|
85 |
|
1010101 |
| 2 |
|
10 |
|
1010 |
|
18 |
|
90 |
|
1011010 |
| 3 |
|
15 |
|
1111 |
|
19 |
|
95 |
|
1011111 |
| 4 |
|
20 |
|
10100 |
|
20 |
|
100 |
|
1100100 |
| 5 |
|
25 |
|
11001 |
|
21 |
|
105 |
|
1101001 |
| 6 |
|
30 |
|
11110 |
|
22 |
|
110 |
|
1101110 |
| 7 |
|
35 |
|
100011 |
|
23 |
|
115 |
|
1110011 |
| 8 |
|
40 |
|
101000 |
|
24 |
|
120 |
|
1111000 |
| 9 |
|
45 |
|
101101 |
|
25 |
|
125 |
|
1111101 |
| 10 |
|
50 |
|
110010 |
|
26 |
|
130 |
|
10000010 |
| 11 |
|
55 |
|
110111 |
|
27 |
|
135 |
|
10000111 |
| 12 |
|
60 |
|
111100 |
|
28 |
|
140 |
|
10001100 |
| 13 |
|
65 |
|
1000001 |
|
29 |
|
145 |
|
10010001 |
| 14 |
|
70 |
|
1000110 |
|
30 |
|
150 |
|
10010110 |
| 15 |
|
75 |
|
1001011 |
|
31 |
|
155 |
|
10011011 |
|
|
|
|
|
|
32 |
|
160 |
|
10100000 |
|
Note: the sets of two, four, eight and sixteen numbers between horizontal
lines with their last digits in red denote full second final one-, two-,
three- and four-digit cycles.
From n=20 to n=32 the last two digits of the denary number
are shown in blue, because this is only the beginning of a (second)
twenty-term final two-digit cycle.
For the same reason the last five digits of the binary number are shown in
blue for n=32, because we may assume (without further empirical
evidence) that this is the beginning of a (second) thirty-two-term final
five-digit cycle.
|
We may not be able to derive factual information about the
divisibility by 101 of a binary number ending in 101, yet we
can say something about the probability of such a number being
divisible by 101.
In general that probability is 1/5=0.200 or 20% for all natural numbers,
so it may be interesting to see whether that percentage deviates for
numbers ending with 101.
Obviously, if we wanted to know in practice whether a number can be evenly
divided by 5, we had better stick to the denary system, but that is not
the point here.
The point here is that the last one or more digits of a number do or could
contain factual and/or statistical information.
And how much or of what kind will depend on the numeral system.
If we know the length of the number which ends with 101, or if we
are able to come up with an estimate of its length which is accurate
enough, we can indeed calculate the chance of its being divisible by
101.
For a number of six digits long, for example, the first three digits are
the variable part.
In theory, the number of variations with 0 and 1 is then 2^3, but in
practice the notations will not start with 0, so the number of actual
variations is only half of that: 2^2=4.
They are 100, 101, 110 and 111.
In the multiples-of-5 sequence table above we can see that 101101
(45) is the only number with six digits and ending with 101 which
can be divided by 101 (5).
A score of one in four is 1/4=0.250 or 25%.
For a number of nine digits long it is the first six digits which are to
be considered the variable part.
The number of variations is then 2^6; that is, 2^5=32, when leaving out
notations starting with 0.
In the same table above we find 6 binary six-digit numbers which can be
divided by 101.
If their notations are treated as the variable beginning parts of longer
notations, and if the end part is 101, they will still be divisible
by 101.
Therefore, the probability of a binary 9-digit number ending with
101 and being divisible by 101 is 6/32=0.188 or 18.8%, which
is less than the general average.
Here are the results for integers whose binary notations are three to
ten digits long:
PROBABILITY OF
DIVISIBILITY BY 101
OF A BINARY INTEGER ENDING WITH 101 |
LENGTH
in digits |
|
DIVISIBILITY BY 101 (5)
probability (with explanation) |
| 3 |
|
100% |
(101 itself) |
| 4 |
|
0% |
(0/1) |
| 5 |
|
0% |
(0/2) |
| 6 |
|
25% |
(1/4) |
| 7 |
|
25% |
(2/8) |
| 8 |
|
25% |
(4/16) |
| 9 |
|
18.8% |
(6/32) |
| 10 |
|
20.3% |
(13/64) |
One or more final digits can sometimes contain all the information we are
interested in, but there is no guarantee whatsoever.
It also depends on the numeral system whether the number presented in
that system gives us the information we want in a slower or in a faster
way.
Thus, the quaternary system is a very handy system for seeing whether a
number can be divided by 2, 4 or 8 — much handier than the denary
system.
Yet, when it is divisibility by 3 and by 9 we are after (something for
which we need the whole number in both systems) the denary system
distinguishes between the sum of the values of the single digits
being divisible by 3 and the sum of these values being divisible by 9.
In the former case the number is indeed divisible by 3, in the latter case
by 9 as well.
In the quaternary system, however, there is only one such divisibility
rule: if the sum of the values of the single digits is divisible
by 3, the number itself is divisible by 3, and could be divisible by 6
or 9.
You may like to check the sums of the base-4 digits in the table below.
With two exceptions, all of them are 3 or 6.
The number 0 is the first exception, and the sum of 333 (63) is
9, while the number itself is also divisible by 9.
QUATERNARY NUMBERS
DIVISIBLE BY 3 (3), 12 (6) OR
21 (9)
N3, N6,
N9 |
BASE
10 |
BASE
4 |
N3, N6,
N9 |
BASE
10 |
BASE
4 |
| 0, 0, 0 |
0 |
(0)0 |
21, -, 7 |
63 |
333 |
| 1 |
3 |
3 |
22, 11 |
66 |
1002 |
| 2, 1 |
6 |
12 |
23 |
69 |
1011 |
| 3, -, 1 |
9 |
21 |
24, 12, 8 |
72 |
1020 |
| 4, 2 |
12 |
30 |
25 |
75 |
1023 |
| 5 |
15 |
33 |
26, 13
| 78 |
1032 |
| 6, 3, 2 |
18 |
102 |
27, -, 9 |
81 |
1101 |
| 7 |
21 |
111 |
28, 14 |
84 |
1110 |
| 8, 4 |
24 |
120 |
29 |
87 |
1113 |
| 9, -, 3 |
27 |
123 |
30, 15, 10 |
90 |
1122 |
| 10, 5 |
30 |
132 |
31 |
93 |
1131 |
| 11 |
33 |
201 |
32, 16 |
96 |
1200 |
| 12, 6, 4 |
36 |
210 |
33, -, 11 |
99 |
1203 |
| 13 |
39 |
213 |
... |
... |
... |
| 14, 7 |
42 |
222 |
36, 18, 12 |
108 |
1230 |
| 15, -, 5 |
45 |
231 |
... |
... |
... |
| 16, 8 |
48 |
300 |
39, -, 13 |
117 |
1311 |
| 17
| 51 |
303 |
... |
... |
... |
| 18, 9, 6 |
54 |
312 |
42, 21, 14 |
126 |
1332 |
| 19 |
57 |
321 |
... |
... |
... |
| 20, 10 |
60 |
330 |
45, -, 15 |
135 |
2013 |
As the prime factors of 6 are 2 and 3, divisibility by 6 means
divisibility by 3 and divisibility by 2.
The latter feature is in the quaternary system only a question of the last
digit being 0 or 2.
Therefore, if the last quaternary digit in the table above, in which all
numbers can be divided by 3, is 0 or 2, the number can also
be divided by 6.
There is no similar rule which distinguishes whole numbers in a quaternary
notation which are divisible by 9 from those which are divisible by 3 but
not by 9, because 9 is a power of 3, and powers have the same prime
factor(s), 3 in this case, as the base of the power.
The final one-digit parts of numbers divisible by 3 follow the pattern of
the sequence (0,3,2,1); those of numbers divisible by 6 the pattern of
(0,2); and those of numbers divisible by 9 the pattern of (0,1,2,3).
In the pattern for 9 the same four digits occur with the same frequency as
in the pattern for 3.
The final two-digit parts of numbers divisible by 3 follow the pattern of
the sequence (00,03,12,21, 30,33,02,11, 20,23,32,01, 10,13,22,31)
—shown as pairs of red digits in the table above— and those of
numbers divisible by 9 the pattern of (00,21,02,23, 10,31,12,33,
20,01,22,03, 30,11,32,13) —highlighted in yellow.
Again, in the pattern for 9 the same sixteen pairs of digits occur with
the same frequency as in the pattern for 3.
Hence, with respect to a list of numbers in quartenary notation divisible
by 3, the single digits at the end tell you whether they are divisible by
6 as well, but neither the single digits nor the pairs of digits at the end
tell you anything about the numbers being or not being divisible
by 9.
The information contained in final digits may be a mixed bag, it is not
an empty bag.
67.MNW
|
