# PYTHON - determining the longest chain in a sequence

Page 1 of 1

## 3 Replies - 3287 Views - Last Post: 28 March 2010 - 06:18 AMRate 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=164079&amp;s=f964eee9942ecad453f7066213a508ef&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 mapexx

Reputation: 0
• Posts: 23
• Joined: 30-November 09

# PYTHON - determining the longest chain in a sequence

Posted 24 March 2010 - 04:20 PM

I want my program to prompt the user for a range of values(such as 1-15), perform a sequence of operations on each value until it equals one, and then count the length of each chain. I then need to know which chain had the longest length. For example, I have these functions that performs the operations:

```# determines if a number is even or odd
def determineOdd(num):
if num % 2 == 0:
return False
else:
return True

# performs operations depending if the number is even or odd
def tempHS(num):
values = []
print num, "->",
while num != 1:
values.append(num)
if determineOdd(num):
num = 3 * num + 1
else:
num /= 2
if num != 1:
print num,"->",
else:
print num,

length = len(values)
print "; length = ",length

```

After I prompt the user for a range of values, I then want my function to return the lengths of each chain.

I am not sure how to have it return which value had the longest chain(longest length). Any ideas?

Output would look something like this for values 13-15:

```
13  -> 40  -> 20  -> 10  -> 5  -> 16  -> 8  -> 4  -> 2  -> 1 ; length = 10

14  -> 7  -> 22  -> 11  -> 34  -> 17  -> 52  -> 26  -> 13  -> 40  -> 20  -> 10
-> 5  -> 16  -> 8  -> 4  -> 2  -> 1 ; length = 18

15  -> 46  -> 23  -> 70  -> 35  -> 106  -> 53  -> 160  -> 80  -> 40  -> 20  -> 1
0  -> 5  -> 16  -> 8  -> 4  -> 2  -> 1 ; length = 18

```
etc..

Thank you

This post has been edited by mapexx: 24 March 2010 - 04:22 PM

Is This A Good Question/Topic? 0

## Replies To: PYTHON - determining the longest chain in a sequence

### #2 chemicalfan

Reputation: 4
• Posts: 95
• Joined: 16-October 09

## Re: PYTHON - determining the longest chain in a sequence

Posted 25 March 2010 - 07:12 AM

Off the top of my head, I'd store the chain lengths per user value as a dictionary (appending the user value as a key, and chain length as a value). Then at the end, query the dictionary to get the highest value (you might need to convert to a list for this, I'm not sure)

### #3 mapexx

Reputation: 0
• Posts: 23
• Joined: 30-November 09

## Re: PYTHON - determining the longest chain in a sequence

Posted 27 March 2010 - 03:33 PM

I haven't yet learned how to use dictionaries. Any other suggestions?

### #4 baavgai

• Dreaming Coder

Reputation: 7151
• Posts: 14,894
• Joined: 16-October 07

## Re: PYTHON - determining the longest chain in a sequence

Posted 28 March 2010 - 06:18 AM

In order to find the longest, you first have to have to function that returns something useful. Just printing isn't going to help.

Your method can be simply written like this:
```def tempHS(num):
values = [num,]
while num != 1:
if num % 2 == 0:
num /= 2
else:
num = 3 * num + 1
values.append(num)
return values

```

Printing can be done pretty simply:
```def printResults(hsList):
print "%s ; length = %d" % (' -> '.join([str(i) for i in hsList]), len(hsList))

```

Now you can tell which is longer:
```(l1, l2) = (tempHS(13), tempHS(14))
if len(l1) < len(l2):
printResults(l2)
else:
printResults(l1)

```

I'll leave finding the longest in a list of choices to you.