Thread: Project Euler Problem 14 Segfault

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    15

    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;
    }

  2. #2
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413
    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?

    Just some code comments:

    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.

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    15
    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

  4. #4
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413
    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.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    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.
    Last edited by slingerland3g; 11-03-2009 at 01:49 PM.

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    15
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Project problem
    By GUI_XP in forum C++ Programming
    Replies: 3
    Last Post: 01-17-2003, 02:57 PM
  2. Project Menu Function output
    By Ryan_P in forum C++ Programming
    Replies: 1
    Last Post: 11-06-2002, 04:58 PM
  3. DJGPP project problems
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 06-08-2002, 07:16 PM
  4. problem with output
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 11-18-2001, 08:34 PM