Home > Uncategorized > The 3n+1 problem–the hard way

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



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)




        xor    eax, eax    ; maxLen = 0

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


        cmp ecx, j

        jg    done       

        push eax

        mov ebx, 1        ; c = 1

        mov edx, ecx    ; np = n


        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


        mov edx, eax    ; np = np / 2

        jmp repeat_while


        pop    eax

        inc ecx            ; [n++]

        cmp    ebx, eax     ; if c > maxlen

        jle repeat_for

        mov eax, ebx    ; c = maxlen

        jmp repeat_for





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

Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: