NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

## All the Perl that's Practical to Extract and Report

#### blazar (7356)

blazar
(email not shown publicly)
http://blazar.perlmonk.org/
Yahoo! ID: bik.mido (Add User, Send Message)
Jabber: blazar@jabber.org

### Journal of blazar (7356)

Friday December 01, 2006
05:55 PM

### Project Euler

[ #31781 ]

I've recently joined Project Euler. For the moment when I have some spare time I check the problems in order and try to solve them. Actually none of those I've seen thus far is particularly challenging either mathematically or algorithmically. (But I'm seeing them in supposed ascending order of difficulty.) Now I've just solved Problem 14, which is the first interesting one. Not that it was terribly challenging either, but it was... well, interesting. And fun to code.

Here's the statement of the 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.

And here's my code:

#!/usr/bin/perl -l

use strict;
use warnings;
use constant MAX => 1_000_000;

my (\$seen,@memz)=0;
sub coll {
my \$n=my \$m=shift;
return 0 if vec(\$seen,\$n,1);
my \$i=0;
while (\$n>1) {
return \$memz[\$m]=\$i+\$memz[\$n] if \$memz[\$n];
vec(\$seen,\$n,1)=1 if \$n < MAX;
\$n = \$n%2 ? 3*\$n+1 : \$n/2;
\$i++;
}
\$memz[\$m]=\$i;
}

my (\$max,\$maxv)=0;
for (2..MAX) {
my \$new=coll(\$_) or next;
(\$max,\$maxv)=(\$new,\$_) if \$new > \$max;
}

print \$maxv;

__END__

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Full
Abbreviated
Hidden