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