Expressability of an electrical circuit with probabilistic switches

Question

Here is a purely number theoretical question that I got to know from our electrical engineering department.

Call a number $q\in \mathbb{N}$, good if one can do the following:

Given a set of "probabilistic" switches, each of which is open with probability $\frac{a}{q}$, $a=1,2,\dots,q-1$ (you have infinitely many of each type), and two nodes $U,V$. Then for every $n,b\in \mathbb{N}$ such that $b\le q^n-1$ one can build a simple series parallel circuit (where one can use each type of switch more than once) connecting $U$ to $V$ where the probability of $U\to V$ being open is exactly $\frac{b}{q^n}$.

The question is which numbers are good? I think the conjecture is that only numbers which are multiples of $2$ or $3$ are good. $5$ for example is not good as one can not construct a circuit which is open with probability exactly $\frac{7}{25}$.

P.S. A "simple series parallel" circuit is one that can be build recursively by the operation of placing a switch in series with our circuit or placing a switch in parallel with our circuit. For example the wheatstone bridge is not simple series parallel. Also if one for example, connects between $U,V$ two switches with probabilities $p_1,p_2$ (of being open) in series one gets a probability of $p_1p_2$ of the section $UV$ being open, while if we connect them in parallel we get a probability $1-(1-p_1)(1-p_2)$ of it being open.

EDIT: I will rephrase the question in simple mathematical terms, as the original question is poorly phrased.

Let $q\in N$. A set $S_q\subset \mathbb{Q}$ contains all numbers of the form $\frac{a}{q}$, with $a=1,2,\dots q-1$. It also satisfies the property $x\in S_q\implies \frac{ax}{q}\in S_q$ and $x+\frac{a-ax}{q}\in S_q$ for any $a=1,2,\dots q-1$.

For which $q$ does $S_q$ contain every number of the form $\frac{b}{q^n}$ (where $b < q^n$)?

Answer 1

If $p$ is a prime of size 5 or greater then it is not good. We can pick a prime $q$ such that $q$ is greater than $p$ and less than $2p-1$. If $p$ is greater than 24 we can find such a number by using a result from this paper: Jitsuro Nagura (1952). "On the interval containing at least one prime number". Proc. Japan Acad. 28: 177–181. The result is that for any number greater than 24 there is always a prime between $n$ and $(1 + 1 / 5)n$. I found this result here.For 5 we have value 7, for 7, 11, for 11, 17, for 13, 17, for 17, 29 and for 23 29. Thus for $n$ equal to 5 or greater we can always find such a value. $q/p^{2}$ has to be represented by a parallel circuit of size two with two parallel elements of the form $a/p$ and $b/p$ with $a$ and $b$ less than $p$ hence it must be of the form $1-ab/p^{2}$ with $a$ and $b$ less than $p$ but $ab$ must be less than $(p-1)(p-1)$ but then smallest value that can be so expressed is $2p-1/p^{2}$ and we have a contradiction.

25 is bad. 31/625 cannot be expressed in this system. to get 31/625 one must get it directly or by a product with 31/125. If we get 31/125 it must involve two parallel elements whose product must be 94 and whose denominators are 25 or less but 47 divides 94 and is a prime greater than 25 so we cannot obtain 31/125. If we get 31/625 from parallel elements we must have two elements whose product is 594 if they both have denominator 25 the maximum product is 576, if one has denominator 5 and the other denominator 125 the maximum product is 496. Both of these are less than 594 so we cannot express 31/625 this way. Since we have exhausted all possibilities 31/625 cannot be expressed in this system and 25 is bad.

2 is good. We can get any odd number in the range 1 to $2^{k+1}$ as a numerator of a fraction with denominator $2^{k+1}$ from an odd number in the range 1 to $2^{k}$ by either taking it in series with the element 1/2 for those numbers less than $2^{k}$ or in parallel for those numbers greater than $2^{k}$. If 2 is good then $2^{m}$ will be good because any fraction with its denominator a power of $2^{m}$ will have a denominator a power of 2. This can be extended if any prime $p$ is good by a similar argument $p^{k}$ is good. We have to take the union of this set with all previously constructed sets to take care of cases where the numerator is divisible by a power of 2.

3 is good. If we have all fractions whose numerators are in the range 1 to $3^{k}$ and whose denominator is $3^{k}$ then we can construct all fractions whose numerators are in the range 1 to $3^{k+1}$ and whose denominator is $3^{k+1}$ by taking fractions whose numerators are in the range 1 to $3^{k}$ and whose denominator is $3^{k}$ in series with $1/3$ and taking the same values in series with $2/3$ together with all fractions whose numerators are in the range 1 to $3^{k}$ and whose denominator is $3^{k}$ in parallel with $1/3$ and then taking the same values in parallel with $2/3$. The values in series with $1/3$ will give the first third of all fractions whose numerators are in the range 1 to $3^{k+1}$. The values in parallel with $1/3$ will give the last third of all fractions whose numerators are in the range 1 to $3^{k+1}$. The values in series with 2/3 will contain all even values of the middle third of all fractions whose numerators are in the range 1 to $3^{k+1}$. The values in parallel with 2/3 will contain all odd values of the middle third of all fractions whose numerators are in the range 1 to $3^{k+1}$. We have to take the union of this set with all previously constructed sets to take care of cases where the numerator is divisible by a power of 3.

Any product of any power of 3 and any power of two is good. We have the fractions $1/2$ and $2/3$ and $1/2$ in the starting set of fractions for any such set. We then use the fracion $1/3$ and $2/3$ to generate the desired set of fractions for any desired power of three whose denominator is the power of three and whose numerator is any number less than the power of three. Then we take this set in parallel with $1/2$ and take the union of this set in series with $1/2$. We repeat this process and we will eventually get the set of numbers whose numerator is is less than the product of the desired power of two and the desired power of three and whose numerator is the desired product of the desired product of two and the desired product of three. We have to take the union of this set with all previously constructed sets to take care of cases where the numerator is divisible by a power of 2, a power of three or both.

Answer 2

For any prime $p$ greater than 3 $p^{2}$ is bad. If there is prime $q$ greater than $p^{2}$ and less than $p^{2}+p-1$ then I claim that $q/p^{4}$ cannot be expressed and hence p is bad. Because $q$ is greater than $p^{2}$ it cannot be expressed by fractions with denominator $p^2$ or less in series. Because it is less than 2p^{2}-1 it cannot be expressed by fractions with denominator $p^2$ or less in parallel. The only alternative left is the product of a fraction with denominator $p$ and $q/p^{3}$. But that means that $q/p^{3}$ must be expressed in parallel but the maximum product is $p^3-p^2-p+1$ which means the minimum value which can be possibly expressed in parallel is $p^2+p-1$ but since $q$ is less than that it cannot be expressed this way and we are done. The only problem is to find such $q$.

Here are some values $q$ for some primes $p$: for 7 53, for 11 127, for 13 171, for 17 293 and for 19 367. I have already proved 25 is bad. So for all primes less than 23 and greater than 3 $p^{2}$ is bad.

Now since For any prime 23 or greater we need a prime gap of 22 or more starting before $p^{2}$ and continuing at least 22 spaces past it for the square of the prime to possibly be good. The first gap of length 22 occurs after 1129 so any prime whose square is less than 1129 is bad which means that for any prime $p$ less than 37 $p^2$ is bad. Now for any prime 37 or greater we need a prime gap of 36 or more starting before $p^2$ and continuing 36 spaces past it for the square of the prime to possibly be good. The first gap of length 36 occurs at 9551 so for any prime less than 90 $p^2$ is bad. Now for any prime greater than 90 to possibly be good there must be a prime gap of 90 or more starting at $p^2$ and continuing at least 90 spaces past it. The first gap of 90 or more occurs at 360653 so any for any prime $p$ less than 600 $p^2$ is bad. For any prime 600 or more for it to possibly be good there must be a prime gap of size at least 600 starting at $p^2$ and continuing at least 600 spaces past it. The first prime gap of size 600 or more is at 1968188556461 so any prime less than 1,000,000 and greater than 3 will have $p^2$ bad. If $p$ is greater than 1,000,000 then for $p^2$ to possibly be good then there must be a prime gap of 1,000,000 or more starting before $p^2$. Now the maximal prime gap for numbers less than 1693182318746371 is 1132 so for all primes less than the square root 3e15 or all primes less 1e7 the square of the prime is bad. The number used here come from the wikipedia article on prime gaps and the material here.

Now to extend the proof that all primes greater than 3 have bad squares past this point we note the following If there is prime $q$ greater than $p^{2}$ and less than $2p^{2}-2$ such that it is not of the form $p^{2}+mp-m$ then the square of the prime is bad. We are modifying are original argument the fraction $q/p^4$ cannot be expressed by fractions with denominators of $p^2$ in parallel or series as before the only way is to get $q/p^3$ by fractions in parallel. But the only way to do this is to have one fraction of the form $p-1/p$ and the other $p^2-m$ for m less than $p$. So that means that the only primes between $p^2$ and $2p^{2}-21$ are of the form $p^{2}+mp-m$ with $m$ less than $p$ which means that there are only the primes less than $p^2$ and $p-1$ more less than $2p^{2}-21$. But we have the following The number of primes less than x is greater than x/ln(x)+2 and less than $x/ln(x)-4$ for $x$ greater than 55. This result is from the wikipedia article on the prime number theorem which gives this citation:

^ Barkley Rosser (January 1941). "Explicit Bounds for Some Functions of Prime Numbers". American Journal of Mathematics 63 (1): 211–232. doi:10.2307/2371291.

Now for primes larger than $e^14$ we can use the inequality cited and the fact that the number of primes must be $p^{2}+mp-m$ with $m$ less than $p$ to get a contradiction but we already have all primes less than 10000000 have bad squares which mean that any prime with a possible good square must be greater than $e^{14}$ since the square of $e$ is less than 10 and hence the any prime greater than 10000000 must be greater than $e^{14}$ and we are done and the square of any prime greater than 3 is bad.