15 August 2009

A number-theoretic tangent for your Saturday afternoon

You may know that 1001 has a simple prime factorization, namely 1001 = (7)(11)(13).

And of course 1000 has a simple prime factorization, namely 1000 = (23)(53).

The natural question to ask at this point, to me, is "how often does this happen?" Of course one has to define "this". One question is "how often are there two consecutive numbers that have all their prime factors less than or equal to 13?" There seem to be finitely many, and after I compiled a list I googled a few numbers from it and discovered that David Rusin had also done so. In case you're wondering why I conjecture there are finitely many: the number of integers less than n with all prime factors at most 13 is proportional to (log n)6. (The exponent 6 comes from the fact that there are six primes which are 13 or less.) So the "probability" (in the usual heuristic number-theoretic sense) that a given number n is "13-smooth" is the derivative of this, and thus of the order of (log n)5/n. The "probability" that two consecutive numbers are "13-smooth" is on the order of the square of this "probability", i. e. (log n)10n-2, and the integral of that from, say, 2 to infinity converges. Nothing is special about 13 here; there should be finitely many pairs of consecutive "p-smooth numbers" where p is any prime.

(Rusin's list, by the way, was something he compiled to illustrate how one might calculate logarithms; since 1000 ~ 1001, we can take common logs and get 3 ~ log(7) + log(11) + log(13). Given enough relations like this one can solve for the logarithms themselves.)

Alternatively, we can define the "roughness" of n as (log p)/(log n) where p is the largest prime factor of n. I call it "roughness", not "smoothness", because if it's smaller than the corresponding number is smoother, i. e. has comparatively small prime factors. This naturally compensates for the size of the number; if I recall correctly the proportion of numbers less than n with roughness less than r approaches some limit (a function of r) as n goes to infinity. (I only dabble in analytic number theory so I can't provide a source off the top of my head.)

It seems reasonable then that there should be a similar limit for pairs of consecutive numbers. Then empirically it seems that the probability that n and n+1 both have roughness at most (log 13)/(log 1001) is about 1 in 250. The pairs of numbers that are "at least as round" as (1000, 1001) in this sense are

(80, 81), (224, 225), (1000, 1001), (1715, 1716), (2079, 2080), (2400, 2401), ...

and it seems like about one in 230 pairs of consecutive numbers have this property (4291 in the first million). As is often the case, the interesting thing is that the limiting probability appears to exist and be neither zero nor one.

Postscript: I know some readers will be offended by my use of "probability" in this number-theoretic sense, because the prime factorization of a number is hardly a random object! But I'm a probabilist; this is how I think.

D. Eppstein said...

Yes, there are only finitely many pairs of consecutive 13-smooth numbers: see http://en.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem

complexzeta said...

The finiteness of consecutive p-smooth numbers for any p follows immediately from the abc conjecture, but it is probably also easier than that.

Anna said...

I'm just writing my master thesis about smooth numbers! Absolutely no offense about the use of probability here. :)

Anonymous said...

renewable setback serum charlotta ranbaxy impairments lhotshampas chemicals firstmonday visuals epistemology
servimundos melifermuly