For fixed hypotenuse, can the number of primitive Pythagorean triples exceed the number of non-primitive ones? For the equation,
$$a^2+b^2=c^2$$
if $c$ is fixed and the number of natural solutions for $a, b$ is greater than $1$, then can the number of primitive solutions (solutions in which $a, b, c$ are coprime) exceed the number of non-primitive ones?
After testing a large number of cases I believe that the number of non-primitive solutions will always exceed the number of primitive ones although I have no proof for this.
If false, what is the smallest counter-example for $c$?
 A: For some hypotenuse $c$, let the number of primitive solutions be greater than the number of non-primitive solutions. 
Assume that $p \mid c$ for some prime $p$. Clearly, there is atleast one primitive solution $(a,b,c)$. Then, we have:
$$p^2 \mid c^2 \implies p^2 \mid (a^2+b^2)$$
It is easy to see that since $p \nmid a$, we must have $p \neq 2$ and $p \not\equiv 3 \pmod{4}$. Thus, any prime $p \mid c$ satisfies $p \equiv 1 \pmod{4}$.
Now, let the prime factorization of $c$ be:
$$c=\prod_{k=1}^n p_k^{x_k}$$
where all $p_k$ are $1 \bmod{4}$. Let $p_k=(a_k+b_ki)(a_k-b_ki)$ where $(a_k+b_ki)$ and $(a_k-b_ki)$ are Gaussian primes (since all primes in naturals which are $1 \bmod{4}$ are products of two Gaussian primes). We clearly have $\gcd(a_k,b_k)=1$. Then:
$$c=\prod_{k=1}^n (a_k+b_ki)^{x_k}(a_k-b_ki)^{x_k}$$
Now, we have $c^2=a^2+b^2=(a+bi)(a-bi)$. We will write $a+bi$ as the product of some of these Gaussian Primes and $a-bi$ as the product of the rest.
For all solutions to $c^2=a^2+b^2$ (including negative), we have to split the Gaussian primes equally, i.e. since we need to maintain the fact that $a+bi$ and $a-bi$ are conjugates, whenever we write $a_k+b_ki$ in the product of $a+bi$, we are to write $a_k-b_ki$ in the product of $a-bi$ and vice versa.
For each $p_k$, we have $2x_k+1$ choices for this process since $p_k^2 \mid (a+bi)(a-bi)$ and we have to divide $(a_k+b_ki)^{2x_k}(a_k-b_ki)^{2x_k}$ (so $a+bi$ can have $a_k+b_ki$ for $t$ number of times for $0 \leqslant t \leqslant 2x_k$). Finally, we can multiply by units $i,-i,1,-1$ which is $4$ choices. Thus, the number of solutions is:
$$4\prod_{k=1}^n (2x_k+1) \geqslant 4 \cdot 3^n$$
Since we need to remove $(c,0),(0,c),(-c,0),(0,-c)$, we reduce $4$. Furthermore, we divide by $4$ since both $a$ and $b$ are positive and divide by $2$ since $(a,b)$ is the same as $(b,a)$, giving:
$$T_{\text{all}} \geqslant \frac{4\cdot3^n-4}{8} = \frac{3^n-1}{2}$$
For primitive solutions alone, we need to segregate either all of the $a_k+b_ki$ or all of the $a_k-b_ki$ to $a+bi$ since $\gcd(a,b)=1$. This only gives $2$ choices per $p_k$. Multiplying by units, total choices are $4 \cdot 2^n$.
Again, we are to do the necessary removal. $(c,0)$ won't work as primitive, so we are to only divide by $8$. Thus:
$$T_{\text{primitive}} = \frac{4 \cdot 2^n}{8}= 2^{n-1}$$
We need to have:
$$2T_{\text{primitive}} > T_{\text{all}}$$
$$2^n>\frac{3^n-1}{2} \implies 2^{n+1}>3^n-1$$
Clearly, we have $n=1$. Thus:
$$T_{\text{all}}=\frac{(2x+1)-1}{2}=x$$
$$T_{\text{primitve}}=2^{n-1}=1$$
Since we have $2T_{\text{primitive}} > T_{\text{all}}$, we have $x=1$ showing $c=p$ is prime.
Thus, only all odd prime hypotenuse of the form $4k+1$ are exceptions. 
A: Given Euclid's formula $\quad A=m^2-n^2\quad B=2mn\quad C=m^2+n^2\quad $you can find Pythagorean triples given only $C$, if they exist, by solving the $C$-function for $n$ and testing for a defined range of $m$-values to see which, if any, yield integers.
$$C=m^2+n^2\implies n=\sqrt{C-m^2}\quad\text{where}\quad \biggl\lceil\sqrt{\frac{C}{2}}\biggr\rceil \le m < \lfloor\sqrt{C}\rfloor$$
For example, I believe this is the $\textbf{smallest counter-example}$ you were looking for:
$\quad C=65\implies n=\sqrt{65-m^2}\quad \text{where}\quad \biggl\lceil\sqrt{\frac{65}{2}}\biggr\rceil=6\le m \le \lfloor\sqrt{65}\rfloor=8 $
Testing,  we find $$F(65,6)=\sqrt{65-36}=\sqrt{29}\notin\mathbb{N}\\F(65,7)=\sqrt{65-49}=\sqrt{16}=4\quad\quad\quad F(65,8)=\sqrt{65-64}=\sqrt{1}=1\quad$$ which yields
$$f(7,4)=(33,56,65)\quad\text{and}\quad f(8,1)=(63,16,65)$$
For $C=1105$, we have $24\le m\le 33$ and
$$f(24,23)=(47,1104,1105)\qquad\qquad f(31,12)=(817,744,1105)\qquad\qquad 
f(32,9)=(943,576,1105)\qquad\qquad 
f(33,4)=(1073,264,1105)\qquad $$
For many $C$-values, non-primitives out-number primitives but $\textbf{all of these triples are primitive}$ and many more are easy to find.
Euclid's formula generates primitives, doubles, and square multiples of primitives but not, for example $(9,12,15)$ or $(15,20,25)$ which are $3\&5$ times multiples of $(3,4,5)$, respectively. If this formula does not find a triple for a given value of $C$, try any of the factors of $C$ that take the form $4x+1, x\in\mathbb{N}$.
