Smallest $k$ Such that $13 + 4 \cdot k \cdot p^2$ is a Perfect Odd Square Given a prime number $p$, I am looking to find the smallest positive integer $k$ such that the following equation $$13 + 4 \cdot k \cdot p^2$$ produces a perfect odd square. All variables are integers. For example, for the prime $43$, $k = 3$. For $p=103$ , it turns out that $k = 1391$. A computer program can solve this for small prime numbers. It is easy to prove that $k$ has to be odd too, which improves the search. But for larger primes, say $p&gt;10^4$, the naive approach of incrementing $k$ untill a suitable value is found just takes a long time.
It is important to mention that not all primes have any solution at all. For those which do have a solution, I am interested in an efficient way for finding it.
Is there any other approach to tackle this? Perhaps one that relates to number theory? Or any other field really which may prove useful.
There is one major optimization screaming at me here.
Check each square sequentially for whether or not it is the “odd square” that the formula equals. This will be faster because $n^2$ (for odd $n$) grows faster than the current linear formula dependent on $k$.
Of course you would start with the first square greater than $13 + 4p^2$ since any lower square is impossible.
This method will be faster when $\frac {n^2}{4p^2} &gt; n - \sqrt{4p^2} = n - 2p$.
I do not know whether or not this equation ever works out to being true. However, for sufficiently large $p$ I strongly suspect that iterating through the squares will be faster.
One may note that my formula assumes that every multiple of $p^2$ needs to be as well as every $n^2$. This cancels out as I would divide both sides by $2$. Therefore it is irrelevant.
EDIT:
I thought about this a bit more. For sufficiently small $k$ iterating through squares will be slower (because the growth rate of sequential squares will be smaller than the growth of sequential multiples of $4p^2$). Once $k &gt; 2p^2 - 1$ the growth of sequential squares outpaces the linear growth of your formula. Therefore you should add something in your code to start counting by squares once you reach $k = 2p^2 - 2$. The value of $n$ to start iterating squares would then be $n = 2p^2 - 1$.
This should be about as fast you can get (assuming $k$ exists) other than iterating through odd values of $k$ and $n$.
Not a 'real' answer, but it was too big for a comment.

I wrote and ran some Mathematica-code:
In[1]:=ParallelTable[
  If[TrueQ[
     OddQ[13 + 4*k*p^2] &amp;&amp; 
      IntegerQ[Sqrt[13 + 4*k*p^2] &amp;&amp; PrimeQ[p]]], {k, p}, 
   Nothing], {k, -10^3, 10^3}, {p, 2, 10^3}] //. {} -&gt; Nothing

Running the code gives:
Out[1]={{{1, 3}}, {{3, 3}, {3, 17}, {3, 43}, {3, 599}}, {{17, 3}, {17, 
   199}}, {{23, 3}}, {{27, 79}}, {{29, 61}}, {{51, 3}, {51, 
   53}}, {{61, 3}}, {{69, 181}}, {{87, 29}}, {{103, 3}}, {{113, 
   23}}, {{117, 3}}, {{129, 211}}, {{131, 257}}, {{153, 23}}, {{173, 
   3}}, {{191, 3}}, {{233, 17}}, {{261, 3}}, {{263, 191}}, {{283, 
   3}}, {{351, 17}}, {{367, 3}}, {{377, 467}}, {{387, 29}}, {{393, 
   3}}, {{491, 3}}, {{521, 3}}, {{537, 101}}, {{633, 3}}, {{667, 
   3}}, {{793, 3}}, {{831, 3}}, {{881, 523}}, {{971, 3}}}

So, we can see that there are a lot of pairs of solutions, in the form $\left(\text{k},\text{p}\right)$. My code, uses a brute force method and looks between $-10^3\le\text{k}\le10^3$ and $2\le\text{p}\le10^3$.

Looking for bigger examples, we can notice that we need $13+4\text{k}\text{p}^2\ge0$. This implies that $\text{k}\ge-\frac{13}{4\text{p}^2}$ so the closest integer is given by $\big\lfloor-\frac{13}{4\text{p}^2}\rfloor$. So I wrote the following code:
In[2]:=ParallelTable[
  If[TrueQ[OddQ[13 + 4*k*p^2] &amp;&amp; 
     IntegerQ[Sqrt[13 + 4*k*p^2] &amp;&amp; PrimeQ[p]]], {k, p}, Nothing], {p,
    2, 10^4}, {k, Floor[-13/(4*p^2)], 10^4}] //. {} -&gt; Nothing

Out[2]={{{1, 3}, {3, 3}, {17, 3}, {23, 3}, {51, 3}, {61, 3}, {103, 3}, {117, 
   3}, {173, 3}, {191, 3}, {261, 3}, {283, 3}, {367, 3}, {393, 
   3}, {491, 3}, {521, 3}, {633, 3}, {667, 3}, {793, 3}, {831, 
   3}, {971, 3}, {1013, 3}, {1167, 3}, {1213, 3}, {1381, 3}, {1431, 
   3}, {1613, 3}, {1667, 3}, {1863, 3}, {1921, 3}, {2131, 3}, {2193, 
   3}, {2417, 3}, {2483, 3}, {2721, 3}, {2791, 3}, {3043, 3}, {3117, 
   3}, {3383, 3}, {3461, 3}, {3741, 3}, {3823, 3}, {4117, 3}, {4203, 
   3}, {4511, 3}, {4601, 3}, {4923, 3}, {5017, 3}, {5353, 3}, {5451, 
   3}, {5801, 3}, {5903, 3}, {6267, 3}, {6373, 3}, {6751, 3}, {6861, 
   3}, {7253, 3}, {7367, 3}, {7773, 3}, {7891, 3}, {8311, 3}, {8433, 
   3}, {8867, 3}, {8993, 3}, {9441, 3}, {9571, 3}}, {{3, 17}, {233, 
   17}, {351, 17}, {1041, 17}, {1277, 17}, {2427, 17}, {2781, 
   17}, {4391, 17}, {4863, 17}, {6933, 17}, {7523, 17}}, {{113, 
   23}, {153, 23}, {1131, 23}, {1251, 23}, {3207, 23}, {3407, 
   23}, {6341, 23}, {6621, 23}}, {{87, 29}, {387, 29}, {1469, 
   29}, {2369, 29}, {4533, 29}, {6033, 29}, {9279, 29}}, {{3, 
   43}, {1703, 43}, {2001, 43}, {7101, 43}, {7697, 43}}, {{51, 
   53}, {2103, 53}, {3617, 53}, {9773, 53}}, {{29, 61}, {3093, 
   61}, {4407, 61}}, {{27, 79}, {5447, 79}, {7089, 79}}, {{537, 
   101}, {6057, 101}}, {{1391, 103}, {4317, 103}}, {{2591, 
   107}, {3147, 107}}, {{2687, 113}, {3741, 113}}, {{3923, 
   127}, {4143, 127}}, {{1257, 131}, {9129, 131}}, {{1949, 
   139}, {8997, 139}}, {{1401, 157}}, {{4593, 173}}, {{2817, 
   179}}, {{69, 181}}, {{263, 191}}, {{17, 199}}, {{129, 
   211}}, {{4341, 233}}, {{1017, 251}}, {{131, 257}}, {{3683, 
   277}}, {{2259, 311}}, {{1343, 313}}, {{2837, 389}}, {{9477, 
   433}}, {{7211, 443}}, {{377, 467}}, {{3497, 491}}, {{881, 
   523}}, {{4163, 563}}, {{1797, 569}}, {{7983, 571}}, {{3, 
   599}}, {{3533, 607}}, {{5847, 641}}, {{5667, 653}}, {{1791, 
   673}}, {{7641, 757}}, {{1473, 881}}, {{9593, 953}}, {{1317, 
   1031}}, {{519, 1069}}, {{7401, 1187}}, {{1431, 1327}}, {{1377, 
   1459}}, {{1613, 1483}}, {{237, 1559}}, {{1587, 1999}}, {{807, 
   2027}}, {{7479, 2129}}, {{207, 2311}}, {{6873, 2473}}, {{39, 
   2549}}, {{4073, 2687}}, {{4299, 2861}}, {{2441, 2887}}, {{8259, 
   2939}}, {{87, 3163}}, {{3, 3301}}, {{1629, 3371}}, {{9777, 
   3467}}, {{387, 3511}}, {{2523, 4007}}, {{3419, 4211}}, {{653, 
   4567}}, {{569, 5281}}, {{8111, 6163}}, {{3111, 6217}}, {{173, 
   7823}}, {{4859, 9161}}}