[math-fun] Prime question
As n grows, what is the limiting probability that n has a prime divisor >= sqrt(n)?
See https://math.stackexchange.com/questions/375270/size-of-largest-prime-factor http://mathworld.wolfram.com/GreatestPrimeFactor.html Apparently, expected size of (max factor of n ) equals x^(log 2) ; also probability that (max factor of n ) exceeds sqrt x equals log 2 [credited to R. Schroeppel] . I find this coincidence a little strange ... WFL On 4/29/17, David Wilson <davidwwilson@comcast.net> wrote:
As n grows, what is the limiting probability that n has a prime divisor >= sqrt(n)?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Look up Dickman's function. I deserve no special credit here: The results were known long before it even occurred to me to ask the questions. I was unknowingly following in Euler's path: He wanted to know what a typical factorization looked like for large integers, and (IIRC) directed his helpers in preparing a sieve to factor the numbers from 1,000,000 to 1,002,000. [This leads to the 1,000,009 story -- presumably he was checking some of the results by hand -- and found that the sieve for 293 was accidentally omitted. Maybe they used something like pieces of paper with holes?] Anyway, to make a short story long, I had written an assembly language factoring program for the PDP6, and decided to have it factor 1000 numbers starting at a trillion. I was curious what an average factorization looked like. I turned up a fair number of primes that looked like 166666666667 etc. I also learned that a modest fraction of numbers factored entirely into smallish primes. 31% of numbers N factor (completely) into primes less than sqrtN, and 4.7% of numbers N factor into primes less than cbrtN. This information is useful for the Continued Fraction method of factoring, which examines a whole bunch of numbers related to the CF for sqrtN, to find a "few" solutions to the congruence X^2 (mod N) = product of small primes. These are combined to produce solutions to the congruence (prod Xi)^2 = Y^2 (mod N), and sometimes (prod Xi)+-Y will smoke out the factors of N. I wanted to learn what level of success to expect if I tried factoring large numbers into (only) small primes. I wrote out the integral to estimate the chances, and one result was the log 2 discovery. Later, I came across an article in Mathematics of Computation that mentioned my integral, and the name, which lead me to discover the literature on Dickman's function. It turns out that the integrals and percentages can be made rigorous, using the prime number theorem. Knuth has written an article analyzing the expected run time of the "simplest" factoring program, that tries divisors up to sqrt N, but is smart enough to quit early when, after removing a divisor, the leftover cofactor is less than the square of the removed divisor. [Example: N = 913, divisor = 11, cofactor = 83, which must be prime.] Rich --------------- Quoting Fred Lunnon <fred.lunnon@gmail.com>:
See
https://math.stackexchange.com/questions/375270/size-of-largest-prime-factor http://mathworld.wolfram.com/GreatestPrimeFactor.html
Apparently, expected size of (max factor of n ) equals x^(log 2) ; also probability that (max factor of n ) exceeds sqrt x equals log 2 [credited to R. Schroeppel] . I find this coincidence a little strange ...
WFL
On 4/29/17, David Wilson <davidwwilson@comcast.net> wrote:
As n grows, what is the limiting probability that n has a prime divisor >= sqrt(n)?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is a super interesting question. Part of the problem is that IF the distribution* of prime factors DOES approach a limit: THEN *in what sense* does it approach the limit? Because it certainly isn't the standard limit. Maybe in a lim inf or lim sup sort of a way? Probability theory has a sense of convergence for continuous distributions on the reals that as I recall is, you compare two distributions by taking the difference of their *cumulative* distribution functions, and integrate something like the square of that difference over R. Maybe something like this works, I don't know. —Dan
On Apr 29, 2017, at 3:25 PM, rcs@xmission.com wrote:
what a typical factorization looked like for large integers
—Dan ————————————————————————————————————————————— * In *some* sense of the word "distribution".
There is a theorem by Billingsley which says that if p_i are the prime factors of n in decreasing order, then (log p_i/log n) coverges to samples from a Poisson process with intensity 1 as n goes to infinity. Victor On Sun, Apr 30, 2017 at 02:50 Dan Asimov <dasimov@earthlink.net> wrote:
This is a super interesting question.
Part of the problem is that
IF the distribution* of prime factors DOES approach a limit:
THEN *in what sense* does it approach the limit?
Because it certainly isn't the standard limit.
Maybe in a lim inf or lim sup sort of a way?
Probability theory has a sense of convergence for continuous distributions on the reals that as I recall is, you compare two distributions by taking the difference of their *cumulative* distribution functions, and integrate something like the square of that difference over R.
Maybe something like this works, I don't know.
—Dan
On Apr 29, 2017, at 3:25 PM, rcs@xmission.com wrote:
what a typical factorization looked like for large integers
—Dan ————————————————————————————————————————————— * In *some* sense of the word "distribution". _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Dan Asimov -
David Wilson -
Fred Lunnon -
rcs＠xmission.com -
Victor Miller