5 votos

Ayúdame a encontrar el fallo en mi método para contar primos

He estado jugando con mi propia notación para estimar el número de enteros relativamente primos a un primor dado y he llegado a un resultado que no puede ser correcto.

Agradecería que alguien me ayudara a replantear mis observaciones en notación estándar y me ayudara a entender mi error.

Esta es mi anotación:

$H_{p_i}(x)$ = el número de enteros menores o iguales a $x$ que son relativamente primordiales para $p_i\#$

Por ejemplo:

$H_3(10) = 3 \left\{ 1,5,7 \right\}$

$H_5(30) = 8 \left\{ 1,7,11,13,17,19,23,29 \right\}$

Utilizo esta notación porque si asumo $p_0 = 1$ y $H_1(x) = x$ me sale:

$H_{p_i}(x) = H_{p_{i-1}}(x) - H_{p_{i-1}}\left(\left\lfloor\dfrac{x}{p_i}\right\rfloor\right)$

También utilizo esta notación:

$p_i\#_{-1} = (p_i -1)(p_{i-1}-1)(p_{i-2}-1)\dots(2-1)$

De modo que el primorial estándar sería:

$p_i\#_{0} = p_i\#$

Y el número de pares de $x,x+2$ que son relativamente primordiales para $p_i\#$ y donde $x < p_i\#$ es $p_i\#_{-2}$ .

Así pues, estaba razonando sobre los primoriales utilizando mi notación como hago normalmente cuando di con una fórmula sencilla para el límite inferior de cualquier $H_{p_i}$

Permítanme comenzar con $H_2(x)$ que es fácil de enunciar en términos de un límite superior e inferior:

$\dfrac{x}{2} \le H_2(x) \le \dfrac{x+1}{2}$

Ahora, me gustaría encontrar una expresión similar para $H_3(x)$ que se vuelve excesivamente complicado y poco útil si lo enfocamos de forma obvia.

Así que pensé en utilizar dos valores diferentes: $H_{\text{min}\,3}(x)$ y $H_{\text{max}\,3}(x)$ que deduzco de forma sencilla de $H_2(x)$ :

$H_{3}(x) = H_2(x) - H_2\left(\left\lfloor\dfrac{x}{3}\right\rfloor\right)$

$H_{\text{min}\, 3}(x) = \dfrac{x}{2} - \dfrac{\frac{x}{3}-\left\{\frac{x}{3}\right\}+1}{2}$

$H_{\text{max}\, 3}(x) = \dfrac{x+1}{2} - \dfrac{\frac{x}{3} -\left\{\frac{x}{3}\right\}}{2}$

para obtener los siguientes límites superior e inferior:

$\dfrac{2x-3}{6} \le H_{\text{min}\, 3}(x) \le \dfrac{2x-1}{6}$

$\dfrac{2x+3}{6} \le H_{\text{max}\, 3}(x) \le \dfrac{2x+5}{6}$

donde $H_{\text{max}\,3}(x) \ge H_3(x) \ge H_{\text{min}\,3}(x)$

Déjalo:

  • $H_{\text{min}\, \text{low}\, 3}(x) = \dfrac{2x-3}{6}$
  • $H_{\text{min}\, \text{high}\, 3}(x) = \dfrac{2x-1}{6}$
  • $H_{\text{max}\, \text{low}\, 3}(x) = \dfrac{2x+3}{6}$
  • $H_{\text{max}\, \text{high}\, 3}(x) = \dfrac{2x+5}{6}$

Entonces, tengo lo siguiente:

$H_{\text{min}\, p_i}(x) = H_{\text{min}\, \text{low}\, p_{i-1}}(x) - H_{\text{min}\, \text{high}\, p_{i-1}}\left(\left\lfloor\dfrac{x}{p_i}\right\rfloor\right)$

$H_{\text{max}\, p_i}(x) = H_{\text{max}\, \text{high}\, p_{i-1}}(x) - H_{\text{max}\, \text{low}\, p_{i-1}}\left(\left\lfloor\dfrac{x}{p_i}\right\rfloor\right)$

Usando la inducción (ver más abajo mi lógica), pude generalizar esto a:

$\dfrac{p_i\#_{-1}x - p_i(p_{i-1}\#_{-1})}{p_i\#} \le H_{\text{min}\, p_i}(x) \le \dfrac{p_i\#_{-1}x - p_i\#_{-1}}{p_i\#}$

$\dfrac{p_i\#_{-1}x + p_i(p_{i-1}\#_{-1})}{p_i\#} \le H_{\text{max}\, p_i}(x) \le \dfrac{p_i\#_{-1}x + p_i(p_{i-1}\#_{-1}) + p_i\#_{-1}}{p_i\#}$

Utilizando los resultados anteriores, intento analizar Conjetura de Legendre :

Dejemos que $p_i$ sea el mayor primo menor o igual a $x$

$\pi(x^2 + 2x) - \pi(x^2) = H_{p_i}(x^2 + 2x) - H_{p_i}(x^2) \ge H_{\text{min}\, p_i}(x^2+2x) - H_{\text{max}\, p_i}(x^2)$

$H_{\text{min}\, p_i}(x^2+2x) - H_{\text{max}\, p_i}(x^2) \ge \dfrac{p_i\#_{-1}(x^2+2x) - p_i(p_{i-1}\#_{-1})}{p_i\#} - \dfrac{p_i\#_{-1}(x^2) + p_i(p_{i-1}\#_{-1}) + p_i\#_{-1}}{p_i\#} =$

$= \dfrac{p_i\#_{-1}(x^2+2x -x^2) - (p_i + p_i + [p_i-1])(p_{i-1}\#_{-1})}{p_i\#} =$

$= \dfrac{p_i\#_{-1}(2x) - (3p_i-1)(p_{i-1}\#_{-1})}{p_i\#} > \dfrac{(p_i-1)(2x) - (3p_i-1)}{p_i p_{i-1}}$

$\dfrac{(p_i-1)(2x) - (3p_i-1)}{p_i p_{i-1}} > \dfrac{2x-3}{p_i} \ge \dfrac{2x-3}{x} =2 -\dfrac{3}{x}$

lo que sugeriría que la conjetura de Legendre es cierta para $x \ge 3$

Este resultado es ridículo dado lo primitivo de mi método. ¿Podría alguien ayudarme a ver qué estoy haciendo mal?


Esta es mi lógica detrás de la inducción.

Lema 1: $\dfrac{p_i\#_{-1}x - p_i(p_{i-1}\#_{-1})}{p_i\#} \le H_{\text{min}\, p_i}(x) \le \dfrac{p_i\#_{-1}x - p_{i-1}\#_{-1}}{p_{i}\#}$

(1) $H_{2}(x) = x - \left\lfloor\dfrac{x}{2}\right\rfloor = \dfrac{x}{2} + \left\{\dfrac{x}{2}\right\}$

(2) $H_{3}(x) = H_{2}(x) - H_2(\left\lfloor\dfrac{x}{3}\right\rfloor)$

(3) $H_{\text{min}\, 3} = \dfrac{x}{2} - \dfrac{\frac{x}{3} -\left\{\frac{x}{3}\right\}+1}{2} = \dfrac{2x-3 + 3\left\{\frac{x}{3}\right\}}{6} $

(4) $\dfrac{2x-3}{6} \le H_{\text{min}\, 3}(x) \le \dfrac{2x-1}{6}$

(5) Supongamos $\dfrac{p_i\#_{-1}x - p_i(p_{i-1}\#_{-1})}{p_i\#} \le H_{\text{min}\, p_i}(x) \le \dfrac{p_i\#_{-1}x - p_{i-1}\#_{-1}}{p_{i}\#}$

(6) $H_{p_{i+1}}(x) = H_{p_i}(x) - H_{p_i}(\left\lfloor\dfrac{x}{p_{i+1}}\right\rfloor)$

(7) $H_{\text{min}\, p_{i+1}} =\dfrac{p_i\#_{-1}x - p_i(p_{i-1}\#_{-1})}{p_i\#} - \dfrac{p_i\#_{-1}\left\lfloor\frac{x}{p_{i+1}}\right\rfloor - p_{i-1}\#_{-1}}{p_i\#} =$

$= \dfrac{p_{i+1}\#_{-1}x - p_{i+1}(p_i\#_{-1}) + (p_i\#_{-1})(p_{i+1})\left\{\frac{x}{p_{i+1}}\right\}}{p_{i+1}\#}$

(8) Así que:

$\dfrac{p_{i+1}\#_{-1}x - p_{i+1}(p_{i}\#_{-1})}{p_{i+1}\#} \le H_{\text{min}\, p_{i+1}}(x) \le \dfrac{p_{i+1}\#_{-1}x - p_{i}\#_{-1}}{p_{i+1}\#}$

Lema 2: $\dfrac{p_i\#_{-1}x + p_i(p_{i-1}\#_{-1})}{p_i\#} \le H_{\text{max}\, p_i}(x) \le \dfrac{p_i\#_{-1}x + p_i(p_{i-1}\#_{-1}) + p_i\#_{-1}}{p_i\#}$

(1) $H_{2}(x) = x - \left\lfloor\dfrac{x}{2}\right\rfloor = \dfrac{x}{2} + \left\{\dfrac{x}{2}\right\}$

(2) $H_{3}(x) = H_{2}(x) - H_2(\left\lfloor\dfrac{x}{3}\right\rfloor)$

(3) $H_{\text{max}\, 3} = \dfrac{x+1}{2} - \dfrac{\frac{x}{3} -\left\{\frac{x}{3}\right\}}{2} = \dfrac{2x+3 + 3\left\{\frac{x}{3}\right\}}{6} $

(4) $\dfrac{2x+3}{6} \le H_{\text{max}\, 3}(x) \le \dfrac{2x+5}{6}$

(5) Supongamos $\dfrac{p_i\#_{-1}x + p_i(p_{i-1}\#_{-1})}{p_i\#} \le H_{\text{max}\, p_i}(x) \le \dfrac{p_i\#_{-1}x + p_i(p_{i-1}\#_{-1}) + p_i\#_{-1}}{p_i\#}$

(6) $H_{p_{i+1}}(x) = H_{p_i}(x) - H_{p_i}(\left\lfloor\dfrac{x}{p_{i+1}}\right\rfloor)$

(7) $H_{\text{max}\, p_{i+1}} =\dfrac{p_{i}\#_{-1}x + p_i(p_{i-1}\#_{-1}) + p_i\#_{-1}}{p_i\#} - \dfrac{p_i\#_{-1}\left\lfloor\frac{x}{p_{i+1}}\right\rfloor + p_i(p_{i-1}\#_{-1}) }{p_i\#}=$

$= \dfrac{p_{i+1}\#_{-1}x + p_{i+1}(p_i\#_{-1}) + (p_i\#_{-1})(p_{i+1})\left\{\frac{x}{p_{i+1}}\right\}}{p_{i+1}\#}$

(8) Así que:

$\dfrac{p_{i+1}\#_{-1}x + p_{i+1}(p_{i}\#_{-1})}{p_{i+1}\#} \le H_{\text{max}\, p_{i+1}}(x) \le \dfrac{p_{i+1}\#_{-1}x + p_{i+1}(p_{i}\#_{-1}) + p_{i+1}\#_{-1}}{p_{i+1}\#}$


Edición: Ejemplos adicionales

$H_5(20) = H_3(20) - H_3(\left\lfloor\dfrac{20}{5}\right\rfloor) = [H_2(20) - H_2(\left\lfloor\dfrac{20}{3}\right\rfloor)] -[H_2(4) - H_2(\left\lfloor\dfrac{4}{3}\right\rfloor)] =$

$= [H_1(20) - H_1(\left\lfloor\dfrac{20}{2}\right\rfloor)] - [H_1(6) - H_1(\left\lfloor\dfrac{6}{2}\right\rfloor)] - [H_1(4) - H_1(\left\lfloor\dfrac{4}{2}\right\rfloor)] + [H_1(1) - H_1(\left\lfloor\dfrac{1}{2}\right\rfloor) =$

$= [20 - 10] - [6-3] - [4-2] +[1-0] = 6 \{1, 7, 11, 13, 17, 19\}$


Edición: Se ha añadido una aclaración sobre $3p_i - 1$ basado en un comentario.

2voto

Zander Puntos 8843

Usted ha demostrado $$ H_{\min\operatorname{low} p_i} \le H_{p_i} \le H_{\max\operatorname{high}p_i} $$ para todos $x$ , a partir de la cual se intenta demostrar

$$ \begin{align} H_{p_{i+1}}(x) & = H_{p_i}(x)-H_{p_i}(\lfloor x/p_{i+1}\rfloor) \\ &\ge H_{\min\operatorname{low} p_i}(x)-H_{\min\operatorname{high} p_i}(\lfloor x/p_{i+1}\rfloor) \\ \end{align} $$

pero desgraciadamente lo mejor que se puede decir es de hecho $$ H_{p_{i+1}}(x) \ge H_{\min\operatorname{low} p_i}(x)-H_{\max\operatorname{high} p_i}(\lfloor x/p_{i+1}\rfloor) $$ y de forma similar para el límite superior.

Sus límites para $H_\min, H_\max$ fallan muy rápidamente: $$ \frac{5\#_{-1}\cdot 28 - 5(3\#_{-1})}{5\#} = \frac{107}{15} > 7 = H_5(28) \\ \frac{5\#_{-1}\cdot 23 + 5(3\#_{-1}) + 5\#_{-1}}{5\#} = \frac{101}{15}<7 = H_5(23) $$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X