# Least Prime Factors: found a counting formula for a given range — what is the standard approach?

Hi Everyone,

I am a math amateur who for the past year has been working on better understanding Bertrand's Postulate, the Ramanujan Primes, and the recent expansion of Bertrand's Postulate (always a prime between 2x and 3x and always a prime between 3x and 4x) using elementary methods.

I've been working with least prime factors and primorials and I came up with a counting formula that I have not seen elsewhere. It is quite similar to the standard prime counting formula using floor functions and it is using elementary methods so it is most likely uninteresting. I hope you don't mind me posting a sketch of it here.

I am presenting it here in hopes that experts can steer me to more modern analytic methods that accomplish the same thing in a better way. I would also be interested in understanding why the new methods are superior to the elementary methods.

The counting formula accomplishes the following:

Let $p_k$ be any prime. The formula provides an exact count of the number of least prime factors greater than $p_k$ in the range $r_{start}$ (exclusive) and $r_{end}$ (inclusive).

The formula consists of $2^{k-2}$ subformulas where each subformula looks something like this:

Least Prime Factor (5 or greater) between $x_{start}$ and $x_{end}$ =

$2\lfloor\frac{x_{end}}{6}\rfloor + \lfloor\frac{(x_{end} \% 6) + 3}{4}\rfloor - 2\lfloor\frac{x_{start}}{6}\rfloor - \lfloor\frac{(x_{start} \% 6) + 3}{4}\rfloor$

where $x_{end} \% 6$ is the value congruent to $x$ modulo $6$.

Note: The above formula, for example, is the expression for finding the number of least prime factors greater than $3$ in the range $r_{start}$ to $r_{end}$.

To give another example, if I wanted to count the number of least prime factors greater than $p_{6} = 13$, then the formula consists of $2^{6-2} = 16$ subformulas where each subformula is roughly similar to the example above.

Thanks very much.

-

First I'll toot my own horn.

There is still some work left for elementary and near elementary methods to accomplish. Based on your description, I think your formulas say something about the distribution of numbers coprime to the kth primorial. I have been working on something similar, and part of the path has led me to finding some elementary arguments which improve on part of the literature. I tell some of the story in the MathOverflow question Erik Westzynthius's cool upper bound argument: update? . The question title refers to a nice argument which serves as an introduction to sieve theory, and shows the potential for getting a handle on something as unwieldy as the distribution of primes which has a lot of regular and fractal behaviour occuring in its development.

If you are interested in this type of mathematics, you could do worse than to read through that question and the answers to it. If you want to know about general lower bound results, the Westzynthius paper has a nice construction which will produce gaps between primes which are larger than average, also using elementary means; it was the first published construction to show that for any constant C there are infinitely many k such that $p_{k+1} \gt C \log p_k + p_k$. You might even find a way to make elementary improvements on the arguments, as well as search the literature to find improvements by Rankin, Erdos, and others. (If you are patient, you can wait for a writeup I am doing which includes an interpretation of the key results of the paper.)

I am somewhat interested in the result of yours, but I suspect that I speak for others as well as myself when I say I would prefer a single approximation (or a small system of equations that I could numerically compute) to an exponential family of formulas I would need to calculate one value precisely. I believe that is one advance of sieve theory over elementary methods: it caters to such a preference. I don't know of any very accessible literature on the subject, but I sometimes refer to Cojocaru and Murty's book, and those more familiar with the literature may come with their recommendations. If you and I are fortunate, we may hear from the likes of zeb or quid, whose opinions I believe are more informed than mine on this subject.

Disclaimer: my training is not in analytic number theory; I suspect my perspective on the subject is much the same as yours.

Gerhard "But That Doesn't Stop Me" Paseman, 2012.01.17

-
Hi Gerhard, Thanks very much for the link! I look forward to reading your question and the answer to it. My method is very straight forward. It consists of the following recurrence relation: The number of LPF for $p_k$ between $x_{start}$ and $x_{end}$ is: $LPF_{p_k}(x_{end}) − LPF_{p_k}(x_{start})$ $LPF_{p_k}(x)=LPF_{p_{k−1}}(x)−LPF_{p_{k−1}}(⌊\frac{x}{p_k}⌋)$ $LPF_3(x)=2⌊\frac{x}{6}⌋+⌊\frac{(x \% 6) +3}{4}⌋$ –  Larry Freeman Jan 18 '12 at 4:28
In my first approach on the upper bound problem, I decided to extend the argument to thinner sets and define a series of error functions; they satisfy a recursion similar to your LPF recursion. Also, similar relations appear implicitly in Ldgendre's analysis of the prime counting function, so I am confident that your relations are used if not explicitly stated in the number theory literature. Gerhard "Ask Me About System Design" Paseman, 2012.01.23 –  Gerhard Paseman Jan 23 '12 at 8:20