mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2011-09-19, 19:03   #1
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default 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
c10ck3r is offline   Reply With Quote
Old 2011-09-19, 19:53   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×32×281 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
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
xilman is offline   Reply With Quote
Old 2011-09-19, 23:09   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·5·593 Posts
Default

http://en.wikipedia.org/wiki/Mertens%27_theorems
CRGreathouse is offline   Reply With Quote
Old 2011-09-19, 23:15   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-09-19, 23:18   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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?
cheesehead is offline   Reply With Quote
Old 2011-09-20, 06:58   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·5·593 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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
CRGreathouse is offline   Reply With Quote
Old 2011-09-20, 13:32   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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]
R.D. Silverman is offline   Reply With Quote
Old 2011-09-21, 01:08   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×5×593 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-09-21, 02:49   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-09-21, 03:21   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2011-09-21, 03:31   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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).
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime Gap Theory robert44444uk Prime Gap Searches 94 2020-10-23 18:24
Ask a number theory question wreck Math 4 2010-04-15 07:11
Theory RichardB Information & Answers 6 2010-04-10 18:39
The offended God theory jasong Soap Box 73 2007-03-27 22:03
Do I need group theory for this? 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.