Numbers problem

Page 1 of 1

5 Replies - 1101 Views - Last Post: 08 July 2010 - 03:09 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=180672&amp;s=111330ed8b926a4f8be2917d344097ef&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 Bocard

Reputation: 15
• Posts: 223
• Joined: 24-September 08

Numbers problem

Posted 07 July 2010 - 11:15 PM

Hello,

I found a problem on a website and I tried to solve it, but I can't figure out where I did wrong.

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...I wrote it in Pascal.
```function f (var n:longint):longint;
begin
if n = 1 then f:= 1
else if n mod 2 = 0 then begin
n:=n div 2;
f:= 1+ f(n);
end
else if n mod 2 = 1 then begin
n:= 3*n + 1;
f:= 1+ f(n);
end;
end;
var n,nr,max,secv:longint;
begin
max:=0;
nr:=0;
for n:= 1 to 1000000 do begin
secv:=f(n);
writeln('n= ',n,'      ', 'secv= ', secv);
if secv > max then begin
max:=secv;
nr:=n;
end;
end;
writeln('nr:= ',nr);
writeln('secventa maxima:= ',secv);
end.

```

The compiling doesn't give any errors, but I just get an infinite loop cuz this is what the console looks like when i run the program.

I would really appreciate any help.

Thx.

Is This A Good Question/Topic? 0

Replies To: Numbers problem

#2 sarmanu

• D.I.C Lover

Reputation: 967
• Posts: 2,362
• Joined: 04-December 09

Re: Numbers problem

Posted 07 July 2010 - 11:49 PM

You have a very big problem: your are modifying the for loop variable n through this function call:
```secv:=f(n);

```

n will be always reset to 1, therefore you are stuck in an infinite loop. That's because of your function parameter, being passed with var qualifier.
```function f (var n:longint):longint;

```

should be:
```function f (n:longint):longint;

```

now n is not modified anymore after the function call, and your program will work.
EDIT: here
```writeln('secventa maxima:= ',secv);

```

you surely want to print max instead:
```writeln('secventa maxima:= ',max);

```

This post has been edited by sarmanu: 07 July 2010 - 11:52 PM

#3 Bocard

Reputation: 15
• Posts: 223
• Joined: 24-September 08

Re: Numbers problem

Posted 08 July 2010 - 12:12 AM

Thx for your answer, now my code is running. First I was thinking making a procedure instead of a function, then I changed my mind but I forgot to erase the 'var'.
But now I have another problem, the answer it gave me was: 538271 and this number seems to be incorrect.
The problem I am trying to solve is from Project Euler Problem 14. Is there something wrong with my code?

This post has been edited by Bocard: 08 July 2010 - 12:16 AM

#4 sarmanu

• D.I.C Lover

Reputation: 967
• Posts: 2,362
• Joined: 04-December 09

Re: Numbers problem

Posted 08 July 2010 - 01:22 AM

The logic of the program is OK, but you simply can't tackle this in Pascal. First of all, your recursive function will eventually throw a stack overflow error, simply because it can't handle such big numbers. You have to go with an iterative approach, though, it will still not work. Why? Take a look at this iterative approach:
```function collatz(n:longint):integer;
var temp:longint;
ret:integer;
begin
ret:=1;
temp:=n;
while (temp > 1) do
begin
if (temp mod 2 = 1) then
temp:=3 * temp + 1
else
temp:=temp div 2;
inc(ret);
end;

collatz:=ret;
end;

```

The function works, but what happens when we pass a number bigger than (with approximation) than 600000? Well, the calculations may exceed the maximum longint range, when the number is odd:
```temp:=3 * temp + 1

```

it will multiply, and multiply, and will exceed the max. range, therefore it will give you the wrong results.
The same algorithm gave me the correct results, in C++.
As a conclusion: Pascal is too old. You can't run that code using it.

#5 Bocard

Reputation: 15
• Posts: 223
• Joined: 24-September 08

Re: Numbers problem

Posted 08 July 2010 - 02:59 AM

Ok thx for the info. Unfortunately I will need pascal for one more exam (that's why I'm still struggling with it) after that I will switch to c. Thx again for your time.

I still have a question though, if longint in pascal isn't enough, what type of variable should I use in c?

#6 sarmanu

• D.I.C Lover

Reputation: 967
• Posts: 2,362
• Joined: 04-December 09

Re: Numbers problem

Posted 08 July 2010 - 03:09 AM

A long long int or unsigned long long int will do it.