FAQ
I was working on a few of the Project Euler puzzles. The first involves
picking the nth element from a particular series, (sum the numbers factored
either by 3 or 5 below 1000). One forum comment on the very first puzzle
raised the criticism that it's easy to solve the question as presented
(i.e. below 1000), but what if you wanted the sum below 10^18?

I started working towards the big number goal using lazy sequences.

First, a lazy sequence of numbers that are factored by 3 or 5. Second,
another lazy sequence such that the nth element is the sum of the first n
elements of the input sequence. Finally, pick the nth element, (it doesn't
quite match the question, but it's of similar complexity):

(def seq-3s-n-5s
(filter
(fn [n] (or (= 0 (mod n 5)) (= 0 (mod n 3)) ) )
(iterate inc 1)))

(defn sums [coll n]
(lazy-seq
(when-let [s (seq coll)]
(let [x (+ n (first s))]
(cons x (sums (rest s) x))))))

(nth (sums seq-3s-n-5s 0) (Math/pow 10 6))

However some where between (Math/pow 10 6) and (Math/pow 10 7) It throws an
error: java.lang.OutOfMemoryError: Java heap space. I'm wondering if I'm
crossing some threshold into a different number type? Or perhaps I've
missed some point and got the lazy sequence stuff wrong?

So my question has two parts:
(1) How can I fix this code so that it will run to further into the
sequence?
(2) What actually has gone wrong? How could you debug something like this?

Notes: we can trust that (nth seq N) is not the problem, it returns in
reasonable time for a test like this: (nth (iterate inc 1) (Math/pow 10 9))


Cheers,
Julian Kelsey.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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

Search Discussions

  • Meikel Brandmeyer at Nov 17, 2011 at 9:50 pm
    Hi,

    this is a “hold unto head” problem.

    Am 17.11.2011 um 15:06 schrieb Julian Kelsey:
    (def seq-3s-n-5s
    (filter
    (fn [n] (or (= 0 (mod n 5)) (= 0 (mod n 3)) ) )
    (iterate inc 1)))
    Here you keep a reference to the head of the generated by iterate. Make it a function:

    (defn seq-3s-n-5s
    []
    (filter #(or (zero? (mod % 5)) (zero? (mod % 3))) (iterate inc 1)))

    Then call it like this:

    (nth (sums (seq-3s-n-5s 0) (Math/pow 10 6))

    That should fix your problem.

    Sincerely
    Meikel

    --
    You received this message because you are subscribed to the Google
    Groups "Clojure" group.
    To post to this group, send email to clojure@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
  • Julian Kelsey at Nov 18, 2011 at 6:42 pm
    Thanks!

    To confirm my understanding: in my original version I defined (using def) a
    reference to a lazy sequence. I then evaluated it, using nth to pick a
    value from the sequence. Because I have a reference to the beginning of the
    sequence all the lazily generated items are retained. I.e. the lazy
    sequence is lazy only for the first time it works through the sequence
    instance, if there is a live reference to the sequence then those now
    generated elements remain, (to avoid the overhead of regenerating them?).

    By providing a function to return a new instance of the sequence each time,
    as in the solution Meikel has provided, I avoid retaining any references to
    the front of the sequence, and the garbage collector can do it's work.

    I always learn much better by making mistakes like these.


    Cheers,
    Julian.
    On Thu, Nov 17, 2011 at 9:49 PM, Meikel Brandmeyer wrote:

    Hi,

    this is a “hold unto head” problem.

    Am 17.11.2011 um 15:06 schrieb Julian Kelsey:
    (def seq-3s-n-5s
    (filter
    (fn [n] (or (= 0 (mod n 5)) (= 0 (mod n 3)) ) )
    (iterate inc 1)))
    Here you keep a reference to the head of the generated by iterate. Make it
    a function:

    (defn seq-3s-n-5s
    []
    (filter #(or (zero? (mod % 5)) (zero? (mod % 3))) (iterate inc 1)))

    Then call it like this:

    (nth (sums (seq-3s-n-5s 0) (Math/pow 10 6))

    That should fix your problem.

    Sincerely
    Meikel

    --
    You received this message because you are subscribed to the Google
    Groups "Clojure" group.
    To post to this group, send email to clojure@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 the Google
    Groups "Clojure" group.
    To post to this group, send email to clojure@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

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupclojure @
categoriesclojure
postedNov 17, '11 at 9:24p
activeNov 18, '11 at 6:42p
posts3
users2
websiteclojure.org
irc#clojure

People

Translate

site design / logo © 2022 Grokbase