java 定义一个数是否为三角数的最快方法

Fastest method to define whether a number is a triangular number

提问by psihodelia

A triangular number is the sum of the n natural numbers from 1 to n. What is the fastest method to find whether a given positive integer number is a triangular one?

三角形数是从1到n的n个自然数之和。查找给定正整数是否为三角形整数的最快方法是什么？

Here is a cut of the first 1200th up to 1300th triangular numbers, you can easily see a bit-pattern here (if not, try to zoom out):

这是第一个 1200th 到 1300th 三角形数的切割，您可以在这里轻松看到位模式（如果没有，请尝试缩小）：

(720600, '10101111111011011000')
(721801, '10110000001110001001')
(723003, '10110000100000111011')
(724206, '10110000110011101110')
(725410, '10110001000110100010')
(726615, '10110001011001010111')
(727821, '10110001101100001101')
(729028, '10110001111111000100')
(730236, '10110010010001111100')
(731445, '10110010100100110101')
(732655, '10110010110111101111')
(733866, '10110011001010101010')
(735078, '10110011011101100110')
(736291, '10110011110000100011')
(737505, '10110100000011100001')
(738720, '10110100010110100000')
(739936, '10110100101001100000')
(741153, '10110100111100100001')
(742371, '10110101001111100011')
(743590, '10110101100010100110')
(744810, '10110101110101101010')
(746031, '10110110001000101111')
(747253, '10110110011011110101')
(748476, '10110110101110111100')
(749700, '10110111000010000100')
(750925, '10110111010101001101')
(752151, '10110111101000010111')
(753378, '10110111111011100010')
(754606, '10111000001110101110')
(755835, '10111000100001111011')
(757065, '10111000110101001001')
(758296, '10111001001000011000')
(759528, '10111001011011101000')
(760761, '10111001101110111001')
(761995, '10111010000010001011')
(763230, '10111010010101011110')
(764466, '10111010101000110010')
(765703, '10111010111100000111')
(766941, '10111011001111011101')
(768180, '10111011100010110100')
(769420, '10111011110110001100')
(770661, '10111100001001100101')
(771903, '10111100011100111111')
(773146, '10111100110000011010')
(774390, '10111101000011110110')
(775635, '10111101010111010011')
(776881, '10111101101010110001')
(778128, '10111101111110010000')
(779376, '10111110010001110000')
(780625, '10111110100101010001')
(781875, '10111110111000110011')
(783126, '10111111001100010110')
(784378, '10111111011111111010')
(785631, '10111111110011011111')
(786885, '11000000000111000101')
(788140, '11000000011010101100')
(789396, '11000000101110010100')
(790653, '11000001000001111101')
(791911, '11000001010101100111')
(793170, '11000001101001010010')
(794430, '11000001111100111110')
(795691, '11000010010000101011')
(796953, '11000010100100011001')
(798216, '11000010111000001000')
(799480, '11000011001011111000')
(800745, '11000011011111101001')
(802011, '11000011110011011011')
(803278, '11000100000111001110')
(804546, '11000100011011000010')
(805815, '11000100101110110111')
(807085, '11000101000010101101')
(808356, '11000101010110100100')
(809628, '11000101101010011100')
(810901, '11000101111110010101')
(812175, '11000110010010001111')
(813450, '11000110100110001010')
(814726, '11000110111010000110')
(816003, '11000111001110000011')
(817281, '11000111100010000001')
(818560, '11000111110110000000')
(819840, '11001000001010000000')
(821121, '11001000011110000001')
(822403, '11001000110010000011')
(823686, '11001001000110000110')
(824970, '11001001011010001010')
(826255, '11001001101110001111')
(827541, '11001010000010010101')
(828828, '11001010010110011100')
(830116, '11001010101010100100')
(831405, '11001010111110101101')
(832695, '11001011010010110111')
(833986, '11001011100111000010')
(835278, '11001011111011001110')
(836571, '11001100001111011011')
(837865, '11001100100011101001')
(839160, '11001100110111111000')
(840456, '11001101001100001000')
(841753, '11001101100000011001')
(843051, '11001101110100101011')
(844350, '11001110001000111110')

For example, can you also see a rotated normal distribution curve, represented by zeros between 807085 and 831405? This pattern repeats itself regularly.-->

例如，您是否还可以看到一条旋转的正态分布曲线，由 807085 和 831405 之间的零表示？这种模式会定期重复。-->

回答by interjay

If nis the mth triangular number, then n = m*(m+1)/2. Solving for musing the quadratic formula:

如果n是第mth 个三角数，则n = m*(m+1)/2。m使用二次公式求解：

m = (sqrt(8n+1) - 1) / 2

So nis triangular if and only if 8n+1is a perfect square. To quickly determine whether a number is a perfect square, see this question: Fastest way to determine if an integer's square root is an integer.

n三角形也是如此，当且仅当8n+1是一个完美的正方形。要快速确定一个数字是否为完全平方数，请参阅此问题：确定整数的平方根是否为整数的最快方法。

Note that if 8n+1 is a perfect square, then the numerator in the above formula will always be even, so there's no need to check that it is divisible by 2.

请注意，如果 8n+1 是一个完全平方数，那么上式中的分子将始终为偶数，因此无需检查它是否可以被 2 整除。

回答by Mihai Toader

An integer x is triangular exactly if 8x + 1 is a square.

如果 8x + 1 是正方形，则整数 x 是三角形的。

回答by Sparky

I don't know if this is the fastest, but here is some math that should get you in the right direction...

我不知道这是否是最快的，但这里有一些数学可以让你朝着正确的方向前进......

S = n (n + 1) / 2
2*S = n^2 + n
n^2 + n - 2*S = 0

You now have a quadratic equation.

你现在有一个二次方程。

Solve for n.

求解 n。

If n does not have an fractional bits, you are good to go.

如果 n 没有小数位，您就可以开始了。

回答by Charles Bretana

Home work ?

在家工作 ？

Sum of numbers from 1 to N

从 1 到 N 的数字总和

1 + 2 + 3 + 4 + ... n-1 + n

1 + 2 + 3 + 4 + ... n-1 + n

if you add the first plus last, and then the second plus the second from last, then ...

如果你添加第一个加最后一个，然后第二个加上倒数第二个，那么......

= (1+n) + (2+n-1) + (3+n-2) + (4+n-3) + ... (n/2 + n/2+1)

= (1+n) + (2+n-1) + (3+n-2) + (4+n-3) + ... (n/2 + n/2+1)

= (n=1) + (n+1) + (n+1) + ... (n+1); .... n/2 times

= (n=1) + (n+1) + (n+1) + ... (n+1); .... n/2 次

= n(n+1)/2

= n(n+1)/2

This should get you started ...

这应该让你开始......

回答by Vishal

We just need to check if 8*(your integer to be checked)+1 is a perfect square or not!

我们只需要检查 8*(您要检查的整数)+1 是否是完全平方数！

public Boolean isSquare(int x)
{
    return(Math.sqrt(x)==(int)Math.sqrt(x));    // x will be a perfect square if and only if it's square root is an Integer.
}

}
public Boolean isTriangular(int z)
{
    return(isSquare(8*z+1));
}

回答by Shivaram

   int tri=(8*number)+1;// you can remove this for checking the perfect square and remaining all same for finding perfect square
   double trinum=Math.sqrt(tri);
int triround=(int) Math.ceil(trinum);
if((triround*triround)==tri)
     {
     System.out.println("Triangular");
     }
    else
    {
    System.out.println("Not Triangular");
    }

Here ceil will always look at next highest number so this will give a perfect chance for verification.

这里 ceil 将始终查看下一个最高数字，因此这将提供一个完美的验证机会。

回答by Stanislav Mozolevskiy

To find if the number triangular number use this formula:

要查找数字三角形数是否使用此公式：

const pagesInBook = (num) => Number.isInteger((Math.sqrt(8 * num+1) -1 )/2)   

回答by Jatin Sanghvi

The accepted answers takes you to another step of checking if the number is a perfect square. Why not simply do following? It takes same effort as finding a perfect square.

接受的答案会将您带到检查数字是否为完全平方数的另一个步骤。为什么不简单地跟随？这与找到一个完美的正方形需要同样的努力。

public final static boolean isTriangularNumber(final long x)
{
    if (x < 0)
        return false;

    final long n = (long) Math.sqrt(2 * x);
    return n * (n + 1) / 2 == x;
}