27 #ifndef NUMBER_THEORY_H_
28 #define NUMBER_THEORY_H_
51 std::vector<int> result;
53 for (
idx i = 0; i < n; ++i)
55 result.push_back(std::llround(std::floor(x)));
56 x = 1 / (x - std::floor(x));
57 if (!std::isfinite(x) || x > cut)
88 double tmp = 1. / cf[n - 1];
89 for (
idx i = n - 2; i != 0; --i)
91 tmp = 1. / (tmp + cf[i]);
112 double tmp = 1. / cf[cf.size() - 1];
113 for (
idx i = cf.size() - 2; i != 0; --i)
115 tmp = 1. / (tmp + cf[i]);
129 unsigned long long int gcd(
unsigned long long int m,
unsigned long long int n)
131 if (m == 0 && n == 0)
134 if (m == 0 || n == 0)
135 return (std::max(m, n));
137 unsigned long long int result = 1;
155 unsigned long long int gcd(
const std::vector<unsigned long long int>& ns)
160 unsigned long long int result = ns[0];
161 for (
idx i = 1; i < ns.size(); ++i)
163 result =
gcd(result, ns[i]);
177 unsigned long long int lcm(
unsigned long long int m,
unsigned long long int n)
179 if (m == 0 || n == 0)
182 return m * n /
gcd(m, n);
192 unsigned long long int lcm(
const std::vector<unsigned long long int>& ns)
200 if (std::find(std::begin(ns), std::end(ns), 0) != std::end(ns))
203 unsigned long long int prod =
204 std::accumulate(std::begin(ns),
206 static_cast<unsigned long long int>(1),
207 std::multiplies<unsigned long long int>());
209 return prod /
gcd(ns);
218 std::vector<idx>
invperm(
const std::vector<idx>& perm)
224 std::vector<idx> result(perm.size());
225 for (
idx i = 0; i < perm.size(); ++i)
239 std::vector<idx>
compperm(
const std::vector<idx>& perm,
240 const std::vector<idx>& sigma)
246 if (perm.size() != sigma.size())
250 std::vector<idx> result(perm.size());
251 for (
idx i = 0; i < perm.size(); ++i)
252 result[i] = perm[sigma[i]];
265 std::vector<unsigned long long int>
factors(
unsigned long long int n)
267 if (n == 0 || n == 1)
270 std::vector<unsigned long long int> result;
271 unsigned long long int d = 2;
304 if (n == 0 or n == 1)
307 std::vector<unsigned long long int> facts =
factors(n);
309 if (facts.size() == 1)
unsigned long long int lcm(unsigned long long int m, unsigned long long int n)
Least common multiple of two positive integers.
Definition: number_theory.h:177
std::vector< unsigned long long int > factors(unsigned long long int n)
Prime factor decomposition.
Definition: number_theory.h:265
Derived::Scalar prod(const Eigen::MatrixBase< Derived > &A)
Element-wise product of A.
Definition: functions.h:213
bool isprime(unsigned long long int n)
Primality test.
Definition: number_theory.h:302
Quantum++ main namespace.
Definition: codes.h:30
std::vector< idx > compperm(const std::vector< idx > &perm, const std::vector< idx > &sigma)
Compose permutations.
Definition: number_theory.h:239
double contfrac2x(const std::vector< int > &cf, idx n)
Real representation of a simple continued fraction.
Definition: number_theory.h:74
std::vector< idx > invperm(const std::vector< idx > &perm)
Inverse permutation.
Definition: number_theory.h:218
bool _check_perm(const std::vector< idx > &perm)
Definition: util.h:256
Generates custom exceptions, used when validating function parameters.
Definition: exception.h:39
unsigned long long int gcd(unsigned long long int m, unsigned long long int n)
Greatest common divisor of two non-negative integers.
Definition: number_theory.h:129
std::vector< int > x2contfrac(double x, idx n, idx cut=1e5)
Simple continued fraction expansion.
Definition: number_theory.h:45
std::size_t idx
Non-negative integer index.
Definition: types.h:36