# Recursive formula to solve chain problem ?

Page 1 of 1

## 3 Replies - 1426 Views - Last Post: 12 July 2011 - 09:44 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=239225&amp;s=cf33c39860d104d0a48fb7fbfd1b9b52&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 wellwell

Reputation: 0
• Posts: 3
• Joined: 23-February 10

# Recursive formula to solve chain problem ?

Posted 12 July 2011 - 04:30 PM

Hi there, i was trying out one of the tasks at project euler.
the task is as following: "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?"

I try with the following:

```laps=1
counter = 1
topnumber = 0
sequencelength=0
nextnumber = 0

def next(number)
if(number%2 == 0)
counter+=1
nextnumber =(number/2)
return true

end
if number==1
return false
end
if(number%2!=0)
counter+=1
nextnumber =(3*number+1)
return true
end
end
while laps < 1000001
nextnumber=laps
while(next(nextnumber))

end
if (counter > sequencelength)
sequencelength = counter
topnumber=laps
counter = 1
laps+=1
end

puts topnumber

```

I get 3 errors.
Line 26 and 28 gives "void value expression"
Line 34 gives "syntar error unexpected \$end, nexpecting kEND"

How can I correct my errors, and is my idea even worth anything? thanks.

edit: just noticed a whole lot of things that are wrong.

This post has been edited by wellwell: 12 July 2011 - 04:34 PM

Is This A Good Question/Topic? 0

## Replies To: Recursive formula to solve chain problem ?

### #2 wellwell

Reputation: 0
• Posts: 3
• Joined: 23-February 10

## Re: Recursive formula to solve chain problem ?

Posted 12 July 2011 - 04:54 PM

After some adjustements of the code the error
"syntar error unexpected \$end, nexpecting kEND" remains.

the new code is the following.

```laps=1
counter = 1
topnumber = 0
sequencelength=0
nextnumber = 0
newone =true

def new(number)
if(number%2 == 0)
counter+=1
nextnumber =(number/2)
newone = true

end
if number==1
newone = false
end
if(number%2!=0)
counter+=1
nextnumber =(3*number+1)
newone = true
end
end
while laps < 1000001
nextnumber=laps
while(newone)
new(nextnumber)

end
if (counter > sequencelength)
sequencelength = counter
topnumber=laps
counter = 1
laps+=1
end

```

any suggestions?

### #3 sepp2k

• D.I.C Lover

Reputation: 2577
• Posts: 4,114
• Joined: 21-June 11

## Re: Recursive formula to solve chain problem ?

Posted 12 July 2011 - 05:08 PM

In ruby error messages, \$end refers to the end of file and kEND refers to the keyword end. So the error message is telling you that ruby found the end of file when it expected the keyword end. In other words you're missing an end somewhere.

In this case you're opening a while loop in line 25 and opening an if statement in line 31, but you have only one end at the end. You'd need two: one to close the if and one to close the while.

Note that this would be much more easily apparent if you'd indent your code properly. I recommend using an editor which automatically indents your code.

### #4 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Recursive formula to solve chain problem ?

Posted 12 July 2011 - 09:44 PM

Since you asked for suggestions. You can make this a lot faster by tabeling. Every time you encounter value n that is smaller than you initial value, you will have already calculate how many steps it took from that number to get to one. So you can save a lot of computational time by doing not calculating it again. You can do this (in pseudocode)

```hash = {}

every time you find a n, you do:
[code]
hash[n] = sequencelength

```

And while doing the steps, you do
```if hash.include? n
sequence_length = steps_done_so_far + hash[n]
end
and don't forget to put this value back into the hash.

```

By tabeling you can often make an algorithm much more efficient if it contains overlapping subproblems with very little thought. This kind of techniques fall under dynamic programming, look it up on wikipedia if you're interested.

This post has been edited by Karel-Lodewijk: 12 July 2011 - 09:50 PM