0
$\begingroup$

I have a series of numbers. It is in the form of a parabola. This series is guaranteed to have at least one perfect square within it (edited I thought there was only one).

The second series is also a parabola describing all possible perfect squares

The function of the first series is $$16(n^2+64n−43)$$

The subset of results I am interested in are: $$352,1424,2528,3664,4832,6032,7264,8528,9824,11152,12512 ... 29584$$

The last number $29584$ is a perfect square of $172$.

The function of the second series (all perfect squares) is $${n^2+2n+1}$$

I presumed that if I graph the first series against the second series that they would cross at the perfect square as this number is common to both.

This is not the case. They do not appear to cross using the functions above.

What I am trying to do is to find the perfect square in the first series of numbers without iterating over the numbers, There are too many to make this efficient. The example I have provided is a very simple series, most series I will be dealing with use the same function $16(x^2+bx−c)$ but result in much larger coefficients.

Clearly I am approaching this all wrong! Is there a way to find the intersection of all perfect squares and the first series of numbers such that the one and only perfect square in the first series can be found without iterating over all numbers in that series?

$\endgroup$
2
$\begingroup$

We give another approach that is also not computationally helpful when the numbers are very large, because it involves factorization.

Complete the square. We want $16((n+32)^2-1067)$ to be a perfect square $x^2$. Then $x=4y$ where $$y^2=(n+32)^2-1067.$$ So we want $$(n+32+y)(n+32-y)=1067.$$ Note that $1067=11\cdot 97$, so there are not many possibilities for $n+32+y$ and $n+32-y$.

Choose $n+32+y=97$, $n+32-y=11$. Then $y=43$, and therefore $x=172$.

Remark: We could have obtained an easier solution that does not involve factorization by choosing $n+32+y=1067$ and $n+32-y=1$. However, that is much larger than the smallest solution.

$\endgroup$
  • $\begingroup$ I can't use factoring, the numbers are too large. Iterating over the list would be quicker than trial division to find the factors. $\endgroup$ – DeveloperChris Apr 4 '15 at 10:37
  • $\begingroup$ As I pointed out, factoring is not needed to find a square, or show there isn't one. But finding other solutions is probably computationally equivalent to factoring. $\endgroup$ – André Nicolas Apr 4 '15 at 12:31
  • $\begingroup$ I am using a bit size in excess of 128. Factoring will take far too long. I need to redo my number series and see if I can come up with a better approach. I was aiming for the intersection of two graphs resulting in a quick algorithm. near polynomial time is the target. $\endgroup$ – DeveloperChris Apr 5 '15 at 4:41
  • $\begingroup$ I had a Doh! moment last night and realised what I was trying to do was not doable in the way I was trying.. Your answer is both the correct answer to the question asked and the first submitted so I have marked yours as correct $\endgroup$ – DeveloperChris Apr 7 '15 at 23:17
2
$\begingroup$

Because $16$ is a square, any time $16(n^2+64n-43)$ is a square, so is $n^2+64n-43$. Write $n^2+64n-43=k^2$. Complete the square in $n$, getting $(n+32)^2-1067=k^2, (n+32-k)(n+32+k)=1067=11\cdot 97$ We can have $k=43,n=22$ or $k=533,n=502$ if we insist that both $n,k$ are positive. The squares in your series are $16k^2$, so $172^2$ and $2132^2$

$\endgroup$
  • $\begingroup$ see my comment in Andre's answer $\endgroup$ – DeveloperChris Apr 4 '15 at 10:38
  • $\begingroup$ You can do modular arithmetic things to eliminate possibilities. In base $10$, many numbers of the sequence end in $2$, so cannot be squares. In binary you can count the trailing zeros. If there are an odd number you don't have a square. You can also easily check if it is divisible by 3 but not 9 and rule it out. I don't know a way without factoring to find the numbers directly. $\endgroup$ – Ross Millikan Apr 4 '15 at 12:49
  • $\begingroup$ That was the approach I was taking before I thought of being able to use the intersection of the two graphs. I realise now my numbers series results in a parabola where the sides are too steep. This is because of the rules I had already applied. I will now seek to redefine my number series. $\endgroup$ – DeveloperChris Apr 5 '15 at 4:36
  • $\begingroup$ I have played around with a few different parameters but made no real progress. I guess my mistake was that because of the quadratic nature of the number series and the fact it contained a maximum of two perfect squares (I had forgotten to include $1067*1$) that it should intersect a series of perfect squares $n^2$ in only two places. Thus allowing me to intersect the two and get the answers. I am confused though as to why it doesn't intersect as I expected it would. $\endgroup$ – DeveloperChris Apr 7 '15 at 11:51
  • $\begingroup$ I appreciate the help you have given in understanding what I was trying to do and why I was wrong in my assumptions. Andre's answer was first and correct so I have marked that as the answer yours was equally correct so I have marked it up. Thanks I appreciate the help. $\endgroup$ – DeveloperChris Apr 7 '15 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.