1

I am right now doing a problem about the Collatz sequence. I have to find the longest Collatz sequence if we start with a number in the range 1,...,1000000. The Collatz sequence of a number n is defined as: if n mod 2 == 0 then the next number is n/2. If n mod 2 != 0 then the next number is 3*n+1. The sequence for n=10 is 10,5,16,8,4,2,1.

Of course if we do this problem the naive way, we would calculate the Collatz sequence of each number n between 1,...,1000000 and check which has the longest sequence. This is not efficient though.

A smarter algorithm would be to use the fact that given a Collatz sequence, the sequence obtained by not looking at the first few elements, is also a Collatz sequence. So if we calculate the sequence for n=10 i.e. 10,5,16,8,4,2,1 then the sequence 5,16,8,4,2,1 is also a Collatz sequence and we have immediately found the length of the Collatz sequence for n=5,n=16,n=8,n=4,n=2 and n=1 by just calculating the sequence for n=10.

With this idea in mind, I wrote the following code in C using pointers and recursion.

#include <stdio.h> #include <stdlib.h> int recursion(int n, int *array){ if((*array)[n]==0){//check if I already have the length of the sequence for this n if(n/2==(double)n/(double)2){//check if n mod 2 == 0 (*array)[n]=recursion(n/2,array)+1; } else{ (*array)[n]=recursion(3*n+1,array)+1; } } else{ return 0; } } int main(int argc, char **argv){ int length[100];//this array will contain the lengths of sequences, //I will only do it for n=1 up to n=10, but I have to have a bigger //array since the Collatz sequence elements can be higher than 10 for (int i=0;i<100;i++){ length[i]=0; } length[0]=1;//the Collatz sequence for n=1 has length 1 for(int n=1; n<=10;i++){ recursion(n,&length);//use the function for each n } for(int i=0;i<10;i++){ printf("%d\n",length[i]); } return 0; }

If I compile this code, I get several errors:

main.c:5:13: error: subscripted value is not an array, pointer, or vector if((*array)[n]==0){ ~~~~~~~~^~ main.c:7:12: error: subscripted value is not an array, pointer, or vector (*array)[n]=recursion(n/2,array)+1; ~~~~~~~~^~ main.c:10:12: error: subscripted value is not an array, pointer, or vector (*array)[n]=recursion(3*n+1,array)+1; ~~~~~~~~^~ main.c:25:15: warning: incompatible pointer types passing 'int (*)[100]' to parameter of type 'int *' [-Wincompatible-pointer-types] recursion(i,&length); ^~~~~~~ main.c:4:27: note: passing argument to parameter 'array' here int recursion(int n, int *array){

I don't know why I get these warnings and errors.

Improve this question
1
  • Start at (oops) 626331? Commented Jul 30, 2015 at 17:57

3 Answers 3

Reset to default
3

array is an int*. *array therefore is an int. You can't say int i; i[0], so why would you be able to say (*array)[0]?

Just access it normally, by saying array[n] instead of (*array)[n].

Also, in your main function , call recursion with recursion(n, length);, not recursion(n, &length);. You're passing the array, not a pointer to the array.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

I think you have to call the function like this

recursion(n,length);

Since, the array name contains the address of the first element of the array.

And you are receiving it also in a pointer to int. Therefore you can use array[] in the function normally. Like array[n]

Improve this answer

Comments

1

  1. Use *(array + n) or array[n] instead of (*array)[n] to access the nth variable.

  2. Since length is an array, calling the function with just the name passes it address.

  3. Small error in for loop. for(int n=1; n<=10;i++){ to for(int n=1; n<=10;n++){

These changes fix the compilation error. 

#include <stdio.h> #include <stdlib.h> int recursion(int n, int *array){ if(*(array + n)==0){//check if I already have the length of the sequence for this n if(n/2==(double)n/(double)2){//check if n mod 2 == 0 *(array + n)=recursion(n/2,array)+1; } else{ *(array + n)=recursion(3*n+1,array)+1; } } else{ return 0; } } int main(int argc, char **argv){ int length[100];//this array will contain the lengths of sequences, //I will only do it for n=1 up to n=10, but I have to have a bigger //array since the Collatz sequence elements can be higher than 10 for (int i=0;i<100;i++){ length[i]=0; } length[0]=1;//the Collatz sequence for n=1 has length 1 for(int n=1; n<=10;n++){ recursion(n,length);//use the function for each n } for(int i=0;i<10;i++){ printf("%d\n",length[i]); } return 0; }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.