The excellent graphic novel
Prime Suspects: The Anatomy of Integers and Permutations
by Andrew Granville and Jennifer Granville, illustrated by Robert J Lewis,
(I wrote a review of this graphic novel, for SIGACT News, here.)
has an appendix, which is not in graphic-novel form, where they describe some of the math talked about in the graphic novel.
Here is a quote that intrigued me for two reasons
2 is the smallest prime factor of half of the integers,
3 is the smallest prime factor of one-sixth of the integers,
5 is the smallest prime factor of one-fifteenth of the integers,
and so forth.
Intrigue One: and so fourth ? Really? That would indicate that it is easy to know what the next fraction is. Is it easy? That depends on your definition of easy.
Intrigue Two: What is the next fraction? What is the fraction asymptotically? I worked both of these out fairly fast; however, I don't think and so forth is appropriate.
We derive the 1/15 for 5. 1/5 of all numbers have a factor of 5. Of those, only those that are \(\equiv 1,5 \pmod 6\) have 5 as the smallest prime factor. Hence \(2/6=1/3\) of those numbers have 5 as the smallest prime factor. Hence the fraction is \(1/5 \times 1/3 = 1/15\).
More generally: For all \(i\in N\) let \(p_i\) be the \(i\)th prime. What fraction of numbers have \(p_n\) as the smallest factor? \(1/p_n\) of all numbers have a factor of \(p_n\). If a number that is divisible by \(p_n\) is also \(\equiv x \pmod {p_1p_2\cdots p_{n-1}}\) where \(1\le x\le p_1\cdots p_n\) and \(x\) is rel prime to \(p_1\cdots p_n\), then that number has \(p_n\) as the smallest factor. Hence the fraction is
\(\frac{1}{p_n} \times \frac{\phi(p_1\cdots p_{n-1})}{p_1\cdots p_n}=\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}= \frac{1}{p_n}\prod_{i=1}^{n-1} (1-\frac{1}{p_i})\)
where \(\phi\) is the Euler-phi function which, on input \(x\), returns the number of naturals in [1,n] that are relatively prime to \(n\). We have used the following well known facts: (a) if \(a,b\) are rel prime then \(\phi(ab)=\phi(a)\phi(b)\), and (b) if \(p\) is prime then \(\phi(p)=p-1\) (this is obvious).
The expression
\(\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}\)
is good for exact calculation. Let's do one!
The fraction of numbers that have 7 as their least prime factor is
\( \frac{1}{7}\times \frac{1\times 2\times 4}{2\times 3\times 5}= \frac{4}{105} \)
From the first three terms \( \frac{1}{2}, \frac{1}{3}, \frac{1}{15} \) I do not think that and so fourth would make anyone think the next term was \(\frac{4}{105}\).
But what is the fraction asymptotically?
ChatGPT tells me (and I believe it) that
\( \prod_{i=1}^{n} (1-\frac{1}{p_i}) \sim \frac{e^{-\gamma}}{\ln p_n} \)
where \(\gamma\) is the Euler-Mascheroni constant, roughly 0.5772 (see here for the Wikipedia entry on that constant).
Hence we get that the fraction of numbers that have \(p_n\) as their smallest prime factor is
\(\frac{1}{p_n} \prod_{i=1}^{n-1} (1-\frac{1}{p_i}) \sim\frac{1}{p_n} \frac{e^{-\gamma}}{\ln p_{n-1}} \)
Wolfram Alpha tells me (and I believe it) that
\(e^{-0.5772}\sim 0.56146\).
Hence we give our final approx for the fraction of numbers that have \(p_n\) as their least prime factor as
\(\frac{0.56146}{p_n\ln(p_{n-1})}\)
I don't think this qualifies as and so forth.
Euler-Mascheroni constant?
ReplyDeleteI think you meant "Euler-Mascheroni constant", after Lorenzo Mascheroni.
ReplyDeleteThe Euler-Maraschino constant presumably would be something about, maybe, the volume of a particular shape of cocktail glass? Or the proportion of ingredients? :)
Anon and Josh- you are of course correct and I made the correction. Josh- great idea, now that you have a word, find something that it fits!
ReplyDelete> I myself once learned 380 digits of π, when I was a crazy high-school kid. My never-attained ambition was to reach the spot, 762 digits out in the decimal expansion, where it goes "999999", so that I could recite it out loud, come to those six 9s, and then impishly say, "and so on!"
ReplyDelete- Hofstadter, Metamagical Themas 1985
https://en.wikipedia.org/wiki/Six_nines_in_pi
It could be related to another murder. Stash-keeper Muliya was killed, but the stash was not found: that is the prologue for the crime drama film by mathematician Roman Mikhaylov.
ReplyDeletehttps://en.wikipedia.org/wiki/A_Fairy_Tale_for_the_Old
Another possible way to look at this prologue and the film's plot in general, with a known share of abstraction, is to consider Muliya as the one from Millennium Prize Problems. So, Poincaré conjecture was proved, i.e. killed in some sense, but the hero of the occasion declined the official money prize, i.e. the stash is lost.
PS
A bit offtopic, but imho Perelman could be understood for refusal of $1 mln prize for prooving Millennium Prize Problem, as it reminds Dumas The Three Musketeers: for Athos it is too much, for the Count de La Fere it is too little.