Repunit
(math/repunit.hpp)
- View this file on GitHub
- Last update: 2026-07-03 15:39:11+09:00
- Include:
#include "math/repunit.hpp"
Overview
A length-$n$ repunit in base $b$ consists of $n$ copies of the digit one:
\[R_n(b) = 1 + b + b^2 + \cdots + b^{n-1}.\]For example, $R_3(10)=111$ and $R_4(2)=15$. This header also handles repdigits, concatenates base-$b$ digit blocks, evaluates these operations under a runtime modulus, and finds the shortest repunit divisible by an integer.
All evaluation uses binary doubling and avoids division by $b-1$. It therefore
works with composite moduli and when base - 1 has no inverse.
Generic Functions
template <class T>
constexpr std::pair<T, T> repunit_and_power(
std::uint64_t length,
T base = T(10));
template <class T>
constexpr T repunit(std::uint64_t length, T base = T(10));
template <class T>
constexpr T repdigit(
std::uint64_t length,
T digit,
T base = T(10));
template <class T>
constexpr T concatenate_digits(
T left,
T right,
std::uint64_t right_length,
T base = T(10));
T must be constructible from 0, 1, and, when the default base is used,
10. It must provide associative and distributive addition and multiplication.
repdigit additionally expects multiplication to commute.
| Function | Description | Complexity |
|---|---|---|
repunit_and_power<T>(length, base) |
Returns {R_length(base), base^length}. |
$O(\log \mathtt{length})$ time, $O(1)$ memory |
repunit<T>(length, base) |
Returns $R_{\mathtt{length}}(\mathtt{base})$. | $O(\log \mathtt{length})$ time, $O(1)$ memory |
repdigit<T>(length, digit, base) |
Returns the length-length numeral whose every digit is digit. |
$O(\log \mathtt{length})$ time, $O(1)$ memory |
concatenate_digits(left, right, right_length, base) |
Appends the right_length-digit block right to left. |
$O(\log \mathtt{right_length})$ time, $O(1)$ memory |
A zero-length repunit or repdigit is zero. Concatenating a zero-length right
block returns left + right, so right should normally be zero in that case.
For a built-in integer type, every intermediate result must fit; use the
runtime-modulus functions, a modular integer, or a big integer otherwise.
Runtime-Modulus Functions
std::pair<std::uint64_t, std::uint64_t> repunit_and_power_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod);
std::uint64_t repunit_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod);
std::uint64_t repdigit_mod(
std::uint64_t length,
std::uint64_t digit,
std::uint64_t base,
std::uint64_t mod);
std::uint64_t concatenate_digits_mod(
std::uint64_t left,
std::uint64_t right,
std::uint64_t right_length,
std::uint64_t base,
std::uint64_t mod);
mod must be positive. These functions use 128-bit intermediate products, so
all unsigned 64-bit arguments are supported without overflow. Each function
runs in logarithmic time in the relevant block length and uses constant memory.
repunit_and_power_mod returns {R_length(base) mod mod, base^length mod mod}.
Divisible Repunit
std::optional<std::uint64_t> minimum_repunit_length(
std::uint64_t divisor,
std::uint64_t base = 10);
Returns the smallest positive length for which
repunit_mod(length, base, divisor) == 0. divisor must be positive and
base must be at least two. A solution exists exactly when base and
divisor are coprime; otherwise the function returns nullopt.
The function iterates remainders and takes $O(\mathtt{divisor})$ time in the worst case and $O(1)$ memory.
Example
#include "math/repunit.hpp"
#include <iostream>
int main() {
std::cout << m1une::math::repunit<unsigned long long>(6) << '\n';
std::cout << m1une::math::repdigit<unsigned long long>(3, 7) << '\n';
std::cout << m1une::math::concatenate_digits(12ULL, 34ULL, 2) << '\n';
std::uint64_t reduced = m1une::math::repunit_mod(
1000000000000000000ULL,
10,
1000
);
std::cout << reduced << '\n';
auto length = m1une::math::minimum_repunit_length(7);
if (length) std::cout << *length << '\n'; // 6
}
Required by
Verified with
Code
#ifndef M1UNE_MATH_REPUNIT_HPP
#define M1UNE_MATH_REPUNIT_HPP 1
#include <cassert>
#include <cstdint>
#include <numeric>
#include <optional>
#include <utility>
namespace m1une {
namespace math {
template <class T>
constexpr std::pair<T, T> repunit_and_power(
std::uint64_t length,
T base = T(10)
) {
T result = T(0);
T result_power = T(1);
T block = T(1);
T block_power = base;
while (length > 0) {
if (length & 1) {
result = result * block_power + block;
result_power = result_power * block_power;
}
block = block * block_power + block;
block_power = block_power * block_power;
length >>= 1;
}
return std::make_pair(result, result_power);
}
// Returns 1 + base + ... + base^(length - 1).
// The arithmetic, including any modular reduction, is performed by T.
template <class T>
constexpr T repunit(std::uint64_t length, T base = T(10)) {
return repunit_and_power<T>(length, base).first;
}
template <class T>
constexpr T repdigit(std::uint64_t length, T digit, T base = T(10)) {
return digit * repunit<T>(length, base);
}
template <class T>
constexpr T concatenate_digits(
T left,
T right,
std::uint64_t right_length,
T base = T(10)
) {
return left * repunit_and_power<T>(right_length, base).second + right;
}
namespace repunit_detail {
inline std::uint64_t multiply_mod(
std::uint64_t left,
std::uint64_t right,
std::uint64_t mod
) {
return static_cast<std::uint64_t>(
static_cast<unsigned __int128>(left) * right % mod
);
}
inline std::pair<std::uint64_t, std::uint64_t> repunit_and_power_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod
) {
if (mod == 1) return std::make_pair(0, 0);
std::uint64_t result = 0;
std::uint64_t result_power = 1;
std::uint64_t block = 1;
std::uint64_t block_power = base % mod;
while (length > 0) {
if (length & 1) {
result = (
static_cast<unsigned __int128>(result) * block_power + block
) % mod;
result_power = multiply_mod(result_power, block_power, mod);
}
block = (
static_cast<unsigned __int128>(block) * block_power + block
) % mod;
block_power = multiply_mod(block_power, block_power, mod);
length >>= 1;
}
return std::make_pair(result, result_power);
}
} // namespace repunit_detail
inline std::pair<std::uint64_t, std::uint64_t> repunit_and_power_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod
) {
assert(mod >= 1);
return repunit_detail::repunit_and_power_mod(length, base, mod);
}
inline std::uint64_t repunit_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod
) {
return repunit_and_power_mod(length, base, mod).first;
}
inline std::uint64_t repdigit_mod(
std::uint64_t length,
std::uint64_t digit,
std::uint64_t base,
std::uint64_t mod
) {
assert(mod >= 1);
if (mod == 1) return 0;
return repunit_detail::multiply_mod(
digit % mod,
repunit_mod(length, base, mod),
mod
);
}
inline std::uint64_t concatenate_digits_mod(
std::uint64_t left,
std::uint64_t right,
std::uint64_t right_length,
std::uint64_t base,
std::uint64_t mod
) {
assert(mod >= 1);
if (mod == 1) return 0;
const std::uint64_t power =
repunit_and_power_mod(right_length, base, mod).second;
return (
static_cast<unsigned __int128>(left % mod) * power + right % mod
) % mod;
}
inline std::optional<std::uint64_t> minimum_repunit_length(
std::uint64_t divisor,
std::uint64_t base = 10
) {
assert(divisor >= 1);
assert(base >= 2);
if (std::gcd(divisor, base) != 1) return std::nullopt;
std::uint64_t remainder = 0;
for (std::uint64_t length = 1; length <= divisor; length++) {
remainder = (
static_cast<unsigned __int128>(remainder) * base + 1
) % divisor;
if (remainder == 0) return length;
}
return std::nullopt;
}
} // namespace math
} // namespace m1une
#endif // M1UNE_MATH_REPUNIT_HPP#line 1 "math/repunit.hpp"
#include <cassert>
#include <cstdint>
#include <numeric>
#include <optional>
#include <utility>
namespace m1une {
namespace math {
template <class T>
constexpr std::pair<T, T> repunit_and_power(
std::uint64_t length,
T base = T(10)
) {
T result = T(0);
T result_power = T(1);
T block = T(1);
T block_power = base;
while (length > 0) {
if (length & 1) {
result = result * block_power + block;
result_power = result_power * block_power;
}
block = block * block_power + block;
block_power = block_power * block_power;
length >>= 1;
}
return std::make_pair(result, result_power);
}
// Returns 1 + base + ... + base^(length - 1).
// The arithmetic, including any modular reduction, is performed by T.
template <class T>
constexpr T repunit(std::uint64_t length, T base = T(10)) {
return repunit_and_power<T>(length, base).first;
}
template <class T>
constexpr T repdigit(std::uint64_t length, T digit, T base = T(10)) {
return digit * repunit<T>(length, base);
}
template <class T>
constexpr T concatenate_digits(
T left,
T right,
std::uint64_t right_length,
T base = T(10)
) {
return left * repunit_and_power<T>(right_length, base).second + right;
}
namespace repunit_detail {
inline std::uint64_t multiply_mod(
std::uint64_t left,
std::uint64_t right,
std::uint64_t mod
) {
return static_cast<std::uint64_t>(
static_cast<unsigned __int128>(left) * right % mod
);
}
inline std::pair<std::uint64_t, std::uint64_t> repunit_and_power_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod
) {
if (mod == 1) return std::make_pair(0, 0);
std::uint64_t result = 0;
std::uint64_t result_power = 1;
std::uint64_t block = 1;
std::uint64_t block_power = base % mod;
while (length > 0) {
if (length & 1) {
result = (
static_cast<unsigned __int128>(result) * block_power + block
) % mod;
result_power = multiply_mod(result_power, block_power, mod);
}
block = (
static_cast<unsigned __int128>(block) * block_power + block
) % mod;
block_power = multiply_mod(block_power, block_power, mod);
length >>= 1;
}
return std::make_pair(result, result_power);
}
} // namespace repunit_detail
inline std::pair<std::uint64_t, std::uint64_t> repunit_and_power_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod
) {
assert(mod >= 1);
return repunit_detail::repunit_and_power_mod(length, base, mod);
}
inline std::uint64_t repunit_mod(
std::uint64_t length,
std::uint64_t base,
std::uint64_t mod
) {
return repunit_and_power_mod(length, base, mod).first;
}
inline std::uint64_t repdigit_mod(
std::uint64_t length,
std::uint64_t digit,
std::uint64_t base,
std::uint64_t mod
) {
assert(mod >= 1);
if (mod == 1) return 0;
return repunit_detail::multiply_mod(
digit % mod,
repunit_mod(length, base, mod),
mod
);
}
inline std::uint64_t concatenate_digits_mod(
std::uint64_t left,
std::uint64_t right,
std::uint64_t right_length,
std::uint64_t base,
std::uint64_t mod
) {
assert(mod >= 1);
if (mod == 1) return 0;
const std::uint64_t power =
repunit_and_power_mod(right_length, base, mod).second;
return (
static_cast<unsigned __int128>(left % mod) * power + right % mod
) % mod;
}
inline std::optional<std::uint64_t> minimum_repunit_length(
std::uint64_t divisor,
std::uint64_t base = 10
) {
assert(divisor >= 1);
assert(base >= 2);
if (std::gcd(divisor, base) != 1) return std::nullopt;
std::uint64_t remainder = 0;
for (std::uint64_t length = 1; length <= divisor; length++) {
remainder = (
static_cast<unsigned __int128>(remainder) * base + 1
) % divisor;
if (remainder == 0) return length;
}
return std::nullopt;
}
} // namespace math
} // namespace m1une