Simplificación de la función

Question

Estoy tratando de expresar más simplemente la siguiente función:

\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{ecuación }

Sé que esto es clase de una petición vaga, pero estoy tratando de alejarse de las funciones de techo y piso y posiblemente la notación de producto, sólo porque se siente como una manera hacky de expresar lo que estoy tratando de expresar.

¿Alguna idea?

Answer 1

$\left\lceil \frac{n}{k} \right\rceil - \left\lfloor \frac{n}{k} \right\rfloor$ es igual a $0$ o $1$ dependiendo de si $k$ o no se dividen $n$. En otras palabras,

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

es igual a $0$ o $1$ dependiendo de si $n$ es compuesto o prime. Así que la función está tratando de describir es la primer función de conteo. Realmente no hay manera más sencilla de describir que "la primer función de conteo," a pesar de que se sabe mucho acerca de su comportamiento asintótico.

Edit: Para funciones como la primer función de conteo, se debe reemplazar la noción de "buena fórmula" con "algoritmo rápido" (el primero es un caso especial de la segunda). La fórmula que usted escribió es equivalente a una muy lenta algoritmo: usar el método de prueba de la división para probar la primalidad de todos los enteros en su rango. Hay mucho más rápido primalidad pruebas que se traduce en mucho más rápido algoritmos para calcular $\pi(n)$, incluso a pesar de que estas pruebas no se traduce fácilmente en apariencia familiar fórmulas.

Edición #2: Como Shreevatsar menciona en los comentarios, tamiz teoría también es relevante para contar o estimar el $\pi(n)$ más directamente, sin tener que hacer todas las pruebas de primalidad.

Answer 2

Suponiendo que busque una fórmula concisa (versus un algoritmo rápido), entonces uno puede simplificar algo reemplazando el producto por un factorial y mediante el empleo de $\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}!$$

Answer 3

Depende en qué contexto quieres definir esa función (para implementaciones de ordenador?), pero tras el post de Qiaochu Yuan, por ejemplo, puede utilizar notaciones basadas en conjunto que indique el test de primalidad más claramente.

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

Claro

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

donde $\mathbb{P}$ denota el conjunto de números primos o simplemente sea el primer función de conteo $f$ es incluso más simple.