# Prime Circuit Optimisation

It's logic gates time!
You are only allowed to use NOT, OR, AND, XOR gates, accepting 1,2,2,2 inputs respectively.

PART ONE
You must build a circuit with $n$ inputs, and 1 output.
The output must be TRUE if and only if an even number of inputs are TRUE.
Can you find a solution which uses the minimal number of gates (the construction must be general for all $n$, express the number of gates in terms of $n$). Can you prove that this is the minimum?

PART TWO
You must build a circuit with $n$ inputs, and 1 output.
The output must be TRUE if and only if a multiple of three inputs are TRUE.
Once again, attempt to find an optimal general solution, expressing the number of gates needed in terms of $n$.

PART THREE
You must build a circuit with $n$ inputs, and 1 output.
The output must be TRUE if and only if exactly $x$ inputs are true. You are given what $x$ is before building the circuit.
Again, attempt to find an optimal general solution.

PART FOUR
You must build a circuit with $n$ inputs, and $n$ outputs.
The number of TRUE outputs must be the same as the number of TRUE inputs, $x$.
Additionally, if you are told what $x$ is AFTER you have built your circuit, but not which $x$ inputs are TRUE, you must still be able to determine without any doubt which $x$ outputs are TRUE.
Once again, optimise to the best of your ability.\

Edit for clarification: Build a circuit, number the outputs 1, 2, 3, 4, 5, 6, ... , n. Now, you are told that x inputs are true, and you should be able to say exactly which x outputs are true.

PART FIVE
You must build a circuit with $n$ inputs, and 1 output.
The output must be TRUE if and only if a prime number of inputs is true. :O
For clarification, 0 TRUE inputs and 1 TRUE input should both return a 0 output. Optimise to best of your ability.

You are not allowed to build a circuit with prior knowledge of what numbers are prime - I.e., the construction should be 100% general, with an identical 'structure' for each number $n$. If you have solved part 3, for example, your solution for this part cannot be 'use the construction for part 3, checking every $x$ which is a prime number less than $n$, and then ORing all of these outputs.' I understand that this restriction sounds a little strange, but essentially, it boils down to:
Your general solution must be feasibly constructable for arbitrarily large but finite $n$.
This rules out things like 'construct these modules for every prime number less than the square root of $n$', because that requires information that you don't realistically have. If you want to use information, derive it from your circuit!

• Part four is a little hazy in the description. Not really sure what you're looking for on that one. Jan 26 '17 at 12:16
• Yeah I worried that my description was a little strange. Basically, suppose your outputs are numbered 1,2,3,4,5,6,...,n. You want to built a circuit that 'sorts' the true inputs. i.e. if you had x true inputs, you should know exactly which x outputs are true. Jan 26 '17 at 12:21
• @LeppyR64 I've made an edit which hopefully clarifies things. Jan 26 '17 at 12:23
• I don't really get in what form $x$ is given in parts III and IV. Is it given the same time as $n$, before designing the circuit? Or my circuit has to be designed without $x$ being known? When $x$ is given, does it come in a binary format on $\log_2n$ bits? Or in unary on $n$ bits? Or am I told verbally, what $x$ is? Jan 26 '17 at 18:36
• For IV, X is given after the circuit must be built. You are told verbally what X is. I'll clarify this, thanks! Jan 26 '17 at 23:17

PART TWO

I won't present a detailed description of a solution, but will attempt to give some heuristics and ideas that answer the question not only in the case of multiples of 3, but for multiples of any $k$. (Though different circuits should be designed for different $k$s.)

First,

notice that if we have less than $k$ inputs, the number of TRUE signals is only divisible with $k$, if and only if it is actually $0$. Hence you can just OR them together (each gate reduces the number of signals by 1, so that's $n-1$ gates), and NOT the final result (for a total number of $n$ gates).

However,

if there are at least $k$ inputs, we have to apply a different method. We can slowly reduce the number of signals while maintaining that the number of TRUE signals modulo $k$ does not change. If we had a circuit that has $k$ inputs, $k-1$ outputs, and the amount of TRUE outputs is the same as the amount of TRUE inputs if this is smaller than $k$, and has $0$ TRUE outputs if all the $k$ inputs are TRUE, we are done: we've decreased the number of signals without affecting the modulo $k$ amount of TRUE signals. Or in other words, we are looking for a circuit that gets $k$ inputs. If at least one of those inputs is FALSE, output the other $k-1$ inputs, if all of them are TRUE, output $k-1$ FALSE signals.

A construction that achieves this:

With the SORT-implementation provided by Kruga, this needs $k^2+k-1$ gates.

Once we have this,

which I will refer to as the MOD-K circuit, the circuit that answers the original question of Part Two looks like:

If all my calculations are correct, this needs $(n-k+1)(k^2+k-1)+k-1$ gates (in the typical case of $n\ge k$).

PART FIVE

I'll refer to

this latter circuit as MULTIPLE-K, as it outputs TRUE if and only if a multiple of $k$ of the $n$ input signals was TRUE.
With that one we are quite close to a prime-testing circuit. Any $x$ is a prime if and only if it has $2$ divisors. As $x\le n$ and one of the divisors is $1$ for every integer, $x$ is prime if and only if it has $1$ divisor in the range of $2$ to $n$.
To check this, We should just pass the $n$ input signals to MULTIPLE-K circuits with all the different $k$s in the range of $2$ to $n$, collect their outputs, and check if only $1$ of those is TRUE. That can be done with sorting those $n-1$ signals, and applying a XOR on the first two outputs of the sort. That's it.
Total number of gates needed: $\Big(\sum\limits_{k=2}^{n}(n-k+1)(k^2+k-1)+k-1\Big)+(n-1)(n-2)+1=\frac{n^4+6n^3+23n^2-54n+36}{12}$

UPDATE:

I just realized,

that this is a more effective implementation of MOD-K:

using only $k(k-1)+1+(k-1)=k^2$ gates.

Furthermore,

in MOD-K there is no need for a complete SORT, we only need to make one of the FALSE signals (if there is any) get to the bottom. This is already achieved after the first pass of the bubble sort (again, see Kruga's answer for terminology), that needs $2k-2$ gates. With this, MOD-K needs a total of $3k-2$ gates, and MULTIPLE-K needs $(n-k+1)(3k-2)+k-1$.

In a similar fashion,

we don't need a complete SORT to check if only one of the MULTIPLE-Ks outputs TRUE. We just need two passes of the bubble sort, this time bubbling up instead of down (as now we are interested in identifying the 'largest' values, the TRUE signals). $x$ is prime if and only if the topmost value is TRUE, and the second is FALSE. Getting these two needs $n-2$ and $n-3$ gates respectively, and we still have to XOR them together for a final answer. So that reduces the total number of gates to: $\Big(\sum\limits_{k=2}^{n}(n-k+1)(3k-2)+k-1\Big)+(n-2)+(n-3)+1=\frac{n^3+2n^2+n-8}{2}$

• Cool! I believe this is a nice working solution for the prime checker. Jan 27 '17 at 13:08
• I think so too, but I am open to any comments. I will calculate the sum to have a closed formula for $n$. And I am very eager to see other, more effective solutions! Jan 27 '17 at 13:14
• Your sum of course does not need to go all the way up to n. It is sufficient to go up to floor(sqrt(n)) because if n factorises then at least one of its factors is less than or equal to its square root. Jan 27 '17 at 13:18
• @JaapScherphuis, nice observation. This also saves us the final sort, we just need to check if all the outputs of the MULTIPLE-Ks are FALSE (by collecting them in a big OR, and finally negating the output of that). I wasn't sure that we are actually allowed to use the concept of square roots, if they weren't calculated by the circuit. Jan 27 '17 at 13:24
• But even if using square roots was not allowed, we can skip the last MULTIPLE-K of $n$, and use the OR instead the SORT. Good point, I will edit all this in my answer, thank you! Jan 27 '17 at 13:32

PART FOUR

This can probably be done with fewer gates, but at least it's a solution

I'm gonna user a bubble sort to make the first $x$ outputs true. For that I'll need a component with 2 inputs and 2 outputs, that will swap the signals if needed. This can be done with the following circuit.

I1 | I2 | O1 | O2
-----------------
0 |  0 |  0 |  0
0 |  1 |  1 |  0
1 |  0 |  1 |  0
1 |  1 |  1 |  1

We need n-1 of these to do one pass and sort the first element. Then another n-2 for the next pass to sort the second element and so on down to 1. Here is an example for n=4. each block represents the circuit above.

This needs a total of $(n-1)n$ gates

• This also works for part 3 if you trim away all but one of the outputs. With the addition of floor(n/3)-1 extra OR gates you get a solution for part 2. Jan 26 '17 at 15:35
• @Jaap I don't see how it can be done with that few extra gates. You would need something like (not O1) or (O3 xor O4) or (O6 xor O7) or ... Jan 26 '17 at 15:51
• You're right. To check for a particular multiple of three you need to check two of the outputs, while I was thinking you only needed to check one. So you would need about n more gates (maybe n-1 or n-2, but I can't be bothered to work it out exactly). Jan 26 '17 at 16:00

PART ONE

Use a XOR gate on every group of 2 inputs and use XOR gates on every group of 2 XOR outputs until only 1 signal is left then use a NOT gate. If n is not even, send the last signal in a XOR gate along with the final result of other inputs. (Thanks to @Jaap Scherphuis to making me notice XNOR gates are not allowed)
n=5 example
1--
|--XOR--
2--              |
|
|--XOR--NOT--
|
3--              |
|--XOR--                        |----XOR------Output
4--

5--------------------------------

The number of gates needed is n.
Proof this is minimal : at best we can only get 2 input per gates which results in 1 output. So at best, we can divide the number of signal by 2 per "stages" but There is also a need for reversing the signal at least once which only the NOT can do.
Example : 8 signals -> 4 signals -> 2 signals -> 1 signal (7 gates aka n-1) + 1 gate for NOT

PART THREE

If you know X beforehand, make a circuit where the number of inputs = X then use AND gates for every group of 2 signals until only 1 output is left. This needs n-1 gates which is optimal.

PART FOUR

Not sure if I missed something but... How about using 0 gates? As many inputs as outputs, as many true inputs as true outputs, you can tell without a doubt which outputs are true and it hardly gets any more optimal than this.

PART FIVE

For now I will assume this is impossible. The interval between each prime number is random and therefore no generic circuit can support all of them.
From Wikipedia : In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known.

NOTE

OK so my ASCII drawing are pretty awful so I will use only words for the next parts...

• A simpler proof that n-1 gates is minimal is that each gate can only reduce the number of outputs by 1. So if you want to get from n signals to 1 signal, you need at least n-1 gates.
– w l
Jan 26 '17 at 6:09
• The question does not allow XNOR gates, so each XNOR you use in your solution counts as 2 gates (XOR+NOT). You could however use XOR gates everywhere, with one extra NOT gate at the end for a solution with n gates. To prove that is minimal - you need n-1 to reduce the number of outputs, but an all-false input must produce true, and none of the two-input gates do that so at least one NOT is needed. Jan 26 '17 at 10:45
• I was about to make the comment that in your ascii drawing you didn't put the NOT gate at the end like I said. However, I then realised that you can put the NOT gate anywhere at all in the circuit, and it is still a valid solution. Jan 26 '17 at 15:45
• In regards to part 4, you aren't told WHICH of the x inputs are true. So in your gateless one, you have no way of telling which outputs are true. Check out Kruga's answer, the intent of this one is a 'sorting' mechanism. In regards to part 5, I'm not sure about the existence of one or not. However, I do have a feeling it's possible to construct using the main ideas from the previous parts, hence the format of this question. It's not 'efficient', no, but neither is eratosthenes' sieve, and that'll tell you whether a finite number is prime or not :) Jan 27 '17 at 3:01
• Part 3 requires a circuit with N inputs. You must still have N inputs, and you don't know which x of them are true. Jan 27 '17 at 3:02

PART TWO   (only, overhauled) – divisibility by 3 (also 4 and 8)

Circuits for divisibility by 3, 4 and 8 are worth presenting, despite a general solution’s already being accepted, as they occupy a neat little middle-ground between the absolute minimality of division by 2 and the complex scaling required for other higher factors.

n inputs   →   1 output   =   TRUE iff the number of TRUE inputs is a multiple of 3

n = 1   and   n = 2   require n gates.
n = 3   can be done with   n +1   gates.
n ≥ 4   can be done with    4 n − 6 4 n − 8   gates   (which happens match the n +1 of n = 3 ).

(This is a little more than half the current general-approach count of   (n −3 +1)(3 2 −2) +3 −1   =   7­n −12   gates, if I correctly understand the formula there.)

Circuits for n ≤ 3 nicely build on each other, and play cameo roles in circuits that follow.

The extended circuit for divisibility by 3 will be especially intriguing after a quick peek at some simple circuitry for divisibility by 2 and 4.

Divisibility by 2   (part 1 of puzzle).   Gates   =   n

Divisibility by 4   (not asked, n ≥ 3 ).   Gates   =   3 n − 3

Signals for +1 and +2 above are relayed as binary digits of the current count’s residue, modulo 4.   According to these results for 2 and 4, divisibility by 3 should vary as 2 n, right?   Not even close.

Divisibility by 3   (extended, n ≥ 4 ).   Gates   =   4 n − 8

This was worked out from circuitry for division by 4 by adding a gate to bypass counts of 3 and rearranging the binary-digit scheme in order to allow fewer gates at the beginning and end. Without further explanation, here are worksheets that helped slim down the 3 stages of circuitry— the 5 gates at left (beginning), the repeating module of 4 gates in the middle (cycle), and 3 gates at right (end).

Beginning:

i1   i2    i3      f f T    T f f    f T f    T f T    f T T    T T f    f f f    T T T
i1 x i2             f        T        T        T        T        f        f        f
(i1 x i2) x i3        T        T        T        f        f        f        f        T
r ≠ 0             T        T        T        T        T        T        f        f
r = 1              T        T        T        f        f        f        f        f

Cycle:    r       0    1         2         0              End:     r     2 to 0    0
===  --------  --------  ==========                     ======   ===
i       -    T    f    T    f    T      f               i_n       T      f
:         :         :
r = 1     f    T    T    f    f    t F    f              r = 1      f      f
:                   :/and
r ≠ 0     f    T    T    T    T    f      f              r ≠ 0      T      f


Here is a much tidier, but less efficient, configuration for divisibility by 3. It uses 4 n − 5 gates, which is 3 more than the configuration above that gives individual treatment to inputs i3 and in

Divisibility by 8   (not asked).   Gates   =   6 n − 7

Divisibility by k = 2b generalizes to gates / input ∼ b (b +1) /2 (with b = log2k), which can be improved marginally by giving individual treatment for inputs i3 and in , as in the circuit for divisibility by 4. This circuit for divisibility by 8 gives an idea of how to treat the count of TRUE inputs as a binary number.

Open question:   Can divisibility by 3 be tested with fewer than 4 gates per additional input?   Perhaps with inputs paired and 7 gates for each pair, to average 312 gates per input.

• Lovely! This is similar to the solution I had in mind for part 2. Jan 27 '17 at 23:46
• Very nice! Isn't it possible to generalize this one for divisibility testing for other numbers? Jan 28 '17 at 7:30
• Good idea, @elias, I'll try to generalize the modulus in a way that fits on the screen. Your answer's point about "different circuits should be designed for different _k_s" is so true, as I might have incidentally found a more-efficient-than-scaled-up approach for mod 4 among other experimental configurations for mod 3. (Also, this solution for mod 3 already has an improvement being edited that saves a whopping 1 gate total, and I'm intrigued by the possibility of a nonlinear layout as well.)
– humn
Jan 28 '17 at 7:51
• I find it hilarious that you didn't use MathJax for the equations here, when you use it for so many other non-equation purposes in your puzzles.
– Deusovi
Feb 8 '17 at 2:50
• Wow, amazing effort! I wish I could +2. Feb 8 '17 at 7:07