4
$\begingroup$

I'm trying to express the following function more simply:

\begin{equation*} f(x) = (\sum_{n=3}^{x} \prod_{k=2}^{\lceil \sqrt n \rceil} \lceil \dfrac {n}{k} \rceil - \lfloor \dfrac{n}{k} \rfloor ) + 1 . \end{equation*}

I know this is kind of a vague request, but I'm trying to get away from the ceiling and floor functions and possibly the product notation, just because it feels like a hacky way of expressing what I'm trying to express.

Any ideas?

  • 0
    @muad: what is a computer program but a particular kind of mathematical expression?2010-08-30

3 Answers 3

11

$\left\lceil \frac{n}{k} \right\rceil - \left\lfloor \frac{n}{k} \right\rfloor$ is equal to $0$ or $1$ depending on whether $k$ does or does not divide $n$. In other words,

$\prod_{k=2}^{ \lceil \sqrt{n} \rceil} \left( \left\lceil \frac{n}{k} \right\rceil - \left\lfloor \frac{n}{k} \right\rfloor \right)$

is equal to $0$ or $1$ depending on whether $n$ is composite or prime. So the function you are trying to describe is the prime counting function. There really is no simpler way to describe it than "the prime counting function," although a lot is known about its asymptotic behavior.

Edit: For functions like the prime counting function, you should replace the notion of "nice formula" with "fast algorithm" (the former being a special case of the latter). The formula you wrote down is equivalent to a very slow algorithm: use trial division to test the primality of all the integers in your range. There are much faster primality tests which translate into much faster algorithms for computing $\pi(n)$ even though these tests cannot be easily translated into familiar-looking formulas.

Edit #2: As Shreevatsar mentions in the comments, sieve theory is also relevant to counting or estimating $\pi(n)$ more directly, without having to do all that primality testing.

  • 0
    @Bill Dubuque: I guess you are right. I was being a little imprecise. I mean something vaguer than "special case" but I'm not sure what.2010-08-29
1

Presuming that you seek a concise formula (versus a fast algorithm), then one can simplify it somewhat by replacing the product by a factorial, and by employing $\rm\;\; a\perp b \;\; := \; 1 \;\;\; if \;\;\; gcd(a,b)=1 \;\;\; else \;\;\; 0$

$\rm \pi(x) \: = \: \sum_{n\;=\;2}^x \;\: n\perp {\lfloor \sqrt{n}\rfloor}!$

  • 2
    Not necessarily, since the products in the factorial need only be computed mod n. In any case, as I said, I presumed the OP was interested interested in "nice formulas", not efficiency, since his original formula is already very inefficient. My remark about the utility of the coprime predicate and gcd-free bases were meant merely as background motivation to explain why the coprime predicate does in fact arise naturally in computational contexts. The utility of gcd-free bases deserves to be much better known.2010-08-30
0

It depends in what context you want to define that function (for computer implementations?), but following Qiaochu Yuan's post, you can e.g. use set-based notations to state the primality test more clearly.

$f(x) = \left| \lbrace x \in \lbrace 3,\ldots, x \rbrace \; |\; \forall k \in \lbrace 2,\ldots,\sqrt n \rbrace . k \not | \; n \rbrace \right| + 1$

Of course

$f(x) = \left| \mathbb{P} \cap \lbrace 3, \ldots, x \rbrace \right|$

where $\mathbb{P}$ denotes the set of prime numbers or simply let $f$ be the prime counting function is even simpler.