Re: Prime Factorization and Digit Congruence

From: Ross A. Finlayson (raf_at_tiki-lounge.com)
Date: 07/17/04 

Date: 17 Jul 2004 13:42:13 -0700

panoptes@iquest.net (Daniel W. Johnson) wrote in message news:<1gh1n8m.w8x6uk1p35j4cN%panoptes@iquest.net>...
> Ross A. Finlayson <raf@tiki-lounge.com> wrote:
>
> > 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.

Thank you. Regards,

Ross F.

Relevant Pages

  • Re: Math logic
    ... processors mask out all ... a fast algorithm if it works, ... Would be great if I could replace multiple MULs, ... The input value can have up to 8 significant digits, ...
    (comp.lang.asm.x86)
  • Re: Prime Factorization and Digit Congruence
    ... > subtracting groups of 3 digits when checking for divisibility by x, ... grouped digits for any positive integer x for any positive integer ... first describing how many units there are to make a multiple of seven, ... divisibility tests, for seven in decimal, and is noted to have been ...
    (sci.math)
  • Re: how to add two no. of 100 digits or more?
    ... number of digits in the larger number, and that is the best you can do, ... if you need to multiple or divide numbers with 100 digits or ... See Knuth volume 2 for the details. ... I think the second edition is the best if you want to ...
    (comp.lang.c)
  • Re: calculate value of 73!
    ... >> digits. ... The Standard imposes no maxima on precision levels - only minima. ... It is, however, true that the writing of "multiple ...
    (comp.lang.c)
  • Re: How to increase Working Precision?
    ... I don't get credit for letting "generally outstanding" slip by? ... and 9.95, with three correct digits. ... It printed as zero because it ... is deemed to have too little precision to print otherwise ...
    (sci.math.symbolic)