How to determine if a number is polygonal for a polygon with s sides

Question

A polygonal number is defined as being a number represented as dots arranged in the shape of a regular polygon.

For example:

Triangular numbers are 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...

Square numbers are 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...

Pentagonal number are 0, 1, 5, 12, 22, 35, 51, 70, 92, 117, ...

and so on...

---

There are well known formulas to calculate any of these numbers. To calculate the n-th s-gonal number, one can use the formula (n^2 * (s - 2) - (n * (s - 4))) / 2

What I would like to know is, is there an efficient way to check if a given number is s-gonal for a given s?

The obvious approach would be to take successive values from a function that generates s-gonal numbers until either n is found, or the values exceed n, however this has linear time complexity.

I know there are formulas that can be used to determine if a number is s-gonal for specific values of s, but I would like one that works for any s.

Answer 1

Based on Wikipedia's article on Polygonal numbers I can up with the following predicate that seems to solve the problems I ran into with the one the OP proposed:

def isPolygonal(s, x):
    ''' Check if x is a s-gonal number '''
    assert s > 2 and s % 1 == 0 and x % 1 == 0
    # Determine if x is some nth s-gonal number,
    # fail if n doesn't come out a whole number
    n = (sqrt(8 * (s - 2) * x + (s - 4) ** 2) + (s - 4)) / (2 * (s - 2))
    return n % 1 == 0