Thread: My homework c project (help)

  1. #1
    Registered User
    Join Date
    Dec 2019
    Posts
    17

    My homework c project (help)

    PROBLEM
    Let g(n) be a sequence defined as follows:
    g(4) = 13,
    g(n) = g(n-1) + gcd(n, g(n-1)) for n > 4. gcd is great common divisor.


    The first few values are:


    n 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
    g(n) 13 14 16 17 18 27 28 29 30 31 32 33 34 51 54 55 60 ...


    You are given that g(1000) = 2524 and g(1000 000) = 2624152.


    Find g(10^15).

    HOW CAN I SOLVE THIS PROBLEM. PLEASE HELP ME!!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Is this a C project in that you're supposed to write a C program to find g(10^15), or is this more of a computer science project such that you could write a C program if you wanted, but could use other means as well?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    You need to find some kind of pattern. The results of this program look promising. Presumably the runs get larger and larger. Maybe you can take advantage of that.
    Code:
    #include <stdio.h>
     
    typedef long Int;
     
    Int gcd(Int a, Int b) {
        while (b) { Int t = a % b; a = b; b = t; }
        return a;
    }
     
    int main() {
        Int n = 4, g = 13;
        int cnt = 1;
        for (++n; n <= 5000; ++n) {
            Int g_prev = g;
            g = g_prev + gcd(n, g_prev);
            if (g == g_prev + 1)
                ++cnt;
            else {
                printf("%4ld.  %5ld   (%4d)\n",
                       n - cnt, g_prev, cnt);
                cnt = 1;
            }
        }
    }

    Code:
    .  4.     14   (   2)
       6.     18   (   3)
       9.     34   (   8)
      17.     51   (   1)
      18.     55   (   2)
      20.     60   (   1)
      21.     82   (  20)
      41.    123   (   1)
      42.    166   (  41)
      83.    249   (   1)
      84.    334   (  83)
     167.    501   (   1)
     168.    505   (   2)
     170.    510   (   1)
     171.    517   (   5)
     176.    528   (   1)
     177.    706   ( 176)
     353.   1059   (   1)
     354.   1064   (   3)
     357.   1081   (  11)
     368.   1104   (   1)
     369.   1111   (   5)
     374.   1122   (   1)
     375.   1127   (   3)
     378.   1135   (   2)
     380.   1140   (   1)
     381.   1522   ( 380)
     761.   2283   (   1)
     762.   3046   ( 761)
    1523.   4569   (   1)
    1524.   4576   (   5)
    1529.   4587   (   1)
    1530.   4592   (   3)
    1533.   4600   (   2)
    1535.   4605   (   1)
    1536.   4625   (  18)
    1554.   4667   (   6)
    1560.   6238   (1559)
    3119.   9357   (   1)
    3120.   9367   (   8)
    3128.   9384   (   1)
    A little inaccuracy saves tons of explanation. - H.H. Munro

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Not that anyone cares, but there is an error in the code above. Here is the fixed code and table. The last value (in parentheses) indicates how many values are in sequence from that point until the next line of the table. For instance, for n=1560 the value is 4680 and continues in sequence for 1559 steps. Presumably this fact can be used to make very large jumps as n gets bigger and bigger.
    Code:
    #include <stdio.h>
     
    typedef long Int;
     
    Int gcd(Int a, Int b) {
        while (b) { Int t = a % b; a = b; b = t; }
        return a;
    }
     
    int main() {
        Int n = 4, g = 13, start = g;
        Int cnt = 1;
        for (++n; n <= 5000; ++n) {
            Int g_prev = g;
            g = g_prev + gcd(n, g_prev);
            if (g == g_prev + 1)
                ++cnt;
            else {
                printf("%4ld.  %5ld   (%4ld)\n",
                       n - cnt, start, cnt);
                cnt = 1;
                start = g;
            }
        }
    }
    Code:
    .  4.     13   (   2)
       6.     16   (   3)
       9.     27   (   8)
      17.     51   (   1)
      18.     54   (   2)
      20.     60   (   1)
      21.     63   (  20)
      41.    123   (   1)
      42.    126   (  41)
      83.    249   (   1)
      84.    252   (  83)
     167.    501   (   1)
     168.    504   (   2)
     170.    510   (   1)
     171.    513   (   5)
     176.    528   (   1)
     177.    531   ( 176)
     353.   1059   (   1)
     354.   1062   (   3)
     357.   1071   (  11)
     368.   1104   (   1)
     369.   1107   (   5)
     374.   1122   (   1)
     375.   1125   (   3)
     378.   1134   (   2)
     380.   1140   (   1)
     381.   1143   ( 380)
     761.   2283   (   1)
     762.   2286   ( 761)
    1523.   4569   (   1)
    1524.   4572   (   5)
    1529.   4587   (   1)
    1530.   4590   (   3)
    1533.   4599   (   2)
    1535.   4605   (   1)
    1536.   4608   (  18)
    1554.   4662   (   6)
    1560.   4680   (1559)
    3119.   9357   (   1)
    3120.   9360   (   8)
    3128.   9384   (   1)
    Last edited by john.c; 12-11-2019 at 07:34 PM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  5. #5
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    For reference: Problem 443 - Project Euler

    That's your homework?!

    If you just want the answer then google will give it to you...

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Quote Originally Posted by Hodor View Post
    If you just want the answer then google will give it to you...
    Well that's hardly fair!
    Still, it serves as a check: 2744233049300770

    Presumably there's a fairly easy way to solve this. I'm wondering how the given values for g(1000) and g(1000000) enter into it.
    Last edited by john.c; 12-11-2019 at 08:04 PM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by john.c View Post
    Well that's hardly fair!
    Still, it serves as a check: 2744233049300770

    Presumably there's a fairly easy way to solve this. I'm wondering how the given values for g(1000) and g(1000000) enter into it.
    I'm tempted to give it a go but don't have an arbitrary precision library on this computer. Maybe when I get home.

    What is 2744233049300770? I found a different, and much larger, number using google...

  8. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    I found it here: projecteuler-solutions/Solutions.md at master * luckytoilet/projecteuler-solutions * GitHub
    Who knows if it's correct, though. If it is then you only need 64-bit numbers, which is what I was assuming.
    Can you post your link?
    A little inaccuracy saves tons of explanation. - H.H. Munro

  9. #9
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by john.c View Post
    I found it here: projecteuler-solutions/Solutions.md at master * luckytoilet/projecteuler-solutions * GitHub
    Who knows if it's correct, though. If it is then you only need 64-bit numbers, which is what I was assuming.
    Can you post your link?
    Can't find it now :/ But 2744233049300770 is correct apparently

    Hashes for answer matches the hash in Project Euler Answers < 200000000 - Pastebin.com
    Code:
    echo -n '2744233049300770' | md5sum 28f9d9a9bf8fb3d606e0b711b59f42aa
    Ok, so 64-bit is fine... that's a relief

  10. #10
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Okay. It's good to have that fact-checked. (It did seem low.)
    A little inaccuracy saves tons of explanation. - H.H. Munro

  11. #11
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    I haven't had time to look at this much (been very busy today) but I think that in addition to the sequence length it's interesting to also look at the delta (g - g_prev). The third column in the bunch of numbers below. At a quick glance the deltas (when they're not 1) are all primes all the way to 100000 except for that first row (??) Edit: What I meant to say/ask... why is the first row not prime when the rest are? (I have to confirm the rest are... will have to write an isprime() when I get home or work out why on paper, if they are indeed all primes except that one row)
    Code:
         9     27      9    (3)
        17     51     17    (8)
        18     54      3    (1)
        20     60      5    (2)
        21     63      3    (1)
        41    123     41    (20)
        42    126      3    (1)
        83    249     83    (41)
        84    252      3    (1)
       167    501    167    (83)
       168    504      3    (1)
       170    510      5    (2)
       171    513      3    (1)
       176    528     11    (5)
       177    531      3    (1)
       353   1059    353    (176)
       354   1062      3    (1)
       357   1071      7    (3)
       368   1104     23    (11)
    Last edited by Hodor; 12-11-2019 at 10:35 PM. Reason: Can't get first row to line up... oh well

  12. #12
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    That's interesting. I'll try to check that out for higher values.
    BTW, to line up the first line, start with a period (or whatever character you think is most inconspicuous) in the first column.

    EDIT: Looks like those differences are all prime up to at least n = 100 million.
    Last edited by john.c; 12-11-2019 at 10:49 PM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  13. #13
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by john.c View Post
    That's interesting. I'll try to check that out for higher values.
    BTW, to line up the first line, start with a period (or whatever character you think is most inconspicuous) in the first column.

    EDIT: Looks like those differences are all prime up to at least n = 100 million.
    Ah ok. Thanks for the dot hint.

    Ok, if we tentatively say that except for that 9 (is that important?) the deltas will be prime, then prime factorization might be somehow related (guessing). Either that or work out how they're (mostly) growing. The numbers below are how they grow (ignoring the in between deltas that are lower). If there is some way to work out that growth then.... yeah.



    Code:
     
    2
    9
    17
    41
    83
    167
    353
    761
    1523
    3119
    6257
    12539
    25121
    50291
    101141
    202817
    405641
    812051
    It won't let me put a dot haha

    generated using

    Code:
                uint64_t biggest_delta = 1;
    /* ... */
                delta = g - prev_g;
    /* ... */
                if (delta > biggest_delta) {
                    printf("%6" PRIu64 "\n", delta);
                    biggest_delta = delta;
                }
    Last edited by Hodor; 12-11-2019 at 11:11 PM.

  14. #14
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    I found a solution for it on the web but it's written in mathematica and I don't understand the reasoning. hmm.

  15. #15
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Quote Originally Posted by Hodor View Post
    I found a solution for it on the web but it's written in mathematica and I don't understand the reasoning. hmm.
    Can you post the link?
    A little inaccuracy saves tons of explanation. - H.H. Munro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need Help With C++ Console Homework Project
    By Sikkirigi in forum C++ Programming
    Replies: 14
    Last Post: 04-07-2016, 10:54 AM
  2. Replies: 4
    Last Post: 08-02-2013, 06:45 PM
  3. Replies: 5
    Last Post: 02-23-2013, 03:37 PM
  4. This Is Not Homework/ A Project
    By joebenjamin in forum C Programming
    Replies: 2
    Last Post: 09-24-2007, 08:42 PM
  5. Homework project(need help)
    By kantze in forum C++ Programming
    Replies: 8
    Last Post: 12-15-2006, 10:41 AM

Tags for this Thread