Copyright | (c) 2017 Andrew Lelechenko |
---|---|

License | MIT |

Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |

Safe Haskell | None |

Language | Haskell2010 |

Helpers for mapping to rough numbers and back. This has various applications in number theory.

**Example**

Let `isPrime`

be an expensive predicate,
which checks whether its argument is a prime number.
We can memoize it as usual:

isPrimeCache1 :: UChimera Bool isPrimeCache1 = tabulate isPrime isPrime1 :: Word -> Bool isPrime1 = index isPrimeCache1

But one may argue that since the only even prime number is 2,
it is quite wasteful to cache `isPrime`

for even arguments.
So we can save half the space by memoizing it for odd
numbers only:

isPrimeCache2 :: UChimera Bool isPrimeCache2 = tabulate (isPrime . (\n -> 2 * n + 1)) isPrime2 :: Word -> Bool isPrime2 n | n == 2 = True | even n = False | otherwise = index isPrimeCache2 ((n - 1) `quot` 2)

Here `\n -> 2 * n + 1`

maps n to the (n+1)-th odd number,
and `\n -> (n - 1) `quot` 2`

takes it back. These functions
are available below as `fromWheel2`

and `toWheel2`

.

Odd numbers are the simplest example of numbers, lacking small prime factors (so called rough numbers). Removing numbers, having small prime factors, is sometimes called wheel sieving.

One can go further and exclude not only even numbers,
but also integers, divisible by 3.
To do this we need a function which maps n to the (n+1)-th number coprime with 2 and 3
(thus, with 6) and its inverse: namely, `fromWheel6`

and `toWheel6`

. Then write

isPrimeCache6 :: UChimera Bool isPrimeCache6 = tabulate (isPrime . fromWheel6) isPrime6 :: Word -> Bool isPrime6 n | n `elem` [2, 3] = True | n `gcd` 6 /= 1 = False | otherwise = index isPrimeCache6 (toWheel6 n)

Thus, the wheel of 6 saves more space, improving memory locality.

(If you need to reduce memory consumption even further,
consider using `Bit`

wrapper,
which provides an instance of unboxed vector,
packing one boolean per bit instead of one boolean per byte for `Bool`

)

## Synopsis

- fromWheel2 :: Word -> Word
- toWheel2 :: Word -> Word
- fromWheel6 :: Word -> Word
- toWheel6 :: Word -> Word
- fromWheel30 :: Word -> Word
- toWheel30 :: Word -> Word
- fromWheel210 :: Word -> Word
- toWheel210 :: Word -> Word

# Documentation

fromWheel2 :: Word -> Word Source #

`fromWheel2`

n is the (n+1)-th positive odd number.
Sequence A005408.

map fromWheel2 [0..] == [ n | n <- [0..], n `gcd` 2 == 1 ]

`>>>`

[1,3,5,7,9,11,13,15,17,19]`map fromWheel2 [0..9]`

toWheel2 :: Word -> Word Source #

Left inverse for `fromWheel2`

. Monotonically non-decreasing function.

toWheel2 . fromWheel2 == id

fromWheel6 :: Word -> Word Source #

`fromWheel6`

n is the (n+1)-th positive number, not divisible by 2 or 3.
Sequence A007310.

map fromWheel6 [0..] == [ n | n <- [0..], n `gcd` 6 == 1 ]

`>>>`

[1,5,7,11,13,17,19,23,25,29]`map fromWheel6 [0..9]`

toWheel6 :: Word -> Word Source #

Left inverse for `fromWheel6`

. Monotonically non-decreasing function.

toWheel6 . fromWheel6 == id

fromWheel30 :: Word -> Word Source #

`fromWheel30`

n is the (n+1)-th positive number, not divisible by 2, 3 or 5.
Sequence A007775.

map fromWheel30 [0..] == [ n | n <- [0..], n `gcd` 30 == 1 ]

`>>>`

[1,7,11,13,17,19,23,29,31,37]`map fromWheel30 [0..9]`

toWheel30 :: Word -> Word Source #

Left inverse for `fromWheel30`

. Monotonically non-decreasing function.

toWheel30 . fromWheel30 == id

fromWheel210 :: Word -> Word Source #

`fromWheel210`

n is the (n+1)-th positive number, not divisible by 2, 3, 5 or 7.
Sequence A008364.

map fromWheel210 [0..] == [ n | n <- [0..], n `gcd` 210 == 1 ]

`>>>`

[1,11,13,17,19,23,29,31,37,41]`map fromWheel210 [0..9]`

toWheel210 :: Word -> Word Source #

Left inverse for `fromWheel210`

. Monotonically non-decreasing function.

toWheel210 . fromWheel210 == id