Like Tree6Likes

A problem I can't figure out at all!

This is a discussion on A problem I can't figure out at all! within the C++ Programming forums, part of the General Programming Boards category; OK, I am actually in a bit of *rage mood* at the moment. So, I'll try to finish the question ...

  1. #1
    Registered User Stormboy's Avatar
    Join Date
    Aug 2013
    Location
    Planet Earth
    Posts
    12

    Angry 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.
    It reads:
    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;
    
    bool checkPentagonal(unsigned long somenum);
    unsigned long genTriNum(long n);
    
    int main()
    {
        unsigned long answer = 0;
        for(int i = 287; answer < 1; i += 2)
        {
            unsigned long cur_tn = genTriNum(i);
            if(checkPentagonal(cur_tn))
            {
                answer = cur_tn;
                break;
            }
        }
        cout << "Answer: " << answer << endl;
        cin.get();
        cin.ignore();
        return 0;
    }
    
    bool checkPentagonal(unsigned long somenum)
    {
        double xyz = (sqrt(double((24*somenum)+1))+1)/6;
        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;
    }
    Please help, I've been trying this all day.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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;
    Last edited by oogabooga; 08-29-2013 at 12:49 PM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User Stormboy's Avatar
    Join Date
    Aug 2013
    Location
    Planet Earth
    Posts
    12
    Quote Originally Posted by oogabooga View Post
    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
    Last edited by Stormboy; 08-29-2013 at 01:01 PM.

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,322
    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)).
    Last edited by rcgldr; 08-29-2013 at 01:23 PM.

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    Last edited by oogabooga; 08-29-2013 at 01:21 PM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Quote Originally Posted by oogabooga View Post
    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
    oogabooga likes this.
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by vart View Post
    Just a note - line 11 could be moved out of the inner loop - and placed between lines 7 and 8
    Good point. Thanks.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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';
    }
    Stormboy likes this.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Registered User Stormboy's Avatar
    Join Date
    Aug 2013
    Location
    Planet Earth
    Posts
    12
    Quote Originally Posted by oogabooga View Post
    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;
     
    bool checkPentagonal(unsigned long somenum);
    unsigned long genTriNum(long n);
     
    int main()
    {
        unsigned long answer = 0;
        for(int i = 287; answer < 1; i += 2)
        {
            unsigned long cur_tn = genTriNum(i);
            if(checkPentagonal(cur_tn))
            {
                answer = cur_tn;
                break;
            }
        }
        cout << "Answer: " << answer << endl;
        cin.get();
        cin.ignore();
        return 0;
    }
     
    bool checkPentagonal(unsigned long somenum)
    {
        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. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,762
    > Just a quick question. What does floor() do?
    It searches google for the answer.

    No wait, that's what you're supposed to do when confronted with the unknown.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Registered User Stormboy's Avatar
    Join Date
    Aug 2013
    Location
    Planet Earth
    Posts
    12
    Quote Originally Posted by Salem View Post
    > Just a quick question. What does floor() do?
    It searches google for the answer.

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

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,322
    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;
    }
    Last edited by rcgldr; 08-29-2013 at 03:45 PM.
    Stormboy likes this.

  13. #13
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    Last edited by oogabooga; 08-29-2013 at 05:18 PM. Reason: fixed it up a little more...
    Stormboy likes this.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  14. #14
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,238
    Wait, if we have 3 equations with 3 unknowns, can't we just represent this as a linear system of equations?

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    1,322
    Quote Originally Posted by MutantJohn View Post
    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)
    Last edited by rcgldr; 08-29-2013 at 08:21 PM.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Cannot figure out my problem can anyone help?
    By caffrea4 in forum C++ Programming
    Replies: 3
    Last Post: 04-20-2011, 02:50 PM
  2. figure - problem
    By jamesfisher in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2009, 05:28 PM
  3. I cant figure the problem out!
    By jturner38 in forum C Programming
    Replies: 5
    Last Post: 03-25-2009, 02:13 AM
  4. strcmp problem, whats the problem, i cant figure it out!
    By AvaGodess in forum C Programming
    Replies: 14
    Last Post: 10-18-2008, 07:45 PM
  5. Can'nt figure out problem
    By HAssan in forum C Programming
    Replies: 7
    Last Post: 12-26-2005, 08:11 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21