Project Euler

blazar on 2006-12-01T22:55:29

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__

---

Or work backwards

runrig on 2006-12-02T02:02:10

Start with a list containing just the number 1. Then on every iteration shift off a value from the list ($n), and unshift back on $n*2, and ($n-1)/3 (if $n-1 is divisible by 3 and $n > 1), keeping track of which numbers you've seen and not re-queuing those numbers. I'm not sure offhand when to terminate though, since you'll have to temporarily go past the max limit.

Then again...

runrig on 2006-12-02T02:07:24

Eh, it was just an idea.

Just fine

blazar on 2006-12-02T08:16:09

Indeed: a reverse algorithm is interesting too. The idea must have blinked in my mind for a few microseconds as well, but then I realized that brute force could become very very lightweight provided one were careful enough to use already done calculations to avoid doing unnecessary ones: experimentation proved that my intuition was right, since the program pasted here gave me the answer in about 20 seconds, which is fine. Although I'm not really sure whether one should call that brute force any more. On a second thought I lean towards the hypothesis that one should not...