5 Replies - 655 Views - Last Post: 08 July 2010 - 03:09 AM Rate Topic: -----

#1 Bocard  Icon User is offline

  • D.I.C Head

Reputation: 15
  • View blog
  • Posts: 222
  • 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.
Posted Image

I would really appreciate any help.

Thx.

Is This A Good Question/Topic? 0
  • +

Replies To: Numbers problem

#2 sarmanu  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 966
  • View blog
  • 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

Was This Post Helpful? 1
  • +
  • -

#3 Bocard  Icon User is offline

  • D.I.C Head

Reputation: 15
  • View blog
  • Posts: 222
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 sarmanu  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 966
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#5 Bocard  Icon User is offline

  • D.I.C Head

Reputation: 15
  • View blog
  • Posts: 222
  • 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?
Was This Post Helpful? 0
  • +
  • -

#6 sarmanu  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 966
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1