{- |
Description: Highly totient numbers
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P38" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P38 (highlyTotientNumbers) where

import           Data.List    (genericLength, genericTake, unfoldr)
import           Problems.P35
import           Problems.P37

{- |
Construct the list of highly totient numbers.
-}
highlyTotientNumbers :: Integral a => [a]
highlyTotientNumbers :: forall a. Integral a => [a]
highlyTotientNumbers = ((a, a) -> Maybe (a, (a, a))) -> (a, a) -> [a]
forall b a. (b -> Maybe (a, b)) -> b -> [a]
unfoldr (a, a) -> Maybe (a, (a, a))
forall a. Integral a => (a, a) -> Maybe (a, (a, a))
find (a
0,a
0)

-- | Find the next highly totient number starting from the given totient number.
find :: Integral a => (a,a) -> Maybe (a,(a,a))
find :: forall a. Integral a => (a, a) -> Maybe (a, (a, a))
find (a
n, a
count) = (a, (a, a)) -> Maybe (a, (a, a))
forall a. a -> Maybe a
Just (a
n', (a
n'a -> a -> a
forall a. Num a => a -> a -> a
+a
1, a
count'))
  where (a
n', a
count') = (a, a) -> (a, a)
forall a. Integral a => (a, a) -> (a, a)
next (a
n, a
count)

next :: Integral a => (a,a) -> (a,a)
next :: forall a. Integral a => (a, a) -> (a, a)
next (a
n, a
count) | a
count' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
count = (a
n, a
count')
                | Bool
otherwise      = (a, a) -> (a, a)
forall a. Integral a => (a, a) -> (a, a)
next (a
na -> a -> a
forall a. Num a => a -> a -> a
+a
1, a
count)
  where count' :: a
count' = a -> a
forall a. Integral a => a -> a
tally a
n

{- |
Count the number of solutions for a given totient number.

For \( x = \prod_{i=1}^r {p_i}^{k_i} = \prod_{i=1}^r {p_i}^{k_i - 1} p_i \),
the totient number is \( \phi(x) = \prod_{i=1}^r {p_i}^{k_i - 1} (p_i - 1).
The prime factorization of \(\phi(x)\) must be of the
form \( \left( \prod_{i=1}^r {p_i}^{k_i - 1} \right) \left( \prod_{i=1}^r \prod_{j=1}^{l_i} q_{ij} \right) \),
where \( p_i - 1 = \prod_{j=1}^{l_i} q_{ij} \) and \( q_{ij} \) is prime..

Consider the product of one added to 1 and all of the prime factors of \( \phi(x) \).
If there is a \( p_i = 2 \), then \( p_i - 1 < 1 \times 2 \).
It is also the case that for \( p_i > 2 \), \( p_i = 1 + \prod_{j=1}^{l_i} q_{ij} < \prod_{j=1}^{l_i} (q_ij + 1) \).
Therefore this product must be larger than \(x\).  I.e., it is an upper bound for \(x\) for a given \(n=\phi(x)\).

This means that if \(n\) has the prime factorization \( \prod_i q_i \),
then a solution \(x\) to \(\phi(x) = n\) must satisfy \( 1 \leq x \leq \prod_i (q_i+1) \).
There may well be a tighter bound we can compute from only \(n\),
but this is relatively simple without having to worry whether a prime factor \(q_i\) of \(n\)
is equal to a prime factor \(p_i\) of \(x\), or whether it is a prime factor of a \(p_i - 1\).
-}
tally :: Integral a => a -> a
tally :: forall a. Integral a => a -> a
tally a
n = [a] -> a
forall i a. Num i => [a] -> i
genericLength ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (a
n ==) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a] -> [a]
forall i a. Integral i => i -> [a] -> [a]
genericTake a
bound [a]
forall a. Integral a => [a]
totients
  where bound :: a
bound = [a] -> a
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$ (a -> a) -> [a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a
1+) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a
1 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a -> [a]
forall a. Integral a => a -> [a]
primeFactors a
n

totients :: Integral a => [a]
totients :: forall a. Integral a => [a]
totients = (a -> a) -> [a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map a -> a
forall a. Integral a => a -> a
totient' [a
1..]