Ya feelin' lucky, punk? A run of non-primes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import Control.Monad
import Data.Time.Clock

import Analytics.Theory.Number    -- http://lpaste.net/107480
import Control.List               -- http://lpaste.net/107211

-- solution to "Primes and ... 'not-primes'" Haskell exercise
-- at http://lpaste.net/107536

plainRun :: Integer -> [Integer]
plainRun prime = whatFactorialIsGoodFor prime

-- so, the straightforward approach is simply:

straightForward :: Integer -> [Integer]
straightForward prime =
   head ([succ prime ..] >>= \try ->
         return (take (fromInteger prime) [try ..]) >>= \ans ->
         guard (all plain ans) >> return ans)

plain :: Integer -> Bool
plain = consList . factors

{--

The problem with the straightForward approach is that the return
time just gets worse and worse over time:

 --}

timeIt :: (Integer -> [Integer]) -> Integer -> IO (NominalDiffTime, [Integer])
timeIt fn prime =
   getCurrentTime >>= \st -> return (fn prime) >>= \ans ->
   guard (length ans == fromInteger prime) >>
   getCurrentTime >>= \et -> return (diffUTCTime et st, ans)

{--

*Main> timeIt straightForward 31
(0.90079s,[1328,1329,1330,1331,1332,1333,1334,1335,1336,1337,1338,1339,
1340,1341,1342,1343,1344,1345,1346,1347,1348,1349,1350,1351,1352,1353,
1354,1355,1356,1357,1358])
*Main> timeIt straightForward 33
(0.902596s,[1328,1329,1330,1331,1332,1333,1334,1335,1336,1337,1338,1339,
1340,1341,1342,1343,1344,1345,1346,1347,1348,1349,1350,1351,1352,1353,
1354,1355,1356,1357,1358,1359,1360])
*Main> timeIt straightForward 37
(119.747299s,[15684,15685,15686,15687,15688,15689,15690,15691,15692,15693,
15694,15695,15696,15697,15698,15699,15700,15701,15702,15703,15704,15705,
15706,15707,15708,15709,15710,15711,15712,15713,15714,15715,15716,15717,
15718,15719,15720])

119 seconds for a run of 37-non-prime numbers? Ouch. That's gotta hurt!

So the above straightForward solution returns in nonlinear time, and it only
gets worse (unless the numbers are ... 'feelin' lucky.' But, ya gotta ask 
yerself the question: 'are you feelin' lucky, punk? Huh?' said with the steely
Clint Eastwood-glare).

Another solution, giving a different result (further out on the number line)
is to use factorials on the prime. This solution was in response to the
@AlgebraFacts observation.

for prime p, there exists a run of consecutive non-prime numbers of length p
such that:

non-primes of length p = [(p + 1)! + 2, (p + 1)! + 3, .. (p + 1)! + (p + 1)]

So, all we have to do is compute the first number in the sequence, and
we have our solution!

 --}

whatFactorialIsGoodFor :: Integer -> [Integer]
whatFactorialIsGoodFor p = take (fromInteger p) [2 + fac (succ p) ..]

{--

Validation can be done separately, as it's redundant, so, here we go:

*Main> plainRun 31 ~> [263130836933693530167218012160000002, ...]
*Main> all plain it ~> True

*Main> plainRun 33 ~> [295232799039604140847618609643520000002, ...]
*Main> all plain it ~> True

*Main> plainRun 37 ~> [523022617466601111760007224100074291200000002, ...]
*Main> all plain it ~> True

All three interactions above took an unnoticeable (subsecond) time to return.

 --}
11:1: Error: Eta reduce
Found:
plainRun prime = whatFactorialIsGoodFor prime
Why not:
plainRun = whatFactorialIsGoodFor
18:10: Error: Monad law, left identity
Found:
return (take (fromInteger prime) [try ..]) >>=
\ ans -> guard (all plain ans) >> return ans
Why not:
((\ ans -> guard (all plain ans) >> return ans)
(take (fromInteger prime) [try ..]))
33:30: Error: Monad law, left identity
Found:
return (fn prime) >>=
\ ans ->
guard (length ans == fromInteger prime) >> getCurrentTime >>=
\ et -> return (diffUTCTime et st, ans)
Why not:
((\ ans ->
guard (length ans == fromInteger prime) >> getCurrentTime >>=
\ et -> return (diffUTCTime et st, ans))
(fn prime))