Q)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.

/*if sequence is 13,40,20,10,5,16,8,4,2,1 remember the indexes 13->1,40->2,20->3,10->4,5->5,16->6,8->7,4->8,2->9,1->10 now if we want to know length of sequence starting at 20 we do 10-3+1 */ /*and if we have completed numbers till 17 then we have the record of the lengths of all the sequences from 1 to 17 plus the lengths of the sequences of , numbers that occured in those 1 to 17 sequences*/ /*a number cannot appear more than once in a sequence,otherwise the sequence will not converge,so no worry about saving the same number twice*/ /*how much big should be the array which stores the elements of the current sequence*/ /*that is how big can be a sequence??*/ /*so make a linked list for the sequence*/ #include<stdio.h> #include<stdlib.h> #define MAX 1000000 //1 million #define PARITY 2 struct element{ unsigned long int number,pos;//pos is the position of that number in the sequence struct element *next; }; void add_ele_end(struct element *,struct element *); void *give_mem(void); unsigned long int big_give(unsigned long int,unsigned long int); int main(){ /*0th position in the lengths array is vacant since numbers start from 1*/ unsigned long int i=0,number,lengths[MAX+1],maxlen=0;//check the range,lengths is for storing what is the length of sequence atarting with that number /*initialise the lengths array to zero*/ while(i<=MAX) lengths[i++]=0; number=1; /*start the loop of numbers*/ while(number<=MAX){ /*start the inner loop*/ char seq_over='0'; struct element *first=NULL,*iterate=NULL,*temp=NULL; unsigned long int position=1,arr_num=number;//position is for number of elements already counted in the array while(seq_over!='1'){ struct element *filled; //arr_num is the number in the array,which can be incremented or decremented /*if got the number in lengths array or got 1 exit the loop*/ if(lengths[number]!=0){ big_give(maxlen,position+lengths[arr_num]); seq_over='1'; } else{ ++position; if( (filled=(struct element *)give_mem()) == NULL){ printf("Memory allocation failed\n"); return 1; } if(position==1) first=filled; filled->number=arr_num; filled->number=position; filled->next=NULL; /*adding the number in the linked list*/ add_ele_end(first,filled); } if(arr_num==1){ big_give(maxlen,position); seq_over='1'; } /*if not find next element and add previous element to seq array*/ if(seq_over!='1'){//find next element in the sequence,add it,increment the position if(arr_num%PARITY==0)//even number arr_num=arr_num/2; else arr_num=arr_num*3+1; } else{ //add the elements and the corresponding length of array in lengths array iterate=first; if(iterate==NULL)//no elements filled ; else{ while((iterate->next)!=NULL){ lengths[iterate->number]=filled->pos; iterate=iterate->next; } } } } /*free the linked list*/ iterate=first; if(iterate==NULL) ; else{ while( (iterate->next) !=NULL){ temp=iterate; iterate=iterate->next; free((void*)temp); } free((void*)iterate);//last element remaining free } ++number; } printf("The maximum lenth of sequence is:%ld\n",maxlen); return 0; } void add_ele_end(struct element *start,struct element *fill){//add element at the end struct element *pointer=start; if(pointer==NULL)//means that first element itself is not there pointer=fill; else{ while(pointer->next!=NULL) pointer=pointer->next; pointer->next=fill; fill->next=NULL; } return; } void *give_mem(void){ return malloc(sizeof(struct element)); } unsigned long int big_give(unsigned long int a1,unsigned long int a2){ return a1>=a2?a1:a2; }

No compile time error.

program gets killed.

terminal message after running the program:

Killed

using gdb

Program terminated with signal SIGKILL, Killed.

The program no longer exists.

so i thought there must be some memory problems since there are no compile time errors.so i tried using valgrind plugin from code::blocks.

so i selected Run Valgrind::MemCheck and i got

valgrind --version

execvp(valgrind, --version) failed with error 2!

valgrind --leak-check=yes --xml=yes "bin/Debug/valtry"

execvp(valgrind, --leak-check=yes, --xml=yes, bin/Debug/valtry, ) failed with error 2!

then i selected Run Valgrind::Cachegrind and i got

valgrind --version

execvp(valgrind, --version) failed with error 2!

valgrind --tool=cachegrind "bin/Debug/valtry"

execvp(valgrind, --tool=cachegrind, bin/Debug/valtry, ) failed with error 2!

but i am not able to know what is happening with the memory or on which line error occurs.is this because valgrind is not able to detect the error or there is some problem with the valgrind plugin?

This post has been edited by **jink**: 27 July 2012 - 11:16 PM