# Thread: A problem I can't figure out at all!

1. ## A problem I can't figure out at all!

OK, I am actually in a bit of *rage mood* at the moment. So, I'll try to finish the question quick. I am trying to solve Problem 45 of Project Euler.
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

 Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ... Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, ... Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, ...
It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.

So, after researching a bit, I summed up that every 'odd' n Triangular number is a Hexagonal number. So, if I generate Triangular numbers from after n = 285, with n being odd and check if its Pentagonal or not, I'll find the next triangle number that is also pentagonal and hexagonal. I wrote a code for that. But it doesn't give the correct result. Why? IDK. But in my program if I put n = say 283. So when n reaches 285 I get 40755 as in the question. So why doesn't it give the correct answer for the question when n > 285.

Here is my code:
Code:
#include <iostream>
#include <cmath>

using namespace std;

unsigned long genTriNum(long n);

int main()
{
for(int i = 287; answer < 1; i += 2)
{
unsigned long cur_tn = genTriNum(i);
if(checkPentagonal(cur_tn))
{
break;
}
}
cin.get();
cin.ignore();
return 0;
}

{
if(fmod(xyz, 2) == 0 || fmod(xyz, 3) == 0)
{
return true;
}
else
{
return false;
}
}

unsigned long genTriNum(long n)
{
unsigned long nth_term = n*((n+1)/2);
return nth_term;
}

2. When something seems inexplicable, it's usually because you've made an incorrect assumption. Your assumption that "every 'odd' n Triangular number is a Hexagonal number" is wrong. Try printing out the first hundred triangular numbers. What do you see?

The pattern is actually two odds, two evens, two odds, two evens, etc. This is obvious when you consider that the formula for triangular numbers is the same for summing the numbers from 1 to n. When you add an even number to a number, the odd/evenness doesn't change. When you add an odd number to a number, it toggles the odd/evenness. When summing consecutive integers, therefore, the odd/evenness therefore changes every other time, not every time.
Code:
The first few go:
1     1   odd
2     3   odd
3     6   even
4    10   even
5    15   odd
6    21   odd
7    28   even
8    36   even
9    45   odd
10    55   odd
EDIT: Hmmm, I think I may have completely misunderstood the question here. I'll think about it some more...

EDIT2:
Try changing this:
Code:
return fmod(x, 2) == 0 || fmod(x, 3) == 0;
to this
Code:
return fmod(x, 6) == 5;

3. Originally Posted by oogabooga
When something seems inexplicable, it's usually because you've made an incorrect assumption. Your assumption that "every 'odd' n Triangular number is a Hexagonal number" is wrong.
My assumption isn't wrong. Lets make a table of odd n, Triangular(n) and Is Hexagonal?

n (odd) -----Triangular(n)----- Is Hexagonal
------------ --------------- -----------------------
1------------------1 -------------------Yes
3----------------- 6-------------------- Yes
5 ----------------15 ------------------- Yes
7 ----------------28 -------------------- Yes
9 --------------- 45 -------------------- Yes
11-------------- 66 --------------------- Yes
13 ---------------91 --------------------- Yes
15 --------------120 ----------------------Yes

Edit:
Still no good after changing to
Code:
fmod(x, 6) == 5

4. You assumption about each hex number equals every other tri number is true. Assuming checkPentagonal() is mathematically correct, the issue could be due to rounding with the math causing problems with checking for numbers == 0. You could try using an integer square root routine which would be a loop. If there is no integer square root, then return a false.

For the rounding issue, you could try something like if (4.99999999 < fmod(x, 6.)) && (fmod(x,6.) < 5.00000001)).

5. I wrote this C program using a different method from yours. It finds the next number that is both triangular and pentagonal. The n value is odd, so if your theory about hexagonal numbers is correct it is also hexagonal.
Code:
#include <stdio.h>

int main(void) {
int t = 285, p = 165, tri = 0, pent = 1;

while (tri != pent) {
p++;
do {
t++;
tri  = t*(t+1)/2;
pent = p*(3*p-1)/2;
} while (tri < pent);
t--;
}

printf("t=%d p=%d result=%d\n", t, p, tri);

return 0;
}
The output is:
t=3975 p=2296 result=7906276

Note to mods:
The "Post quick reply" box seems to be double-spacing text.

6. Originally Posted by oogabooga
I wrote this C program using a different method from yours.
Just a note - line 11 could be moved out of the inner loop - and placed between lines 7 and 8

7. Originally Posted by vart
Just a note - line 11 could be moved out of the inner loop - and placed between lines 7 and 8
Good point. Thanks.

8. This seems to be the proper test for pentagonal numbers:
Code:
#include <iostream>
#include <cmath>

typedef unsigned long ulong;

bool checkPentagonal(ulong n)
{
double x = (sqrt(24.0 * n + 1) + 1) / 6;
return floor(x) == x;
}

int main()
{
for (size_t i = 1; i < 2000; i++)
if (checkPentagonal(i))
std::cout << i << '\n';
}

9. Originally Posted by oogabooga
This seems to be the proper test for pentagonal numbers:
Code:
#include <iostream>
#include <cmath>

typedef unsigned long ulong;

bool checkPentagonal(ulong n)
{
double x = (sqrt(24.0 * n + 1) + 1) / 6;
return floor(x) == x;
}

int main()
{
for (size_t i = 1; i < 2000; i++)
if (checkPentagonal(i))
std::cout << i << '\n';
}

Aww yeah!! The solution came correct when I replaced my checkPentagonal() function with yours.
Thanks a bunch dude.

Output: 1533776805

The new code:
Code:
#include <iostream>
#include <cmath>

using namespace std;

unsigned long genTriNum(long n);

int main()
{
for(int i = 287; answer < 1; i += 2)
{
unsigned long cur_tn = genTriNum(i);
if(checkPentagonal(cur_tn))
{
break;
}
}
cin.get();
cin.ignore();
return 0;
}

{
double x = (sqrt(24.0 * somenum + 1) + 1) / 6;
return floor(x) == x;
}

unsigned long genTriNum(long n)
{
unsigned long nth_term = n*((n+1)/2);
return nth_term;
}
And thank you all for trying to help me .

EDIT:
Just a quick question. What does floor() do?

10. > Just a quick question. What does floor() do?

No wait, that's what you're supposed to do when confronted with the unknown.

11. Originally Posted by Salem
> Just a quick question. What does floor() do?

No wait, that's what you're supposed to do when confronted with the unknown.

12. Note:

n(n+1)/2 = sum(1 to n) of i
n(3 n-1)/2 = sum(1 to n) of 3i - 2
n(2 n-1) = n(4 n - 2)/2 = sum(1 to n) of 4i - 3

Truncation still could be an issue. If x is slightly truncated, then floor(x) will be about x - 1.0 and floor(x) == x will fail. You could use a integer check, alternate example:

Code:
#include <iostream>
#include <cmath>

using namespace std;

unsigned long checkPentagonal(unsigned long s);
unsigned long genTriNum(unsigned long n);

int main()
{
unsigned long t;
unsigned long p = 0ul;
unsigned long s;
for(t = 287; 1; t += 2)
{
s = genTriNum(t);
if(p = checkPentagonal(s))
break;
}
cout << "Answer: " << s << ' ' << t << ' ' << p << endl;
cin.get();
cin.ignore();
return 0;
}

unsigned long checkPentagonal(unsigned long s)
{
double dp = (1. + sqrt((24. * (double)s + 1.)))/6.;
unsigned long p = (int) (dp+.5);
if((p*(3*p-1)) == 2*s)
return p;
else
return 0;
}

unsigned long genTriNum(unsigned long n)
{
unsigned long s = (n*(n+1))/2;
return s;
}

13. Here's a fix-up of the code from post #5.
It gets the same answer as yours.
Code:
#include <stdio.h>

int main(void) {
unsigned t = 287, p = 165, tri, pent;

do {
p++;
pent = p * (3 * p - 1) / 2;
t -= 2;
do {
t += 2;
tri  = t * (t + 1) / 2;
} while (tri < pent);
} while (tri != pent);

printf("t=%u p=%u result=%u\n", t, p, tri);

return 0;
}
/* Output:
t=55385 p=31977 result=1533776805
*/
Note to mods: It's not just the "Post quick reply" that double-spaces. Even if you choose "Go Advanced" it will do it. It only does it the first time, i.e., paste some code into the box (in code tags, of course) and pick "Preview Post"; single empty lines are turned into double empty lines. If you delete the extra lines and pick "Preview Post" again, it won't do it anymore.

14. Wait, if we have 3 equations with 3 unknowns, can't we just represent this as a linear system of equations?

15. Originally Posted by MutantJohn
Wait, if we have 3 equations with 3 unknowns, can't we just represent this as a linear system of equations?
It's two equations, 3 unknowns, and you want to solve for solutions with integer values:

t(t + 1)/2 = p(3 p - 1)/2 = h(2 h-1)