如何确定一个数字是否为具有 s 边的多边形

Question

多边形数字被定义为以正多边形形状排列的点表示的数字。

例如：

三角数是 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...

平方数是 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...

五角数分别是0,1,5,12,22,35,51,70,92,117,...

等等...

有众所周知的公式可以计算这些数字中的任何一个。要计算第 n 个 s-gonal 数，可以使用公式 (n^2 * (s - 2) - (n * (s - 4))) / 2

我想知道的是，对于给定的 s，是否有一种有效的方法来检查给定的数字是否是 s-gonal 的？

显而易见的方法是从生成 s-gonal 数的函数中获取连续值，直到找到 n，或者值超过 n，但是这具有线性时间复杂度。

我知道有一些公式可用于确定一个数对于特定的 s 值是否为 s 角函数，但我想要一个适用于任何 s 的公式。

Answer 1

基于 Wikipedia's article on Polygonal numbers 我可以提出以下谓词，它似乎解决了我运行 OP 提出的问题：

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

如何确定一个数字是否为具有 s 边的多边形

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

language-agnostic

algorithm

number-theory