# Project Euler Problem 14 Segfault

• 11-03-2009
vincent01910
Project Euler Problem 14 Segfault
Hi,

I'm trying to solve this problem from Project Euler. Here's the problem.

The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.

My code segfaults when it reaches item 113383. And i don't know what is wrong with it.
Any help or advice highly appreciated.

Code:

```#include <stdio.h> int f(int i); int main() {                 long long terms[1000001]; /* how many terms for each number */                 long long i;                 long long max = 0;                                 terms[0] = terms[1] = 0;                 for(i = 2; i < 1000000; i++)                 {                                 long long  step = 0;                                 long long  temp = i;                                 printf("%lld",i);                                 do                                 {                                                 temp = f(temp);                                                 step++;                                                 printf("->%lld",temp);                                 }                                 while(temp > i - 1); /* all the values under i are already calculated */                                 terms[i] = step + terms[temp];                                 max = terms[i]>max?terms[i]:max;                                 printf("\n%lld,%lld,%lld\n",i,terms[i],max);                 }                 printf("%lld\n",max);                 return 0; } int f(int n) {                 return (n%2 == 0) ? n/2 : 3*n+1; }```
• 11-03-2009
Epy
Would be nice to see the output before it reaches the segfault, i.e. does it even begin that sequence or just instantly crap when it reaches i = 113383?

Shouldn't really set up new variables with the name step and temp every time, declare them before the for loop and just set them to 0 and i at the beginning of the for loop.

Probably be safer to use unsigned long longs for more room, since the values don't dip below zero.
• 11-03-2009
vincent01910
Thanks Epy. These are really good suggestions.
I updated code according to these.
Code:

```#include <stdio.h> int f(int i); int main() {                 unsigned long long terms[1000001];                 unsigned long long i;                 unsigned long long max = 0;                                 terms[0] = terms[1] = 0;                 unsigned long long  step;                 unsigned long long  temp;                 for(i = 2; i < 1000000; i++)                 {                                 step = 0;                                 temp = i;                                 //printf("%llu",i);                                 do                                 {                                                 temp = f(temp);                                                 step++;                                                 //printf("->%llu",temp);                                 }                                 while(temp > i - 1);                                 terms[i] = step + terms[temp];                                 max = terms[i]>max?terms[i]:max;                                 printf("\n%llu,%llu,%llu\n",i,terms[i],max);                 }                 printf("%llu\n",max);                 return 0; } int f(int n) {                 return (n%2 == 0) ? n/2 : 3*n+1; }```
Now the code is running and it seems it's running forever when reaching the same value.
Last few lines of output:

Code:

```113380,66,353 113381,66,353 113382,66,353```
• 11-03-2009
Epy
Hahaha damnit I'm retarded. I don't know if it's the specific problem you're looking for, but a major problem would be:

Code:

`int f(int n)`
Your function f should accept and return the kind of integer you're working with, unsigned long longs.
• 11-03-2009
slingerland3g
113382->56691->170074->85037->255112->127556->63778->31889->95668->47834->23917->71752->35876->17938->8969->26908->13454->6727->20182->10091->30274->15137->45412->22706->11353->34060->17030->8515->25546->12773->38320->19160->9580->4790->2395->7186->3593->10780->5390->2695->8086->4043->12130->6065->18196->9098->4549->13648->6824->3412->1706->853->2560->1280->640->320->160->80->40->20->10->5->16->8->4->2->1

Step = 66, terms[113382] = 66

Breaks here!
113383->340150->170075->510226->255113->765340->382670->191335->574006->287003->861010->430505->1291516->645758->322879->968638->484319->1452958->726479->2179438->1089719->3269158->1634579->4903738->2451869->7355608->3677804->1838902->919451->2758354->1379177->4137532->2068766->1034383->3103150->1551575->4654726->2327363->6982090->3491045->10473136->5236568->2618284->1309142->654571->1963714->981857->2945572->1472786->736393->2209180->1104590->552295->1656886->828443->2485330->1242665->3727996->1863998->931999->2795998->1397999->4193998->2096999->6290998->3145499->9436498->4718249->14154748->7077374->3538687->10616062->5308031->15924094->7962047->23886142->11943071->35829214->17914607->53743822->26871911->80615734->40307867->120923602->60461801->181385404->90692702->45346351->136039054->68019527->204058582->102029291->306087874->153043937->459131812->229565906->114782953->344348860->172174430->86087215->258261646->129130823->387392470->193696235->581088706->290544353->871633060->435816530->217908265->65372479

Does this ever end?

Continuing after this you are still good for 113384 and 113385. The problem is within this iteration of which I believe you are over stepping your limits. Checking limits.h may help here.
• 11-04-2009
vincent01910
Epy you were right. After I changed that function declaration to
Code:

`unsigned long long f(unsigned long long i)`
It went on without a problem and I got the right answer.

Thank you guys for your enlightenment!