#triangle numbers

[noelements-setempty]

What badges should I get for my 28th birthday?

1, 2, 3, 4, 5, 6, and 7

1, 2, 4, 7, and 14

Voting ended onDec 6, 2023

[paulspuzzles-blog]

Solution #15

Well, all right, it wasn’t tomorrow.  I was, in fairness, busy with work :).  But yeah, solution below the line as per usual...

So I was thinking a little bit about sums, and alternate product formulas for writing out sums.  The formula for triangle numbers (aka the sum of the first n natural numbers) of course being perhaps one of the most famous formulae of all time:

The first few triangle numbers are 1, 3, 6, 10, 15, 21, 28, 36... you might be wondering why I’m bothering to list them, but I’ll be getting to that shortly.

Another formula I was thinking about was the formula for computing perfect numbers.  To recap: a perfect numbers is a numbers whose factors (other than itself) add up to itself.  E.g. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14.  There aren’t many perfect numbers, the list starts out 6, 28, 496, 8128 before leaping up to 33,550,336 and then just kinda going crazy from there.

Now the formula for even* perfect numbers is another famous mathsy formula, and is as follows:

where 2^p - 1 is prime (such prime numbers being called Mersenne primes).  3 (4-1) is prime, and so 6 (2x3) ends up being perfect.  7 (8-1) is prime, so 28 (4x7) ends up being perfect.  Then we skip up to 31 being prime, which leads to 496 (16x31) being perfect, and 127 (128-1) being prime, which leads to 8128 (64x127) being perfect.  Followed by a big ol’ leap to 8191 (8192-1) being prime and 33,550,336 (4096x8191) being perfect.

I’m honestly not sure if I’m spending too much or too little time explaining this stuff but at this point I really just want to get to the galaxy brain moment, which is:

or in other words “hey, the triangle number formula and the perfect number formula look weirdly similar.  what if... what if I just take a factor of ½ out of the perfect number formula?”

A little more arranging gives us:

So every even* perfect number is the (corresponding Mersenne prime)th triangle number!  And if you look back at the triangle numbers I listed above, sure enough, there are 6 and 28 bold as brass as the 3rd and 7th triangle numbers.  496 is the 31st triangle number, 8128 is the 127th triangle number, 33,550,336 is the 8191st triangle number, and so on and so forth.

All right.  After all that, back to the actual dang puzzle.  Well, let’s go back to our original definitions of what triangle numbers (adding up consecutive natural numbers) and perfect numbers (adding up factors of a number) involve!  For 6 we get the fascinatingly trivial

1 + 2 + 3 = 1 + 2 + 3

Cancelling down, this just gives us our first term, 0 = 0.

For 28 it gets more fun and was the starting point idea for this puzzle:

1 + 2 + 3 + 4 + 5 + 6 + 7 = 1 + 2 + 4 + 7 + 14

which cancelled down gives us our second term

3 + 5 + 6 = 14

It’s odd to think that this simple sum can be hiding so much behind it!

The third term is the same logic applied to 496, on the LHS we have the sum of the natural numbers from 1 to 31 and on the other side we have the sum of the factors of 496 (other than itself).  And hopefully you’re starting to see why doing this for the fourth term felt nightmarish, and the fifth term was unthinkable!

In some ways this is a kind of barmy puzzle but hey, I had an idea and investigated where it went and something vaguely puzzle-like popped out.  That’s how most of the puzzles on this blog work anyway.  See you in another year or something, I guess.

* An odd perfect number has never been discovered, and it’s a reasonable conjecture that there is no such thing, but it hasn’t been proven. So we’re stuck with having to qualify a lot of statements about perfect numbers with “for any even perfect number”...

[allofthemath]

The Handshake Problem

This is a really good problem for looking at through the lens of patterns.

With 1 person, there are no handshakes.

Between two people, there is one, just between the two.

For three handshakes between Alice, Bob and Carol, Alice shakes both Bob and Carol’s hand (that’s two) and then Bob and Carol need to shake hands. So that’s 3. 

Four handshakes: A, B, C, D. A shakes everyone’s hand (3). Then B has to shake C and D’s hand, but *not* A’s because they already shook. So that’s two more, and then C and D shake. That’s 6 in total.

We could run through five handshakes, or we could imagine that A, B, C and D have already done all their handshaking, and then E walks into the room. What happens? Ze shakes everyone’s hand in the room, which is 4 more. So that’s 10.

The next person has five hands to shake, so that’s 15.

So our pattern is:

0, 0+1, 0+1+2, 0+1+2+3, 0+1+2+3+4, 0+1+2+3+4+5 and so on.

So how many handshakes occur between and among 10 people? Well, the first person has to shake 9 hands, the next person 8, and so on. So 9+8+7+6+5+4+3+2+1=45.

Triangle Numbers

These are called the triangle numbers, because you can make increasing sizes of triangles like this, with each row having one more dot.

Consider, though, that in a group of 10, every person shakes 9 hands. So why aren’t there 90 handshakes? (Think about it)

Well, when two people shake hands, they both come away thinking there’s been a handshake, so there are two handshakes accounted for in the count. Each handshake is double counted, so there are 90/2=45 handshakes.

And this gives us a method for finding the number of handshakes among 100 people. It’s 100*99/2=4950. Or n people: n(n-1)/2.

This is just a bit off of the nth triangular number, because for triangular numbers, we don’t count 0 as the first, with one person. So the 100th triangular number is the number of handshakes among 101 people.

And we get a slightly different equation, which we can derive algebraically, or geometrically, which is cool. Take one of the above triangles, left justify it, double it and put them together to make a rectangle:

The area of the rectangle is n(n+1) and we divide it by two to get the area of the triangle, n(n+1)/2.

Other Problems

Diagonals: How many diagonals does an n-gon have? Go try and find a pattern!

A triangle has no diagonals. A quadrilateral has two. A pentagon has five. A hexagon has nine. 

0, 2, 5, 9. Looks like we add two, then three, then four. Why would that be?

Well, let’s look at a pentagon. There are five diagonals already. If we add a corner, what connects to that? This is our 6th corner, and it can’t connect to itself, nor to those corners directly adjacent to it. So it has three dots to connect to, adding three diagonals. But ALSO, one of the sides of our original pentagon is no longer a side, but a diagonal. This is probably best seen in pictures:

You see the original on the left, and then the new sides (in green) and the new diagonals (in purple), including IH, which was a side (DC) in the original.

What would happen next? The 7th corner will connect to four (7-itself-two adjacents=4) diagonals, and there will be another side turning into a diagonal. So 9+5=14.

So how many for a 10-gon? Well let’s recap:

3-gon (triangle): 0

4-gon (quadrilateral): 2

5-gon (pentagon): 5 (2+3)

6-gon (hexagon): 9 (2+3+4)

7-gon (heptagon): 14: (2+3+4+5)

So it looks like 10-gon would be: 8 (start at 2 less than the number of sides) +7+6+5+4+3+2 (don’t include 1) = 35.

If you notice, we have the triangle numbers minus 1, because of no shape with only 1 diagonal.

Equation

Is there a faster way, like for the triangle numbers? Well, of course you could just do the triangle numbers minus 1, but being careful about which triangle number we’re at, because we start at n=3, with a triangle, because the first triangle number (1) minus 1 =0. So we have to subtract two from our n’s.

So we could do (n-2)(n-1)/2 - 1. Let’s test to see if I’ve done it right.

For n=3: (1)(2)/2 - 1=0. Good!

Or n=10: (8)(9)/2 - 1 =35. Great.

OR, look for another pattern like the handshakes. Every corner (n) connects to every other one, except itself and the two next to it (n-3).

That’s n(n-3). But again, every line connecting two dots/corners is going to be counted twice, A to B and then B to A. So n(n-3)/2.

Again: for n=3, we get 0.

For n=10: 10(7)/2=35.

The power of patterns!

[allofthemath]

What do these have in common?

1. How many diagonals does a quadrilateral have? A pentagon? A triangle? An n-gon? 2. A line cuts a piece of paper (or a plane) into two sections. How about two lines (non parallel)? Three (only intersecting one other line at a time)? Four? N? 3. You're stacking cups. One sits on its own. Three make a triangle. How many cups do you need for the next size triangle? The next?

[whymathiscool]

[munzicodes]

Project Euler, Exercise 12

This one was all about Triangle numbers. Here's a song to get us in the mood.

Back to our regularly scheduled bit of code. 

Here was my first shot at it. 

Spoilers for exercise 12, below the fold...

While seemingly logical, this was a no-go. Ever slow, perhaps it would have worked if I let it just run on my machine for the night, but instead I turned to my pal Histocrat, always there to lend a hand.

The difference here is that instead of running through all of the numbers, we instead find all of the divisors for the square root and then multiply them by 2. This is not entirely intuitive for me, but is apparently true. In any case, the code ran significantly faster and we were able to get a workable answer. 

From there, Histocrat decided to teach me a lesson in classes:

I had learned about classes before, but to be honest I've been sort of taking a break from them and I think it was a good call. Now that I have been coding with only methods, the use for a class has become clear (or clearer anyway). Codecademy likes to talk about Classes with Persons and attributes of that person and such or classes of Animals with specific creatures defined beneath. While the semantics appear understandable through this process and a hierarchy is clear to piece a part, I find the purpose of such items are a little fuzzier until you start to go a little deeper. At least that was my experience. 

Using this TriangleNumber class we basically have this lovely container filled with an infinite amount of TriangleNumbers (sort of like our Universe Man, above, no?) Here we can easily access and do things to it. Pretty sweet. 

Also Yield to me was pretty vague before, but is becoming more and more clear. While the concept of yielding made sense, I was unclear when would you need to yield something exactly? I had yet to see a real purpose for it when learning it. But here as we have to define our each method in our Triangle Number class, it's clear, how else could you teach your computer the word each without the word yield. And how could your computer know each without you telling it first. Pretty sensible stuff.