mersenneforum.org Theory Question
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-09-19, 19:03 #1 c10ck3r     Aug 2010 Kansas 547 Posts Theory Question Hey, I was hoping RDS et al could hint me in on whether or not there are any formulas for this... What are the chances that a randomly chosen integer n, with x digits, is factorable by a number less than p? More questions later! Thanks all! John Shuck
2011-09-19, 19:53   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22×32×281 Posts

Quote:
 Originally Posted by c10ck3r Hey, I was hoping RDS et al could hint me in on whether or not there are any formulas for this... What are the chances that a randomly chosen integer n, with x digits, is factorable by a number less than p? More questions later! Thanks all! John Shuck
You need to specify how the number is chosen randomly. I think you mean that all such integers have an equal probability of being chosen --- the uniform distribution in other words --- but either this supposition needs confirmation or you need to specify an alternative distribution.

Paul

 2011-09-19, 23:09 #3 CRGreathouse     Aug 2006 2·5·593 Posts
2011-09-19, 23:15   #4
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by c10ck3r Hey, I was hoping RDS et al could hint me in on whether or not there are any formulas for this... What are the chances that a randomly chosen integer n, with x digits, is factorable by a number less than p? More questions later! Thanks all! John Shuck
Assuming that n is chosen unifrmly at random from the set of x-digit numbers,
and p = n^alpha ~ 10^((x-1)alpha) then the answer is simply given by Dickman's function rho(alpha). A more accurate estimate can be
done by integrating rho(alpha) as n varies over the entire set of x digit numbers. A less accurate estimate can be found via the Canfield-Erdos-Pomerance thm. ~ u^-u with u = log(n)/log(p)

A good exposition of Dickman's function can be found in Knuth Vol 2.

2011-09-19, 23:18   #5
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts

Quote:
 Originally Posted by CRGreathouse http://en.wikipedia.org/wiki/Mertens%27_theorems
That's a bit too cryptic for me right now.

Will someone explain more about how Mertens' theorems are related to what is posted earlier?

2011-09-20, 06:58   #6
CRGreathouse

Aug 2006

2·5·593 Posts

Quote:
 Originally Posted by cheesehead That's a bit too cryptic for me right now. Will someone explain more about how Mertens' theorems are related to what is posted earlier?
The probability that a random* integer has no prime factor below y is
$\prod_{p\le y}\left(1-\frac1p\right)\approx\frac{1}{e^\gamma\log y}$
where $\gamma$ is Euler's constant.

* Chosen uniformly at random from 1..10^x for some large x. It turns out x doesn't matter unless it's small.

Last fiddled with by CRGreathouse on 2011-09-20 at 07:00

2011-09-20, 13:32   #7
R.D. Silverman

Nov 2003

161008 Posts

Quote:
 Originally Posted by CRGreathouse The probability that a random* integer has no prime factor below y is $\prod_{p\le y}\left(1-\frac1p\right)\approx\frac{1}{e^\gamma\log y}$ where $\gamma$ is Euler's constant. * Chosen uniformly at random from 1..10^x for some large x. It turns out x doesn't matter unless it's small.
Uh, NO. We have $\prod_{p < y} = exp(y + o(1))$.
[by the PNT or via estimates of the psi function; they are the same]

The probability that some p divides the random integer is not independent
of the probability that p1 (p != p1) divides the integer once there are
sufficiently many primes, because unless your integer is greater than
exp(y+o(1)), they ALL can't divide. They "get in the way" of each other.
Which, BTW, is why we have no sieve method proof of PNT.

Your expression is correct provided that y is small enough relative
to the random integer such that all primes less than y can divide it.

This difficulty is closely tied to the Fundamental Lemma of the Sieve
[see e.g. Halberstam & Richert's "Sieve Methods"] and is also somewhat
tied to the parity problem in sieve methods. Put another way, once
there are sufficiently many primes in the product (i.e. y is big), the error
terms in the sieve start to overtake the main terms.

This discussion can get very technical in a hurry. I have only given a
high-level explanation. For more details the readers might like to read
Tao's essay on the parity problem. [sorry, I don't have the
URL handy]

2011-09-21, 01:08   #8
CRGreathouse

Aug 2006

2×5×593 Posts

Quote:
 Originally Posted by R.D. Silverman Your expression is correct provided that y is small enough relative to the random integer such that all primes less than y can divide it.
Thus the note at the bottom of my post that disallows small x.

2011-09-21, 02:49   #9
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by CRGreathouse Thus the note at the bottom of my post that disallows small x.
This really doesn't say much. I would say that 10^500 is large, but even
this only allows e.g. y ~ 1150. I think most people would agree that a
500-digit integer is large. Yet Mertens' Thm only applies if one asks
about factors less than 1150. I can easily imagine asking: e.g. what is the
probability that a 500-digit number has a factor less than 10 digits.
Mertens' Thm is much too weak to answer this.

2011-09-21, 03:21   #10
R.D. Silverman

Nov 2003

11100010000002 Posts

Quote:
 Originally Posted by R.D. Silverman Assuming that n is chosen unifrmly at random from the set of x-digit numbers, and p = n^alpha ~ 10^((x-1)alpha) then the answer is simply given by Dickman's function rho(alpha). A more accurate estimate can be done by integrating rho(alpha) as n varies over the entire set of x digit numbers. A less accurate estimate can be found via the Canfield-Erdos-Pomerance thm. ~ u^-u with u = log(n)/log(p) A good exposition of Dickman's function can be found in Knuth Vol 2.
A correction . I was thinking that the OP wanted all
factors to be less than p. This is clearly an incorrect assumption. If one
wants just at least ONE factor, use the following:

The probability that an integer n has a factor between x and x^(1+e), for
x^(1+e) < sqrt(n) [i.e. we are asking about factors less than the sqrt(n)]
is e/(e+1)

2011-09-21, 03:31   #11
R.D. Silverman

Nov 2003

161008 Posts

Quote:
 Originally Posted by R.D. Silverman This really doesn't say much. I would say that 10^500 is large, but even this only allows e.g. y ~ 1150. I think most people would agree that a 500-digit integer is large. Yet Mertens' Thm only applies if one asks about factors less than 1150. I can easily imagine asking: e.g. what is the probability that a 500-digit number has a factor less than 10 digits. Mertens' Thm is much too weak to answer this.
It is interesting to quantify this. Suppose we use Mertens' Thm
to ask: what is the probability that there is no factor less than
sqrt(n)? The answer is exp(-gamma)/log(sqrt(n) = 2 exp(-gamma)/log(n).

2 exp(-gamma) is ~ 1.123. Yet the PNT says the answer should be 1/log(n).

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post robert44444uk Prime Gap Searches 94 2020-10-23 18:24 wreck Math 4 2010-04-15 07:11 RichardB Information & Answers 6 2010-04-10 18:39 jasong Soap Box 73 2007-03-27 22:03 Orgasmic Troll Math 1 2005-01-21 12:50

All times are UTC. The time now is 00:47.

Sat Oct 24 00:47:23 UTC 2020 up 43 days, 21:58, 0 users, load averages: 1.29, 1.39, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.