Project Euler Problem 407: Idempotents
If we calculate a^2 mod 6 for 0 <= a <= 5 we get: 0, 1, 4, 3, 4, 1. The largest value of a such that a^2 = a (mod 6) is 4. Let M(n) be the largest value of a < n such that a^2 = a (mod n). Find: Su...
Problem Statement
This archive keeps the full statement, math, and original media on the page.
If we calculate \(a^2 \mod 6\) for \(0 \leq a \leq 5\) we get: \(0, 1, 4, 3, 4, 1\).
The largest value of \(a\) such that \(a^2 \equiv a \pmod {6}\) is \(4\).
Let’s call \(M(n)\) the largest value of \(a < n\) such that \(a^2 \equiv a \pmod {n}\).
So \(M(6) = 4\).
Find \(\sum M(n)\) for \(1 \leq n \leq 10^7\).
Project Euler Problem 407: Idempotents
Mathematical Analysis
Idempotent Equation
We need a^2 = a (mod n), i.e., a(a-1) = 0 (mod n). This means n | a(a-1).
Since gcd(a, a-1) = 1, by CRT, if n = p1^e1 * p2^e2 * … * pk^ek, then each prime power factor pi^ei must divide either a or a-1.
Chinese Remainder Theorem Approach
For each prime power p^e dividing n, we have two choices:
- a = 0 (mod p^e), meaning p^e | a
- a = 1 (mod p^e), meaning p^e | (a-1)
This gives 2^k solutions modulo n (where k is the number of distinct prime factors of n), all obtainable via CRT. We want the largest such solution less than n.
Computing M(n)
For each n:
- Factorize n into prime powers.
- For each subset of prime factors, construct a via CRT where a = 0 mod (product of selected prime powers) and a = 1 mod (product of remaining prime powers).
- Take the maximum such a with a < n.
Sieve Optimization
For efficiency, we use a sieve approach:
- Precompute the smallest prime factor for all n up to 10^7.
- For each n, factorize using the SPF sieve.
- Enumerate all 2^k CRT solutions and find the maximum.
Editorial
a. Factorize n using SPF. b. Enumerate 2^k idempotents via CRT. We build a smallest-prime-factor sieve up to 10^7. We then iterate over each n from 1 to 10^7. Finally, sum all M(n).
Pseudocode
Build a smallest-prime-factor sieve up to 10^7
For each n from 1 to 10^7:
Sum all M(n)Complexity Analysis
- Sieve: O(N log log N)
- Factorization: O(log n) per n
- CRT enumeration: O(2^k) per n where k is the number of distinct prime factors. Since 2357111317*19 > 10^7, k <= 8.
- Total: O(N * average 2^k) which is efficient in practice.
Answer
Code
Each problem page includes the exact C++ and Python source files from the local archive.
#include <bits/stdc++.h>
using namespace std;
/*
* Project Euler Problem 407: Idempotents
*
* Find sum of M(n) for n = 1..10^7 where M(n) is the largest a < n
* with a^2 = a (mod n).
*
* a(a-1) = 0 mod n. Since gcd(a,a-1) = 1, for each prime power p^e || n,
* either p^e | a or p^e | (a-1). Enumerate via CRT.
*/
const int MAXN = 10000001;
int spf[MAXN]; // smallest prime factor
long long extgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) { x = 1; y = 0; return a; }
long long x1, y1;
long long g = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
// CRT: find x = r1 mod m1, x = r2 mod m2
// Returns (combined_r, combined_m)
pair<long long, long long> crt(long long r1, long long m1, long long r2, long long m2) {
long long x, y;
long long g = extgcd(m1, m2, x, y);
long long lcm = m1 / g * m2;
long long diff = r2 - r1;
long long r = (r1 + m1 * ((diff / g % (m2 / g) * x) % (m2 / g))) % lcm;
if (r < 0) r += lcm;
return {r, lcm};
}
int main() {
ios_base::sync_with_stdio(false);
// Sieve smallest prime factor
for (int i = 2; i < MAXN; i++) spf[i] = i;
for (int i = 2; (long long)i * i < MAXN; i++) {
if (spf[i] == i) { // i is prime
for (int j = i * i; j < MAXN; j += i) {
if (spf[j] == j) spf[j] = i;
}
}
}
long long total = 0;
for (int n = 2; n < MAXN; n++) {
// Factorize n
vector<int> primes_powers; // prime power factors
int tmp = n;
while (tmp > 1) {
int p = spf[tmp];
int pe = 1;
while (tmp % p == 0) {
tmp /= p;
pe *= p;
}
primes_powers.push_back(pe);
}
int k = primes_powers.size();
long long best = 1;
// Enumerate all 2^k combinations
for (int mask = 0; mask < (1 << k); mask++) {
// For each prime power: if bit is 0, a = 0 mod pe; if bit is 1, a = 1 mod pe
long long r = 0, m = 1;
for (int i = 0; i < k; i++) {
long long ri = (mask >> i) & 1;
long long mi = primes_powers[i];
auto [nr, nm] = crt(r, m, ri, mi);
r = nr;
m = nm;
}
if (r > 0 && r < n) {
best = max(best, r);
}
}
total += best;
}
printf("%lld\n", total);
return 0;
}
"""
Project Euler Problem 407: Idempotents
Find sum of M(n) for n = 1..10^7 where M(n) is the largest a < n
with a^2 = a (mod n).
a(a-1) = 0 mod n. Since gcd(a,a-1)=1, for each prime power p^e || n,
either p^e | a or p^e | (a-1). Enumerate all 2^k solutions via CRT.
"""
def solve():
MAXN = 10_000_001
# Smallest prime factor sieve
spf = list(range(MAXN))
i = 2
while i * i < MAXN:
if spf[i] == i:
for j in range(i * i, MAXN, i):
if spf[j] == j:
spf[j] = i
i += 1
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
def crt(r1, m1, r2, m2):
g, x, _ = extended_gcd(m1, m2)
lcm = m1 // g * m2
diff = r2 - r1
r = (r1 + m1 * ((diff // g * x) % (m2 // g))) % lcm
if r < 0:
r += lcm
return r, lcm
total = 0
for n in range(2, MAXN):
# Factorize
tmp = n
prime_powers = []
while tmp > 1:
p = spf[tmp]
pe = 1
while tmp % p == 0:
tmp //= p
pe *= p
prime_powers.append(pe)
k = len(prime_powers)
best = 1
for mask in range(1 << k):
r, m = 0, 1
for i in range(k):
ri = (mask >> i) & 1
mi = prime_powers[i]
r, m = crt(r, m, ri, mi)
if 0 < r < n:
best = max(best, r)
total += best
print(total)
if __name__ == "__main__":
solve()