[Top] [All Lists]

 ```Daniel Fischer web.de> writes: > rollÂÂÂÂÂÂ = scanl (+) > wheelÂÂÂÂÂ = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2: > ÂÂÂÂÂÂÂÂÂÂ 4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel > wheel11 = res > where > snms = scanl (+) 11 (take 47 wheel) > nums = tail \$ scanl (+) 11 (take 529 wheel) > cops = nums `minus` map (*11) snms > diffs = zipWith (-) (tail cops) cops > res = foldr (:) res diffs > wheel13 = res > where > snms = take 480 \$ scanl (+) 13 wheel11 > nums = take (480*13+1) . tail \$ scanl (+) 13 wheel11 > cops = nums `minus` map (*13) snms > diffs = zipWith (-) (tail cops) cops > res = foldr (:) res diffs > BTW have you seen my take on the "faithful Euler's sieve"? It shows another way to look at the wheels, which for me was really the first time I really understood what's going on there. It also makes for easier wheel extention (IMO): > euler [email protected](p:rs) = p : euler (rs `minus` map (*p) ks) > primes = euler [2..] The essence of Euler's sieve is the wheel: after each step we're left with lists of non-multiples of the preceding primes: primes = euler \$ listFrom [2] 1 = 2:euler ( listFrom [3] 1 `minus` map(2*) (listFrom [2] 1)) ) listFrom [3,4] 2 `minus` listFrom [4] 2 -- listFrom [3] 2 -- = 2:3:euler (listFrom [5] 2 `minus` map(3*) (listFrom [3] 2)) listFrom [5,7,9] 6 `minus` listFrom [9] 6 -- listFrom [5,7] 6 -- = 2:3:5:euler (listFrom [7,11] 6 `minus` listFrom [25,35] 30) [7,11, 13,17, 19,23, 25,29, 31,35] 30 -- listFrom [7,11,13,17,19,23,29,31] 30 -- = ..... where listFrom xs by = concat \$ iterate (map (+ by)) xs so -- startRoll = ([2],1) nextRoll [email protected]([email protected](x:xt),b) = ( (x,r') , r') where [email protected](y:_) = xt ++ [x + b] r' = (xs',b') b' = x*b xs' = takeWhile (< y + b') (listFrom ys b) `minus` map (x*) xs rolls = unfoldr (Just . nextRoll) ([2],1) nthWheel n = let (ps,rs) = unzip \$ take n rolls (x:xs,b) = last rs in ((ps, x), zipWith (-) (xs++[x+b]) (x:xs)) {- *Main> mapM print \$ take 4 rolls (2,([3],2)) (3,([5,7],6)) (5,([7,11,13,17,19,23,29,31],30)) (7,([11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169, 173,179,181,187,191,193,197,199,209,211],210)) *Main> nthWheel 3 (([2,3,5],7),[4,2,4,2,4,6,2,6]) *Main> nthWheel 4 (([2,3,5,7],11),[2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2, 4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]) -} Coincidentally, the function specified by eulerPrimes n = let (ps,rs) = unzip \$ take n rolls ([email protected](q:_),b) = last rs in ps ++ takeWhile (< q^2) qs can be used to write the specialized nthEulerPrime etc., whose complexity seems to be about O(n^1.5). Maybe this reinvents some spiraling wheels or somethn'. :) _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe ```