# Function simplification

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?

-
This looks more like a computer program than a mathematical expression. – anon Aug 29 '10 at 23:00
@muad: what is a computer program but a particular kind of mathematical expression? – Qiaochu Yuan Aug 30 '10 at 0:46

$\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.

-
By the way, the idea behind your formula is not a bad idea at all; it is clever to take advantage of the fact that a product of 0s and 1s is 1 if and only if all of the factors are 1, and such ideas are often useful for computing other things and in other areas of mathematics; see e.g. the standard proof of the Chevalley-Warning theorem. – Qiaochu Yuan Aug 29 '10 at 18:31
+1. For computation of the prime-counting function, where you're counting all primes in a large range, having faster sieves would be more useful than faster primality tests directly. There are a few references on the Wikipedia page, though I think it's incomplete… of course, if you don't want the exact value of π(n) there are much faster approaches that are asymptotically right. – ShreevatsaR Aug 29 '10 at 19:06
+1. "[..] you should replace the notion of "nice formula" with "fast algorithm" (the former being a special case of the latter)." I like this observation. Wondering if all functions have algorithms that compute them eventually led me to the concept of computable function: en.wikipedia.org/wiki/Computable_function – user365 Aug 29 '10 at 20:05
"Nice formulas" aren't necessarily special cases of fast algorithms. Perhaps that's what you intended to say above. – Bill Dubuque Aug 29 '10 at 20:47
@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. – Qiaochu Yuan Aug 29 '10 at 21:08

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}!$$

-
If you are willing to introduce this perpendicular notation wouldn't it be even easier to just define the indicator function of the primes? – Qiaochu Yuan Aug 29 '10 at 21:34
Said function is just the "coprime" predicate, which is obviously more general and more efficiently computable than is the "prime" predicate. Of course it will be a matter of taste what one permits as "nice" functions. In computational number theory, for efficiency, one often works with factorizations into coprimes rather than primes, e.g. google "gcd-free basis". – Bill Dubuque Aug 29 '10 at 21:52
Sure, but that efficiency gain is more than offset by the fact that the number you need to compute a gcd with respect to is huge. – Qiaochu Yuan Aug 30 '10 at 0:46
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. – Bill Dubuque Aug 30 '10 at 1:07

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.

-