| Copyright | Copyright (C) 2021 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P38
Description
Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P38.
Synopsis
- highlyTotientNumbers :: Integral a => [a]
Documentation
highlyTotientNumbers :: Integral a => [a] Source #
It is possible for more than one number \(x\) to have the same totient number \(\phi(x)\). For example, \(\phi(77) = \phi(93) = 60\).
A highly totient number \(n\) has the most such \(x\) among the totient numbers less than or equal to \(n\). I.e., \(n\) is a highly totient number if \(|\{x \,|\, \phi(x)=n \}| > |\{x \,|\, \phi(x)=m \}|\) for \(m < n\).
Construct the list of highly totient numbers.
Examples
>>>take 10 highlyTotientNumbers[1,2,4,8,12,24,48,72,144,240]
Hint
Given a totient number \(n=\phi(x)\), find an upper bound for \(x\), which will bound the set of numbers from which to search for solutions. Compare the prime factorizations between \(\phi(x)\) and \(x\), and devise a modification of the former so that it must be larger than the latter.