Given an integral polynomial \$p\$, determine if \$p\$ is a square of another integral polynomial.

An integral polynomial is a polynomial with only integers as coefficients.

For example, \$x^2+2x+1\$ should gives truthy, because \$x^2+2x+1 = (x+1)^2\$.

On the other hand, \$2x^2+4x+2\$ should gives falsy: \$2x^2+4x+2 = (\sqrt{2}x+\sqrt{2})^2\$. but \$\sqrt{2}x+\sqrt{2}\$ is not an integral polynomial.


A polynomial, in any reasonable format. For example, the polynomial \$x^4-4x^3+5x^2-2x\$ may be represented as:

  • a list of coefficients, in descending order: [1,-4,5,-2,0];
  • a list of coefficients, in ascending order: [0,-2,5,-4,1];
  • a list of pairs of (coefficient, degree), in any order: [(1,4),(-4,3),(5,2),(-2,1),(0,0)];
  • a map with degrees as keys and coefficient as values: {4:1,3:-4,2:5,1:-2,0:0};
  • a string representation of the polynomial, with a chosen variable, say x: "x^4-4*x^3+5*x^2-2*x";
  • a built-in polynomial object, e.g., x^4-4*x^3+5*x^2-2*x in PARI/GP.


A value representing whether the polynomial is a square. You can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

This is , so the shortest code in bytes wins.


Here I use coefficient lists in descending order:




  • 1
    \$\begingroup\$ Related. Related. \$\endgroup\$
    – alephalpha
    Apr 24 at 23:49
  • 6
    \$\begingroup\$ Currently "Evaluate the polynomial as \$x = 10\$, check if result is square" passes all test cases, I'd suggest adding in a counter example, such as \$x + 111\$ \$\endgroup\$ Apr 25 at 5:05
  • 1
    \$\begingroup\$ Is it reasonable to require at least one coefficient, using [0] instead of []? \$\endgroup\$
    – Neil
    Apr 25 at 7:37
  • 4
    \$\begingroup\$ There is a safe "sufficiently large value" for non-square polynomials of even degree, and polynomials of odd degree can't be squares. \$\endgroup\$
    – Nitrodon
    Apr 25 at 17:57
  • 2
    \$\begingroup\$ @Nitrodon This might be fixed by requiring the leading coefficient to be a square. In that case, for a input polynomial \$p\$ with degree \$2d\$, we may write \$p=q^2+r\$ for some polynomials \$q\$ and \$r\$ such that \$\deg(q)=d\$, \$\deg(r)<d\$ (by repeatedly completing the square). Multiplying a sufficiently large square number, we may assume that \$q\$ and \$r\$ are integral. When \$x\$ is sufficiently large, we would have \$(q-1)^2<q^2+r<(q+1)^2\$, so \$q^2+r\$ being a square will force that \$r=0\$. \$\endgroup\$
    – alephalpha
    Apr 26 at 6:25

7 Answers 7


JavaScript (Node.js), 102 bytes


Try it online!

Input a list of coefficients, in descending order. The list should either contain only a zero or the first value in the list should be non-zero.

I believe it is correct. But I cannot prove it with my math knowledge. It at least passed all testcases.

  • 1
    \$\begingroup\$ Looks very similar to the algorithm I was planning to implement. \$\endgroup\$
    – Neil
    Apr 25 at 7:36

Python3, 289 bytes:

def m(a,b):
 for x,y in a:
  for j,k in b:r[y+k]=r.get(y+k,0)+x*j
 return[(r[i],i)for i in r]
def c(d,k=[]):
 if[]==d:yield k;return
 for x in R(abs(d[0][0])+1):
  for e in R(d[0][1]+1):
   for i in[1,-1]:yield from c(d[1:],k+[(i*x,e)])
f=lambda x:any(x==m(i,i)for i in c(x))

Try it online!

Basic brute force.


Python NumPy, 103 bytes

lambda a:any(poly1d(rint((a[0]**.5*poly(sort(around(roots(a),7))[::2])).real))**2-a)
from numpy import*

Attempt This Online!

Inverted output: False for squares and True for non squares.

Direct approach using roots/linear factors. Floating point issues may lurk at some point (but not with the given test cases).

Basically, we take every other root, multiply corresponding linear factors and the square root of the leading coefficient, discard imaginary and fractional components, square and compare to the input.

For those not familiar with legacy numpy polynomials: roots takes a vector coefficients and returns tthe vector of roots. poly takes a vector of roots and returns the vector of coefficients of the monic polynomial with the given roots (with multiplicity). poly1d takes a vector of coefficients and returns a polynomial object. This changes semantics of basic algebraic operations.

Python NumPy, 149 bytes

lambda l,a:all([any(poly1d(rint((fft.ifft(fft.fft(a)**.5*(1-2*int_([*bin(i)[3:]]))))[:l//2+1].real))**2-a)for i in r_[1<<l:2<<l]])
from numpy import*

Attempt This Online!

Inverted output. Takes the number of coefficients and the coefficient list.

This computes the square root directly in the Fourier domain. Unfortunately, for each Fourier coefficient we have to check both signs, making this approach more complicated than I had hoped.


Ruby, 122 bytes

->b{w=b.sum &:abs;(z=*-w..w).product(*[z]*k=b.size/2).any?{|c|x=-1;b==b.map{(0..x+=1).sum{|y|(a=c[x-y])&&c[y]?c[y]*a:0}}}}

Try it online!

Sheer brute force.


Charcoal, 56 bytes


Try it online! Link is to verbose version of code. Does not support empty lists (use [0] instead). Outputs a Charcoal boolean, i.e. - if it thinks the polynomial is a square, nothing if not. Explanation: Since @tsh beat me to my original algorithm I've gone for this approach instead but I can only prove that it has no false negatives. If someone can come up with a counterexample I'll delete this answer pending a rewrite using @tsh's approach. Edit: A counterexample was found, but @Nitrodon's claim is that only polynomials of odd degree can be counterexamples, so I've spent 5 bytes checking that the polynomial is of even degree. Edit: Another counterexample was found, so I've spent 6 bytes checking that the leading coefficient is a perfect square.


Output a - if the polynomial is of even degree.


Calculate a very large integer given by taking the absolute values of all of the coefficients, incrementing and doubling them, and then taking the product. Evaluate the polynomial at this value. Loop over the leading coefficient of the polynomial and the result.


Perform a binary search for the nearest integer to the square root of this value.


If its square does not equal the value, clear the output.

  • 1
    \$\begingroup\$ @alephalpha Now using Nitrodon's claim that my approach only fails for polynomials of odd degree. \$\endgroup\$
    – Neil
    Apr 26 at 0:18
  • \$\begingroup\$ @alephalpha If I add checks that the first and last coefficients are also perfect squares will that satisfy you? \$\endgroup\$
    – Neil
    Apr 26 at 8:50
  • \$\begingroup\$ Checking the first coefficient would be enough. I'm not sure if that large integer is sufficiently large, but I can't find any counterexample. \$\endgroup\$
    – alephalpha
    Apr 26 at 8:59

Jelly, 26 bytes


A monadic Link that accepts a non-empty list of coefficients ordered by degree* and yields 1 if the input represents the square of an integer polynomial, or 0 if not.

* i.e. the reverse order to the examples in the question, and \$0\$ being [0] rather than []

Try it online!


Same approach as loopy walt's Python answer:

  • get the polynomial with every other root of the polynomial defined by the input
  • rescale using the square root of the coefficient of the highest degree in the input
  • get the coefficients of the square of that polynomial
  • check if that is equal to the input

Just a little fiddly when the input defines a constant since we find no roots whereupon finding coefficients would error (this is why J}¹? is there).

Ærm2ÆṛJ}¹?×AṪ½Ɗ×þ`ŒdṙLƊṚ§⁼ - Link: list of coefficients, C
Ær                         - get the roots of the polynomial P defined by C
  m2                       - modulo-2 slice
         ?                 - if...
        ¹                  - ...condition: no-op (falsey if P is just a constant)
    Æṛ                     - ...then: get polynomial coefficients
       }                   - ...else: use the right argument (implicitly C) with:
      J                    -            range of length (in this case that's [1])
                             (call this list NewCoefficients)
              Ɗ            - last three links as a monad - f(C):
           A               -   absolute values
            Ṫ              -   tail (absolute of coefficient of highest degree)
             ½             -   square root
          ×                - (NewCoefficients) multiplied by (that)
                 `         - use as both arguments of:
                þ          -   table of:
               ×           -     multiplication
                      Ɗ    - last three links as a monad - f(X=that)
                  Œd       -   anti-diagonals of X (starts with main, sweeps South-East)
                                 (has the effect of grouping product coefficients by degree)
                     L     -   length of X
                    ṙ      -   rotate (the anti-diagonals) left by (length of X)
                                 (ensures that the groups are sorted by degree descending)
                       Ṛ   - reverse
                        §  - sums (sum each group of like-degree product coefficients)
                         ⁼ - equals C?

PARI/GP, 8 bytes


Attempt This Online!

A boring built-in. Return 1 for truthy and 0 for falsy.

PARI/GP, 68 bytes


Attempt This Online!

Return 0 for truthy and 1 for falsy.

Basically a port of @tsh's JavaScript answer. Interestingly, the loop body r+=(p-r^2)\r/2 looks very similar to the formula of calculating the square root of a real number using Newton's method.


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.