Hi, so I feel like I’m going crazy. I’m relatively new to Clojure (been using it on and off for a month or so) and I’m going through problems on 4Clojure. I’m on question 95 (http://www.4clojure.com/problem/95) and I’ve been wrestling with it for a few hours now and have absolutely no idea why it’s not passing the unit tests. I can’t see how it’s logically different from an answer I found online (the answer-key version is far more elegant, that’s for sure). Can somebody lend me a second pair of eyes? What am I doing wrong? My version:

(fn tree? [tree]
    (if (= tree nil)
    true)
    (if (seq? tree)
    (if (= (count tree) 3)
        (if (and (tree? (second tree)) (tree? (last tree)))
        true
        false)
        false)
    false))

(fn tree? [coll]
    (cond
    (or (seq? coll) (vector? coll))
        (and (= 3 (count coll)) (tree? (nth coll 1)) (tree? (nth coll 2)))
    (nil? coll) true
    :else false))

Is anyone using vim with emacs? Evil mode. On OSX. Wiii. I got it to work. Just had to restart emacs.

Is there a limit to lazy sequences? I am trying to solve Project Euler #357, which basically requires generating primes up to 100 million. The general prime? filter I'd cooked up (more or less memoized trial division) is too slow for this particular problem, so I borrowed a lazy-sequence solution from someone on SO:

(def lazy-primes
 ;; Adapted from 
 (letfn [(no-smaller-prime-factors? [x]
           (not-any? (fn [p] (divisible? x p))
                     (take-while #(<= % (Math/sqrt x)) lazy-primes)))]
   (lazy-seq (filter no-smaller-prime-factors? (drop 2 (range))))))

Execution error (IndexOutOfBoundsException) at scratch.euler2/eval48451 (form-init5213815999557406566.clj:1).
null

I noticed that the error is an Index out of bounds, which I guess is coming from the nth. (last (take 800000 lazy-primes)) worked for me, don't know why nth is limited though

It is not running the function? Crashes on line 1?

@nathantech2005 re: long limit—I didn't think of that! I thought "oh, I'm just finding square roots, there's no need to coerce to bigint (or place to do so)." Interestingly, I was able to get around the Out of Bounds error by changing Math/sqrt x to tower/expt x 1/2, but finding the 800,000th prime seems like it will take all afternoon. re: function crashing—I'm just running it in the REPL. No crash at 700,000 or below.

What is the highest max value possible in your code?

800,000th prime # is?

Over the 64 bit long maximum?

I cannot get a value higher than 8325781, which is far less than the 800,000th prime.

Seems to be around the 560,000th prime or so.

Hmm.. index error is not a stack error though. I dont think its a 64 long max problem

i don't think it's an overflow

(last (take  800000 lazy-primes ))
;; => 12195257

yeah I’m also able to run the code

Ya, you'd get an explicit overflow error. I just checked my fibonacci code.

user=> (defn divisible? [i p] (zero? (rem i p)))
#'user/divisible?
user=> (def lazy-primes
  #_=>  ;; Adapted from 
  #_=>  (letfn [(no-smaller-prime-factors? [x]
  #_=>            (not-any? (fn [p] (divisible? x p))
  #_=>                      (take-while #(<= % (Math/sqrt x)) lazy-primes)))]
  #_=>    (lazy-seq (filter no-smaller-prime-factors? (drop 2 (range))))))
#'user/lazy-primes
user=> (time (nth lazy-primes 800000))
"Elapsed time: 29022.974863 msecs"
12195263

Weird, I just tried to "refresh" the function by converting it back to Math/sqrt x (bad idea) and then back to tower/expt x 1/2 again. It seems to get stuck at the first value I find? i.e., after clearing the cached sequence from memory, this is what I get:

(last (take 100000 lazy-primes))
=> 364031
(last (take 300000 lazy-primes))
=> 364031
(last (take 600000 lazy-primes))
=> 364031

What is your JVM running on? Memory/ram?

I have no idea. I'm working in Atom via Proto-REPL. Must be some memory issue because I'm now getting out of bounds errors even on nth lazy-primes 40000 I guess?

I think you are getting the same number, because a lazy seq caches the first result

https://clojuredocs.org/clojure.core/lazy-seq

And nth is probably throwing the index out of bounds error

But I cannot find a max allowed on the sequence data type... I'd assume it depends on ram, memory

Because the default JVM can eat a ton of memory... depends on underlieing data structures and complexity big O

Ah, I restarted Atom and the REPL and I'm getting results again. (Except with nth, as you say, which is still throwing the Index OOB error.) It is already becoming too slow at (last (take 200000 lazy-primes)) though. Worse yet, I need all of the primes up to n (100 million), not just the nth, and I have no idea how many primes that is. So frustrating because everyone says this problem is so easy! Conceptually it isn't very hard but I just can't get my computer to do it. I might end up just rewriting this one in Python just to get it over with. Thanks for your help guys!

(nth coll index not-found)

not-found should skip the index error

https://clojuredocs.org/clojure.core/nth

Says nth is O(n) complexity on sequences

Ok... I think the problem is

That makes sense. But even if nth was O(1), it wouldn't really help much in this case since I need them all 😕

You are looking for a number at exactly the 800,000 index and its missing

It depends... if you call nth each time in a loop, that is linear times linear = exponential

Calling nth 800,000 has to go through sequence, 1 at a time

It's missing because the first result from the lazy-seq is cached, right? Because now (time (count (doall (take 400000 lazy-primes)))) is giving me the same count for 400k, 1M, 10M, etc...

Lazy seq caches the first result, memoizes it

So basically I should just restart the REPL, run the code for the problem without testing intermediate values, and let the program run all afternoon until it gets the answer?

I think the problem is... there is no 800,000 index

Testing for intermediate values will cause 2^n complexity

If nth is called repeatedly

Linear inside linear, loop inside loop

No, not testing for intermediate values in the program. Just testing in the REPL (but results are still cached)

I would try to batch process it

Problem is when I try to test 800,000 right off the bat, I have no idea how long it is going to take (and the real count I need is, well, I have no idea). Seems like this is one I should just let run overnight

Save every 10,000 numbers

Id modify it into a batch... estimate time for each 10,000 #s, resets memory resources, see where it crashes

But memory probably is fine... just an example

Cool, thanks for your help. I don't have a C++ background so I am pretty clueless about memory allocation and all the really low-level stuff. Although I do get the impression that Clojure is not the best fit for this problem anyway (given the ginormous range of numbers involved). There aren't many, but I had to raise the white flag on a couple others and switch over to Python.

I can't repro your IndexOutOfBoundsException -- I can get (nth lazy-primes 1000000) just fine (but it takes a long time to get there)

But as it stands your lazy-primes will eventually eat up all available memory because you're holding on to the entire sequence there.

It must have been a memory issue on my machine, because the upper bound that would trigger the exception was not consistent.

Must be storing some insanely large numbers?

I'm still waiting for it to calculate 10000000 primes (or crash) 🙂

I wonder if it will exceed a big int

But Euler 357 doesn't require you calculate all those primes. It just requires that you have a fast way of determining whether any given number is prime or not.

And it also wants you to produce the list of divisors for any given number. Which is a related computation (primes have no divisors other than themselves or 1).

I'd check 1 to 9 with a modulo operator

Well, I have another non-lazy-seq function that I use for most problems. It is technically a primality checker and I use it, memoized, with filter? on range to generate a sequence, which (for its simplicity) is surprisingly fast up to a decent number (a million or so?). But it was too slow for this problem. The reason I wanted to calculate all the primes is because the initial set of candidates will be all numbers that are 1 less than a prime. (And the valid numbers are a subset of those.) So I thought it would be faster to do it that way than to test every even number. The rest of the problem (divisors and all) is manageable; I'm getting correct results as long as I can generate primes correctly.

Fair point. I strongly suspect the "best" answer is something mathematically clever rather than anything brute force (which tends to be the case with a lot of these Euler problems... which is why I gave up on Project Euler... and I'm a mathematician by training!).

Ya... example... there is a formula to find nth fibonacci... called Binet Formula

But all the prime formulas look like sequence formulas

Maybe he can run it concurrently

Certainly given unlimited memory you can calculate and cache them all (which is probably why they set the limit to be 100,000,000 to try to prevent brute force solutions?).

There's a lot of filtering you can do since for d + n/d the divisors are going to be symmetric (5 + 30/5 is the same as 6 + 30/6, and the same is true for all the smaller/larger divisors).

Yeah, absolutely. So I looked at this problem up, down and sideways but still couldn't think of any fast, intuitive way to check the validity of a given number. Of course, I don't have a math background at all; just getting into "real math" for the first time since high school.

I last studied "serious" math in university in the early 80's 🙂

Check if the # is divisible by 1 to 9

Because 1 to 9 makes up all numbers

If there is a remainder on all the divisions... it is prime

E.g. 29

29 / 9, 29 / 8, 29 / 7 etc

Modulo is a remainder

Everything is divisible by 1. 289 is not divisible by 2..9 tho' but it isn't prime.

:rolling_on_the_floor_laughing:

(289 is divisible by 17)

Ya... you are right

(all those years of math study still count for something 😆 )

I found it

Its a vedic math trick

https://youtu.be/1Yzb8IirwYQ

All primes end in 1, 3, 7, 9

But have to divide by 6, and check if remainder is 1 or 5

That's basically wheel factorization, isn't it?

I have no idea... but it is interesting to find out why it works

https://images.app.goo.gl/Cpgk7tY59rQBcgwi6

Heh, what was I saying earlier about Project Euler? 🙂

I love how it's "tune in next week to learn about the 5% of numbers for which this doesn't work!"...

sicp contains a primality check that works for all but a very small number of primes (chapter 2 i think)

(my (take 100000000 lazy-primes) still hasn't completed, BTW)

He's going to melt his ram

check probabilistic methods: http://sarabander.github.io/sicp/html/1_002e2.xhtml#g_t1_002e2_002e6

That's been fun, but I'm out for the night. See y'all tomorrow. I'll leave my REPL running that to see what I get...

my favorite footnote ever

haha, thanks for sacrificing your RAM in the name of mathematics 😄

> Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.

Hmm... If that's the case, I wonder if something not too elaborate like using Java interop for isProbablePrime would be sufficient to make the problem tractable. Will have to try after lunch

Prime numbers are the cardinal points on a base 12 system

The 1, 3, 7, 9 and modulo 1, 5 works

If you use a clock, base 12. You will see the pattern... I found a video on it

I'll write some code, tomorrow... getting sleepy

289 fails the 1-3-7-9 mod 6 test as well (289 mod 6 = 1)

Mod 6 must = 1 or 5, then it is prime

289 isn't prime

https://youtu.be/HvMSRWTE2mI

Ok... try this... numberphile better be accurate 😂

Omg... nevermind. 289 would go in the power. Meaning a 289th degree polynomial

I will look tomorrow. But it says Binet also works for primes over 5

https://math.stackexchange.com/questions/913287/relationship-between-primes-and-fibonacci-sequence

There are pretty good reasons why factoring very large numbers is computationally difficult, although I hear from a friend who has been looking seriously into the issue that quantum computers are likely to be able to start doing a few problems faster than today's computers in 5 years or so. I am not 100% certain whether factoring large numbers is one of them, but I think it is.

I am looking up Fermat's test

@dpsutton Thanks for suggesting a probabilistic method. I used isProbablePrime to create the initial list of candidates, and then used my trial division primality checker to confirm the validity of the candidates. My machine managed to get the correct answer after 13.5 minutes.

(defn problem-357 [lim]
  "Find the sum of all positive integers n not exceeding 100 000 000
  such that for every divisor d of n, d+n/d is prime."
  (let [primes     (->> (range (inc lim))
                        (filter #(.isProbablePrime (BigInteger/valueOf %) 5)))
        candidates (map dec primes)
        valid?     (fn [n]
                     (loop [d 2]
                       (cond
                         (> d (tower/sqrt n))          true
                         (or (not (h/divisible? n d))
                             (h/prime? (+ d (/ n d)))) (recur (inc d))
                         :else                         false)))]
    (reduce + (filter valid? candidates))))

(time (problem-357 100000000))
;; Elapsed time: 808512.398784 msecs

why lein run does not run in background?

Have you tried lein run & to see if it will run in the background that way, assuming that the command shell you are using, e.g. bash, uses the syntax & at the end of the command to start the process in the background?

it will not start to listen for ports unless I run fg later - weird because if I run simple bash script this way it will run in background.

I'd recommend asking in the #leiningen channel -- someone there may know more about why that is, or if there is a way to make it work as you are hoping.

Hi, Is there a way to do a`trigger fn if atom value changes`? similar how reagent atom works - trigger rerender once atom state changes? but in my case call that fn

@lepistane you probably looking for https://clojuredocs.org/clojure.core/add-watch

registers a function that gets called every time the passed in agent/atom/var/ref changes

i looked at that but i am afraid ordering might get messed up

ordering? You might have to explain a bit more what you're trying to do

I'm working on this problem: http://www.4clojure.com/problem/118 And I am attempting to solve with lazy-seq as this seems to make sense. However, I can't figure out why this is not working.

(defn my-map
  [f s]
  (lazy-seq (cons (f (first s)) (my-map f (rest s)))))

clojure-test.core=> (my-map inc [1 2 3])

NullPointerException   clojure.lang.Numbers.ops (Numbers.java:1013)

Any tips would be appreciated

What happens when s becomes empty? You haven't defined a base case for your recursive call, so eventually s will be empty. Then (inc nil) gives your null pointer

Hmm i was wondering about this, and if that is the case where would the check go? I see in this example they use rest similarly with no check. https://clojuredocs.org/clojure.core/lazy-seq#example-542692d3c026201cdc326ff1

But yeah that didn't make sense to me anyway. @dts.siedel

That sieve returns an infinite sequence. With lazy sequences you can do that (ex. (range) tries to return every number from 0 on) - note that they call take 20 when they use it, because otherwise it would try to give them every prime number

quick question guys I’m using component and I have some Services ( http clients ) which need some configuration ( api-tokens / auth … ) is it ok to create a component for that Http Clients ?

it is a matter of taste. when using component I like for any services used to be made a first class value as their own component

so for example if I was using the github api, instead of creating a http client component I would make a github api component

yeah, I meant, create a component for each service ! like you said github api component

I’m doing that @hiredman

and injecting on my server component the clients

If you create a list of futures and then dereference them right after creation, is that considered pointless? Couldn't you have just ran the functions sequentially?

result [(future (ten-min-func)) (future (five-min-func)) (future (twenty-min-func)))] and then (map deref result)

hmm I guess not

they're still running in the background, and you're still waiting for all of them to complete

now that i wrote that out

but map is lazy, remember

do you might not be waiting at the point of the code that runs (map deref result). Whoever realizes that seq will do the waiting

gotcha!

you also have to careful when creating futures, if you create them in a lazy seq they of course won't run until the seq is realized

so for example using for or map to create a seq of futures, then maping deref, then forcing that seq is bad

good catch because ive seen that around our code base somewhere

but what if you are dereferencing right after?

futures (map .... ) then (doall (map deref futures)

that's the scenario that hiredman was mentioning. map is lazy, so the futures (first map) won't be launched until the second map happens

I understand but I guess I dont understand the error in that

If I call (doall (map deref futures) right after then whats the problem?

it's equivalent to running @(future1) @(future2) @(future3)

which was probably not the intent of using the futures

they're effectively running in the current thread

and future2 isn't launched until future1 completes

ahhhhh

that makes sense

you want to spawn them all at once, then wait all at once

like in your original Q https://clojurians.slack.com/archives/C053AK3F9/p1553711929647700

(but mapv or something eager instead of map)

gotcha, thanks for clearing that up

np

@mario.cordova.862 for (let [futures (map ...)] (doall (map deref futures))) the futures aren't created until the ones before them return

(modulo chunking)

you want to create all of them in one go, or at least explicitly control how many are in flight instead of relying on lazy-seq internals for the pipelining

@noisesmith How did you make the fancy code chunk? I’m still new to Slack

@tabidots via the + button on the left

Neat, thanks!