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.
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.
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.
> 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 panop...@iquest.net http://members.iquest.net/~panoptes/ 039 53 36 N / 086 11 55 W
> > 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.
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.
> 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). -- Daniel W. Johnson panop...@iquest.net http://members.iquest.net/~panoptes/ 039 53 36 N / 086 11 55 W
> > 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).
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: .(0101010101010101010101010101010101010101010101010101010101010101010101010 1010101010101010101010101)....
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...)....
> 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:
> 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.) -- Daniel W. Johnson panop...@iquest.net http://members.iquest.net/~panoptes/ 039 53 36 N / 086 11 55 W
> > 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:
> > 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.)
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.
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.
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
> 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.
> 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.
> 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. -- Daniel W. Johnson panop...@iquest.net http://members.iquest.net/~panoptes/ 039 53 36 N / 086 11 55 W
> > 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.
> > 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.
> > 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.
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.
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.
I wrote a little program to output some of the values of b^c mod x for 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.
