Common value sequence between a arithmetic sequence and quadratic sequence

Given a arithmetic sequence in the form $s(n)=an+b$, and a simple quadratic equation in the form $q(n) = n^2+d$ (however, $q(n)=an^2+bn+c$ would be ideal), find the resulting quadratic sequence of the common values between the terms. So far, I have figured out that the resulting sequence there may be multiple interleaved quadratics.

For example (starting from n = 1),

$s(n)=3n+1$; values: $4, 7, 10, 13, 16, 19, 22, 25, ..., 49, ..., 64, ...$

$q(n)=n^2$; values: $1, 4, 9, 16, 25, 36, 49, 64, ...$

the resulting sequence is $4, 16, 25, 49, 64, 100, 121, 169, 196, ...$

In this particular example, the sequence is defined by two quadratic sequences that are interleaved: $(3n-1)^2$ (odd terms) and $(3n+1)^2$(even terms)

How can a common-value sequence be constructed from the common values of a arithmetic and quadratic sequence?

I cannot seem to find a pattern by examples, and cannot think of a way to analytically approach the problem. I also cannot find any resources on the internet relating to the problem (however, my keyword game may just be weak).

Thanks in advance for any help or pointers

• oeis.org/A001082 I think that a general solution would be very complicated. Try to find an integer such that $4n+3$ is a square... – Raffaele Jul 6 '17 at 14:10

For your example, we need to solve $q(m) = s(n)$, or $m^2 = 3n + 1$, when $m$ and $n$ are natural numbers. For example, we have $q(2) = s(1)$, yielding the 4 as the first term in your sequence. Were they to be integers, we would have an example of a nonlinear (and nonhomogeneous) Diophantine equation. Maybe those keywords will help your search?
Say $$an_1^2+bn_1+c=dm_1+e=p(1^2)+q(1)+r$$$$...$$$$an_k^2+bn_k+c=dm_k+e=p(k^2)+q(k)+r$$ You can try to prove that $n_i=\alpha i + \beta$ and $m_i = ki^2+li+m$ (you can try to prove the second one - $m_i$), so that $$a(\alpha n+\beta)^2+b(\alpha n + \beta) + c = d(kn^2+l n+m)+e=pn^2+qn+r$$ So that $$a\alpha^2n^2+(2a\beta+b)\alpha n + (a\beta^2+b\beta+c)$$$$=dkn^2+dln+(dm+e)$$$$=pn^2+qn+r$$ If we chose $\alpha=d$, then $k=ad, l=2a\beta+b$. We must also have $d|(a\beta^2+b\beta+(c-e))$. If we can show that there exists $\beta$ satisfying the above then we're done. There are cases when $\beta$ doesn't exist, for eg, when $d|a$ and $d|b$ but $d$ doesn't divide $c-e$, and as @Raffaele pointed out there are no squares when the arithmetic progression is $4n+3$.