Re: SF: Back to theory
From: J (Jaybirdmac_at_yahoo.com)
Date: 02/25/05
- Next message: William Elliot: "Re: Definition of vector"
- Previous message: Dave Rusin: "Re: P.S. Sorry for the lack of wrapping in the text of my messages..."
- In reply to: Nora Baron: "Re: SF: Back to theory"
- Next in thread: Nora Baron: "Re: SF: Back to theory"
- Reply: Nora Baron: "Re: SF: Back to theory"
- Messages sorted by: [ date ] [ thread ]
Date: 25 Feb 2005 13:51:09 -0800
Thanks for posting a clear, intelligent explanation of your factoring
method. There are only about 71 primes less than 349. Did your
factoring method go through more or less j's to get to the factor 349?
Nora Baron wrote:
> J wrote:
> > Wouldn't the Strong Law of Small Numbers apply here? Try factoring
> > 47143269.
> >
>
> J,
>
> That is not so much a law, I think, as a rule of thumb.
>
> One thing I should have pointed out regarding my variant
> of Harris's scheme: there is an easy proof that it is
> guaranteed to factor M. Harris has not succeeded in proving
> that for his version.
>
> It's also easier to program.
>
> So here's how it works with M = 47143269.
>
> Let j = 2: T = 47143267. Let f = 47143266, g = 1.
>
> Then X = (47143267 - 1)/(4713267 + 1). The numerator of
> X is 47143266, which has a factor of 3 in common with M.
> Thus replace M with M / 3 = 15714423.
>
> Now let j = 2 again, T = 15714421, f = 15714421, g = 1,
> X = 15714420 / 15714422. Again the numerator has a factor of
> 3 in common with 15714423. Thus let the new M = 15714423 / 3
> = 5238141.
>
> Continue one more step like this until you get to M = 1746047.
>
> At this point you go through a lot of j's before you hit the
> next factor. But when j = 348, T = M - j = 1746047 - 348 = 1745699.
> Letting f = 1745699, g = 1, the numerator of X is 1745698.
>
> As it happens, 1745698 has a factor of 349 (a prime) in common with
> M = 1746047. And 1746047 /349 = 5003, which is a prime. Therefore
> putting all this together, the factorization of the *original* M is
>
> M = 47143269 = 3^3 * 349 * 5003.
>
>
> Nora B.
>
>
- Next message: William Elliot: "Re: Definition of vector"
- Previous message: Dave Rusin: "Re: P.S. Sorry for the lack of wrapping in the text of my messages..."
- In reply to: Nora Baron: "Re: SF: Back to theory"
- Next in thread: Nora Baron: "Re: SF: Back to theory"
- Reply: Nora Baron: "Re: SF: Back to theory"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
