16

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?

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):

(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.-->

Improve this question
4
  • 2
    What exactly is the aim of "fastest" here? Is something like int n = sqrt((double) (2*k)); n*(n+1)/2 == k not fast enough for your purposes? Commented May 26, 2010 at 13:20
  • 2
    Testing this quickly is, one way or another, basically equivalent to testing whether an integer is a square, as others have pointed out. Here's a pretty extensive question devoted to that topic: stackoverflow.com/questions/295579/… Commented May 26, 2010 at 13:26
  • Is this part of a larger problem you're trying to solve? If so, perhaps you'd like to explain that instead? Commented May 26, 2010 at 13:39
  • @Bart: Yes, I need a fast check whether a network topology is every-to-every or not. Commented May 26, 2010 at 13:54

9 Answers 9

Reset to default
48

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

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

So n is triangular if and only if 8n+1 is 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.

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

You also need to mention that if n is triangular, then 8n+1 is a perfect square: i.e x is triangular if and only if 8x+1 is a perfect square. Having it one way is incomplete.
Very helpful. So really, in code, you could just check if sqrt(8n+1) is an integer. If it is, then n is triangular.
16

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

Improve this answer

3 Comments

If you follow the sparky's answer you will reach the test above. The problem right now is how do you check if a number is a square easily :). See interjay's answer for this.
Your answer rocks! Simple and elegant. Incidentally, it can be easily demonstrated in at least two different ways. #1 is to work it out via solving the quadratic equation. #2 is to substitue n(n+1)/2 for x in your equation and factor.
You could just test if sqrt(8x+1) is an integer, at least in code, correct?
4

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.

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

Improve this answer

Comments

3

Home work ?

Sum of numbers from 1 to 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)

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

= n(n+1)/2

This should get you started ...

Improve this answer

Comments

2

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

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)); }
Improve this answer

Comments

1 
 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.

Improve this answer

Comments

0

To find if the number triangular number use this formula:

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

Comments

0

Here is a very (most?) efficient python variation (in 3.8 & 3.9).

def isTriangular(n: int) -> bool: """ when 8.0*n+1.0 is a perfect square it is triangular """ x = 8.0*n+1.0 return x % x**0.5 == 0.0
Improve this answer

Comments

-1

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; }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.