# Thread: My homework c project (help)

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

2. 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?

3. 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)```

4. 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)```

5. For reference: Problem 443 - Project Euler

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

6. Originally Posted by Hodor
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.

7. Originally Posted by john.c
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. 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.

9. Originally Posted by john.c
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'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. Okay. It's good to have that fact-checked. (It did seem low.)

11. 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)```

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

13. Originally Posted by john.c
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;
}```

14. I found a solution for it on the web but it's written in mathematica and I don't understand the reasoning. hmm.

15. Originally Posted by Hodor
I found a solution for it on the web but it's written in mathematica and I don't understand the reasoning. hmm.