-- |
-- Module      : Math.OEIS
-- Copyright   : (c) Eric Bailey, 2020-2025
--
-- License     : MIT
-- Maintainer  : eric@ericb.me
-- Stability   : experimental
-- Portability : POSIX
--
-- Some sequences from [OEIS](https://oeis.org)
module Math.OEIS
  ( a000010,
    a000040,
    a000078,
    a000111,
    a000120,
    a000182,
    a000203,
    a000217,
    a000285,
    a000290,
    a000312,
    a000326,
    a000330,
    a000364,
    a000384,
    a000537,
    a001065,
    a001142,
    a001913,
    a002034,
    a002088,
    a002109,
    a002326,
    a002378,
    a003313,
    a004185,
    a005101,
    a005153,
    a005252,
    a007318,
    a007947,
    a007953,
    a013928,
    a014445,
    a015614,
    a027748,
    a034705,
    a048260,
    a049690,
    a051885,
    a056924,
    a057627,
    a060735,
    a072389,
    a076314,
    a082949,
    a111251,
    a161680,
    a204692,
    a211264,
    digitSum,
    distinctPrimeFactors,
    hexagonalNumbers,
    isPentagonal,
    isPractical,
    pentagonalNumbers,
    squarePyramidalNumbers,
    squares,
    triangularNumbers,
  )
where

import Control.Arrow (first, (&&&), (***), (>>>))
import Control.Monad (ap, join)
import Data.Bits (Bits, popCount)
import Data.Bool (bool)
import Data.Euclidean (GcdDomain)
import Data.FastDigits (digits, undigits)
import Data.Foldable (toList)
import Data.IntSet qualified as IS
import Data.List (sortOn)
import Data.List.Extra (productOn', sumOn')
import Data.List.Infinite (Infinite ((:<)), (...), (....))
import Data.List.Infinite qualified as Infinite
import Data.List.NonEmpty (NonEmpty ((:|)))
import Data.List.NonEmpty qualified as NE
import Data.List.Ordered qualified as Ordered
import Data.Map.Strict (Map)
import Data.Map.Strict qualified as Map
import Data.Ord (Down (..))
import Data.Ratio (numerator)
import Data.Semiring (Semiring)
import Data.Set (deleteFindMin, insert, singleton)
import Math.Combinatorics.Exact.Binomial (choose)
import Math.NumberTheory.ArithmeticFunctions (moebius, runMoebius, sigma, tau, totient)
import Math.NumberTheory.Primes (Prime, UniqueFactorisation, factorise, nextPrime, unPrime)
import Math.NumberTheory.Primes.Testing (isPrime)
import Math.NumberTheory.Recurrences (bernoulli, binomial, binomialLine, euler, fibonacci, lucas)
import Math.NumberTheory.Roots (integerSquareRoot, isSquare)
import Math.OEIS.HybridInteger (HybridInteger (..))
import Numeric.Natural (Natural)

-- | Euler totient function \(\phi(n)\): count numbers \(1 \le k \le n\) such
-- that \(k\) is coprime with \(n), i.e., [A000010](https://oeis.org/A000010).
a000010 :: (Integral a, UniqueFactorisation a) => Infinite a
a000010 :: forall a. (Integral a, UniqueFactorisation a) => Infinite a
a000010 = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
forall n. UniqueFactorisation n => n -> n
totient (a
1 ...)

-- | The prime numbers, i.e., [A000040](https://oeis.org/A000040).
a000040 :: (Bits a, Enum (Prime a), Integral a, UniqueFactorisation a) => Infinite a
a000040 :: forall a.
(Bits a, Enum (Prime a), Integral a, UniqueFactorisation a) =>
Infinite a
a000040 = (Prime a -> a) -> Infinite (Prime a) -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map Prime a -> a
forall a. Prime a -> a
unPrime (a -> Prime a
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
nextPrime a
2 ...)

-- | Tetranacci numbers, i.e., [A000078](https://oeis.org/A000078).
a000078 :: (Integral a) => Infinite a
a000078 :: forall a. Integral a => Infinite a
a000078 = ((a, a, a, a) -> (a, (a, a, a, a))) -> (a, a, a, a) -> Infinite a
forall b a. (b -> (a, b)) -> b -> Infinite a
Infinite.unfoldr (a, a, a, a) -> (a, (a, a, a, a))
forall {d}. Num d => (d, d, d, d) -> (d, (d, d, d, d))
go (a
0, a
0, a
0, a
1)
  where
    go :: (d, d, d, d) -> (d, (d, d, d, d))
go (d
a, d
b, d
c, d
d) = (d
a, (d
b, d
c, d
d, d
a d -> d -> d
forall a. Num a => a -> a -> a
+ d
b d -> d -> d
forall a. Num a => a -> a -> a
+ d
c d -> d -> d
forall a. Num a => a -> a -> a
+ d
d))

-- | Euler up/down numbers: e.g.f. \(\sec(x) + \tan(x)\), i.e.
-- [A000111](https://oeis.org/A000111).
a000111 :: (Integral a) => Infinite a
a000111 :: forall a. Integral a => Infinite a
a000111 = Infinite a -> Infinite a -> Infinite a
forall a. Infinite a -> Infinite a -> Infinite a
Infinite.interleave Infinite a
forall a. Integral a => Infinite a
a000364 Infinite a
forall a. Integral a => Infinite a
a000182

-- | Binary weight, i.e., [A000120](https://oeis.org/A000120).
a000120 :: Infinite Int
a000120 :: Infinite Int
a000120 = (Integer -> Int) -> Infinite Integer -> Infinite Int
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map (forall a. Bits a => a -> Int
popCount @Integer) (Integer
0 ...)

-- | Tangent (or \"Zag\") numbers: e.g.f. \(\tan(x)\), also (up to signs), e.g.,
-- \(\tanh(x)\), i.e., [A000182](https://oeis.org/A000182).
a000182 :: (Integral a) => Infinite a
a000182 :: forall a. Integral a => Infinite a
a000182 =
  ((a, Ratio a) -> a) -> Infinite (a, Ratio a) -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map
    (\(a
n, Ratio a
b) -> Ratio a -> a
forall a. Ratio a -> a
numerator (Ratio a
2 Ratio a -> a -> Ratio a
forall a b. (Num a, Integral b) => a -> b -> a
^ a
n Ratio a -> Ratio a -> Ratio a
forall a. Num a => a -> a -> a
* (Ratio a
2 Ratio a -> a -> Ratio a
forall a b. (Num a, Integral b) => a -> b -> a
^ a
n Ratio a -> Ratio a -> Ratio a
forall a. Num a => a -> a -> a
- Ratio a
1) Ratio a -> Ratio a -> Ratio a
forall a. Num a => a -> a -> a
* Ratio a -> Ratio a
forall a. Num a => a -> a
abs Ratio a
b) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
n)
    (Infinite (a, Ratio a) -> Infinite a)
-> Infinite (a, Ratio a) -> Infinite a
forall a b. (a -> b) -> a -> b
$ Infinite a -> Infinite (Ratio a) -> Infinite (a, Ratio a)
forall a b. Infinite a -> Infinite b -> Infinite (a, b)
Infinite.zip ((a
2, a
4) ....)
    (Infinite (Ratio a) -> Infinite (a, Ratio a))
-> Infinite (Ratio a) -> Infinite (a, Ratio a)
forall a b. (a -> b) -> a -> b
$ Infinite (Ratio a) -> Infinite (Ratio a)
forall a. Infinite a -> Infinite a
Infinite.tail
    (Infinite (Ratio a) -> Infinite (Ratio a))
-> Infinite (Ratio a) -> Infinite (Ratio a)
forall a b. (a -> b) -> a -> b
$ Infinite (Ratio a) -> Infinite (Ratio a)
forall a. Infinite a -> Infinite a
everyOther Infinite (Ratio a)
forall a. Integral a => Infinite (Ratio a)
bernoulli

-- | The sum of the divisors of \(n\), i.e., [A000203](https://oeis.org/A000203).
a000203 :: forall a. (UniqueFactorisation a, Integral a, GcdDomain a) => Infinite a
a000203 :: forall a.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
Infinite a
a000203 = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map (Word -> a -> a
forall n a.
(UniqueFactorisation n, Integral n, Num a, GcdDomain a) =>
Word -> n -> a
sigma Word
1) ((a
1 :: a) ...)

-- | Triangular numbers: \(T_{n} = \frac{n(n+1)}{2}\), i.e., [A000217](https://oeis.org/A000217).
a000217 :: (Integral a) => a -> a
a000217 :: forall a. Integral a => a -> a
a000217 a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
* (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2

-- | Pseudo-Fibonacci numbers, i.e., [A000285](https://oeis.org/A000285).
a000285 :: (Num a) => Infinite a
a000285 :: forall a. Num a => Infinite a
a000285 = (Int -> a) -> Infinite Int -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map ((a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Num a => a -> a -> a
(+) ((a, a) -> a) -> (Int -> (a, a)) -> Int -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int -> a
forall a. Num a => Int -> a
fibonacci (Int -> a) -> (Int -> Int) -> Int -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int
forall a. Enum a => a -> a
pred) (Int -> a) -> (Int -> a) -> Int -> (a, a)
forall b c c'. (b -> c) -> (b -> c') -> b -> (c, c')
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& Int -> a
forall a. Num a => Int -> a
lucas)) (Int
1 ...)

-- | See 'a000217'.
triangularNumbers :: (Integral a) => Infinite a
triangularNumbers :: forall a. Integral a => Infinite a
triangularNumbers = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
forall a. Integral a => a -> a
a000217 (a
0 ...)

a000290, squares :: (Enum a, Num a) => Infinite a
a000290 :: forall a. (Enum a, Num a) => Infinite a
a000290 = (a -> a -> a) -> a -> Infinite a -> Infinite a
forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
Infinite.scanl a -> a -> a
forall a. Num a => a -> a -> a
(+) a
0 ((a
1, a
3) ....)
-- ^ The squares: \(a000290(n) = n^2\), i.e., [A000290](https://oeis.org/A000290).
squares :: forall a. (Enum a, Num a) => Infinite a
squares = Infinite a
forall a. (Enum a, Num a) => Infinite a
a000290
-- ^ See 'a000290'.

-- | \(a(n) = n^n\), i.e., [A000312](https://oeis.org/A000312).
a000312 :: (Integral a) => Infinite a
a000312 :: forall a. Integral a => Infinite a
a000312 = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map ((a -> a -> a) -> a -> a
forall (m :: * -> *) a. Monad m => m (m a) -> m a
join a -> a -> a
forall a b. (Num a, Integral b) => a -> b -> a
(^)) (a
0 ...)

-- | Pentagonal numbers: \(P_{n} = \frac{n(3n-1)}{2}\), i.e., [A000326](https://oeis.org/A000326).
a000326 :: (Integral a) => a -> a
a000326 :: forall a. Integral a => a -> a
a000326 a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
* (a
3 a -> a -> a
forall a. Num a => a -> a -> a
* a
n a -> a -> a
forall a. Num a => a -> a -> a
- a
1) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2

-- | See 'a000326'.
pentagonalNumbers :: (Integral a) => Infinite a
pentagonalNumbers :: forall a. Integral a => Infinite a
pentagonalNumbers = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
forall a. Integral a => a -> a
a000326 (a
0 ...)

-- | Determine whether a given number is pentagonal, i.e., a member of 'a000326'.
isPentagonal :: (Integral a) => a -> Bool
isPentagonal :: forall a. Integral a => a -> Bool
isPentagonal a
0 = Bool
True
isPentagonal a
n = let s :: a
s = a
24 a -> a -> a
forall a. Num a => a -> a -> a
* a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1 in a -> Bool
forall a. Integral a => a -> Bool
isSquare a
s Bool -> Bool -> Bool
&& a -> a
forall a. Integral a => a -> a
integerSquareRoot a
s a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
6 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
5

-- | Square pyramidal numbers: \(a(n) = 0^2+1^2+2^2 + \dotsb + n^2 = \frac{n(n+1)(2n+1)}{6}\),
-- i.e., [A000330](https://oeis.org/A000330).
a000330 :: (Integral a) => a -> a
a000330 :: forall a. Integral a => a -> a
a000330 a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
* (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) a -> a -> a
forall a. Num a => a -> a -> a
* (a
2 a -> a -> a
forall a. Num a => a -> a -> a
* a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
6

-- | See 'a000330'.
squarePyramidalNumbers :: (Integral a) => Infinite a
squarePyramidalNumbers :: forall a. Integral a => Infinite a
squarePyramidalNumbers = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
forall a. Integral a => a -> a
a000330 (a
0 ...)

-- | Euler (or secant or \"Zig\") numbers: e.g.f. (even powers only)
-- \(\sec(x) = \frac{1}{\cos(x)}\), i.e., [A000364](https://oeis.org/A000364).
a000364 :: (Integral a) => Infinite a
a000364 :: forall a. Integral a => Infinite a
a000364 = Infinite a -> Infinite a
forall a. Infinite a -> Infinite a
everyOther ((a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
forall a. Num a => a -> a
abs Infinite a
forall a. Integral a => Infinite a
euler)

-- | Hexagonal numbers: \(H_{n} = n(2n-1)\), i.e., [A000384](https://oeis.org/A000384).
a000384 :: (Integral a) => a -> a
a000384 :: forall a. Integral a => a -> a
a000384 a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
* (a
2 a -> a -> a
forall a. Num a => a -> a -> a
* a
n a -> a -> a
forall a. Num a => a -> a -> a
- a
1)

-- | See 'a000384'.
hexagonalNumbers :: (Integral a) => Infinite a
hexagonalNumbers :: forall a. Integral a => Infinite a
hexagonalNumbers = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
forall a. Integral a => a -> a
a000384 (a
0 ...)

-- | Sum of first \(n\) cubes; or \(n\)-th triangular number squared, i.e.
-- [A000537](https://oeis.org/A000537).
a000537 :: (Integral a) => Infinite a
a000537 :: forall a. Integral a => Infinite a
a000537 = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map ((a -> a -> a) -> a -> a
forall (m :: * -> *) a. Monad m => m (m a) -> m a
join a -> a -> a
forall a. Num a => a -> a -> a
(*) (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (\a
n -> (a
n a -> a -> a
forall a. Num a => a -> a -> a
* (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1)) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2)) (a
0 ...)

-- | Aliquot sum of \(n\), i.e., [A001065](https://oeis.org/A001065).
a001065 :: forall a. (UniqueFactorisation a, Integral a, GcdDomain a) => Infinite a
a001065 :: forall a.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
Infinite a
a001065 = a
0 a -> Infinite a -> Infinite a
forall a. a -> Infinite a -> Infinite a
:< (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map ((-) (a -> a -> a) -> (a -> a) -> a -> a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Word -> a -> a
forall n a.
(UniqueFactorisation n, Integral n, Num a, GcdDomain a) =>
Word -> n -> a
sigma Word
1) (a
1 ...)

-- | Products of rows of Pascal's triangle, i.e., [A001142](https://oeis.org/A001142).
a001142 :: (Integral a, GcdDomain a) => Infinite a
a001142 :: forall a. (Integral a, GcdDomain a) => Infinite a
a001142 = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map ([a] -> a
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([a] -> a) -> (a -> [a]) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> [a]
forall a. (Enum a, GcdDomain a) => a -> [a]
binomialLine) (a
0 ...)

-- | Full reptend primes, i.e., [A001913](https://oeis.org/A001913).
a001913 :: (Bits a, Enum (Prime a), Integral a, UniqueFactorisation a) => Infinite a
a001913 :: forall a.
(Bits a, Enum (Prime a), Integral a, UniqueFactorisation a) =>
Infinite a
a001913 = (a -> Bool) -> Infinite a -> Infinite a
forall a. (a -> Bool) -> Infinite a -> Infinite a
Infinite.filter a -> Bool
forall a. Integral a => a -> Bool
go (Int -> Infinite a -> Infinite a
forall a. Int -> Infinite a -> Infinite a
Infinite.drop Int
3 Infinite a
forall a.
(Bits a, Enum (Prime a), Integral a, UniqueFactorisation a) =>
Infinite a
a000040)
  where
    go :: a -> Bool
go a
p = a -> a -> a
forall a. Integral a => a -> a -> a
orderMod' a
10 a
p a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
p a -> a -> a
forall a. Num a => a -> a -> a
- a
1

-- | Kempner numbers: smallest positive integer \(m\) such that \(n\) divides
-- \(m!\), i.e., [A002034](https://oeis.org/A002034).
a002034 :: (Integral a, UniqueFactorisation a) => Infinite a
a002034 :: forall a. (Integral a, UniqueFactorisation a) => Infinite a
a002034 = a
1 a -> Infinite a -> Infinite a
forall a. a -> Infinite a -> Infinite a
:< (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
go (a
2 ...)
  where
    go :: a -> a
go = [a] -> a
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([a] -> a) -> (a -> [a]) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Prime a, Word) -> a) -> [(Prime a, Word)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map ((a, a) -> a
forall {b}. Integral b => (b, b) -> b
kempner ((a, a) -> a)
-> ((Prime a, Word) -> (a, a)) -> (Prime a, Word) -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Prime a -> a
forall a. Prime a -> a
unPrime (Prime a -> a) -> (Word -> a) -> (Prime a, Word) -> (a, a)
forall b c b' c'. (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** Word -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral)) ([(Prime a, Word)] -> [a]) -> (a -> [(Prime a, Word)]) -> a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> [(Prime a, Word)]
forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
factorise
    kempner :: (b, b) -> b
kempner (b
p, b
e)
      | b
e b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
p = b
e b -> b -> b
forall a. Num a => a -> a -> a
* b
p
      | Bool
otherwise =
          (b -> Bool) -> (b -> b) -> b -> b
forall a. (a -> Bool) -> (a -> a) -> a -> a
until ((b -> b -> Bool
forall a. Ord a => a -> a -> Bool
>= b
e) (b -> Bool) -> (b -> b) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> b -> b
forall a. Integral a => a -> a -> a
dePolignac b
p) (b -> b -> b
forall a. Num a => a -> a -> a
+ b
p) (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$
            b
e b -> b -> b
forall a. Num a => a -> a -> a
* (b
p b -> b -> b
forall a. Num a => a -> a -> a
- b
1) b -> b -> b
forall a. Integral a => a -> a -> a
`div` b
p b -> b -> b
forall a. Num a => a -> a -> a
* b
p

-- | Summatory totient, i.e., [A002088](https://oeis.org/A002088).
--
-- See also 'a000010'.
a002088 :: (Integral a, UniqueFactorisation a) => Infinite a
a002088 :: forall a. (Integral a, UniqueFactorisation a) => Infinite a
a002088 = (a -> a -> a) -> a -> Infinite a -> Infinite a
forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
Infinite.scanl a -> a -> a
forall a. Num a => a -> a -> a
(+) a
0 Infinite a
forall a. (Integral a, UniqueFactorisation a) => Infinite a
a000010

-- | Hyperfactorials: \(\prod_{k=1}^n k^k\), i.e.
-- [A002109](https://oeis.org/A002109).
--
-- See also 'a000312'.
a002109 :: (Integral a) => Infinite a
a002109 :: forall a. Integral a => Infinite a
a002109 = (a -> a -> a) -> a -> Infinite a -> Infinite a
forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
Infinite.scanl a -> a -> a
forall a. Num a => a -> a -> a
(*) a
1 (Infinite a -> Infinite a
forall a. Infinite a -> Infinite a
Infinite.tail Infinite a
forall a. Integral a => Infinite a
a000312)

-- | Multiplicative order of \(2 \bmod{2n + 1}\), i.e.,
-- [A002326](https://oeis.org/A002326).
a002326 :: (Integral a) => Infinite a
a002326 :: forall a. Integral a => Infinite a
a002326 = a
1 a -> Infinite a -> Infinite a
forall a. a -> Infinite a -> Infinite a
:< (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map (\a
n -> a -> a -> a
forall a. Integral a => a -> a -> a
orderMod' a
2 (a
2 a -> a -> a
forall a. Num a => a -> a -> a
* a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1)) (a
1 ...)

-- | Oblong (or promic, pronic, or heteromecic) numbers:
-- \(a002378(n) = n(n+1)\), i.e., [A002378](https://oeis.org/A002378).
a002378 :: (Integral a) => a -> a
a002378 :: forall a. Integral a => a -> a
a002378 a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
* (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1)

-- | Length of shortest addition chain for \(n\), i.e.
-- [A003313](https://oeis.org/A003313).
a003313 :: Natural -> Int
a003313 :: Natural -> Int
a003313 Natural
n
  | Natural
n Natural -> [Natural] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [Natural
77, Natural
154] = Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
  | Bool
otherwise = Int
k
  where
    k :: Int
k = [Natural] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Natural -> [Natural]
powerTree Natural
n) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

-- | Sort the digits of \(n\) in ascending order, removing any zeros, i.e.,
-- [A004185](https://oeis.org/A004185).
a004185 :: Infinite Integer
a004185 :: Infinite Integer
a004185 = Integer
0 Integer -> Infinite Integer -> Infinite Integer
forall a. a -> Infinite a -> Infinite a
:< (Integer -> Integer) -> Infinite Integer -> Infinite Integer
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map (forall a b. (Integral a, Integral b) => a -> [b] -> Integer
undigits @Int Int
10 ([Int] -> Integer) -> (Integer -> [Int]) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Down Int) -> [Int] -> [Int]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn Int -> Down Int
forall a. a -> Down a
Down ([Int] -> [Int]) -> (Integer -> [Int]) -> Integer -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0) ([Int] -> [Int]) -> (Integer -> [Int]) -> Integer -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Integer -> [Int]
digits Int
10) (Integer
1 ...)

-- | Abundant numbers (sum of divisors of \(n\) exceeds \(2n\), i.e.,
-- [A005101](https://oeis.org/A005101).
a005101 :: (UniqueFactorisation a, Integral a, GcdDomain a) => Infinite a
a005101 :: forall a.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
Infinite a
a005101 = (a -> Bool) -> Infinite a -> Infinite a
forall a. (a -> Bool) -> Infinite a -> Infinite a
Infinite.filter a -> Bool
forall {a}.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
a -> Bool
isAbundant (a
1 ...)
  where
    isAbundant :: a -> Bool
isAbundant a
n = Word -> a -> a
forall n a.
(UniqueFactorisation n, Integral n, Num a, GcdDomain a) =>
Word -> n -> a
sigma Word
1 a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
2 a -> a -> a
forall a. Num a => a -> a -> a
* a
n

-- | Practical numbers, i.e., [A005153](https://oeis.org/A005153).
a005153 :: (Integral a, UniqueFactorisation a, GcdDomain a) => Infinite a
a005153 :: forall a.
(Integral a, UniqueFactorisation a, GcdDomain a) =>
Infinite a
a005153 = a
1 a -> Infinite a -> Infinite a
forall a. a -> Infinite a -> Infinite a
:< (a -> Bool) -> Infinite a -> Infinite a
forall a. (a -> Bool) -> Infinite a -> Infinite a
Infinite.filter a -> Bool
forall {a}.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
a -> Bool
isPractical' ((a
2, a
4) ....)

-- | Determine whether a given number is practical, i.e., a member of 'a005153'.
isPractical :: (Integral a, UniqueFactorisation a, GcdDomain a) => a -> Bool
isPractical :: forall a.
(Integral a, UniqueFactorisation a, GcdDomain a) =>
a -> Bool
isPractical a
0 = [Char] -> Bool
forall a. HasCallStack => [Char] -> a
error [Char]
"n must be positive!"
isPractical a
1 = Bool
True
isPractical a
n = a -> Bool
forall a. Integral a => a -> Bool
even a
n Bool -> Bool -> Bool
&& a -> Bool
forall {a}.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
a -> Bool
isPractical' a
n

isPractical' :: (UniqueFactorisation a, Integral a, GcdDomain a) => a -> Bool
isPractical' :: forall {a}.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
a -> Bool
isPractical' a
n = ((a, Word) -> Bool) -> [(a, Word)] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a -> Bool
good (a -> Bool) -> ((a, Word) -> a) -> (a, Word) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, Word) -> a
forall a b. (a, b) -> a
fst) [(a, Word)]
factors
  where
    factors :: [(a, Word)]
factors = (Prime a -> a) -> (Prime a, Word) -> (a, Word)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Prime a -> a
forall a. Prime a -> a
unPrime ((Prime a, Word) -> (a, Word)) -> [(Prime a, Word)] -> [(a, Word)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [(Prime a, Word)]
forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
factorise a
n
    good :: a -> Bool
good a
p =
      (a
p <=) (a -> Bool) -> (a -> a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
1 +) (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> a -> a
forall n a.
(UniqueFactorisation n, Integral n, Num a, GcdDomain a) =>
Word -> n -> a
sigma Word
1 (a -> Bool) -> a -> Bool
forall a b. (a -> b) -> a -> b
$
        ((a, Word) -> a) -> [(a, Word)] -> a
forall b a. Num b => (a -> b) -> [a] -> b
productOn' ((a -> Word -> a) -> (a, Word) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> Word -> a
forall a b. (Num a, Integral b) => a -> b -> a
(^)) ([(a, Word)] -> a) -> [(a, Word)] -> a
forall a b. (a -> b) -> a -> b
$
          ((a, Word) -> Bool) -> [(a, Word)] -> [(a, Word)]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile ((a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
p) (a -> Bool) -> ((a, Word) -> a) -> (a, Word) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, Word) -> a
forall a b. (a, b) -> a
fst) [(a, Word)]
factors

-- | \(a(n) = \sum_{k=0}^{\lfloor \frac{n}{4} \rfloor} \binom{n-2k}{2k}\), i.e.,
-- [A005252](https://oeis.org/A005252).
a005252 :: (Integral a) => Infinite a
a005252 :: forall a. Integral a => Infinite a
a005252 = (Int -> a) -> Infinite Int -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map Int -> a
forall {a}. Integral a => Int -> a
go (Int
0 ...)
  where
    go :: Int -> a
go Int
n = Int -> a
forall a. Num a => Int -> a
fibonacci (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2 a -> a -> a
forall a. Num a => a -> a -> a
+ a -> a -> Bool -> a
forall a. a -> a -> Bool -> a
bool a
0 a
1 (Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
6 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2)

-- | Pascal's triangle read by rows: \(\binom{n}{k}\) for \(0 \le k \le n\),
-- i.e., [A007318](https://oeis.org/A007318).
a007318 :: (Integral a, Semiring a) => Infinite a
a007318 :: forall a. (Integral a, Semiring a) => Infinite a
a007318 = (Word -> NonEmpty a) -> Infinite Word -> Infinite a
forall a b. (a -> NonEmpty b) -> Infinite a -> Infinite b
Infinite.concatMap ([a] -> NonEmpty a
forall a. HasCallStack => [a] -> NonEmpty a
NE.fromList ([a] -> NonEmpty a) -> (Word -> [a]) -> Word -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Infinite [a]
forall a. Semiring a => Infinite [a]
binomial Infinite.!!)) (Word
0 ...)

-- | Largest squarefree number diving \(n\): the square free kernel of \(n\),
-- \(\text{rad}(n)\), radical of \(n\), i.e., [A007947](https://oeis.org/A007947).
a007947 :: (UniqueFactorisation a) => a -> a
a007947 :: forall n. UniqueFactorisation n => n -> n
a007947 = NonEmpty a -> a
forall a. Num a => NonEmpty a -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product (NonEmpty a -> a) -> (a -> NonEmpty a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> NonEmpty a
forall a. UniqueFactorisation a => a -> NonEmpty a
distinctPrimeFactors

-- | The [distinct prime factors](https://mathworld.wolfram.com/DistinctPrimeFactors.html)
-- of a given number.
--
-- >>> distinctPrimeFactors 504
-- 2 :| [3,7]
--
-- See also 'a007947' and 'a027748'.
distinctPrimeFactors :: (UniqueFactorisation a) => a -> NonEmpty a
distinctPrimeFactors :: forall a. UniqueFactorisation a => a -> NonEmpty a
distinctPrimeFactors = ((Prime a, Word) -> a) -> NonEmpty (Prime a, Word) -> NonEmpty a
forall a b. (a -> b) -> NonEmpty a -> NonEmpty b
NE.map (Prime a -> a
forall a. Prime a -> a
unPrime (Prime a -> a)
-> ((Prime a, Word) -> Prime a) -> (Prime a, Word) -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Prime a, Word) -> Prime a
forall a b. (a, b) -> a
fst) (NonEmpty (Prime a, Word) -> NonEmpty a)
-> (a -> NonEmpty (Prime a, Word)) -> a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Prime a, Word)] -> NonEmpty (Prime a, Word)
forall a. HasCallStack => [a] -> NonEmpty a
NE.fromList ([(Prime a, Word)] -> NonEmpty (Prime a, Word))
-> (a -> [(Prime a, Word)]) -> a -> NonEmpty (Prime a, Word)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> [(Prime a, Word)]
forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
factorise

a007953, digitSum :: (Integral a) => a -> a
a007953 :: forall a. Integral a => a -> a
a007953 a
n
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
10 = a
n
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
100 = a -> a
forall a. Integral a => a -> a
a076314 a
n
  | Bool
otherwise = (a -> a) -> (a, a) -> (a, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first a -> a
forall a. Integral a => a -> a
a007953 ((a, a) -> (a, a)) -> ((a, a) -> a) -> (a, a) -> a
forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
>>> (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Num a => a -> a -> a
(+) ((a, a) -> a) -> (a, a) -> a
forall a b. (a -> b) -> a -> b
$ a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
divMod a
n a
10
-- ^ Digital sum of \(n\), i.e., [A007953](https://oeis.org/A007953).
digitSum :: forall a. Integral a => a -> a
digitSum = a -> a
forall a. Integral a => a -> a
a007953
-- ^ See 'a007953'.

-- | Number of (positive) squarefree numbers \(< n\), i.e.,
-- [A013928](https://oeis.org/A013928).
a013928 :: (Integral a, UniqueFactorisation a) => Infinite a
a013928 :: forall a. (Integral a, UniqueFactorisation a) => Infinite a
a013928 = a
0 a -> Infinite a -> Infinite a
forall a. a -> Infinite a -> Infinite a
:< (a -> a -> a) -> Infinite a -> Infinite a -> Infinite a
forall a b c.
(a -> b -> c) -> Infinite a -> Infinite b -> Infinite c
Infinite.zipWith (-) (a
1 ...) Infinite a
forall a. (Integral a, UniqueFactorisation a) => Infinite a
a057627

-- | -- ^ Even Fibonacci numbers; or \(F_{3n}\); i.e.,
-- [A014445](https://oeis.org/A014445).
a014445 :: Infinite Integer
a014445 :: Infinite Integer
a014445 = Integer
0 Integer -> Infinite Integer -> Infinite Integer
forall a. a -> Infinite a -> Infinite a
:< Integer
2 Integer -> Infinite Integer -> Infinite Integer
forall a. a -> Infinite a -> Infinite a
:< ((Integer, Integer) -> (Integer, (Integer, Integer)))
-> (Integer, Integer) -> Infinite Integer
forall b a. (b -> (a, b)) -> b -> Infinite a
Infinite.unfoldr (Integer, Integer) -> (Integer, (Integer, Integer))
forall {b}. Num b => (b, b) -> (b, (b, b))
go (Integer
0, Integer
2)
  where
    go :: (b, b) -> (b, (b, b))
go (b
x, b
y) = let z :: b
z = b
4 b -> b -> b
forall a. Num a => a -> a -> a
* b
y b -> b -> b
forall a. Num a => a -> a -> a
+ b
x in (b
z, (b
y, b
z))

-- | \(a(n) = -1 + \Phi(n)\), i.e., [A015614](https://oeis.org/A015614).
--
-- See also 'a002088'.
a015614 :: (Integral a, UniqueFactorisation a) => Infinite a
a015614 :: forall a. (Integral a, UniqueFactorisation a) => Infinite a
a015614 = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map (a -> a -> a
forall a. Num a => a -> a -> a
subtract a
1) (Infinite a -> Infinite a
forall a. Infinite a -> Infinite a
Infinite.tail Infinite a
forall a. (Integral a, UniqueFactorisation a) => Infinite a
a002088)

-- | \(\binom{n}{2}\), i.e., [A161680](https://oeis.org/A161680).
a161680 :: (Integral a) => a -> a
a161680 :: forall a. Integral a => a -> a
a161680 a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
* (a
n a -> a -> a
forall a. Num a => a -> a -> a
- a
1) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2

-- | Irregular triangle in which first row is \(1\), \(n\)-th row \((n > 1)\)
-- lists distinct prime factors of \(n\), i.e.
-- [A027748](https://oeis.org/A027748).
--
-- See 'distinctPrimeFactors'.
a027748 :: (Enum a, UniqueFactorisation a) => Infinite a
a027748 :: forall a. (Enum a, UniqueFactorisation a) => Infinite a
a027748 = a
1 a -> Infinite a -> Infinite a
forall a. a -> Infinite a -> Infinite a
:< (a -> NonEmpty a) -> Infinite a -> Infinite a
forall a b. (a -> NonEmpty b) -> Infinite a -> Infinite b
Infinite.concatMap a -> NonEmpty a
forall a. UniqueFactorisation a => a -> NonEmpty a
distinctPrimeFactors (a
2 ...)

-- | Numbers that are sums of consecutive squares, i.e.
-- [A034705](https://oeis.org/A034705).
--
-- See also 'a000290' and 'squares'.
a034705 :: Infinite Int
a034705 :: Infinite Int
a034705 = ((Int, Infinite (NonEmpty Int), IntSet)
 -> (Int, (Int, Infinite (NonEmpty Int), IntSet)))
-> (Int, Infinite (NonEmpty Int), IntSet) -> Infinite Int
forall b a. (b -> (a, b)) -> b -> Infinite a
Infinite.unfoldr (Int, Infinite (NonEmpty Int), IntSet)
-> (Int, (Int, Infinite (NonEmpty Int), IntSet))
go (Int
0, Infinite (NonEmpty Int) -> Infinite (NonEmpty Int)
forall a. Infinite a -> Infinite a
Infinite.tail (Infinite Int -> Infinite (NonEmpty Int)
forall a. Infinite a -> Infinite (NonEmpty a)
Infinite.inits1 Infinite Int
forall a. (Enum a, Num a) => Infinite a
a000290), [Int] -> IntSet
IS.fromList [Int
0])
  where
    go :: (Int, Infinite (NonEmpty Int), IntSet)
-> (Int, (Int, Infinite (NonEmpty Int), IntSet))
go (Int
x, NonEmpty Int
vs :< Infinite (NonEmpty Int)
vss, IntSet
seen)
      | Int
minSeen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
x = (Int
minSeen, (Int
x, NonEmpty Int
vs NonEmpty Int -> Infinite (NonEmpty Int) -> Infinite (NonEmpty Int)
forall a. a -> Infinite a -> Infinite a
:< Infinite (NonEmpty Int)
vss, IntSet
seen'))
      | Bool
otherwise = (Int, Infinite (NonEmpty Int), IntSet)
-> (Int, (Int, Infinite (NonEmpty Int), IntSet))
go (Int
w, Infinite (NonEmpty Int)
vss, IntSet -> IntSet -> IntSet
IS.union IntSet
seen ([Int] -> IntSet
IS.fromList ((Int -> Int -> Int) -> Int -> [Int] -> [Int]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Int
w [Int]
ws)))
      where
        (Int
w :| [Int]
ws) = NonEmpty Int -> NonEmpty Int
forall a. NonEmpty a -> NonEmpty a
NE.reverse NonEmpty Int
vs
        (Int
minSeen, IntSet
seen') = IntSet -> (Int, IntSet)
IS.deleteFindMin IntSet
seen

-- | The sum of two (not necessarily distinct) abundant numbers, i.e.,
-- [A048260](https://oeis.org/A048260).
--
-- See also 'a005101'.
a048260 :: (UniqueFactorisation a, Integral a, GcdDomain a) => Infinite a
a048260 :: forall a.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
Infinite a
a048260 =
  NonEmpty a -> Infinite a
forall a. NonEmpty a -> Infinite a
Infinite.cycle (NonEmpty a -> Infinite a) -> NonEmpty a -> Infinite a
forall a b. (a -> b) -> a -> b
$
    [a] -> NonEmpty a
forall a. HasCallStack => [a] -> NonEmpty a
NE.fromList ([a] -> NonEmpty a) -> [a] -> NonEmpty a
forall a b. (a -> b) -> a -> b
$
      [a] -> [a]
forall a. (Ord a, Num a) => [a] -> [a]
pairwiseSums ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$
        Infinite a -> [a]
forall a. Infinite a -> [a]
Infinite.toList Infinite a
forall a.
(UniqueFactorisation a, Integral a, GcdDomain a) =>
Infinite a
a005101

pairwiseSums :: (Ord a, Num a) => [a] -> [a]
pairwiseSums :: forall a. (Ord a, Num a) => [a] -> [a]
pairwiseSums [a]
xs =
  [a] -> [a]
forall a. Ord a => [a] -> [a]
Ordered.nub ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$
    [[a]] -> [a]
forall a. Ord a => [[a]] -> [a]
Ordered.mergeAll ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$
      [(a -> a) -> [a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a -> a -> a
forall a. Num a => a -> a -> a
+ a
x) ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x) [a]
xs) | a
x <- [a]
xs]

-- | \(a(n) = \sum_{k=1}^n \phi(2k)\), i.e.,
-- [A049690](https://oeis.org/A049690).
--
-- See also 'a000010' and 'a002088'.
a049690 :: (Integral a, UniqueFactorisation a) => Infinite a
a049690 :: forall a. (Integral a, UniqueFactorisation a) => Infinite a
a049690 = (a -> a -> a) -> a -> Infinite a -> Infinite a
forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
Infinite.scanl a -> a -> a
forall a. Num a => a -> a -> a
(+) a
0 (Infinite a -> Infinite a
forall a. Infinite a -> Infinite a
everyOther (Infinite a -> Infinite a
forall a. Infinite a -> Infinite a
Infinite.tail Infinite a
forall a. (Integral a, UniqueFactorisation a) => Infinite a
a000010))

-- | Smallest number whose sum of digits is \(n\), i.e.
-- [A051885](https://oeis.org/A051885).
--
-- See also 'a007953' and 'digitSum'.
a051885 :: (Integral a) => a -> a
a051885 :: forall a. Integral a => a -> a
a051885 = (a -> a -> (a, a)) -> a -> a -> (a, a)
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
divMod a
9 (a -> (a, a)) -> ((a, a) -> a) -> a -> a
forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
>>> ((a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) (a -> a) -> (a -> a) -> (a, a) -> (a, a)
forall b c b' c'. (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** (a
10 ^) ((a, a) -> (a, a)) -> ((a, a) -> a) -> (a, a) -> a
forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
>>> (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Num a => a -> a -> a
(*) ((a, a) -> a) -> (a -> a) -> (a, a) -> a
forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
>>> a -> a -> a
forall a. Num a => a -> a -> a
subtract a
1)

-- | Number of divisors of \(n\) that are smaller than \(\sqrt{n}\), i.e.
-- [A056924](https://oeis.org/A056924).
--
-- \(a056924(n) = N(4n)\) from [Project Euler Problem 174: Hollow Square
-- Laminae II](https://projecteuler.net/problem=174).
a056924 :: (Integral a, UniqueFactorisation a) => a -> a
a056924 :: forall a. (Integral a, UniqueFactorisation a) => a -> a
a056924 = (a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2) (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall n a. (UniqueFactorisation n, Num a) => n -> a
tau

-- | Number of nonsquarefree numbers not exceeding \(n\), i.e.,
-- [A057627](https://oeis.org/A057627).
a057627 :: (Integral a, UniqueFactorisation a) => Infinite a
a057627 :: forall a. (Integral a, UniqueFactorisation a) => Infinite a
a057627 = (a -> a) -> Infinite a -> Infinite a
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map a -> a
forall {a}. (UniqueFactorisation a, Integral a) => a -> a
go (a
1 ...)
  where
    go :: a -> a
go a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
- (a -> a) -> [a] -> a
forall b a. Num b => (a -> b) -> [a] -> b
sumOn' (\a
k -> Moebius -> a
forall a. Num a => Moebius -> a
runMoebius (a -> Moebius
forall n. UniqueFactorisation n => n -> Moebius
moebius a
k) a -> a -> a
forall a. Num a => a -> a -> a
* (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`div` (a
k a -> a -> a
forall a. Num a => a -> a -> a
* a
k))) [a
1 .. forall a b. (RealFrac a, Integral b) => a -> b
floor @Double (Double -> Double
forall a. Floating a => a -> a
sqrt (a -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
n))]

-- | \(a060735(1) = 1\), \(a060735(2) = 2\); thereafter, \(a060735(n)\) is the
-- smallest number \(m\) not yet in the sequence such that every prime that
-- divides \(a(n-1)\) also divides \(m\), i.e.
-- [A060735](https://oeis.org/A060735).
--
-- See 'a007947'.
a060735 :: (UniqueFactorisation a) => Infinite a
a060735 :: forall a. UniqueFactorisation a => Infinite a
a060735 = (a -> a) -> a -> Infinite a
forall a. (a -> a) -> a -> Infinite a
Infinite.iterate (a -> a -> a
forall a. Num a => a -> a -> a
(+) (a -> a -> a) -> (a -> a) -> a -> a
forall (m :: * -> *) a b. Monad m => m (a -> b) -> m a -> m b
`ap` a -> a
forall n. UniqueFactorisation n => n -> n
a007947) a
2

-- | Numbers of the form \(x(x+1)y(y+1)\) ("bipronics") with \(x\) and \(y\)
-- nonnegative integers, i.e., [A072389](https://oeis.org/A072389).
--
-- See 'a002378'.
a072389 :: (Integral a) => Infinite a
a072389 :: forall a. Integral a => Infinite a
a072389 =
  Infinite a -> Infinite a
forall a. Eq a => Infinite a -> Infinite a
Infinite.nub (Infinite a -> Infinite a)
-> ([[a]] -> Infinite a) -> [[a]] -> Infinite a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> Infinite a
forall a. NonEmpty a -> Infinite a
Infinite.cycle (NonEmpty a -> Infinite a)
-> ([[a]] -> NonEmpty a) -> [[a]] -> Infinite a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
0 :|) ([a] -> NonEmpty a) -> ([[a]] -> [a]) -> [[a]] -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
4 :) ([a] -> [a]) -> ([[a]] -> [a]) -> [[a]] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[a]] -> [a]
forall a. Ord a => [[a]] -> [a]
Ordered.mergeAll ([[a]] -> Infinite a) -> [[a]] -> Infinite a
forall a b. (a -> b) -> a -> b
$
    [ [a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
y | a
x <- a -> a
forall a. Integral a => a -> a
a002378 (a -> a) -> [a] -> [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a
1 ..]]
      | a
y <- a -> a
forall a. Integral a => a -> a
a002378 (a -> a) -> [a] -> [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a
2 ..]
    ]

-- | \(a076314(n) = \lfloor \frac{n}{10} \rfloor + (n \bmod 10)\), i.e.
-- [A0076314](https://oeis.org/A0076314).
a076314 :: (Integral a) => a -> a
a076314 :: forall a. Integral a => a -> a
a076314 = (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Num a => a -> a -> a
(+) ((a, a) -> a) -> (a -> (a, a)) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> (a, a)) -> a -> a -> (a, a)
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
divMod a
10

-- | Numbers of the form \(p^{q}q^{p}\), with distinct primes \(p\) and \(q\),
-- i.e., [A082949](https://oeis.org/A082949).
a082949 :: Infinite HybridInteger
a082949 :: Infinite HybridInteger
a082949 = (Set HybridInteger -> (HybridInteger, Set HybridInteger))
-> Set HybridInteger -> Infinite HybridInteger
forall b a. (b -> (a, b)) -> b -> Infinite a
Infinite.unfoldr Set HybridInteger -> (HybridInteger, Set HybridInteger)
go (HybridInteger -> Set HybridInteger
forall a. a -> Set a
singleton (Prime Integer -> Prime Integer -> HybridInteger
HybridInteger (Integer -> Prime Integer
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
nextPrime Integer
2) (Integer -> Prime Integer
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
nextPrime Integer
3)))
  where
    go :: Set HybridInteger -> (HybridInteger, Set HybridInteger)
go Set HybridInteger
seen
      | Prime Integer
p' Prime Integer -> Prime Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Prime Integer
q = (HybridInteger
hi, HybridInteger -> Set HybridInteger -> Set HybridInteger
forall a. Ord a => a -> Set a -> Set a
insert (Prime Integer -> Prime Integer -> HybridInteger
HybridInteger Prime Integer
p' Prime Integer
q) Set HybridInteger
seen')
      | Bool
otherwise = (HybridInteger
hi, Set HybridInteger
seen')
      where
        seen' :: Set HybridInteger
seen' = HybridInteger -> Set HybridInteger -> Set HybridInteger
forall a. Ord a => a -> Set a -> Set a
insert (Prime Integer -> Prime Integer -> HybridInteger
HybridInteger Prime Integer
p Prime Integer
q') Set HybridInteger
rest
        p' :: Prime Integer
p' = Prime Integer -> Prime Integer
forall a. Enum a => a -> a
succ Prime Integer
p
        q' :: Prime Integer
q' = Prime Integer -> Prime Integer
forall a. Enum a => a -> a
succ Prime Integer
q
        (hi :: HybridInteger
hi@(HybridInteger Prime Integer
p Prime Integer
q), Set HybridInteger
rest) = Set HybridInteger -> (HybridInteger, Set HybridInteger)
forall a. Set a -> (a, Set a)
deleteFindMin Set HybridInteger
seen

-- | Numbers \(k\) such that \(3k^2 + 3k + 1\) is prime, i.e.
-- [A111251](https://oeis.org/A111251).
a111251 :: Infinite Integer
a111251 :: Infinite Integer
a111251 =
  (Integer -> Bool) -> Infinite Integer -> Infinite Integer
forall a. (a -> Bool) -> Infinite a -> Infinite a
Infinite.filter Integer -> Bool
isPrime (Infinite Integer -> Infinite Integer)
-> Infinite Integer -> Infinite Integer
forall a b. (a -> b) -> a -> b
$
    (Integer -> Integer) -> Infinite Integer -> Infinite Integer
forall a b. (a -> b) -> Infinite a -> Infinite b
Infinite.map (\Integer
k -> Integer
3 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
k Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
k Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
3 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
k Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1) (Integer
1 ...)

-- | The number of base-10 [bouncy numbers](https://projecteuler.net/problem=113)
-- below \(10^{n}\), i.e., [A204692](https://oeis.org/A204692).
a204692 :: (Integral a) => a -> a
a204692 :: forall a. Integral a => a -> a
a204692 a
n
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
3 = a
0
  | Bool
otherwise = a
10 a -> a -> a
forall a b. (Num a, Integral b) => a -> b -> a
^ a
n a -> a -> a
forall a. Num a => a -> a -> a
- (a -> a -> a
forall a. Integral a => a -> a -> a
choose (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
10) a
10 a -> a -> a
forall a. Num a => a -> a -> a
+ a -> a -> a
forall a. Integral a => a -> a -> a
choose (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
9) a
9 a -> a -> a
forall a. Num a => a -> a -> a
- a
1 a -> a -> a
forall a. Num a => a -> a -> a
- a
10 a -> a -> a
forall a. Num a => a -> a -> a
* a
n)

-- | Number of integer pairs \((x,y,)\) such that \(0 < x < y \leq n\) and
-- \(xy \leq n\), i.e., [A211264](https://oeis.org/A211264).
a211264 :: (Integral a) => a -> a
a211264 :: forall a. Integral a => a -> a
a211264 a
n = [a] -> a
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [a
n a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
k | a
k <- [a
1 .. a
m]] a -> a -> a
forall a. Num a => a -> a -> a
- a
m a -> a -> a
forall a. Num a => a -> a -> a
* (a
m a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2
  where
    m :: a
m = forall a b. (RealFrac a, Integral b) => a -> b
floor @Double (Double -> Double
forall a. Floating a => a -> a
sqrt (a -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
n))

-- -------------------------------------------------------- [ Helper functions ]

-- | [De Polignac's
-- Formula](https://proofwiki.org/wiki/De_Polignac%27s_Formula), i.e.,
-- the \(p\)-adic valuation of \(n!\).
dePolignac :: (Integral a) => a -> a -> a
dePolignac :: forall a. Integral a => a -> a -> a
dePolignac a
p = a -> a -> a
go a
0
  where
    go :: a -> a -> a
go !a
z a
0 = a
z
    go !a
z a
x = a -> a -> a
go (a
z a -> a -> a
forall a. Num a => a -> a -> a
+ a
x a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
p) (a
x a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
p)

everyOther :: Infinite a -> Infinite a
everyOther :: forall a. Infinite a -> Infinite a
everyOther (a
x :< a
_ :< Infinite a
xs) = a
x a -> Infinite a -> Infinite a
forall a. a -> Infinite a -> Infinite a
:< Infinite a -> Infinite a
forall a. Infinite a -> Infinite a
everyOther Infinite a
xs

-- | The multiplicative order of \(n \pmod m\), i.e., the smallest postive
-- integer \(k\) such that \(n^k \equiv 1 \pmod m\).
--
-- This function assumes and does not check that m > 1 and n and m are coprime.
orderMod' :: (Integral a) => a -> a -> a
orderMod' :: forall a. Integral a => a -> a -> a
orderMod' a
n a
m = a -> a -> a
forall {t}. Num t => t -> a -> t
go a
1 (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
m)
  where
    go :: t -> a -> t
go !t
k a
1 = t
k
    go !t
k a
r = t -> a -> t
go (t
k t -> t -> t
forall a. Num a => a -> a -> a
+ t
1) ((a
n a -> a -> a
forall a. Num a => a -> a -> a
* a
r) a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
m)

powerTree :: Natural -> [Natural]
powerTree :: Natural -> [Natural]
powerTree Natural
n
  | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
<= Natural
0 = []
  | Bool
otherwise = NonEmpty (Map Natural [Natural]) -> [Natural]
forall {t :: * -> *} {a}.
Foldable t =>
NonEmpty (Map Natural (t a)) -> [a]
findIn NonEmpty (Map Natural [Natural])
levels
  where
    findIn :: NonEmpty (Map Natural (t a)) -> [a]
findIn (Map Natural (t a)
m :| [Map Natural (t a)]
ms) = [a] -> (t a -> [a]) -> Maybe (t a) -> [a]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (NonEmpty (Map Natural (t a)) -> [a]
findIn ([Map Natural (t a)] -> NonEmpty (Map Natural (t a))
forall a. HasCallStack => [a] -> NonEmpty a
NE.fromList [Map Natural (t a)]
ms)) t a -> [a]
forall a. t a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList (Natural -> Map Natural (t a) -> Maybe (t a)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Natural
n Map Natural (t a)
m)

levels :: NonEmpty (Map Natural [Natural])
levels :: NonEmpty (Map Natural [Natural])
levels = (Map Natural [Natural] -> Map Natural [Natural])
-> Map Natural [Natural] -> NonEmpty (Map Natural [Natural])
forall a. (a -> a) -> a -> NonEmpty a
NE.iterate Map Natural [Natural] -> Map Natural [Natural]
expand (Natural -> [Natural] -> Map Natural [Natural]
forall k a. k -> a -> Map k a
Map.singleton Natural
1 [Natural
1])
  where
    expand :: Map Natural [Natural] -> Map Natural [Natural]
expand = (Map Natural [Natural]
 -> Map Natural [Natural] -> Map Natural [Natural])
-> Map Natural [Natural] -> Map Natural [Natural]
forall (m :: * -> *) a. Monad m => m (m a) -> m a
join ((Natural
 -> [Natural] -> Map Natural [Natural] -> Map Natural [Natural])
-> Map Natural [Natural]
-> Map Natural [Natural]
-> Map Natural [Natural]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey Natural
-> [Natural] -> Map Natural [Natural] -> Map Natural [Natural]
forall {a}. (Ord a, Num a) => a -> [a] -> Map a [a] -> Map a [a]
addLevel)
    addLevel :: a -> [a] -> Map a [a] -> Map a [a]
addLevel a
n [a]
xs Map a [a]
tree = (a -> Map a [a] -> Map a [a]) -> Map a [a] -> [a] -> Map a [a]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (a -> [a] -> a -> Map a [a] -> Map a [a]
forall {a}.
(Ord a, Num a) =>
a -> [a] -> a -> Map a [a] -> Map a [a]
addNext a
n [a]
xs) Map a [a]
tree [a]
xs
    addNext :: a -> [a] -> a -> Map a [a] -> Map a [a]
addNext a
n [a]
xs a
m = a -> [a] -> Map a [a] -> Map a [a]
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
m) (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
m a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs)