Why is this Project Euler solution slow?

[David Chambers]

Last night I attempted Project Euler #5 in Clojure. The problem is as follows:

> # Smallest multiple

>

> 2520 is the smallest number that can be divided by each of the numbers

> from 1 to 10 without any remainder.

>

> What is the smallest positive number that is evenly divisible by all of the

> numbers from 1 to 20?

Here's my solution:

    (defn divisible?

      [numer denom]

      (= 0 (mod numer denom)))

    (defn smallest-multiple

      "Find the smallest positive number that is evenly divisible by all

      of the numbers from 1 to n."

      [n]

      (let [s (range 1 (inc n))]

        (first (filter (fn [x] (every? (partial divisible? x) s))

                       (rest (range))))))

This gives the expected answer for n of 10, but takes a long time to

solve n of 20. I'd like to understand what make this code slow. Am I

doing something inefficiently? What steps might I take to rework this

code to have it solve n of 20 within a minute?

---

p.s. I'm new to Clojure. Don't hesitate to mention applicable Clojure

idioms of which I may not be aware.

[Wes Freeman]

Any brute force solution will be relatively slow. The fast solutions require a doing math to simplify.

Wes

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
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 clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Ben Wolfson]

You can actually solve this problem quite directly. I just looked up my python solution and it's just "print 9*16*5*7*11*13*17*19".

--

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
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 clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--
Ben Wolfson
"Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure." [Larousse, "Drink" entry]

[David Chambers]

> Any brute force solution will be relatively slow. The fast solutions

> require a doing math to simplify.

Quite right. The fault lies with me rather than with Clojure. I'll rework

the code so that it expands to:

    2^4 * 3^2 * 5^1 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1

Relevant Stack Overflow post: http://stackoverflow.com/questions/14668272/what-can-i-do-to-speed-up-this-code

[Stan Dyck]

>
> On Tue, Oct 1, 2013 at 11:22 AM, David Chambers <david.ch...@gmail.com <javascript:>> wrote:
>
> Last night I attempted Project Euler #5 <http://projecteuler.net/problem=5> in Clojure. The problem is as follows:

>
> > # Smallest multiple
> >
> > 2520 is the smallest number that can be divided by each of the numbers
> > from 1 to 10 without any remainder.
> >
> > What is the smallest positive number that is evenly divisible by all of the
> > numbers from 1 to 20?
>
> Here's my solution:
>
> (defn divisible?
> [numer denom]
> (= 0 (mod numer denom)))
>
> (defn smallest-multiple
> "Find the smallest positive number that is evenly divisible by all
> of the numbers from 1 to n."
> [n]
> (let [s (range 1 (inc n))]
> (first (filter (fn [x] (every? (partial divisible? x) s))
> (rest (range))))))
>

> This gives the expected answer for /n/ of 10, but takes a long time to
> solve /n/ of 20. I'd like to understand what make this code slow. Am I

> doing something inefficiently? What steps might I take to rework this

> code to have it solve /n/ of 20 within a minute?
>

I'm always struck by how attractive brute force solutions look in clojure (and lisps in general I'd say). Very concise
and plain about what it is trying to do. I'm not sure if that is a good or bad thing about the language.

StanD.

[David Chambers]

> I'm always struck by how attractive brute force solutions look in

> clojure (and lisps in general I'd say). Very concise and plain about

> what it is trying to do.

Right. The thing I've noticed in my (very) limited experience with the

language is that it forces me to think about what it is that I'm trying to

do before I write any code at all.

I need to keep in mind that *how* a piece of code arrives at a result

is significant, even though solving such problems with Clojure feels

very much like doing mathematics.

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to

clojure+unsubscribe@googlegroups.com

For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

--- You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/e3kwOl9CtX8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+unsubscribe@googlegroups.com.