Determining primality by removing select composits

You should use more Data.List functions - explicit recursion is hard to read.

comp1 y = sort [ m | (i,n) <- zip [0..149] n7sl , m <- takeWhile ((<= 11 * last (take y n7sl))) $ map (n*) $ drop i $ take n n7sl ] 

Edit: Not sure whether my version fails to be equal to your original one, but here's a further refactoring of the one in your comment to get rid of some number manipulation. The takeWhile reflects the short-circuiting behavior of the original, explicitly recursive implementation, which uses that bs is ascending.

t = sort [ m | bs@(a:_) <- tails n7s, m <- takeWhile (<= 11*last n7s) $ map (a*) bs] 

After simplifications, your infinite code (from your answer) turns out to be equivalent to

import Data.List (tails) import Data.List.Ordered (minus, unionAll) primes = ([2,3,5,7] ++) . minus n7sl . unionAll $ [ map (x*) xs | xs@(x:_) <- tails n7sl ] 

The main difference is that whereas your code builds the matrix

> mapM_ print $ take 20 $ zip n7sl [take i n7sl | i <- [1..]] (11,[11]) (13,[11,13]) (17,[11,13,17]) (19,[11,13,17,19]) (23,[11,13,17,19,23]) (29,[11,13,17,19,23,29]) (31,[11,13,17,19,23,29,31]) (37,[11,13,17,19,23,29,31,37]) (41,[11,13,17,19,23,29,31,37,41]) (43,[11,13,17,19,23,29,31,37,41,43]) (47,[11,13,17,19,23,29,31,37,41,43,47]) (53,[11,13,17,19,23,29,31,37,41,43,47,53]) (59,[11,13,17,19,23,29,31,37,41,43,47,53,59]) (61,[11,13,17,19,23,29,31,37,41,43,47,53,59,61]) (67,[11,13,17,19,23,29,31,37,41,43,47,53,59,61,67]) (71,[11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]) (73,[11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73]) (79,[11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79]) (83,[11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83]) (89,[11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89]) 

by rows (in each row, the list is multiplied by the first number in the tuple), and processes it by rows -- putting them through the unionAll process -- the rewrite in this answer is as if working on the same matrix by columns (after the multiplication by the first number in the tuple, again).

Because tails is much less computationally demanding compared with your repeated use of take, and because we use minus from Data.List.Ordered package instead of your rms (with the flipped order of arguments), this runs much much faster now. Testing in GHCi:

> primes !! 1000000 15485867 it :: Integral a => a (2.12 secs, 3734834160 bytes) > primes !! 500000 7368791 it :: Integral a => a (0.98 secs, 1765893576 bytes) > logBase 2 (2.12 / 0.98) 1.113210610447991 

Yes, that's a million primes that it now reaches, in just over 2 seconds, at about n^1.1 empirical orders of growth (in n primes produced), which is quite good (the coefficient, not the time; arithmoi's code reaches the one millionth prime in 0.1 seconds on the same computer).

This is not a sieve of Eratosthenes though. It builds the multiples not from primes, but from the 2-3-5-7-wheel enumeration.

---

For proper testing always compile with the -O2 switch and run the resulting standalone executable at the shell, with +RTS -s run-time options (to get the time and space statistics).

Breaking up comps results in simpler, more efficient, easier to control functions.

Two lists (x,y) for a Cartesian product are usual. The products are half duplicates. If each column starts with a perfect square, the duplicates are eliminated.

Then each column is generated. Each column starts with a perfect square but then must also be specifically trimmed in length. Each multiple is compared to the limititing value.

So, about 25% or less of the Cartesian product are used, that is, calculated.

calcc limits the value of each factor multiple it calculates just like comps but unlike comps it doesn't use an initial-factor list. Each initial-factor squared is first on the multiple list. Each initial-factor is the head of each factor lists input.

I tried making comps use one list only instead of two. The function was short, more complicated but not faster. Two remaining problems with it were the calculation for the limit value which only needs to be calculated one time at the beginning and a problem with all such functions a glob of parameters or superflous where calculations. The functions need the parameters but should not be recalculated time-after-time.

runr passes the initial-factor to apply to itself and all other factors. The list sent to calcc starts with a perfect square factor value. The diagonal eliminates duplicates.

rrunr sarts runr with a length n factor list and the limit based on that list length.
The 11 multiples extend to n. Successive columns shorten to none at about n/10

Checking every perfect square against the limit does not save time.

I also tried mergeAll from Data.List.Ordered but it seemed to error around 3/4 the way down a prime list. I still have to investigate. sort is what I still use but the functions now let me create a single list or a list of lists for mergeAll.

calcc _ _ []= [] calcc f lim (x:xs) | m<= lim= m:calcc f lim xs | True= [] where m= f*x runr _ []= [] runr lim xss@(x:xs) = (calcc x lim xss)++runr lim xs rrunr n = runr lim ds where ds= take n n7sl lim= 11*last ds 

last.rms (sort $ rrunr 5000) $ n7sl

240641

(0.07 secs, 50,617,744 bytes)

last.rms (sort $ rrunr 10000) $ n7sl

481249

(0.18 secs, 115,282,560 bytes)

last.rms (sort $ rrunr 15000) $ n7sl

721891

(0.25 secs, 179,096,928 bytes)

5/13/2019

I tried unionAll instead of mergeAll because each sub-list is already in order. It did result in a minor speed up. runr produces individual sub-lists for unionAll.

runr _ []= [] runr lim xss@(x:xs) = [calcc x lim xss]++runr lim xs 

last $ rms (unionAll $ rrunr 10000) n7sl

481249

(0.12 secs, 89,250,264 bytes)

last $ rms (unionAll $ rrunr 15000) n7sl

721891

(0.20 secs, 140,110,392 bytes)

last $ rms (unionAll $ rrunr 20000) n7sl

962509

(0.27 secs, 192,858,656 bytes)

I have an infinite version of this which is much simpler coding but it is a little slower.

mupcl _ [] = [] mupcl (x:xs) (y:ys) = [(x*) <$> y]++ mupcl xs ys uat = unionAll.mupcl n7sl $ (\i-> (take i n7sl)) <$> [1..] 

take 50000 $ rms uat n7sl

611993

(0.45 secs, 269,026,264 bytes)

I updated this because finding the nth prime is important and this can. It's still slower than the fixed just before this but has some uses not available to the fixed. I toyed with making the sublists sequences but then found that I could generate the sublist end value and multiply it by all previous values and itself. Sequence would access the end value in about O(1) which is awesome but the end values are in one-to-one correspondence with each sublist.

The diagonal of these is just each sublist is one longer than the previous.This is the top diagonal necessary for an infinite list.

The previous functions use a bottom diagonal and a limit value. If they used the top diagonal would they end as this function? IDK

5/27/2019

The composite list was being traversed twice and it was driving me nuts. I could not come up with a single function that would multiply two identical infinite lists diagonally.

I had developed one function to multiply 2s, 3s & 5s together to form the Hamming list. Saturday morning I looked at that function and followed the pattern for this function. It amazed me it worked. unionAll does the limiting.

umap = unionAll $ map (\n -> (n*) <$> n7sl) n7sl 

But, I am such an impatient idiot the function is going through two lists, exactly what I didn't want. I have an aversion to tails, more like a phobia because of experience with tails crashing my PC in an infinite function. What I discovered the past two or three months is that mergeAll and unionAll do magic with infinite lists. They automatically limit end points. Talk about no coding. I spent so much time coding end points in this and in the Hamming numbers (which are way fast, too) that I really feel like an idiot. @Will Ness knows way more than I, too. Haskell is pure (no pun) magic with laziness.

c2 = unionAll $ map (\xs@(x:_)-> (x*) <$> xs) $ tails n7sl 

(minus n7sl c2) !! 1000000

15485941

(1.55 secs, 3,545,902,888 bytes)

And now, it's way faster than the non-infinite above.

This does 75803 primes to 962509 in 0.08 and the non-infinite does 75803 to 962509 in 0.27 and uses a little more memory.

This does

(minus n7sl c2) !! 75803

962509

(0.08 secs, 162,030,280 bytes)

5.30.2019

OMG. It worked! I told @Will Ness it might, but that it would not with the non-infinite. What it is is the size of the wheel. I started calling it a wheel when I saw the deltas to create it. Mine is not a wheel because I have to generate the deltas from a column in Excel. I take 300 of n7sl into a column in Excel them I remove all the 11 multiples. I take the deltas of the remainder then find where it repeats.

My no 11s list is

n11s=[4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,12,10,2,4,2,4,6,2,6,4,6,6,6,2,6,4,2,6,4,6,8,4,2,4,6,8,6,10,2,4,6,2,6,6,4,2,4,6,2,6,4,2,6,10,2,10,2,4,2,4,6,8,4,2,4,12,2,6,4,2,6,4,6,12,2,4,2,4,8,6,4,6,2,4,6,2,6,10,2,4,6,2,6,4,2,4,2,10,2,10,2,4,6,6,2,6,6,4,6,6,2,6,4,2,6,4,6,8,4,2,6,4,8,6,4,6,2,4,6,8,6,4,2,10,2,6,4,2,4,2,10,2,10,2,4,2,4,8,6,4,2,4,6,6,2,6,4,8,4,6,8,4,2,4,2,4,8,6,4,6,6,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10,2,6,4,6,2,6,4,2,4,6,6,8,4,2,6,10,8,4,2,4,2,4,8,10,6,2,4,8,6,6,4,2,4,6,2,6,4,6,2,10,2,10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,6,6,4,6,8,4,2,4,2,4,8,6,4,8,4,6,2,6,6,4,2,4,6,8,4,2,4,2,10,2,10,2,4,2,4,6,2,10,2,4,6,8,6,4,2,6,4,6,8,4,6,2,4,8,6,4,6,2,4,6,2,6,6,4,6,6,2,6,6,4,2,10,2,10,2,4,2,4,6,2,6,4,2,10,6,2,6,4,2,6,4,6,8,4,2,4,2,12,6,4,6,2,4,6,2,12,4,2,4,8,6,4,2,4,2,10,2,10,6,2,4,6,2,6,4,2,4,6,6,2,6,4,2,10,6,8,6,4,2,4,8,6,4,6,2,4,6,2,6,6,6,4,6,2,6,4,2,4,2,10,12,2,4,2,10,2,6,4,2,4,6,6,2,10,2,6,4,14,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,12,2,12] n11sl = scanl (+) 13 $ cycle n11s 

The improvement is not stark and going any further with this would not be beneficial. c2 modified to use n11sl

c2 = unionAll $ map (\xs@(x:_) -> (x*) <$> xs) $ tails n11sl 

Executing it would be

(11:(minus n11sl c2)) !! 1000000

15485941

(1.30 secs, 2,968,456,072 bytes)

(11:(minus n11sl c2)) !! 500000

7368841

(0.55 secs, 1,305,594,104 bytes)