Prime Factorization and Digit Congruence
Ross A. Finlayson
There are two groups of people in the world:
Those who can be categorized into one of two
groups of people, and those who can't.
http://www.workjoke.com/projoke22.htm
The statement must be false, for it claims to not be able to achieve
its claim.
I was interested the other day to read mention of testing decimal
numbers for divisibility by seven, in summing each odd group of three
digits as a decimal number and subtracting the sum of each even group
of three digits as a decimal number.
It reminds me of the case of "casting nines" or "casting out nines",
where a decimal number that has digits that sum to a multiple of nine
is a multiple of nine.
Also mentioned was a method for eleven, the same method as for seven.
Dissimilarly for eleven it is not necessary to group the digits to
consider a higher base but only to alternately add and subtract the
digits and test for divisibility.
I figure it would be worthwhile to apply that as a method to factorize
fall primes from an arbitrary number represented as a bitstring, in
addition to the method of factoring twos by counting the number of
least significant zeros and factoring the Mersenne numbers using digit
summation congruence. Yet, while I have a clue that the digit
summation congruence for base b can be used as a test for the factor
b-1, or one of its roots, for testing as factors the Mersenne numbers
2^n-1, I need better understanding of this method for sevens and
elevens in base ten if I am to apply it to the easily tractable bases
in binary: two, four, eight, sixteen, etcetera, 2^n.
In decimal, three digits in the first three integral moduli from zero
(or "orders of magnitude") allows a range from 0 to 999. Neither
seven nor eleven divides into a thousand. 1000%7, 1000 mod 7, the
remainder of even division of 1000 by 7, = 6, 1000%11 = 10. So in the
case of those numbers seven and eleven, x, for base b=10, b^3 % x =
x-1.
In base 8, 8^3 is 512. There do not seem to be many numbers x near 8
that 512%x=x-1. Perhaps 16, 2^4, will have an easier example.
Sixteen cubed is 2^12 or 4096, in looking for x s.t. b^3 % x = x-1.
This is where I am thinking that the fact that b^3 % x = x-1 is the
reason this method appears to work as digit summation, in this case
alternating grouped digit summation and subtraction, offers a
factorization test for small primes.
We discussed the case of b-1 and its roots that is used for the
Mersenne numbers in the thread "A INTRACTABLE problem on PRIMES." I
implemented and described toy softwarer using this method in a few
posts of "Factorial/Exponential Identity, Infinity", Mersenne Digit
Summation Congruence, DSC.
Here's a decent exposition:
http://www.mathpages.com/home/kmath269/kmath269.htm
The idea is to use this method with the computer's very rapid and
efficient binary arithmetic to produce algorithms in the bases that
are a power of two. The large composites to be tested for these small
factors are sequences of tens to hundreds to thousands of bits, and
it's simple to operate on them particularly in groups of eight bits,
bytes, base 2^8 = 256. Instead of, say, actually dividing the huge
number using extended precision arithmetic to see if there is a
remainder, the Mersenne numbers can be more rapidly determined to be
factors, and then division results. It's efficient for us, too,
determining if a decimal number is a multiple of nine is as simple as
summing its digits, and that sum, recursively, until a known multiple
of nine is recognized.
So I wonder about seven and eleven in decimal, and how to apply a
similar method for "a base that is a power of two".
What's a word that's an adjective describing a number being a power of
two? That's to ask, as example "of two" is binary or binal, "of four"
quaternary or quanternal, "of sixteen" hexadecimal or sexadecimal,
what's the general term for "of a power of two"? That would be
convenient instead of continually grammatically structuring "of any
power of two" in use.
From MathWorld, "Divisibility Tests":
http://mathworld.wolfram.com/DivisibilityTests.html
There are some more methods described for divisibility and congruence.
I have in mind to design further algorithms to use a variety of
divisibility tests to test factors of tracts of binary digits of large
composites, as I develop some factorization software.
I had this in mind in determining some of the ways that Stirling
numbers always are integers, analysis tools, because I want to
understand more about the rational functions that comprise some
Stirling numbers, and analytical forms of those, towards some better
understanding of some of the other contents of the
"Factorial/Exponential Identity, Infinity" thread.
Besides that, they're high performance factorization algorithms
suitable for pre-treatment of numbers before the factorized result is
sent to elliptic curve or other modern, memory-intensive, methods of
integer factorization.
Regards,
Ross F.
Daniel W. Johnson
> In decimal, three digits in the first three integral moduli from zero
> (or "orders of magnitude") allows a range from 0 to 999. Neither
> seven nor eleven divides into a thousand. 1000%7, 1000 mod 7, the
> remainder of even division of 1000 by 7, = 6, 1000%11 = 10. So in the
> case of those numbers seven and eleven, x, for base b=10, b^3 % x =
> x-1.
Another way to state this is x | b^3 + 1 = 1001 = 7 * 11 * 13
> In base 8, 8^3 is 512. There do not seem to be many numbers x near 8
> that 512%x=x-1.
You are looking for numbers x that divide 512+1 = 3^3 * 19
> Perhaps 16, 2^4, will have an easier example.
> Sixteen cubed is 2^12 or 4096, in looking for x s.t. b^3 % x = x-1.
4097 = 17 * 241
Of course, checking for a multiple of 17 in base 16 (like checking for a
multiple of 11 in base 10 or of 3^2 in base 8) can be done more easily
with alternating digits than with alternating groups of three digits.
--
Daniel W. Johnson
pano...@iquest.net
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W
Ross A. Finlayson
That might be so, but why then does seven need multiples of three
grouped in decimal?
I haven't really done much work on this yet, I would like to implement
the algorithm in a well-specified way for high-performance extended
precision integer arithmetic.
I noticed that x | b^3+1, x evenly divides into the value of the base
cubed, plus one, but that might be a red herring and not a true
indicator of the ability to consider the digits as a set besides as
representing the large composite (or perhaps prime).
Maybe one way to approach it is to consider the case of eleven in
decimal, and setting the even digits, that would subtract from the
value, to zero and only consider the digits that would be part of the
positive contribution to the test integer. As example, 209 is
supposed to be divisible by eleven because 2+9 (-0) =11. 209 is
11*19. Now a hundred minus one, ninety-nine, is a multiple of eleven,
so each even hundred contributes a value of one beyond an even
multiple of eleven, and each even ten needs one, because ten is one
less than a multiple of eleven. Each one's digit smply contributes
one. So as the integer a_n is a_0*b^0 + a_1*b^1 + ... + a_n+b^n,
each a_i for even i from zero to n is summed showing how many extra
units there are as remainders to form an even multiple of eleven, and
each a_i for odd i is subtracted. Then, if that result is a multiple
of eleven, then a_n is a multiple of eleven, for n < 6.
A thousand, 10^3, is again one less than a multiple of eleven, and
ten thousand, 10^4, is one more than a multiple of eleven. That
extends the range of n, and through induction 10^n for odd n is one
less than a multiple of eleven, and 10^n for even n is one more.
For seven, there are a variety of divisibility tests noted on the
MathWorld list, with various coefficients applied to each a_i. I'm
interested, somewhat, in the case of the noted example that describes
grouped elements, for example grouping into base b^3 and then having
a_0_g being a_0*b^0+a_1*b+a_2*b^2, and a_1_g being
a_3*b^0+a_4*b+a_5*b^2, etcetera, a_x_g=
a_(3x)*b^0+a_(3x+1)*b+a_(3x+2)*b^2.
So for seven, in decimal, it's a consideration about seven being
congruent in some way to a thousand, and basically then considering in
base thousand instead of base ten, and as above, illustrating through
induction the proof of the relation.
So, then I'm trying to figure out some more general forms for base b
and values x. Also, there are probably various consideration where
there are different sized groupings instead of one or three, in terms
of alternately adding and subtracting the digits in a higher base that
is a power of the lower base. As well, there are linear relations
that allow simple functions upon the coefficients to scale the
coefficients in the various moduli's contribution to the even
multiple.
I leave that as an exercise to myself, in terms of implementing the
high performance extended precision computerized divisibility tests,
use the simple tests on the binary string for each value from 3
onwards as it is efficient, then as a test is met multiply the known
factors together, and then divide that value out of the binary
bitstring, because division is computationally expensive. Repeat for
any of those known factors of the original integer. This, among
various other considerations as described as mentioned, I believe
leads to improved performance for most general purpose computerized
factorization methods.
Thank you. Regards,
Ross F.
Daniel W. Johnson
> That might be so, but why then does seven need multiples of three
> grouped in decimal?
Because 7 is a factor of 1001, but not of 11 or 101.
Consider a number written as a3*1000^3 + a2*1000^2 + a1*1000^1 +
a0*1000^0, where a0, a1, a2, and a3 can take values from 0 up to 999.
This number is equal to (a0-a1+a2-a3) + 1001*(a1 + 999*a2 + 999001*a3)
The difference between the original number and (a0-a1+a2-a3) is clearly
a multiple of 1001 and therefore of 7. Thus, the two numbers are either
both divisible by 7 or neither divisible by 7.
If you are interested in a divisor which happens to be a factor of 999
rather than 1001, the relevant expression would be (a0+a1+a2+a3) +
999*(a1 + 1001*a2 + 1001001*a3).
> I haven't really done much work on this yet, I would like to implement
> the algorithm in a well-specified way for high-performance extended
> precision integer arithmetic.
>
> I noticed that x | b^3+1, x evenly divides into the value of the base
> cubed, plus one, but that might be a red herring and not a true
> indicator of the ability to consider the digits as a set besides as
> representing the large composite (or perhaps prime).
x being a factor of b^3+1 is equivalent to b^3 being congruent to -1
modulo x. The congruence of b^3 and -1 modulo x is equivalent to the
ability to replace (a1*b^3 + a0) with (a0 - a1) in a test for
divisibility by x.
Or to look at this another way: If you can alternate adding and
subtracting groups of 3 digits when checking for divisibility by x, what
happens when you check b^3+1 for divisibility by x that way?
> So, then I'm trying to figure out some more general forms for base b
> and values x. Also, there are probably various consideration where
> there are different sized groupings instead of one or three, in terms
> of alternately adding and subtracting the digits in a higher base that
> is a power of the lower base. As well, there are linear relations
> that allow simple functions upon the coefficients to scale the
> coefficients in the various moduli's contribution to the even
> multiple.
If x is a factor of b^k-1, you can add successive groups of k digits in
base b when checking for divisibility by x. If x is a factor of b^k+1,
you can alternating adding and subtracting groups of k digits when
checking for divibility by x. And vice versa on both (consider b^k+x-1
and b^k+1, respectively).
Ross A. Finlayson
There are a variety of considerations in devising a variety of
divisibility tests through addition or subtraction of single or
grouped digits for any positive integer x for any positive integer
base b.
Say x=7 and b=10, then 10 mod 7 is 3, 100 mod 7 is 2, 1000 mod 7 is 6,
10000 mod 7 is 4, and 100000 mod 7 is 5, and 1 000 000 mod 7 is 1.
Where that is so, I want to understand a little better why:
10^0 mod 7 = 1
10^1 mod 7 = 3
10^2 mod 7 = 2
10^3 mod 7 = 6
10^4 mod 7 = 4
10^5 mod 7 = 5
and
10^(6n+0) mod 7 = 1
10^(6n+1) mod 7 = 3
10^(6n+2) mod 7 = 2
10^(6n+3) mod 7 = 6
10^(6n+4) mod 7 = 4
10^(6n+5) mod 7 = 5
for positive integer n.
One reason is that 10^3 mod 7 is 7-1. For c from 0 to 5, b^c mod x =
x-6, x-4, x-5, x-1, x-3, x-2. As x is not a factor of b in this case,
not x | b, for no n does x | b^n. Thus, in a cycle of six, that being
x-1, the result of b^((x-1)n+c) mod x is equal to b^c mod x.
10^600000000000000000000000000000 mod 7 = 1, b^((x-1)*googol) mod x =
1.
That's in a way reflective of how 1/7 is represented in decimal as a
repeating decimal of x-1= 6 digits: .(142857)....
That's similar to how 1/99 is a repeating decimal with 99-1=98 digits
in the repeating term:
.(01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101)....
That's the same value as the repeating term .(01)..., but in base ten
a divisibility test for 99 might be expected to be in groups of 98
terms as 99 shares no factors with 10, except that 99 = 3^2*11, and 9
is a perfect square.
Back to the case of 7, there are six unique values form 1 to b-1 to
consider that are the remainders of dividing 10^n by 7. They can be
considered as 1, 2, 3, and b-1, b-2, b-3.
10^(6n+0) mod 7 = 1
10^(6n+1) mod 7 = 3
10^(6n+2) mod 7 = 2
10^(6n+3) mod 7 = b-1
10^(6n+4) mod 7 = b-3
10^(6n+5) mod 7 = b-2
So, sum a_(x-1)n, and subtract from that sum a_(x-1)n+3, sum
a_(x-1)n+1 and subtract the sum a_(x-1)n+4, and sum a_(x-1)n+2 and
subtract the sum of a(x-1)n+5, and then there are three sums: the
first describing how many units there are to make a multiple of seven,
the second describing three times how many units there are to make a
multiple of seven, and the third describing twice as many units there
are to make a multiple of seven. If those sums are s_1, s_2, and s_3,
where 3<x/2, then if s_1 + 3s_2 _ 2s_1 is a multiple of 7, then so is
a. That's because n + x- n = x, and x | x and equivalently x mod x =
0. That's one of the examples given on the MathWorld page on
divisibility tests, for seven in decimal, and is noted to have been
discovered by Blaise Pascal. It might be that he used quite a
different approach, one nice thing about number theory is that there
are a variety of ways to prove these number theoretic relations.
If the idea is to determine general forms for divisibility tests for
any positive integer x into any positive integer base b, further
consideration may lead to more understanding of a variety of methods
to explore those options.
For x < b, and not x | b and for no factors f of x does x | b, I
wonder if it is always so that the grouping size of floor x/2 leads to
a divisibility test for any value positive integer x. That's what's
called a triviai conjecture.
Thanks again, your input is appreciated. I wonder your reaction to
1/99 being the repeating decimal .(0101010...)....
Regards,
Ross F.
Daniel W. Johnson
> There are a variety of considerations in devising a variety of
> divisibility tests through addition or subtraction of single or
> grouped digits for any positive integer x for any positive integer
> base b.
>
> Say x=7 and b=10, then 10 mod 7 is 3, 100 mod 7 is 2, 1000 mod 7 is 6,
> 10000 mod 7 is 4, and 100000 mod 7 is 5, and 1 000 000 mod 7 is 1.
> Where that is so, I want to understand a little better why:
>
> 10^0 mod 7 = 1
> 10^1 mod 7 = 3
> 10^2 mod 7 = 2
> 10^3 mod 7 = 6
> 10^4 mod 7 = 4
> 10^5 mod 7 = 5
>
> and
>
> 10^(6n+0) mod 7 = 1
> 10^(6n+1) mod 7 = 3
> 10^(6n+2) mod 7 = 2
> 10^(6n+3) mod 7 = 6
> 10^(6n+4) mod 7 = 4
> 10^(6n+5) mod 7 = 5
>
> for positive integer n.
The set of remainders relatively prime to a given number (e.g., 7) forms
a group under multiplication. In this case, the group has a size of 6,
and a little group theory results in the conclusion that b^6 mod 7 = 1
for any b which is relative prime to 7. Shorter cycles are possible in
some cases, such as 2^3 mod 7 = 1 and 6^2 mod 7 = 1, but the cycle
length would always be a factor of 6.
> One reason is that 10^3 mod 7 is 7-1. For c from 0 to 5, b^c mod x =
> x-6, x-4, x-5, x-1, x-3, x-2. As x is not a factor of b in this case,
> not x | b, for no n does x | b^n. Thus, in a cycle of six, that being
> x-1, the result of b^((x-1)n+c) mod x is equal to b^c mod x.
> 10^600000000000000000000000000000 mod 7 = 1, b^((x-1)*googol) mod x =
> 1.
>
> That's in a way reflective of how 1/7 is represented in decimal as a
> repeating decimal of x-1= 6 digits: .(142857)....
Note that 142857 * 7 = 999999 = 10^6 - 1.
> That's similar to how 1/99 is a repeating decimal with 99-1=98 digits
> in the repeating term:
>
.(0101010101010101010101010101010101010101010101010101010101010101010101
0101010101010101010101010101)....
>
> That's the same value as the repeating term .(01)..., but in base ten
> a divisibility test for 99 might be expected to be in groups of 98
> terms as 99 shares no factors with 10, except that 99 = 3^2*11, and 9
> is a perfect square.
A divisibility test for 99 in any base might be expected to be in groups
of 60, because phi(99) = 60, not 98. Note that 2^30 = 10845877 * 99 +
1, so 1/99 would repeat after 30 digits in base 2. (A little more work
shows that 30 digits are always enough, but some bases will manage with
a proper factor of 30.)
Ross A. Finlayson
For the phi function, I think you mean the totient function, Euler's
phi. phi(x) for positive integer x is the count of integers less than
x that are relatively prime to x, sharing no factors, plus one for
one.
So phi(7) is 6, for 1, 2, 3, 4, 5, and 6, for prime p phi(p)=p-1.
http://mathworld.wolfram.com/TotientFunction.html
http://www.research.att.com/projects/OEIS?Anum=A000010
This is interesting, a theorem of Euler states that if integers a and
n have no common non-unit factors, that gcd(a, n)=1, that they're
relatively prime, that they're coprime, that a^phi(n) mod n = 1.
http://primes.utm.edu/glossary/page.php?sort=EulersTheorem
You mention in decimal about phi(98) being 60, 10^60 mod 98 = 1.
Trivially, a^0 mod 0 = 1. In determining a form for a divisibility
test for 99 in base ten, it may well be completely easier to go to
base 100 where each digit is added and that result is tested for
divisibility by 99, reducing to the case of b and b-1, instead of
groups of 60, with determining what pairs x-n, n, are the "residues"
in each integral modulus. For example in the case of 7, a prime
number, there are three pairs phi(7)/2 = 6/2=3, and they are uniquely
7-1 and 1, 7-2 and 2, and 7-3 and 3.
In looking for the cycle length, if it's to be phi(x) then a^ 2phi(x)
mod x must equal 1. I wonder what is 10^120 mod 99. If it's 1, and so
on and so forth a ^ n(phi(x), and also for each c from 0 to phi(x)-1
that a ^ c mod x = a ^ n(phi(x))+c mod x, then it is similar to 7 and
the cycle length of phi(7)=6. It may be that each residue in the
cycle is unique, or not, I don't know, and if the cycle length is less
than x-1 then some residues, remainders, do not exist as any of b^c
mod x, where c is the cycle length.
So I'm wondering about the cycle repetition for a cycle of phi(x), why
that is so, and what remainders there of the possible values for c
from 0 to x-1 for each of b^0=1 to b^(phi(x)-1), and also about from
b^0 to b^c.
The abovementioned resources don't directly describe a method of
determining phi(n) without counting the totatives of n, there may well
be a recurrence relation or family to determine that value, yet its
very presence in the integer sequence dictionary as its own definition
leads one to think that it is not obvious or known.
So it looks like we can talk about Euler's totient function, phi, and
Euler's totient theorem, for coprime a and n a^phi(n) mod n = 1.
It's nice to remember the law of small numbers, while that is so,
there is much to be taken from decimal seven. The "cycle length" is
x-1, but more importantly it's phi(x). Each of the values mod 7,
except for zero, occur for b^c, because seven is coprime to ten, and
prime.
One way to select a direction is to return to the original concept on
this wayward path through some aspects of introductory number theory
with regards to integral moduli congruence to various integers x
relatie to base b.
The idea with that was to determine for which values it would be
feasible and wise to apply a digit summation congruence or alternating
or multilinear digit summation congruence test on large binary numbers
in computer memory to determine lists of its factors to then divide
the large number by those factors to reiteratively factorize the
quotient, with a predetermined lack of remainder.
The Mersenne numbers, binary rep-units, in binary where a power of two
is one greater than each Mersenne numbers, are the simple case for
using digit summation congruence.
Here, I want to note a brief aside about computer programming and the
bitstring. Have you ever worked with trying to get bits out of
octets, rotating or shifting arrays of octets/bytes, or otherwise
doing bitwise arithmetic on large sequential bit sequences? It
happens often. I've cobbled together a few bitstream functions but
have always been surprised that there weren't a variety of general
purpose bitsequence libraries as ATLAS (Automatically Tuned Linear
Algebra Software), or even whole pattern schools about processor
efficient operations on bit sequenecs larger than a word. I digress.
For the binary Mersenne case, b^n mod (b-1) = 1, that is generally
true for positive integer b and n. What that means is that grouping
the bits into contiguous subsequences of length c for base b= 2^c
allows the sum of those subsequences to be tested for divisibility by
2^c-1, b-1, to test the divisibility of the entire sequence by b-1.
The grouped subsequences become single symbols in the aggregated base.
So that works conveniently where it is efficient to sum those
subsequences, for example on a processor register where all
computation within a computer occurs. In accord with the above
digression, it is easier to program using a value of c that is itself
a power of two, to avoid having to straddle bytes in the array of
bytes, simply testing for divisibility of the Mersenne number less
than 4, 16, 256, 32678, etcetera, and less simply for 8 (2^3), 32
(2^5), 64 (2^6), etcetera. That is further detailed in "Factorial /
Exponential Identity, Infinity."
In binary then with considering arbitrary values and tests for
division against them, the values to test for a given base will be
coprime to the base and as well near the base, that is to say nearer
2^c than 2^(c-1) or 2^(c+1), nearer logarithmically.
It's convenient to work with base 4, a subsequence of two bits. For
base four, testing for divisibility by 1 or 2 is trivial, testing for
3 is the Mersenne test, and testing for 5 is to be considered. 4 mod
5 is 5-1, 16 mod 5 = 1, 64 mod 5 is 5-1. It appears that five is
simply determined to be a factor of a number in base four by
alternately adding and subtracting digits from the least significant
digit and testing for divisibility by five.
So then an algorithm might maintain two running sums, one with adding
each coefficient to test for divisibility of three, and the other
alternately adding and subtracting, with a signed variable, and
testing for the divisibility of five, as two-bit subsequences were
picked from the sequence. If each is respectively evenly divisible,
then divide the original sequence by 3*5=15, times whatever other
prime factors were determined for the original large number, and
divide that product into the large number.
If there existed another number x such that b^2n mod x = 1 and
b^(2n+1) mod x = x-1, then the resulting sum of alternating positive
and negated coefficients could also be used to test for that x, or any
other that met those conditions.
For base four, six is not a prime, the use of the divisibility test is
for prime factorization. For x = 7, 7 is the Mersenne prime tested by
DSC(8).
For base 8, and in general, it appears that for x= b+1 that b^2n mod x
= 1 and b^(2n+1) mod x = -1, because b^2-1 = (b+1)(b-1), b^4-1 factors
to (x^2+1)(x^2-1), etcetera. For 9, that being 8+1, 9 is a perfect
square and 3 shall already have been factorized from the number, yet
in the phase of collecting known factors, two is better than one, yet
that may be inconvenient later in the processing.
So for each test, it seems that in the cumbersome selection of each
subsequence as a digit of a given base of a power of two, to maintain
two sums for testing against divisibility by b+1 and b-1.
So it seems that a rational algorithm might determine what registers
it may allocate, say eight registers, with a few other registers to
load a pair of octets, or words, from the bit sequence, for straddling
octets, or words, with preemptive loads. Then, starting with the
least significant byte, it loads each byte, or word, and the next and
then picks the subsequences of length 2, 3, 4, 5, from each byte, or
word, and adds each determined value to one of the b-1 registers and
alternatively adds and subtracts from one of the b+1 registers. Then,
when the sequence is exhausted, the contents of the registers are
tested for divisibility by the appropriate value. Then, those are
factors of the original sequence, yet unmodified in memory, and then
the tests for the remaining values are to be tested using modified
digit summation congruence are done, then each known factor is
multiplied together, and the original sequence is divided by that, and
then the test repeats for any factor that was determined in the
original sequence, but not for the others.
It takes time and register space to select the subsequence, it takes
time and sometimes specific registers to place the addends and
subtrahends (subtehends). It takes time and organization upon
completion to send the list of factorized elements and the reduced
integer back to the calling process
While that may be an efficient algorithm, if not necessarily available
to the higher level programming languages than assembler, if may be
inefficient to program for portable application as processors utilize
a variety of word lengths, and registers, and have various methods of
cache coherency, and various operation counts for addition,
subtraction, shift, mask, bit test, division of extended precision
large integers, a linear and temporal system. Where that is so, a
computer tasked to factorize numbers all day, every day, may well see
a large performance increase.
In considering tests for divisibility for numbers that are about
halfway, logarithmically, between Mersenne numbers, for example 13
with regards to 8 and 16, or 23 to 16 and 32, then comes into
consideration a higher base than those. I'm not quite sure how to
formulate that without thinking about it some more and deriving those
equations. Thirteen is a factor of one of the non-prime Mersenne
numbers, testing for it may be a matter of multiplying the original
number by the other factors of the rep-unit tested not to exist, where
multiplication is much cheaper than division, and consideration of the
various non-unit coefficients on the elements is a consideration, e.g.
Pascal's test for seven in decimal, because multiplication on a value
that fits within a register word may be much less than multiplication
of the entire original sequence, again where the coefficients can be
stored in a few registers on the processor, or addition operations
repeated with as necessary nops or code interleaving.
Hard-core register allocation, what with the graph coloring and
operation counts and the prefetches and hints and the process
switching and so on, is something that I approach from the land of
book-learning, and not yet application. I should try and figure out
some assembler programming, I'm one of those high-level language
programmers. This expression of my ignorance of machine language and
function is another digression, because a deeper understanding of
Euler's totient function phi and various theorems of number theory may
well provide algorithms that make obsolete these high performance
computing concepts.
I guess I wonder how to determine the minimum cycle length, and as
well, a closed form for phi. These are integers, prime and composite,
abundant, deficient, and perfect, squares, cubes, and other powers,
and so on and so forth.
These described methods do greatly aid in the efficient computation of
small prime factors of any integer. Where we can determine any digit
in the expansion of pi, for many ten years ago an unexpected result, I
think the future will see the solution of many NP-hard problems.
Warm regards,
Ross F.
Daniel W. Johnson
> For the phi function, I think you mean the totient function, Euler's
> phi. phi(x) for positive integer x is the count of integers less than
> x that are relatively prime to x, sharing no factors, plus one for
> one.
Yes. (But what's this "plus one for one"?)
> So phi(7) is 6, for 1, 2, 3, 4, 5, and 6, for prime p phi(p)=p-1.
>
> http://mathworld.wolfram.com/TotientFunction.html
> http://www.research.att.com/projects/OEIS?Anum=A000010
>
> This is interesting, a theorem of Euler states that if integers a and
> n have no common non-unit factors, that gcd(a, n)=1, that they're
> relatively prime, that they're coprime, that a^phi(n) mod n = 1.
Ah, I forgot that that had been proven directly.
> http://primes.utm.edu/glossary/page.php?sort=EulersTheorem
>
> You mention in decimal about phi(98) being 60, 10^60 mod 98 = 1.
Typo: phi(99) = 60, so 10^60 mod 99 = 1.
> Trivially, a^0 mod 0 = 1. In determining a form for a divisibility
> test for 99 in base ten, it may well be completely easier to go to
> base 100 where each digit is added and that result is tested for
> divisibility by 99, reducing to the case of b and b-1, instead of
> groups of 60, with determining what pairs x-n, n, are the "residues"
> in each integral modulus. For example in the case of 7, a prime
> number, there are three pairs phi(7)/2 = 6/2=3, and they are uniquely
> 7-1 and 1, 7-2 and 2, and 7-3 and 3.
>
> In looking for the cycle length, if it's to be phi(x) then a^ 2phi(x)
> mod x must equal 1. I wonder what is 10^120 mod 99. If it's 1, and so
> on and so forth a ^ n(phi(x), and also for each c from 0 to phi(x)-1
> that a ^ c mod x = a ^ n(phi(x))+c mod x, then it is similar to 7 and
> the cycle length of phi(7)=6. It may be that each residue in the
> cycle is unique, or not, I don't know, and if the cycle length is less
> than x-1 then some residues, remainders, do not exist as any of b^c
> mod x, where c is the cycle length.
I don't know where that "2" came from. By the Euler theorem you
mentioned, a^phi(x) mod x must equal 1. But 10^120 = (10^phi(99))^2
must be congruent to 1^2 (mod 99).
> So I'm wondering about the cycle repetition for a cycle of phi(x), why
> that is so, and what remainders there of the possible values for c
> from 0 to x-1 for each of b^0=1 to b^(phi(x)-1), and also about from
> b^0 to b^c.
Consider the calculation of 1/x in base a by long division. The
remainder after k digits is simply the remainder when a^k is divided by
x. Since a^phi(x) has a remainder of 1, that means you will have a
definite feeling of déją vu after phi(x) digits.
> The abovementioned resources don't directly describe a method of
> determining phi(n) without counting the totatives of n, there may well
> be a recurrence relation or family to determine that value, yet its
> very presence in the integer sequence dictionary as its own definition
> leads one to think that it is not obvious or known.
phi(n) can be calculated by multiplying n by (p-1)/p for each of the
distinct prime factors p of n. For example, phi(99) = 99 * (2/3) *
(10/11) = 60.
> So it looks like we can talk about Euler's totient function, phi, and
> Euler's totient theorem, for coprime a and n a^phi(n) mod n = 1.
>
> It's nice to remember the law of small numbers, while that is so,
> there is much to be taken from decimal seven. The "cycle length" is
> x-1, but more importantly it's phi(x). Each of the values mod 7,
> except for zero, occur for b^c, because seven is coprime to ten, and
> prime.
Note that the minimal cycle length could be less than phi(x); there is
nothing about the long division I mentioned to prevent seeing a
remainder of 1 before phi(x) digits have been calculated. For example,
dividing by 11 in base 10 will repeat after 2 digits, not 10. And in
any base, dividing by 99 will repeat at the 30th digit at the latest.
But the minimal cycle length must always be a factor of phi(x). (If a^6
and a^15 are both congruent to 1 in a certain modulus, it is easy to
calculate that the same must be true of a^3.)
> I guess I wonder how to determine the minimum cycle length, and as
> well, a closed form for phi. These are integers, prime and composite,
> abundant, deficient, and perfect, squares, cubes, and other powers,
> and so on and so forth.
A closed form for phi (given the prime factorization) was stated above.
The minimum cycle length is another matter; there are primes for which
the minimum cycle length will be one less than the prime. The 6 digit
loop for 7 is not unusual. And even using a "-1" to cut the effective
cycle in half (like the 3-digit groups for 7) is not going to do much
for efficiency.
Ross A. Finlayson
Hi Daniel,
One is normally considered not a prime. Also I guess the definition
of relatively prime is sharing no (integer) factors other than one.
phi(99)=60, and there are various methods to compute it that have to
do with the prime factorization or using the divisor function that
returns the number of divisors of a number.
http://mathworld.wolfram.com/DivisorFunction.html
About b ^ 2c mod 1, what I'm trying to understand is the direct
reasoning why the cycles repeat, regardless of the remainder of 1
existing for cycle of length phi(x), that the cycle repeats. Your
analogy of dividing one by a number coprime to ten for decimal and
observing the repeating pattern in the decimal representation helps to
see why that would be true.
There are a variety of "closed" forms for determining phi(x), some are
detailed right there in the EIS (Encyclopedia of Integer Sequences)
listing, but they're not rational functions (ratios of polynomials),
nor is there a generating function of sorts that doesn't use the
divisor or other function that at some level depends on sieving the
primes from the integers to get the primes, and recursively
determining these characteristics and others about primes and prime
distributions for each.
In browsing MathWorld, a CRC/Wolfram Science product edited by the
glorious and magnanimous Eric Weisstein, there's an entry for a
"veryprime", a reference for it is given as one of Jim Ferry's posts
to sci.math in 1999. The CRC refers to sci.math! If you find an
error in that, one of a variety of mathematical references published
by the old Chemical Rubber Company, he'll correct it. In the
"Factorial/Exponential Identity, Infinity" thread, I found typos or
brainos, or perhaps a simple mistake, in another CRC publication and a
treatise by Knuth.
About the minimum cycle length, it appears that for any (positive)
integer x that for base b that there are bases b^c where b^c mod x =
b^2c mod x = b^nc mod x, that in a base of some power of b, eg b^c,
b^2c, etcetera that the remainder is a constant, for example b^phi(x).
Where c can be a factor of phi(x), for example a factor of
phi(99)=60, or one of 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, or 30: 60 is
an abundant number.
About efficiency, I think there is actually much to be gained in terms
of a digit summation congruence technique. You and I, people, can
compute. If given only pencils, much paper, and a hundred digit
decimal number to factorize, we'd be well off to check for these small
factors using these methods, before filling pages with long division,
or calculating the products of large matrices, or using other known
techniques for factorizing large numbers. We could remove the
multiples of ten at one shot. We could each start at once, adding
each element to recursively add the digits of that to check for
divisibility by nine or three, and adding and subtracting in various
group sizes that we calculate provably determine the huge number to be
a multiple of some small factor, and using other divisibility tests.
They're efficient divisibility tests. That would be more efficient.
While the digital computer operates on somewhat different principles
than a human, the fact that it is a worthwhile algorithm to consider
for us, provably in the language of complexity theory of which I am
largely ignorant, lends to that it would be an efficient method for
the computer to use, at least while the cycle fits within a computer
word.
I wonder about which bases would be particularly tractable to these
kinds of methods. For example, in base twelve, the cycles might be
shorter than in base ten, because twelve has more factors than ten.
In a prime base, the cycles would be no less than phi(x), x is coprime
to b. Perhaps we can compare the factors of b and phi(x) to compute
the minimum cycle length given those values.
For that, a lot of time again the computer is a productivity aid for
us. What I hav ein mind with that is to generate charts and lists for
various values of b, x, c, n, b mod x, n^c mod x, phi(x), divisors(x),
the factorizations of b, x, phi(x), etcetera. Then, with charts of
those precomputed values, it might be easier and at least more
leisurely to search further for these connections.
Regards,
Ross F.
Ross A. Finlayson
coprime b and x and c > 2. It currently suffera from needing extended
precision arithmetic to calculate b^c for relatively small values of b
and c, as there is overflow.
There are some interesting things of note, though, that I had not
calculated to see before. For example, in base 16, b=16, there are a
variety of numbers that have a cycle length of 5, for example x = 25,
31, 33, 41, 55, 75, 93, 123, 155, 165, 205, .... A variety of numbers
have cycles of length two, the plain alternating digit test would
suffice for them: 3, 5, 15, 51, 85, and 255, where I charted from 2
to b^2.
Thus if an algorithm summed the alternatingly negated digits, then it
could test for divisibility of the original number in base 16 by 3, 5,
15, 51, 85, and 255. Fifteen is obviously b-1, 51 is b+1=17 *3, 85 is
17*5, and 255 is obviously enough 3*5*17. The value of b^2 is 256,
b^2-1 is 255, and in base 256, 255 is tested for division. Yet, with
the alternating sums of base 16: 3, 5, 15, 51, 85, and 255 can each
granularly be tested.
I generated for b from two to fifty, it's about a three megabyte file.
I need to get some extended precision C libraries if I am going to
compute some of the larger exponents, unless I can figure out how to
calculate b^c mod x without having to calculate b^c, and otherwise
keeping the intermediate result less than 2^32.
Let's see, I don't recall, what is a way to test a*b mod x for
congruence to a function of a mod x and b mod x. If I had a product
congruence test for relatively small numbers that are exponentiated,
then I could determine values of b^n mod x without exponentiating b.
Browsing MathWorld's entry for congruence, if a === a' (mod m) and b
=== b' (mod m) then ab === a'b' (mod m). So, to get a^2, a^3,
etcetera, a^2=== (a')^2 (mod m). So I should be able to say that b^c
mod x is (b mod x)^c. While that is so, I implemented that and got
spurious results. Ah, perhaps I know why, when x is greater than b, b
mod x = b and b^c is some large number. I guess I'll use a multiple
precision big integer library. I've been using Java, this GNU MP
BigNum Library, http://www.swox.com/gmp/, seems useful. First I
change the type of b^c from unsigned long to unsigned long long, that
appears to help, as it is defined in stdint.h as uintmax_t. That's
better, but still not genereal purpose. There might be some
interesting phenomena that would not be visible until an integer base
higher than 1000, decimal. Yet, for high values of b, the data set is
unwieldy, for sampling each x coprime to b that is less than b^2.
Of special interest might be the cases of b = 256, 2^8, and 2^16 and
2^32. These are of interest in the computational case because memory
is addressable at each 8 bits and is often aligned on 16, 32, or power
two bits, about a base that's a power of two of a power of two, a
tetration. Anyways, in summing bytes instead of subsequences of the
bytes, no logic is required to access the bits, and the divisibility
test would still be accurate for any one that was good for a factor of
256. The program is generating a chart for 256. ... In reviewing
the chart (a table) for b=64, there are a variety of values with a
cycle of one or two, with the concept of using the plain sum an
dalternating sum and not necessarily the linear coefficients on the
summands that are not +-1. Ah, 256 is done. In reviewing the table
for 256, these elements can be tested for divisibility into a big
integer represented by an array of bytes by summing the bytes and
testing for even divisibility by a zero remainder:
3, 5, 15, 17, 51, 85, 255
The only improvement over the base 16 (2^4) alternating test is the
base 256 (2^8) test for 17. Thus presumably plainly summing 16 bit
subsequences (base 2^16) would allow for constant time divisibility
tests of the linear time summation for the same values as the
alternating sum for 256, avoiding a sample division, which I don't
know is linear, polynomial, or exponential.
Then the following elements can be tested for divisibility of the
alternating sum of 256:
257, 771, 1285, 3855, 4369, 13107, 21845, and 65535
So, there is not some excellent advance so far in this post for better
divisibility tests tractable to computers, those numbers are sparse
within the integers.
Regards,
Ross F.
***** Table for base 256 of 256^c mod x *****
x= \ c= 1 2 3 4 5 6 7 8
----------------------------------------------------------
3 | 1 1 (1)
5 | 1 1 1 1 (1)
7 | 4 2 1 4 2 1 (3)
9 | 4 7 1 4 7 1 (3)
11 | 3 9 5 4 1 3 . . (5)
13 | 9 3 1 9 3 1 . . (3)
15 | 1 1 1 1 1 1 . . (1)
17 | 1 1 1 1 1 1 . . (1)
19 | 9 5 7 6 16 11 . . (.)
21 | 4 16 1 4 16 1 . . (3)
23 | 3 9 4 12 13 16 . . (.)
25 | 6 11 16 21 1 6 . . (5)
27 | 13 7 10 22 16 19 . . (.)
29 | 24 25 20 16 7 23 . . (.)
31 | 8 2 16 4 1 8 . . (5)
33 | 25 31 16 4 1 25 . . (5)
35 | 11 16 1 11 16 1 . . (3)
37 | 34 9 10 7 16 26 . . (.)
39 | 22 16 1 22 16 1 . . (3)
41 | 10 18 16 37 1 10 . . (5)
43 | 41 4 35 16 11 21 . . (.)
45 | 31 16 1 31 16 1 . . (3)
47 | 21 18 2 42 36 4 . . (.)
49 | 11 23 8 39 37 15 . . (.)
51 | 1 1 1 1 1 1 . . (1)
53 | 44 28 13 42 46 10 . . (.)
55 | 36 31 16 26 1 36 . . (5)
57 | 28 43 7 25 16 49 . . (.)
59 | 20 46 35 51 17 45 . . (.)
61 | 12 22 20 57 13 34 . . (.)
63 | 4 16 1 4 16 1 . . (3)
65 | 61 16 1 61 16 1 . . (3)
67 | 55 10 14 33 6 62 . . (.)
69 | 49 55 4 58 13 16 . . (.)
71 | 43 3 58 9 32 27 . . (.)
73 | 37 55 64 32 16 8 . . (.)
75 | 31 61 16 46 1 31 . . (5)
77 | 25 9 71 4 23 36 . . (.)
79 | 19 45 65 50 2 38 . . (.)
81 | 13 7 10 49 70 19 . . (.)
83 | 7 49 11 77 41 38 . . (.)
85 | 1 1 1 1 1 1 . . (1)
87 | 82 25 49 16 7 52 . . (.)
89 | 78 32 4 45 39 16 . . (.)
91 | 74 16 1 74 16 1 . . (3)
93 | 70 64 16 4 1 70 . . (5)
95 | 66 81 26 6 16 11 . . (.)
97 | 62 61 96 35 36 1 . . (6)
99 | 58 97 82 4 34 91 . . (.)
101 | 54 88 5 68 36 25 . . (.)
103 | 50 28 61 63 60 13 . . (.)
105 | 46 16 1 46 16 1 . . (3)
107 | 42 52 44 29 41 10 . . (.)
109 | 38 27 45 75 16 63 . . (.)
111 | 34 46 10 7 16 100 . . (.)
113 | 30 109 106 16 28 49 . . (.)
115 | 26 101 96 81 36 16 . . (.)
117 | 22 16 1 22 16 1 . . (3)
119 | 18 86 1 18 86 1 . . (3)
121 | 14 75 82 59 100 69 . . (.)
123 | 10 100 16 37 1 10 . . (5)
125 | 6 36 91 46 26 31 . . (.)
127 | 2 4 8 16 32 64 . . (.)
129 | 127 4 121 16 97 64 . . (.)
131 | 125 36 46 117 84 20 . . (.)
133 | 123 100 64 25 16 106 . . (.)
135 | 121 61 91 76 16 46 . . (.)
137 | 119 50 59 34 73 56 . . (.)
139 | 117 67 55 41 71 106 . . (.)
141 | 115 112 49 136 130 4 . . (.)
143 | 113 42 27 48 133 14 . . (.)
145 | 111 141 136 16 36 81 . . (.)
147 | 109 121 106 88 37 64 . . (.)
149 | 107 125 114 129 95 33 . . (.)
151 | 105 2 59 4 118 8 . . (.)
153 | 103 52 1 103 52 1 . . (3)
155 | 101 126 16 66 1 101 . . (5)
157 | 99 67 39 93 101 108 . . (.)
159 | 97 28 13 148 46 10 . . (.)
161 | 95 9 50 81 128 85 . . (.)
163 | 93 10 115 100 9 22 . . (.)
165 | 91 31 16 136 1 91 . . (5)
167 | 89 72 62 7 122 3 . . (.)
169 | 87 133 79 113 29 157 . . (.)
171 | 85 43 64 139 16 163 . . (.)
173 | 83 142 22 96 10 138 . . (.)
175 | 81 86 141 46 51 106 . . (.)
177 | 79 46 94 169 76 163 . . (.)
179 | 77 22 83 126 36 87 . . (.)
181 | 75 14 145 15 39 29 . . (.)
183 | 73 22 142 118 13 34 . . (.)
185 | 71 46 121 81 16 26 . . (.)
187 | 69 86 137 103 1 69 . . (5)
189 | 67 142 64 130 16 127 . . (.)
191 | 65 23 158 147 5 134 . . (.)
193 | 63 109 112 108 49 192 . . (.)
195 | 61 16 1 61 16 1 . . (3)
197 | 59 132 105 88 70 190 . . (.)
199 | 57 65 123 46 35 5 . . (.)
201 | 55 10 148 100 73 196 . . (.)
203 | 53 170 78 74 65 197 . . (.)
205 | 51 141 16 201 1 51 . . (5)
207 | 49 124 73 58 151 154 . . (.)
209 | 47 119 159 158 111 201 . . (.)
211 | 45 126 184 51 185 96 . . (.)
213 | 43 145 58 151 103 169 . . (.)
215 | 41 176 121 16 11 21 . . (.)
217 | 39 2 78 4 156 8 . . (.)
219 | 37 55 64 178 16 154 . . (.)
221 | 35 120 1 35 120 1 . . (3)
223 | 33 197 34 7 8 41 . . (.)
225 | 31 61 91 121 151 181 . . (.)
227 | 29 160 100 176 110 12 . . (.)
229 | 27 42 218 161 225 121 . . (.)
231 | 25 163 148 4 100 190 . . (.)
233 | 23 63 51 8 184 38 . . (.)
235 | 21 206 96 136 36 51 . . (.)
237 | 19 124 223 208 160 196 . . (.)
239 | 17 50 133 110 197 3 . . (.)
241 | 15 225 1 15 225 1 . . (3)
243 | 13 169 10 130 232 100 . . (.)
245 | 11 121 106 186 86 211 . . (.)
247 | 9 81 235 139 16 144 . . (.)
249 | 7 49 94 160 124 121 . . (.)
251 | 5 25 125 123 113 63 . . (.)
253 | 3 9 27 81 243 223 . . (.)
255 | 1 1 1 1 1 1 . . (1)
257 | 256 1 256 1 256 1 . . (2)
259 | 256 9 232 81 16 211 . . (.)
261 | 256 25 136 103 7 226 . . (.)
263 | 256 49 183 34 25 88 . . (.)
265 | 256 81 66 201 46 116 . . (.)
267 | 256 121 4 223 217 16 . . (.)
269 | 256 169 224 47 196 142 . . (.)
271 | 256 225 148 219 238 224 . . (.)
273 | 256 16 1 256 16 1 . . (3)
275 | 256 86 16 246 1 256 . . (5)
277 | 256 164 157 27 264 273 . . (.)
279 | 256 250 109 4 187 163 . . (.)
281 | 256 63 111 35 249 238 . . (.)
283 | 256 163 127 250 42 281 . . (.)
285 | 256 271 121 196 16 106 . . (.)
287 | 256 100 57 242 247 92 . . (.)
289 | 256 222 188 154 120 86 . . (.)
291 | 256 61 193 229 133 1 . . (6)
293 | 256 197 36 133 60 124 . . (.)
295 | 256 46 271 51 76 281 . . (.)
297 | 256 196 280 103 232 289 . . (.)
299 | 256 55 27 35 289 131 . . (.)
301 | 256 219 78 102 226 64 . . (.)
303 | 256 88 106 169 238 25 . . (.)
305 | 256 266 81 301 196 156 . . (.)
307 | 256 145 280 149 76 115 . . (.)
309 | 256 28 61 166 163 13 . . (.)
311 | 256 226 10 72 83 100 . . (.)
313 | 256 119 103 76 50 280 . . (.)
315 | 256 16 1 256 16 1 . . (3)
317 | 256 234 308 232 113 81 . . (.)
319 | 256 141 49 103 210 168 . . (.)
321 | 256 52 151 136 148 10 . . (.)
323 | 256 290 273 120 35 239 . . (.)
325 | 256 211 66 321 276 131 . . (.)
327 | 256 136 154 184 16 172 . . (.)
329 | 256 65 190 277 177 239 . . (.)
331 | 256 329 150 4 31 323 . . (.)
333 | 256 268 10 229 16 100 . . (.)
335 | 256 211 81 301 6 196 . . (.)
337 | 256 158 8 26 253 64 . . (.)
339 | 256 109 106 16 28 49 . . (.)
341 | 256 64 16 4 1 256 . . (5)
343 | 256 23 57 186 282 162 . . (.)
345 | 256 331 211 196 151 16 . . (.)
347 | 256 300 113 127 241 277 . . (.)
349 | 256 273 88 192 292 66 . . (.)
351 | 256 250 118 22 16 235 . . (.)
353 | 256 231 185 58 22 337 . . (.)
355 | 256 216 271 151 316 311 . . (.)
357 | 256 205 1 256 205 1 . . (3)
359 | 256 198 69 73 20 94 . . (.)
361 | 256 195 102 120 35 296 . . (.)
363 | 256 196 82 301 100 190 . . (.)
365 | 256 201 356 251 16 81 . . (.)
367 | 256 210 178 60 313 122 . . (.)
369 | 256 223 262 283 124 10 . . (.)
371 | 256 240 225 95 205 169 . . (.)
373 | 256 261 49 235 107 163 . . (.)
375 | 256 286 91 46 151 31 . . (.)
377 | 256 315 339 74 94 313 . . (.)
379 | 256 348 23 203 45 150 . . (.)
381 | 256 4 262 16 286 64 . . (.)
383 | 256 43 284 317 339 226 . . (.)
385 | 256 86 71 81 331 36 . . (.)
387 | 256 133 379 274 97 64 . . (.)
389 | 256 184 35 13 216 58 . . (.)
391 | 256 239 188 35 358 154 . . (.)
393 | 256 298 46 379 346 151 . . (.)
395 | 256 361 381 366 81 196 . . (.)
397 | 256 31 393 167 273 16 . . (.)
399 | 256 100 64 25 16 106 . . (.)
401 | 256 173 178 255 318 5 . . (.)
403 | 256 250 326 35 94 287 . . (.)
405 | 256 331 91 211 151 181 . . (.)
407 | 256 9 269 81 386 322 . . (.)
409 | 256 96 36 218 184 69 . . (.)
411 | 256 187 196 34 73 193 . . (.)
413 | 256 282 330 228 135 281 . . (.)
415 | 256 381 11 326 41 121 . . (.)
417 | 256 67 55 319 349 106 . . (.)
419 | 256 172 37 254 79 112 . . (.)
421 | 256 281 366 234 122 78 . . (.)
423 | 256 394 190 418 412 145 . . (.)
425 | 256 86 341 171 1 256 . . (5)
427 | 256 205 386 179 135 400 . . (.)
429 | 256 328 313 334 133 157 . . (.)
431 | 256 24 110 145 54 32 . . (.)
433 | 256 153 198 27 417 234 . . (.)
435 | 256 286 136 16 181 226 . . (.)
437 | 256 423 349 196 358 315 . . (.)
439 | 256 125 392 260 271 14 . . (.)
441 | 256 268 253 382 331 64 . . (.)
443 | 256 415 363 341 25 198 . . (.)
445 | 256 121 271 401 306 16 . . (.)
447 | 256 274 412 427 244 331 . . (.)
449 | 256 431 331 324 328 5 . . (.)
451 | 256 141 16 37 1 256 . . (5)
453 | 256 304 361 4 118 310 . . (.)
455 | 256 16 1 256 16 1 . . (3)
457 | 256 185 289 407 453 347 . . (.)
459 | 256 358 307 103 205 154 . . (.)
461 | 256 74 43 405 416 5 . . (.)
463 | 256 253 411 115 271 389 . . (.)
465 | 256 436 16 376 1 256 . . (5)
467 | 256 156 241 52 236 173 . . (.)
469 | 256 345 148 368 408 330 . . (.)
471 | 256 67 196 250 415 265 . . (.)
473 | 256 262 379 59 441 322 . . (.)
475 | 256 461 216 196 301 106 . . (.)
477 | 256 187 172 148 205 10 . . (.)
479 | 256 392 241 384 109 122 . . (.)
481 | 256 120 417 451 16 248 . . (.)
483 | 256 331 211 403 289 85 . . (.)
485 | 256 61 96 326 36 1 . . (6)
487 | 256 278 66 338 329 460 . . (.)
489 | 256 10 115 100 172 22 . . (.)
491 | 256 233 237 279 229 195 . . (.)
493 | 256 460 426 103 239 52 . . (.)
495 | 256 196 181 301 331 91 . . (.)
497 | 256 429 484 151 387 169 . . (.)
499 | 256 167 337 444 391 296 . . (.)
501 | 256 406 229 7 289 337 . . (.)
503 | 256 146 154 190 352 75 . . (.)
505 | 256 391 106 371 36 126 . . (.)
507 | 256 133 79 451 367 157 . . (.)
509 | 256 384 67 355 278 417 . . (.)
511 | 256 128 64 32 16 8 . . (.)
513 | 256 385 64 481 16 505 . . (.)