## The 3n+1 problem–the hard way

A sample problem from the book Programming challenges is published here and it has been named The 3n+1 problem. It does not take a great effort to come up with a solution; in F# it might look like:

let threeNPlusOne = Seq.unfold (fun n -> let n’ = if n%2=0 then n/2 else n*3+1 in Some(n,n’))

let cycleLength n = 1 + n |> threeNPlusOne |> Seq.takeWhile ((<>) 1) |> Seq.length

let solve i j = seq { i..j } |> Seq.map cycleLength |> Seq.max

Or maybe, using a more imperative style, it might look like:

let solve i j =

let mutable maxLen = 0

for n in i..j do

let mutable n’ = n

let mutable c = 1

while n’ <> 1 do

n’ <- if n’%2=0 then n’/2 else n’*3+1

c <- c + 1

if c > maxLen then

maxLen <- c

maxLen

Ok, that was fun for a little while but not a real challenge. Rewriting the solution in assembler makes it more interesting:

int solve(int i, int j)

{

__asm

{

xor eax, eax ; maxLen = 0

mov ecx, i ; for n = i..j

repeat_for:

cmp ecx, j

jg done

push eax

mov ebx, 1 ; c = 1

mov edx, ecx ; np = n

repeat_while:

cmp edx, 1

je term_loop ; while (np <> 1)

inc ebx ; c++

mov eax, edx

shr eax, 1

jnc case_even

mov eax, edx ; np = np * 3 + 1

shl edx, 1

add edx, eax

inc edx

jmp repeat_while

case_even:

mov edx, eax ; np = np / 2

jmp repeat_while

term_loop:

pop eax

inc ecx ; [n++]

cmp ebx, eax ; if c > maxlen

jle repeat_for

mov eax, ebx ; c = maxlen

jmp repeat_for

done:

}

}

Erhmm. That’s all for today. Good night.