Prime Circuit Optimisation

Question

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!

Answer 1

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}$

Answer 2

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

Answer 3

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...

Answer 4

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) +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 i ₃ and i_n

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

Divisibility by k = 2^b generalizes to gates / input ∼ b (b +1) /2 (with b = log₂ k), which can be improved marginally by giving individual treatment for inputs i ₃ and i_n , 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 3¹⁄₂ gates per input.