un primer práctica función de conteo

Question

Mirando el Primer conteo de funciones en la Wikipedia, sólo he encontrado fórmulas con ningún indicio sobre cómo la gente llegó allí. Así, para entender mejor, me he decidido a crear uno desde cero, a partir de un ingenuo tipo de Tamices de Eratóstenes. Aquí es lo que he encontrado hasta ahora: $$\text{Vamos a } k = \left\lfloor\frac {x - 1} {6} \right\rfloor \text{ y una función } p1(x) \text {: }$$ $$p1(x)=k-\sum _{i=1}^{6i^2-2i\leqslant k} \left( \left\lfloor \frac{k+i}{6i-1}\right\rfloor -i+1 \right) - \sum _{i=1}^{6i^2+2i\leqslant k} \left( \left\lfloor \frac{k-i}{6i+1}\right\rfloor -i+1 \right) + \sum _{i=0}^{i\leqslant \frac{k-29}{25}} \left( \left\lfloor \frac{k+5i+6}{30i+35}\right\rfloor -1 \right) + \sum _{i=0}^{i\leqslant \frac{k-29}{35}} \left\lfloor \frac{k-5i-4}{30i+25}\right\rfloor + \sum _{i=0}^{i\leqslant \frac{k-64}{35}} \left( \left\lfloor \frac{k+7i+13}{42i+77}\right\rfloor -1 \right) + \sum _{i=0}^{i\leqslant \frac{k-57}{49}} \left( \left\lfloor \frac{k-7i-8}{42i+49}\right\rfloor -1 \right)$$ $$\text{y vamos a } k=\left\lfloor \frac{x+1}{6}\right\rfloor \text{ y una función } p2(x) \text{tales que}:$$ $$p2(x)=k-\sum _{i=1}^{i\leqslant \frac{k+1}{7}} \left\lfloor \frac{k-i}{6i-1}\right\rfloor + \sum _{i=0}^{i\leqslant \frac{k-21}{25}} \left( \left\lfloor \frac{k+5i+4}{30i+25}\right\rfloor -1 \right) + \sum _{i=0}^{i\leqslant \frac{k-41}{35}} \left\lfloor \frac{k-5i-6}{30i+35}\right\rfloor + \sum _{i=0}^{i\leqslant \frac{k-41}{35}} \left( \left\lfloor \frac{k+7i+8}{42i+49}\right\rfloor -1 \right)$$ $$\text{para cualquier } x\leqslant 874, \text {:}$$ $$2+p1(x)+p2(x)= \pi (x)$$ Aunque el resultado parece complicado, este es sólo muy simples sumas y programación de un algoritmo que coincide con ella es realmente sencillo. Aquí, por ejemplo, es el correspondiente código de Mathematica:

Manipulate[
 Module[{panel, p1, p2, pcount},

  p1[x_] :=
   Module[{k, i, sum, sum1, sum2, sum3, sum4, sum5, sum6},
    k = Floor[(x - 1)/6];
    sum1 = (i = 1; sum = 0; 
      While[6*i^2 - 2*i <= k, sum += Floor[(k + i)/(6*i - 1)] - i + 1;
        i++]; sum);
    sum2 = (i = 1; sum = 0; 
      While[6*i^2 + 2*i <= k, sum += Floor[(k - i)/(6*i + 1)] - i + 1;
        i++]; sum);
    sum3 = (i = 0; sum = 0; 
      While[i <= (k - 29)/25, 
       sum += Floor[(k + 5*i + 6)/(30*i + 35)] - 1; i++]; sum);
    sum4 = (i = 0; sum = 0; 
      While[i <= (k - 29)/35, sum += Floor[(k - 5*i - 4)/(30*i + 25)];
        i++]; sum);
    sum5 = (i = 0; sum = 0; 
      While[i <= (k - 64)/35, 
       sum += Floor[(k + 7*i + 13)/(42*i + 77)] - 1; i++]; sum);
    sum6 = (i = 0; sum = 0; 
      While[i <= (k - 57)/49, 
       sum += Floor[(k - 7*i - 8)/(42*i + 49)] - 1; i++]; sum);
    k - sum1 - sum2 + sum3 + sum4 + sum5 + sum6
    ];

  p2[x_] :=
   Module[{km, i, sum, sum1, sum2, sum3, sum4, sum5, sum6},
    km = Floor[(x + 1)/6];
    sum1 = (i = 1; sum = 0; 
      While[i <= (km + 1)/7, sum += Floor[(km - i)/(6*i - 1)]; i++]; 
      sum);
    sum2 = (i = 0; sum = 0; 
      While[i <= (km - 21)/25, 
       sum += Floor[(km + 5*i + 4)/(30*i + 25)] - 1; i++]; sum);
    sum3 = (i = 0; sum = 0; 
      While[i <= (km - 41)/35, 
       sum += Floor[(km - 5*i - 6)/(30*i + 35)]; i++]; sum);
    sum4 = (i = 0; sum = 0; 
      While[i <= (km - 41)/35, 
       sum += Floor[(km + 7*i + 8)/(42*i + 49)] - 1; i++]; sum);
    km - sum1 + sum2 + sum3 + sum4
    ];

  pcount[x_] := 2 + p1[x] + p2[x];

  panel =
   Panel@Column[{
      Grid[{
        {"x", x}, {"\[Pi](x)", PrimePi[x]}, {"pcount(x)", pcount[x]}
        }, Alignment -> {Left, Top}, Frame -> All]
      }];

  panel
  ]
 , {{x, 301}, 1, 1500, 1, Appearance -> "Open"}
 ]

He encontrado muy interesante el hecho de que usted no tiene que confiar en la tabla de los números Primos ni necesidad de prueba de la división.

Aunque el rango de $x\leqslant 874$ (de hecho, también funciona para el rango de $1001\leqslant x\leqslant 1224$) es muy pequeña, creo que la fórmula puede ser extendido a cualquier rango mediante la adición de cantidades necesarias, pero después se hace difícil evitar duplicados cuenta.

EDIT1: algunas personas incomprendido "por la adición de cantidades necesarias". Me refiero en el hecho de que yo estoy bastante seguro de que $p1(x)$ $p2(x)$ válido para cualquier $x$ puede ser escrita en la forma de un único doble de la suma de $k$ (i.e: $pn(x)=\sum \sum f(k)$ ).

Yo no encuentro nada en la red sobre este o el mismo tipo de fórmula. ¿Alguien sabe algo al respecto?

Answer 1

No quiero ser pesimista, pero la complejidad computacional de esta "fórmula" es más probable que la mayor o igual a la complejidad de sólo ejecutar el tamiz de la misma. Sin embargo, en realidad hay "fórmulas" para los números primos, que sólo tienen un enorme complejidad de la computación. Por ejemplo, ver aquí. También, se discuten las cuestiones antes mencionadas.

Yo uso "fórmulas" en la comilla porque la fórmula se supone que simplifican enormemente el proceso de búsqueda de una solución a un problema. Por ejemplo, la integración de las fórmulas simplifican enormemente el proceso de adición de un (naciones unidas)contable importe de las cosas y de monto indeterminado de veces! Las fórmulas mencionadas no hacen eso, lo que generalmente no se consideran fórmulas.

Básicamente lo que hay, se traduce en un algoritmo en el formalismo matemático.

Answer 2

Muy pocas personas han buscado fórmulas para los primos de antes; este esfuerzo cae en el cuerpo de la obra. Usted puede convertir esto en un primer examen a través de pcount(x+1)-pcount(x).

Por desgracia, este algoritmo no parece ser más simple que un directo tamiz, y no parece ser más compacta que una lista de números primos (por ejemplo, el espacio necesario para almacenar el algoritmo es aproximadamente igual a la que se requiere para almacenar simplemente una lista de todos los números primos hasta 874). No es posible tener un único polinomio que se obtiene de todos los números primos (esto fue demostrado por Legendre). Si usted permite piso funciones (como el OP no), entonces una sola fórmula es suficiente (esto fue demostrado por los Molinos).

Si la fórmula fueron generados por computadora, es decir, si 874 fueron un parámetro, que podrían convertir a 2000 o lo que te guste y automáticamente obtener la correspondiente fórmula, entonces ESA parte podría ser interesante. Por desgracia, la fórmula que se presenta es de interés limitado en sí mismo.