Expressability de un circuito eléctrico con probabilística de los interruptores

Question

Aquí es puramente número de pregunta teórica que llegué a conocer de nuestro departamento de ingeniería eléctrica.

Llamar a un número $q\in \mathbb{N}$, bueno si uno puede hacer lo siguiente:

Dado un conjunto de "probabilístico" interruptores, cada uno de los cuales está abierto con una probabilidad de $\frac{a}{q}$, $a=1,2,\dots,q-1$ (usted tiene un número infinito de cada tipo), y dos nodos de $U,V$. A continuación, para cada $n,b\in \mathbb{N}$ tal que $b\le q^n-1$ se puede construir una simple serie circuito paralelo (donde uno puede utilizar cada tipo de interruptor más de una vez), conectando a $U$ $V$donde la probabilidad de $U\to V$ abierto es exactamente $\frac{b}{q^n}$.

La cuestión es que los números son buenos? Creo que la conjetura es que sólo los números que son múltiplos de $2$ o $3$ son buenos. $5$ , por ejemplo, no es bueno, ya que uno no puede construir un circuito que se abre con una probabilidad de exactamente $\frac{7}{25}$.

P. S. Una "simple serie paralelo" circuito es uno de los que se puede construir de forma recursiva por la operación de la colocación de un interruptor en serie con nuestro circuito o la colocación de un interruptor en paralelo con nuestro circuito. Por ejemplo, el puente de wheatstone no es simple serie paralelo. También si uno, por ejemplo, se conecta entre el $U,V$ dos interruptores con probabilidades $p_1,p_2$ (de abrir) en serie se obtiene una probabilidad de $p_1p_2$ de la sección $UV$ ser abierto, mientras que si las conectamos en paralelo tenemos una probabilidad de $1-(1-p_1)(1-p_2)$ de la misma está abierta.

EDIT: voy a reformular la pregunta en simples términos matemáticos, como el original de la pregunta está mal formulada.

Deje $q\in N$. Un conjunto $S_q\subset \mathbb{Q}$ contiene todos los números de la forma$\frac{a}{q}$,$a=1,2,\dots q-1$. También satisface la propiedad $x\in S_q\implies \frac{ax}{q}\in S_q$ $x+\frac{a-ax}{q}\in S_q$ cualquier $a=1,2,\dots q-1$.

Para que $q$, $S_q$ contienen cada número de la forma $\frac{b}{q^n}$ (donde $b < q^n$)?

Answer 1

Si $p$ es una flor de tamaño de 5 o mayor, entonces no es bueno. Podemos elegir un primer $q$ tal que $q$ es mayor que $p$ y menos de $2p-1$. Si $p$ es mayor de 24 podemos encontrar un número mediante el uso de un resultado de este trabajo: Jitsuro Nagura (1952). "En el intervalo que contenga al menos un número primo". Proc. Japón Acad. 28: 177-181. El resultado es que para cualquier número mayor que 24 siempre hay un primer entre el$n$$(1 + 1 / 5)n$. He encontrado este resultado aquí.Para 5 tenemos un valor de 7, 7, 11, 11, 17, 13, 17, 17, 29 y 23 29. Así, por $n$ igual a 5 o mayor, siempre podemos encontrar un valor. $q/p^{2}$ tiene que ser representado por un circuito paralelo de tamaño dos con dos en paralelo de los elementos de la forma $a/p$ $b/p$ $a$ $b$ menos de $p$ por lo tanto debe ser de la forma $1-ab/p^{2}$ $a$ $b$ menos de $p$ pero $ab$ debe ser menor que $(p-1)(p-1)$ pero, a continuación, el valor más pequeño que puede ser así se expresa es $2p-1/p^{2}$ y tenemos una contradicción.

25 es malo. 31/625 no puede ser expresado en este sistema. para obtener 31/625 uno debe obtener directamente o por un producto con 31/125. Si conseguimos 31/125 se debe incluir dos elementos en paralelo cuyo producto debe ser 94 y cuyos denominadores son de 25 o menos, pero 47 divide 94 y es un primo mayor que 25, de manera que no podemos obtener 31/125. Si conseguimos 31/625 de paralelo de elementos que debe tener dos elementos cuyo producto es de 594 si ambos tienen un denominador 25 el máximo de producto es 576, si uno tiene denominador 5 y el otro denominador 125 la máxima del producto es de 496. Ambas están a menos de 594 así que no podemos expresar 31/625 de esta manera. Ya hemos agotado todas las posibilidades 31/625 no puede ser expresado en este sistema y los 25 es malo.

2 es buena. Podemos obtener cualquier número impar en el intervalo de 1 a $2^{k+1}$ como numerador de una fracción con denominador $2^{k+1}$ a partir de un número impar en el intervalo de 1 a $2^{k}$ por tomar en serie con el elemento de 1/2 para los números de menos de $2^{k}$ o en paralelo para obtener los números de mayor a $2^{k}$. Si 2 es buena, $2^{m}$ va a ser bueno, porque cualquier fracción con su denominador una potencia de $2^{m}$ tienen un denominador una potencia de 2. Esto puede ser extendido si cualquier prime $p$ es bueno por un argumento similar $p^{k}$ es bueno. Tenemos que tomar el de la unión de este conjunto con todo lo anteriormente construido conjuntos para cuidar de los casos en donde el numerador es divisible por una potencia de 2.

3 es bueno. Si tenemos todas las fracciones cuyos numeradores son en el rango de 1 a $3^{k}$ y cuyo denominador es $3^{k}$, entonces podemos construir todas las fracciones cuyos numeradores son en el rango de 1 a $3^{k+1}$ y cuyo denominador es $3^{k+1}$ tomando fracciones cuyos numeradores son en el rango de 1 a $3^{k}$ y cuyo denominador es $3^{k}$ en la serie con $1/3$ y tomando los mismos valores en serie con $2/3$ junto con todas las fracciones cuyos numeradores son en el rango de 1 a $3^{k}$ y cuyo denominador es $3^{k}$, en paralelo con la $1/3$ y, a continuación, tomar los mismos valores en paralelo con $2/3$. Los valores en serie con $1/3$ va a dar el primer tercio de todas las fracciones cuyos numeradores son en el rango de 1 a $3^{k+1}$. Los valores en paralelo con $1/3$ le dará el último tercio de todas las fracciones cuyos numeradores son en el rango de 1 a $3^{k+1}$. Los valores en serie con 2/3 contendrá todos los valores del tercio medio de todas las fracciones cuyos numeradores son en el rango de 1 a $3^{k+1}$. Los valores en paralelo con 2/3 contendrá todos los valores impares del tercio medio de todas las fracciones cuyos numeradores son en el rango de 1 a $3^{k+1}$. Tenemos que tomar el de la unión de este conjunto con todo lo anteriormente construido conjuntos para cuidar de los casos en donde el numerador es divisible por una potencia de 3.

Cualquier producto de cualquier potencia de 3 y de cualquier potencia de dos es buena. Tenemos las fracciones $1/2$ y $2/3$ $1/2$ en el conjunto inicial de fracciones para cualquier conjunto. A continuación, utilizamos la fracion $1/3$ $2/3$ para generar el conjunto deseado de fracciones para cualquier potencia de tres cuyo denominador es el poder de tres y cuyo numerador es cualquier número menor que el poder de tres. A continuación, tomamos este conjunto en paralelo con $1/2$ y tomar la unión de este conjunto en serie con $1/2$. Repetimos este proceso y vamos a conseguir finalmente el conjunto de números cuyo numerador es menor que el producto de la potencia deseada de dos deseado y el poder de tres y cuyo numerador es el producto deseado del producto deseado de los dos y el producto de tres. Tenemos que tomar el de la unión de este conjunto con todo lo anteriormente construido conjuntos para cuidar de los casos en donde el numerador es divisible por una potencia de 2, una potencia de tres o ambos.

Answer 2

Para cualquier prime $p$ mayor que 3 $p^{2}$ es mala. Si no es el prime $q$ mayor que $p^{2}$ y menos de $p^{2}+p-1$, entonces afirmo que $q/p^{4}$ no puede ser expresado y por lo tanto p es malo. Debido a $q$ es mayor que $p^{2}$ no puede ser expresado por las fracciones con denominador $p^2$ o menos en la serie. Porque es menos que 2p^{2}-1 no puede ser expresado por las fracciones con denominador $p^2$ o menos en paralelo. La única alternativa que queda es el producto de una fracción con denominador $p$$q/p^{3}$. Pero eso significa que $q/p^{3}$ debe ser expresado en paralelo, pero el máximo de producto es $p^3-p^2-p+1$ lo que significa que el mínimo valor que puede ser, posiblemente, expresados en paralelo es $p^2+p-1$ pero desde $q$ es menor que el que no puede ser expresado de esta manera y ya está. El único problema es encontrar ese $q$.

Aquí están algunos de los valores de $q$ para algunos de los números primos $p$: para el 7 de 53, de 11 127, de 13 171, 17 293 y para el 19 de 367. Ya he probado los 25 es malo. Así que para todos los números primos menos de 23 y mayor que 3 $p^{2}$ es mala.

Ahora, ya que Para cualquier prime 23 o superior tenemos un primer espacio de 22 o más comenzar antes de $p^{2}$ y continua por lo menos 22 espacios pasado por la plaza de la primer a posiblemente ser bueno. La primera brecha de longitud 22 se produce después de 1129 por lo que cualquier prime cuyo cuadrado es menor que 1129 es mala, lo que significa que para cualquier prime $p$ menos que el 37 $p^2$ es mala. Ahora para cualquier prime de 37 o más necesitamos de un primer espacio de 36 o más comenzar antes de $p^2$ y continuando con 36 espacios pasado por la plaza de la primer a posiblemente ser bueno. El primer espacio de la longitud de 36 se produce en 9551 así que para cualquier primer al menos el 90 $p^2$ es mala. Ahora para cualquier primer mayor de 90 a posiblemente ser bueno, debe haber un primer espacio de 90 o más a partir de $p^2$ y continua por lo menos 90 espacios pasado. El primer espacio de 90 o más se produce en 360653 para cualquier para cualquier prime $p$ menos de 600 $p^2$ es mala. Para cualquier primer 600 o más por él, posiblemente para ser bueno, debe haber un primer espacio de tamaño de al menos 600 partir de $p^2$ y continua por lo menos 600 espacios pasado. El primer presidente de la brecha de tamaño 600 o más en 1968188556461 por lo que cualquier prime menos de 1.000.000 y mayor que 3 se han $p^2$ malo. Si $p$ es mayor de 1.000.000 a continuación, para $p^2$ a, posiblemente, ser bueno, entonces debe haber un primer espacio de 1,000,000 o más comenzar antes de $p^2$. Ahora la máxima primer hueco para números menores que 1693182318746371 es 1132 así que para todos los números primos menor que la raíz cuadrada 3e15 o todos los números primos menos 1e7 la plaza de la prime es malo. El número que se usa aquí vienen de la wikipedia artículo sobre el primer lagunas y el material de aquí.

Ahora para extender la prueba de que todos los números primos mayores que 3 tienen mala plazas allá de este punto, podemos señalar los siguientes Si no es el prime $q$ mayor que $p^{2}$ y menos de $2p^{2}-2$ tal que no es de la forma$p^{2}+mp-m$, entonces el cuadrado de la prime es malo. Estamos modificando están argumento original de la fracción del $q/p^4$ no puede ser expresado por las fracciones con denominadores de $p^2$ en serie o en paralelo, como antes, la única forma es conseguir $q/p^3$ por fracciones en paralelo. Pero la única manera de hacer esto es tener una fracción de la forma $p-1/p$ y el otro $p^2-m$ m menos de $p$. Lo que significa que los únicos números primos entre $p^2$ $2p^{2}-21$ son de la forma $p^{2}+mp-m$ $m$ menos de $p$, lo que significa que no son sólo los números primos menos de $p^2$ $p-1$ más menos de $2p^{2}-21$. Pero tenemos las siguientes El número de números primos menos de x es mayor que x/ln(x)+2 y menos de $x/ln(x)-4$ $x$ mayor de 55 años. Este resultado es de un artículo de wikipedia sobre el primer número teorema que da a esta cita:

^ Barkley Rosser (Enero De 1941). "Límites explícitos para Algunas de las Funciones de los Números Primos". American Journal of Mathematics 63 (1): 211-232. doi:10.2307/2371291.

Ahora para los números primos mayores que $e^14$ podemos utilizar la desigualdad citado y el hecho de que el número de números primos deben ser $p^{2}+mp-m$ $m$ menos de $p$ para obtener una contradicción, pero ya tenemos todos los números primos menos de 10000000 de tener mal plazas, lo que significa que cualquier prime con una posible buena plaza debe ser mayor que $e^{14}$ desde el cuadrado de $e$ está a menos de 10 y, por tanto, la mayor que cualquier otro primer 10000000 debe ser mayor que $e^{14}$ y hemos terminado y el cuadrado de cualquier prime mayor que 3 es mala.