The problem is known as Collatz Conjecture (also 3n + 1 conjecture).
Basically given a n number then you apply the following rule.
If n is even then n/2 otherwise 3 * n + 1, you keep applying this until you
reach the number 1.
For instance, starting with *n = 6*, one gets the sequence 6, 3, 10, 5, 16, 8,
4, 2, 1. (with *8 items*)
Now the challenge tell the *n* with n descending from 1000000 to 1 and with the
*greater number of items*.
Then I did the program bellow (I'm very happy for feedback since I'm totally
noobie to clj), but it takes forever, there is anyway to make it fast?
(defn- apply-collatz-conjecture
"Given n, it returns n/2 if it's even or n*3+1 if it's odd."
[n]
(if (even? n)
(/ n 2)
(+ (* 3 n) 1)))
(defn- collatz-conjecture-seq
"Given n, it returns the sequence of collatz-conjecture."
[n]
(loop [n n sequence []]
(if (not= n 1)
(recur (apply-collatz-conjecture n) (cons
(apply-collatz-conjecture n) sequence))
(reverse sequence))))
(defn- collatz-conjecture-number-of-items
"It returns a map with n and number of items on its collatz-conjecture
sequence."
[n]
{ :n n :count (count (collatz-conjecture-seq n)) } )
(defn- greater
"Given x and y, it returns the element with greater count."
[x y]
(if (> (:count x) (:count y))
x
y))
(defn n-with-more-items
"Given n, it applies collatz-conjecture for the range 1..n
and return the n with more items."
[n]
(reduce greater (pmap collatz-conjecture-number-of-items (range 1 n))))
The only thing I thought was use pmap but it didn't make it super fast.
*Using only map*
user=> (time (n-with-more-items 999999))
"Elapsed time: *21191.762883 msecs*"
{:n 837799, :count 524}
*Using pmap*
user=> (time (n-with-more-items 999999))
"Elapsed time: *13230.919979 msecs*"
{:n 837799, :count 524}
Any thoughts on how can I apply parallelism to solve this (especially on
my frustrate try of use map and reduce)?
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
