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.

--
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

## Search Discussions

•  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))

Sincerely
Meikel

--
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
•  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))

Sincerely
Meikel

--
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
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
--
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

## Related Discussions

Discussion Overview
 group clojure categories clojure posted Nov 17, '11 at 9:24p active Nov 18, '11 at 6:42p posts 3 users 2 website clojure.org irc #clojure

### 2 users in discussion

Content

People

Support

Translate

site design / logo © 2023 Grokbase