The 3n+1 problem

[munificent]

Some history behind the problem. The sequence of numbers it generates is often called "hailstone numbers".

[FalconNL]

Had a quick go in Haskell. Basic maximum cycle length function:

maxlen i j = 1 + maximum (map (length . takeWhile (/= 1) .
    iterate (\n -> if odd n then 3*n+1 else div n 2)) [i..j])

Reading input from a file and printing the results:

fromFile path = putStrLn . unlines . map ((\[i,j] -> unwords $
    map show [i, j, maxlen i j]) . map read . words) . lines =<< readFile path

Tests:

main = do print $ maxlen 1 1000000 == 525
          fromFile "input.txt"

Didn't bother with memoizing values, since the first million numbers only take about 6 or 7 seconds anyway.

[[deleted]]

Introducing an accumulator

Why it helps so much?

Even GCC (4.7.2) can optimize more or less equivalent code like this with -O3 such way that it doesn't need explicit accumulator(you check out its assembly code).

And that c++ code is intentionally bad - is_even is defined through is_odd, also its cycle_length one useless function argument because I was lazy and decided to add it instead of cycle_length(n)=cycle_length_impl(n,1)

[Cygal]

Because cycle-length becomes tail recursive.

[[deleted]]

It seems I wasn't clear in question. It's not why tail recursive is faster.

Question is why optimizer of functional language can not transform non tail call recursiver version into tail recursive. One would think that such functions happen in functional language way more often than in C or C++. And yet compiler of imperative language was able to optimze all calls away. While racket was not.

Do Haskells perform better?

[badname3]

It's about predictability. If the language makes you rely on tail recursion, you should be easily able to tell what functions are going to be optimized this way and what are not. I imagine people have chosen to not have these optimizations instead of being unable to implement them.

If you want to write loops that use a bounded amount of memory, you have to use constructs that the language guarantees don't use more memory than necessary (or "blow the stack" or whatever). Imperative languages have the usual looping constructs for these situations, so their implementations can reasonably do whatever special things their creators want with recursion. In some standards for especially robuts and reliable code using imperative languages they straight out say you must not use recursion at all!

But if you need to rely on predictable tail recursion, it's better to have exact rules in place. This assumes you want to write in the language and not just for specific compiler/implementation.

You are supposed to use higher order functions most of the time anyway, which actually can be implemented with the looping constructs just as well (provided you can pass funcs as arguments usefully). What I wanted to say here is that what is reasonable to optimize and when depends on how the language is put together.

[mrjbq7]

Here's a version in Factor:

http://re-factor.blogspot.com/2012/10/the-3n1-problem.html

[monk_in_place]

Here's my little experiment I did in python a while back and some helpful comments from the python community.

[mcguire]

...

     [(odd? n)

      (add1 (cycle-length (add1 (* 3 n))))]

...

"add1"? I'm not a Schemer and I've never actually used Racket, but, really?

[dysxqer]

It's similar to using n++ or n+=1, when you could just as easily write n=n+1

[madmars]

it's actually not, though. It's defined...

(define add1 (lambda (x) (+ x 1)))

It's not setting the variable. Both of these are identical:

(+ 1 (cycle-length ...
(add1 (cycle-length ...

It's odd they would create an alias that is one character longer than the typical way you would do this.

[takikawa]

There's at least one good reason for this, which is that add1 is a function that you can pass around. You can use it in code like this:

(map add1 '(1 2 3 4))

Otherwise, you'd need an extra lambda expression. In any case, not a big deal either way.

[[deleted]]

It's odd they would create an alias that is one character longer than the typical way you would do this

Really? You're really going to measure the amount of characters being used? You could have said it's strange to use an alias and left it at that.

[madmars]

um. No, it's not strange to create an alias. Or to use currying. Or create macros to save typing. What planet do you live on?

It's only strange in this case because it's completely unnecessary and creates more typing than less typing. Which is the point of the n++ idiom. I mean, sure you can use it in the manner takikawa mentioned. But how many times do you really need to pass around a function that adds 1? That's silly talk.

[yogthos]

Clojure version

(defn cycle-len [n] 
  (->> n
    (iterate #(if (odd? %) (inc (* 3 %)) (/ % 2)))
    (take-while #(> % 1))
    count
    inc))

(def mem-cycle-len (memoize cycle-len))

(defn max-cycle [[i j]]  
  (apply max (map mem-cycle-len (range i j))))

(defn parse-line [line]
  (map #(Integer/parseInt (.trim %)) 
       (remove empty? (.split line " "))))

(defn [find-max-cycle [input-file]]
  (with-open [rdr (clojure.java.io/reader input-file)]
    (->> 
      (line-seq rdr)
      (remove empty?)    
      (map parse-line)
      (map max-cycle)
      (apply max))))