Problem Summary

For each integer $n \le N$, define $M(n)$ as the largest residue $a \lt n$ satisfying

$$a^2 \equiv a \pmod{n}.$$

The goal is to compute

$$\sum_{n=1}^{N} M(n)$$

for the large bound $N=10^7$. The key observation is that these residues are exactly the idempotents modulo $n$, and their structure is controlled by the prime-power factorization of $n$.

Mathematical Approach

Step 1: Rewrite the Congruence

The defining condition is equivalent to

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

This form is more informative because the two factors differ by $1$, so

$$\gcd(a,a-1)=1.$$

Therefore every prime power dividing $n$ must divide one of these two coprime factors completely.

Step 2: Prime-Power Blocks Force Local Choices

Write the factorization of $n$ as

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i},$$

where the numbers $q_1,\dots,q_k$ are pairwise coprime prime powers. If $q_i\mid a(a-1)$, then the prime underlying $q_i$ cannot divide both $a$ and $a-1$, so the whole block $q_i$ must divide exactly one of them. Hence for each $i$,

$$a\equiv 0 \pmod{q_i}\qquad\text{or}\qquad a\equiv 1 \pmod{q_i}.$$

Conversely, any residue that is $0$ or $1$ modulo every $q_i$ is automatically idempotent modulo $n$, because locally $0^2=0$ and $1^2=1$, and the Chinese remainder theorem glues the local conditions into one residue modulo $n$.

So idempotents modulo $n$ are in one-to-one correspondence with the $2^k$ ways to choose, for each prime-power block, whether the residue is $0$ or $1$.

Step 3: Encode an Idempotent by a Subset

Choose a subset $U\subseteq\{1,\dots,k\}$. Let

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}.$$

The subset $U$ means: force the residue to be $0$ on the blocks inside $U$, and $1$ on the complementary blocks. That is, solve

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}.$$

Because $u$ and $v$ are coprime, the Chinese remainder theorem gives a unique solution modulo $n$.

Step 4: Closed Form for Each Candidate

Since $a\equiv 0\pmod{u}$, write $a=ut$. The second congruence becomes

$$ut\equiv 1 \pmod{v}.$$

As $\gcd(u,v)=1$, a unique inverse exists modulo $v$. Let $t_U$ be the integer with

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}.$$

Then the idempotent attached to $U$ is

$$a_U = u\,t_U.$$

When $U=\emptyset$, we get $u=1$, $a=1$. When $U=\{1,\dots,k\}$, we get $u=n$, which corresponds to $a=0$. These two trivial idempotents can never beat a nontrivial larger residue, so the maximum only needs nonempty proper subsets. Therefore

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

The case $k=1$ means $n$ is a prime power. Then only $0$ and $1$ are idempotent, so the largest residue below $n$ is $1$.

Step 5: Worked Example

Take $n=12$. Its prime-power blocks are

$$12=4\cdot 3.$$

There are four idempotent patterns:

$$\begin{aligned} (0 \bmod 4,\ 0 \bmod 3) &\Rightarrow a=0,\\ (1 \bmod 4,\ 1 \bmod 3) &\Rightarrow a=1,\\ (0 \bmod 4,\ 1 \bmod 3) &\Rightarrow a=4,\\ (1 \bmod 4,\ 0 \bmod 3) &\Rightarrow a=9. \end{aligned}$$

So the idempotents modulo $12$ are $\{0,1,4,9\}$, and therefore

$$M(12)=9.$$

The same construction for $n=6=2\cdot 3$ gives the nontrivial idempotents $3$ and $4$, hence $M(6)=4$, matching the standard checkpoint for this problem.

How the Code Works

The C++, Python, and Java implementations begin by building a smallest-prime-factor table up to the limit. That lets them factor each $n$ quickly and compress repeated prime factors into the prime-power blocks $q_i$ used in the derivation above.

If an $n$ has only one distinct prime factor, the implementation immediately adds $1$. Otherwise it enumerates every nonempty proper subset of the prime-power blocks. To make that fast, it precomputes the product attached to each subset, so each candidate only needs the subset product $u$, the complementary factor $v=n/u$, one modular inverse of $u$ modulo $v$, and one multiplication to recover $a_U$. The maximum candidate is then added to the global sum. The Java implementation uses the same per-$n$ mathematics inside a parallel outer summation.

Complexity Analysis

Building the smallest-prime-factor table with a linear sieve costs $O(N)$ time and $O(N)$ memory. For a fixed $n$, the factorization step is cheap, and the dominant work is enumerating all subsets of the $k=\omega(n)$ distinct prime factors. That contributes $O(2^k)$ subset products and $O(2^k \log n)$ time if the modular inverse is computed with the extended Euclidean algorithm.

A precise overall bound is therefore

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

time and $O(N)$ memory. For the actual bound $N=10^7$, one has $\omega(n)\le 8$, so no number ever needs more than $2^8-2=254$ nontrivial subset checks. That is why the method is practical even though it explicitly searches all idempotent patterns for each $n$.

Footnotes and References

Problem page: https://projecteuler.net/problem=407
Chinese remainder theorem: Wikipedia — Chinese remainder theorem
Idempotent elements: Wikipedia — Idempotent (ring theory)
Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse
Fundamental theorem of arithmetic: Wikipedia — Fundamental theorem of arithmetic

Problemzusammenfassung

Für jede ganze Zahl $n \le N$ sei $M(n)$ der größte Rest $a \lt n$ mit

$$a^2 \equiv a \pmod{n}.$$

Gesucht ist also

$$\sum_{n=1}^{N} M(n)$$

für die große Schranke $N=10^7$. Der entscheidende Punkt ist, dass diese Reste genau die idempotenten Elemente modulo $n$ sind und sich vollständig aus der Primzahlpotenzzerlegung von $n$ beschreiben lassen.

Mathematischer Ansatz

Schritt 1: Die Kongruenz umformen

Die Bedingung ist äquivalent zu

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

Diese Form ist nützlich, weil die beiden Faktoren aufeinanderfolgende Zahlen sind und daher

$$\gcd(a,a-1)=1$$

gilt. Somit muss jede Primzahlpotenz, die $n$ teilt, vollständig einen der beiden Faktoren teilen.

Schritt 2: Primzahlpotenz-Blöcke erzwingen lokale Entscheidungen

Schreibe

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i},$$

wobei die Zahlen $q_1,\dots,q_k$ paarweise teilerfremde Primzahlpotenzen sind. Aus $q_i\mid a(a-1)$ und der Teilerfremdheit von $a$ und $a-1$ folgt, dass der ganze Block $q_i$ genau einen der beiden Faktoren teilen muss. Also gilt für jedes $i$:

$$a\equiv 0 \pmod{q_i}\qquad\text{oder}\qquad a\equiv 1 \pmod{q_i}.$$

Umgekehrt ist jeder Rest, der modulo jedem $q_i$ entweder $0$ oder $1$ ist, automatisch idempotent modulo $n$. Lokal gilt nämlich $0^2=0$ und $1^2=1$, und der chinesische Restsatz setzt die lokalen Bedingungen zu genau einem Rest modulo $n$ zusammen.

Damit entsprechen die idempotenten Elemente modulo $n$ genau den $2^k$ Möglichkeiten, für jeden Primzahlpotenz-Block zwischen $0$ und $1$ zu wählen.

Schritt 3: Ein Idempotent durch eine Teilmenge kodieren

Wähle eine Teilmenge $U\subseteq\{1,\dots,k\}$ und setze

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}.$$

Die Bedeutung von $U$ ist: auf den Blöcken aus $U$ soll der Rest $0$ sein, auf den komplementären Blöcken $1$. Also lösen wir

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}.$$

Da $u$ und $v$ teilerfremd sind, liefert der chinesische Restsatz genau eine Lösung modulo $n$.

Schritt 4: Geschlossene Form für jeden Kandidaten

Aus $a\equiv 0\pmod{u}$ folgt $a=ut$. Die zweite Kongruenz wird damit zu

$$ut\equiv 1 \pmod{v}.$$

Wegen $\gcd(u,v)=1$ existiert modulo $v$ ein eindeutiges Inverses. Sei $t_U$ die Zahl mit

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}.$$

Dann ist das zu $U$ gehörige idempotente Element

$$a_U = u\,t_U.$$

Für $U=\emptyset$ erhält man $a=1$, für $U=\{1,\dots,k\}$ erhält man $a=0$. Diese beiden trivialen Fälle müssen für das Maximum nicht eigens betrachtet werden. Also gilt

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

Der Fall $k=1$ bedeutet, dass $n$ selbst eine Primzahlpotenz ist. Dann gibt es nur die idempotenten Reste $0$ und $1$, also ist $M(n)=1$.

Schritt 5: Durchgerechnetes Beispiel

Nehmen wir $n=12$. Die Primzahlpotenz-Blöcke sind

$$12=4\cdot 3.$$

Es gibt vier mögliche Muster:

Die idempotenten Reste modulo $12$ sind also $\{0,1,4,9\}$, daher

$$M(12)=9.$$

Für den bekannten Kontrollwert $n=6=2\cdot 3$ erhält man auf dieselbe Weise die nichttrivialen Reste $3$ und $4$, also $M(6)=4$.

Wie der Code arbeitet

Die C++-, Python- und Java-Implementierungen bauen zunächst eine Tabelle der kleinsten Primfaktoren bis zur Schranke auf. Damit lässt sich jedes $n$ schnell faktorisieren, und gleiche Primfaktoren werden sofort zu den Primzahlpotenz-Blöcken $q_i$ zusammengefasst, die in der Herleitung auftreten.

Hat ein $n$ nur einen einzigen verschiedenen Primfaktor, wird direkt $1$ addiert. Andernfalls werden alle nichtleeren echten Teilmengen der Primzahlpotenz-Blöcke durchlaufen. Um das effizient zu machen, wird das Produkt jeder Teilmenge vorab aufgebaut. Dann braucht jeder Kandidat nur noch das Teilmengenprodukt $u$, den Komplementfaktor $v=n/u$, ein modulares Inverses von $u$ modulo $v$ und eine Multiplikation zur Rekonstruktion von $a_U$. Das größte gefundene $a_U$ wird zur Gesamtsumme addiert. Die Java-Implementierung verwendet dieselbe Mathematik in einer parallelen äußeren Summation.

Komplexitätsanalyse

Der Aufbau der Tabelle der kleinsten Primfaktoren mit einem linearen Sieb kostet $O(N)$ Zeit und $O(N)$ Speicher. Für ein festes $n$ ist die Faktorisierung dann billig; der dominante Teil ist die Enumeration aller Teilmengen der $k=\omega(n)$ verschiedenen Primfaktoren. Das ergibt $O(2^k)$ Teilmengenprodukte und mit erweitertem Euklid für das Inverse insgesamt $O(2^k\log n)$ Zeit.

Damit erhält man als präzise Gesamtschranke

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

Zeit und $O(N)$ Speicher. Für die tatsächliche Schranke $N=10^7$ gilt $\omega(n)\le 8$; daher müssen für kein einzelnes $n$ mehr als $2^8-2=254$ nichttriviale Teilmengen geprüft werden. Genau deshalb ist das Verfahren praktisch schnell.

Fußnoten und Quellen

Problemseite: https://projecteuler.net/problem=407
Chinesischer Restsatz: Wikipedia — Chinesischer Restsatz
Idempotenz: Wikipedia — Idempotenz
Modulares Inverses: Wikipedia — Multiplikativ inverses Element
Fundamentalsatz der Arithmetik: Wikipedia — Fundamentalsatz der Arithmetik

Problem Özeti

Her $n \le N$ tam sayısı için $M(n)$,

$$a^2 \equiv a \pmod{n}$$

koşulunu sağlayan ve $a \lt n$ olan en büyük kalandır. Hesaplanmak istenen toplam

$$\sum_{n=1}^{N} M(n)$$

ifadesidir ve gerçek sınır $N=10^7$ olduğu için doğrudan deneme uygun değildir. Çözümün ana fikri, bu kalıntıların mod $n$ altında idempotent elemanlar olması ve yapılarının $n$'nin asal-kuvvet çarpanlarıyla tamamen belirlenmesidir.

Matematiksel Yaklaşım

Adım 1: Kongruansı yeniden yaz

Verilen koşul şu biçime çevrilir:

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

Bu yazım önemlidir, çünkü $a$ ile $a-1$ ardışık sayılardır ve dolayısıyla

$$\gcd(a,a-1)=1.$$

Böylece $n$'yi bölen her asal kuvvet, bu iki çarpandan birini bütünüyle bölmek zorundadır.

Adım 2: Asal-kuvvet blokları yerel seçimleri zorlar

$n$'yi

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i}$$

şeklinde yazalım. Burada $q_1,\dots,q_k$ birbirleriyle aralarında asal asal-kuvvet bloklarıdır. $q_i\mid a(a-1)$ olduğunda, alttaki asal hem $a$'yı hem $a-1$'i bölemeyeceği için tüm $q_i$ bloğu tam olarak bu iki sayıdan birini bölmelidir. Sonuç olarak her $i$ için

$$a\equiv 0 \pmod{q_i}\qquad\text{veya}\qquad a\equiv 1 \pmod{q_i}$$

olmalıdır. Tersi de doğrudur: her blokta kalan $0$ ya da $1$ ise, yerel olarak $0^2=0$ ve $1^2=1$ olduğundan, Çin kalan teoremi bunları mod $n$ altında tek bir idempotent kalana birleştirir.

Bu nedenle mod $n$ altındaki idempotentler, her asal-kuvvet bloğu için $0$ veya $1$ seçmeye karşılık gelen toplam $2^k$ örüntüden oluşur.

Adım 3: Bir altküme ile idempotent tanımla

$U\subseteq\{1,\dots,k\}$ biçiminde bir altküme seçelim ve

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}$$

tanımlarını yapalım. $U$ içindeki bloklarda kalan $0$, dışındakilerde $1$ olsun istiyoruz. Bu da

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}$$

denklem sistemini verir. $u$ ile $v$ aralarında asal olduğu için Çin kalan teoremi mod $n$ altında tek bir çözüm verir.

Adım 4: Her aday için kapalı form

$a\equiv 0\pmod{u}$ olduğundan $a=ut$ yazabiliriz. İkinci kongruans

$$ut\equiv 1 \pmod{v}$$

haline gelir. $\gcd(u,v)=1$ olduğundan mod $v$ altında tek bir ters vardır. $t_U$,

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}$$

şartını sağlayan sayı olsun. O zaman $U$'ya karşılık gelen idempotent

$$a_U = u\,t_U$$

olur. $U=\emptyset$ seçilirse $a=1$, tüm blokların seçildiği durumda ise $a=0$ elde edilir. Bunlar trivyal çözümler olduğundan maksimumu ararken yalnızca boş olmayan gerçek altkümeler gerekir. Dolayısıyla

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

$k=1$ durumu, $n$'nin tek bir asal kuvvet olması demektir. Bu durumda yalnızca $0$ ve $1$ idempotenttir; dolayısıyla $M(n)=1$.

Adım 5: Çözümlü örnek

$n=12$ alalım. Asal-kuvvet blokları

$$12=4\cdot 3$$

şeklindedir. Olası dört örüntü şöyledir:

Böylece mod $12$ altındaki idempotentler $\{0,1,4,9\}$ olur ve

$$M(12)=9.$$

Aynı fikir $n=6=2\cdot 3$ için uygulandığında nontrivial adaylar $3$ ve $4$ çıkar; dolayısıyla $M(6)=4$ elde edilir.

Kodun Çalışma Mantığı

C++, Python ve Java implementasyonları önce üst sınıra kadar en küçük asal bölen tablosu kurar. Böylece her $n$ hızlı biçimde çarpanlarına ayrılır ve tekrar eden asal çarpanlar bir araya getirilerek yukarıdaki türetmede kullanılan asal-kuvvet blokları elde edilir.

Bir $n$'nin yalnızca tek bir farklı asalı varsa doğrudan $1$ eklenir. Aksi halde tüm boş olmayan gerçek altkümeler gezilir. Her altkümenin çarpımı önceden oluşturulduğu için her aday için sadece altküme çarpımı $u$, tamamlayıcı çarpan $v=n/u$, $u$'nun mod $v$ altında tersi ve son bir çarpma gerekir. Bulunan en büyük $a_U$ toplam cevaba eklenir. Java implementasyonu aynı kişi-başı mantığı paralel bir dış toplam içinde uygular.

Karmaşıklık Analizi

En küçük asal bölen tablosunun lineer elekle kurulması $O(N)$ zaman ve $O(N)$ bellek gerektirir. Sabit bir $n$ için çarpanlara ayırma ucuzdur; asıl maliyet $k=\omega(n)$ farklı asal faktörün bütün altkümelerini gezmektir. Bu kısım $O(2^k)$ altküme çarpımı ve modüler ters genişletilmiş Öklid ile alındığında $O(2^k\log n)$ zaman ister.

Dolayısıyla toplam çalışma süresi

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

ve bellek kullanımı $O(N)$ olur. Gerçek sınır $N=10^7$ için $\omega(n)\le 8$ olduğundan hiçbir sayı için $2^8-2=254$ adetten fazla nontrivial altküme denenmez; yöntemin pratikte hızlı olmasının nedeni budur.

Dipnotlar ve Kaynakça

Problem sayfası: https://projecteuler.net/problem=407
Çin kalan teoremi: Wikipedia — Çin kalan teoremi
İdempotent: Wikipedia — İdempotent
Modüler çarpmaya göre ters: Wikipedia — Çarpmaya göre ters eleman
Aritmetiğin temel teoremi: Wikipedia — Aritmetiğin temel teoremi

Resumen del Problema

Para cada entero $n \le N$, $M(n)$ es el mayor residuo $a \lt n$ que cumple

$$a^2 \equiv a \pmod{n}.$$

La tarea consiste en calcular

$$\sum_{n=1}^{N} M(n)$$

para el límite grande $N=10^7$. La observación central es que esos residuos son exactamente los idempotentes módulo $n$, y su estructura queda determinada por la factorización de $n$ en potencias primas.

Enfoque Matemático

Paso 1: Reescribir la congruencia

La condición se transforma en

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

Esta forma es útil porque $a$ y $a-1$ son consecutivos, así que

$$\gcd(a,a-1)=1.$$

Por tanto, cada potencia prima que divide a $n$ debe dividir por completo a uno de esos dos factores.

Paso 2: Los bloques de potencias primas imponen elecciones locales

Escribimos

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i},$$

donde $q_1,\dots,q_k$ son potencias primas coprimas entre sí. Si $q_i\mid a(a-1)$, entonces el primo subyacente no puede dividir a la vez a $a$ y a $a-1$, de modo que el bloque completo $q_i$ debe dividir exactamente a uno de ellos. En consecuencia, para cada $i$,

$$a\equiv 0 \pmod{q_i}\qquad\text{o}\qquad a\equiv 1 \pmod{q_i}.$$

La recíproca también vale: si en cada bloque el residuo es $0$ o $1$, entonces localmente $a^2\equiv a$, y el teorema chino del resto reúne esas condiciones locales en un único residuo módulo $n$.

Así, los idempotentes módulo $n$ están en biyección con las $2^k$ formas de elegir $0$ o $1$ para cada bloque de potencia prima.

Paso 3: Codificar un idempotente mediante un subconjunto

Elegimos un subconjunto $U\subseteq\{1,\dots,k\}$ y definimos

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}.$$

La idea es imponer residuo $0$ en los bloques de $U$ y residuo $1$ en los bloques complementarios. Por tanto resolvemos

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}.$$

Como $u$ y $v$ son coprimos, el teorema chino del resto garantiza una solución única módulo $n$.

Paso 4: Fórmula cerrada para cada candidato

De $a\equiv 0\pmod{u}$ se sigue que $a=ut$. La segunda congruencia se convierte en

$$ut\equiv 1 \pmod{v}.$$

Puesto que $\gcd(u,v)=1$, existe un único inverso módulo $v$. Sea $t_U$ el entero tal que

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}.$$

Entonces el idempotente asociado a $U$ es

$$a_U = u\,t_U.$$

Si $U=\emptyset$, aparece $a=1$. Si $U=\{1,\dots,k\}$, aparece $a=0$. Esos son los dos casos triviales, así que el máximo sólo necesita subconjuntos propios no vacíos. En resumen,

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

Cuando $k=1$, $n$ es una sola potencia prima; en ese caso sólo existen los idempotentes $0$ y $1$, por lo que $M(n)=1$.

Paso 5: Ejemplo resuelto

Tomemos $n=12$. Sus bloques de potencia prima son

$$12=4\cdot 3.$$

Los cuatro patrones posibles son

Por tanto, los idempotentes módulo $12$ son $\{0,1,4,9\}$, y así

$$M(12)=9.$$

Aplicando el mismo método a $n=6=2\cdot 3$ se obtienen los idempotentes no triviales $3$ y $4$, luego $M(6)=4$.

Cómo Funciona el Código

Las implementaciones en C++, Python y Java empiezan construyendo una tabla del menor factor primo hasta el límite. Eso permite factorizar cada $n$ con rapidez y agrupar los factores repetidos en los bloques de potencia prima $q_i$ usados en la derivación matemática.

Si un valor $n$ tiene un único factor primo distinto, la implementación suma directamente $1$. En caso contrario, enumera todos los subconjuntos propios no vacíos de esos bloques. Para evitar recomputar productos desde cero, primero se calcula el producto asociado a cada subconjunto. Luego cada candidato sólo requiere el producto $u$, el factor complementario $v=n/u$, un inverso modular de $u$ módulo $v$ y una multiplicación para reconstruir $a_U$. El máximo se añade a la suma global. La implementación en Java aplica exactamente la misma lógica dentro de una suma externa paralela.

Análisis de Complejidad

Construir la tabla del menor factor primo mediante una criba lineal cuesta $O(N)$ tiempo y $O(N)$ memoria. Para un $n$ fijo, la factorización es barata; el trabajo dominante es recorrer todos los subconjuntos de los $k=\omega(n)$ factores primos distintos. Eso produce $O(2^k)$ productos de subconjuntos y $O(2^k\log n)$ tiempo si el inverso modular se obtiene con el algoritmo extendido de Euclides.

Por ello, una cota precisa para toda la ejecución es

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

de tiempo y $O(N)$ de memoria. Para el límite real $N=10^7$, se cumple $\omega(n)\le 8$, así que ningún valor necesita revisar más de $2^8-2=254$ subconjuntos no triviales. Esa es la razón práctica de que el método funcione bien.

Referencias

Página del problema: https://projecteuler.net/problem=407
Teorema chino del resto: Wikipedia — Teorema chino del resto
Idempotencia: Wikipedia — Idempotencia
Inverso multiplicativo modular: Wikipedia — Inverso multiplicativo
Teorema fundamental de la aritmética: Wikipedia — Teorema fundamental de la aritmética

问题概述

对每个整数 $n \le N$，记 $M(n)$ 为满足

$$a^2 \equiv a \pmod{n}$$

且 $a \lt n$ 的最大剩余类代表。题目要求计算

$$\sum_{n=1}^{N} M(n)$$

其中实际范围达到 $N=10^7$。关键观察是：这样的 $a$ 正好是模 $n$ 的幂等元，而幂等元的全部结构都可以由 $n$ 的素数幂分解直接刻画出来。

数学方法

步骤 1：改写同余条件

原条件等价于

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

这种写法很重要，因为 $a$ 与 $a-1$ 是相邻整数，所以

$$\gcd(a,a-1)=1.$$

因此，凡是整除 $n$ 的素数幂，必须完整地落在这两个互素因子中的某一个上。

步骤 2：素数幂块带来局部二选一

把 $n$ 写成

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i},$$

其中 $q_1,\dots,q_k$ 是两两互素的素数幂块。若 $q_i\mid a(a-1)$，由于对应的素数不可能同时整除 $a$ 与 $a-1$，所以整个块 $q_i$ 必须完全整除其中一个。于是对每个 $i$ 都有

$$a\equiv 0 \pmod{q_i}\qquad\text{or}\qquad a\equiv 1 \pmod{q_i}.$$

反过来，如果一个剩余类在每个素数幂块上都是 $0$ 或 $1$，那么它在每个局部模数下都满足 $x^2\equiv x$，再由中国剩余定理拼起来，就得到模 $n$ 的一个幂等元。

因此，模 $n$ 的幂等元与每个素数幂块上选择 $0$ 或 $1$ 的方式一一对应，总数正好是 $2^k$。

步骤 3：用子集编码一个幂等元

取一个子集 $U\subseteq\{1,\dots,k\}$，定义

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}.$$

子集 $U$ 的含义是：属于 $U$ 的块上取剩余 $0$，补集中的块上取剩余 $1$。于是需要解

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}.$$

因为 $u$ 与 $v$ 互素，中国剩余定理保证模 $n$ 下存在唯一解。

步骤 4：每个候选值的显式公式

由 $a\equiv 0\pmod{u}$ 可写 $a=ut$。第二个同余变成

$$ut\equiv 1 \pmod{v}.$$

由于 $\gcd(u,v)=1$，模 $v$ 下的逆元唯一存在。设 $t_U$ 满足

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}.$$

那么与子集 $U$ 对应的幂等元就是

$$a_U = u\,t_U.$$

当 $U=\emptyset$ 时得到 $a=1$；当 $U=\{1,\dots,k\}$ 时得到 $a=0$。这两个是平凡幂等元，真正决定 $M(n)$ 的是所有非空真子集对应的值，因此

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

$k=1$ 表示 $n$ 本身就是一个素数幂，这时只有 $0$ 和 $1$ 两个幂等元，所以 $M(n)=1$。

步骤 5：算例

取 $n=12$。它的素数幂块分解为

$$12=4\cdot 3.$$

四种局部模式分别对应

所以模 $12$ 的幂等元集合是 $\{0,1,4,9\}$，于是

$$M(12)=9.$$

同样地，对 $n=6=2\cdot 3$ 会得到两个非平凡幂等元 $3$ 和 $4$，因此 $M(6)=4$。

代码如何工作

C++、Python 和 Java 实现都先建立到上界为止的最小素因子表。这样每个 $n$ 都能快速分解，并把重复出现的素因子压缩成上面推导中的素数幂块 $q_i$。

如果某个 $n$ 只有一个不同的素因子，实现会直接把 $1$ 加入答案。否则，它会枚举这些素数幂块的所有非空真子集。为了避免反复重算乘积，程序先得到每个子集对应的乘积。随后每个候选值只需要子集乘积 $u$、补因子 $v=n/u$、$u$ 在模 $v$ 下的逆元，以及一次乘法来重建 $a_U$。其中最大者被加入总和。Java 实现只是把同样的逐个 $n$ 逻辑放入了并行的外层求和中。

复杂度分析

用线性筛构造最小素因子表需要 $O(N)$ 时间和 $O(N)$ 空间。对固定的 $n$，分解本身很快；主要成本来自枚举 $k=\omega(n)$ 个不同素因子的全部子集。这部分需要 $O(2^k)$ 个子集乘积，如果用扩展欧几里得算法求逆元，则总计为 $O(2^k\log n)$ 时间。

因此总体时间界可以写成

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

空间复杂度是 $O(N)$。对于实际范围 $N=10^7$，总有 $\omega(n)\le 8$，所以任意一个 $n$ 最多只需检查 $2^8-2=254$ 个非平凡子集，这正是该方法在实践中可行的原因。

参考资料

题目页面：https://projecteuler.net/problem=407
中国剩余定理：Wikipedia — 中国剩余定理
幂等元：Wikipedia — 幂等元
模逆元：Wikipedia — 模反元素
算术基本定理：Wikipedia — 算术基本定理

Краткое описание

Для каждого целого $n \le N$ величина $M(n)$ определяется как наибольший остаток $a \lt n$, удовлетворяющий

$$a^2 \equiv a \pmod{n}.$$

Нужно вычислить сумму

$$\sum_{n=1}^{N} M(n)$$

при большом пределе $N=10^7$. Основная идея состоит в том, что такие остатки являются идемпотентами по модулю $n$, а вся их структура полностью задается разложением $n$ на простые степени.

Математический подход

Шаг 1: Перепишем сравнение

Исходное условие равносильно

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

Такой вид удобен, потому что $a$ и $a-1$ являются соседними числами, а значит

$$\gcd(a,a-1)=1.$$

Следовательно, каждая простая степень, входящая в $n$, должна целиком делить ровно один из этих двух взаимно простых множителей.

Шаг 2: Блоки простых степеней задают локальный выбор

Пусть

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i},$$

где $q_1,\dots,q_k$ попарно взаимно просты. Если $q_i\mid a(a-1)$, то соответствующее простое число не может делить одновременно $a$ и $a-1$, поэтому весь блок $q_i$ обязан делить либо $a$, либо $a-1$. Значит, для каждого $i$

$$a\equiv 0 \pmod{q_i}\qquad\text{or}\qquad a\equiv 1 \pmod{q_i}.$$

Обратное тоже верно: если по каждому модулю $q_i$ остаток равен $0$ или $1$, то локально выполняется $x^2\equiv x$, а китайская теорема об остатках склеивает эти локальные условия в единственный остаток по модулю $n$.

Итак, идемпотенты по модулю $n$ находятся во взаимно однозначном соответствии с $2^k$ способами выбрать $0$ или $1$ для каждого блока простой степени.

Шаг 3: Кодирование идемпотента подмножеством

Выберем подмножество $U\subseteq\{1,\dots,k\}$ и положим

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}.$$

Смысл выбора $U$: на блоках из $U$ остаток должен быть $0$, а на дополняющих блоках $1$. Поэтому нужно решить систему

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}.$$

Поскольку $u$ и $v$ взаимно просты, китайская теорема об остатках дает единственное решение по модулю $n$.

Шаг 4: Явная формула для кандидата

Из $a\equiv 0\pmod{u}$ следует представление $a=ut$. Второе сравнение становится

$$ut\equiv 1 \pmod{v}.$$

Так как $\gcd(u,v)=1$, у числа $u$ есть единственный обратный элемент по модулю $v$. Обозначим через $t_U$ число, для которого

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}.$$

Тогда соответствующий идемпотент равен

$$a_U = u\,t_U.$$

При $U=\emptyset$ получаем $a=1$, а при $U=\{1,\dots,k\}$ получаем $a=0$. Это два тривиальных случая, поэтому максимум ищется только по непустым собственным подмножествам. Итак,

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

Случай $k=1$ означает, что $n$ само является степенью одного простого. Тогда существуют только идемпотенты $0$ и $1$, поэтому $M(n)=1$.

Шаг 5: Разобранный пример

Возьмем $n=12$. Его блоки простых степеней таковы:

$$12=4\cdot 3.$$

Четыре возможных локальных шаблона дают

Следовательно, идемпотенты по модулю $12$ равны $\{0,1,4,9\}$, и потому

$$M(12)=9.$$

Для $n=6=2\cdot 3$ тот же прием дает нетривиальные идемпотенты $3$ и $4$, так что $M(6)=4$.

Как работает код

Реализации на C++, Python и Java сначала строят таблицу наименьших простых делителей до заданного предела. Это позволяет быстро факторизовать каждое $n$ и объединять одинаковые простые множители в блоки простых степеней $q_i$, которые используются в математическом выводе.

Если у числа $n$ только один различный простой делитель, реализация сразу добавляет $1$. Иначе перебираются все непустые собственные подмножества блоков. Чтобы не перемножать одни и те же значения заново, заранее строится произведение для каждого подмножества. После этого для каждого кандидата нужны только произведение $u$, дополнительный множитель $v=n/u$, обратный элемент к $u$ по модулю $v$ и одна финальная операция умножения для получения $a_U$. Максимум прибавляется к общему ответу. В реализации на Java та же логика для каждого $n$ помещена внутрь параллельного внешнего суммирования.

Анализ сложности

Построение таблицы наименьших простых делителей линейным решетом требует $O(N)$ времени и $O(N)$ памяти. Для фиксированного $n$ факторизация дешева; основная стоимость связана с перебором всех подмножеств $k=\omega(n)$ различных простых делителей. Это дает $O(2^k)$ произведений подмножеств и $O(2^k\log n)$ времени, если обратный элемент вычисляется расширенным алгоритмом Евклида.

Тем самым точная общая оценка имеет вид

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

по времени и $O(N)$ по памяти. Для реального предела $N=10^7$ всегда выполняется $\omega(n)\le 8$, поэтому ни для одного числа не нужно проверять больше чем $2^8-2=254$ нетривиальных подмножеств. Именно это делает метод практически быстрым.

Ссылки

Страница задачи: https://projecteuler.net/problem=407
Китайская теорема об остатках: Wikipedia — Китайская теорема об остатках
Идемпотентность: Wikipedia — Идемпотентность
Обратный элемент по модулю: Wikipedia — Обратный элемент
Основная теорема арифметики: Wikipedia — Основная теорема арифметики

ملخص المسألة

لكل عدد صحيح $n \le N$، نعرّف $M(n)$ بأنه أكبر باقي $a \lt n$ يحقق

$$a^2 \equiv a \pmod{n}.$$

والمطلوب هو حساب

$$\sum_{n=1}^{N} M(n)$$

عندما يكون الحد الأعلى الكبير هو $N=10^7$. الفكرة الحاسمة هي أن هذه البواقي هي بالضبط العناصر الإيدمبوتنتية بترديد $n$، وأن بنيتها تُستخرج مباشرة من تحليل $n$ إلى قوى أولية.

المنهج الرياضي

الخطوة 1: إعادة كتابة التطابق

الشرط الأصلي يكافئ

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

هذه الصيغة مفيدة لأن $a$ و $a-1$ عددان متتاليان، وبالتالي

$$\gcd(a,a-1)=1.$$

ومن ثم فإن كل قوة أولية تقسم $n$ يجب أن تقسم أحد العاملين بالكامل.

الخطوة 2: كتل القوى الأولية تفرض اختيارًا محليًا

نكتب

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i},$$

حيث إن $q_1,\dots,q_k$ قوى أولية متباينة ومتباعدة نسبيًا. إذا كان $q_i\mid a(a-1)$، فإن العدد الأولي الكامن في $q_i$ لا يمكن أن يقسم $a$ و $a-1$ معًا، لذلك يجب أن تقسم الكتلة الكاملة $q_i$ أحدهما فقط. لهذا نحصل، لكل $i$، على

$$a\equiv 0 \pmod{q_i}\qquad\text{or}\qquad a\equiv 1 \pmod{q_i}.$$

والعكس صحيح أيضًا: إذا كان الباقي يساوي $0$ أو $1$ في كل كتلة قوة أولية، فإنه يحقق محليًا $x^2\equiv x$، ثم تجمع نظرية البواقي الصينية هذه الشروط المحلية في باقي وحيد بترديد $n$.

إذن العناصر الإيدمبوتنتية بترديد $n$ تقابل تمامًا جميع الطرق وعددها $2^k$ لاختيار $0$ أو $1$ لكل كتلة قوة أولية.

الخطوة 3: ترميز الإيدمبوتنت بمجموعة جزئية

نختار مجموعة جزئية $U\subseteq\{1,\dots,k\}$، ثم نعرّف

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}.$$

ومعنى ذلك أننا نطلب أن يكون الباقي $0$ على الكتل الموجودة داخل $U$، و$1$ على الكتل المتممة. أي إننا نحل النظام

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}.$$

وبما أن $u$ و $v$ أوليان فيما بينهما، فإن نظرية البواقي الصينية تعطي حلًا وحيدًا بترديد $n$.

الخطوة 4: صيغة صريحة لكل مرشح

بما أن $a\equiv 0\pmod{u}$، نكتب $a=ut$. عندئذ يصبح الشرط الثاني

$$ut\equiv 1 \pmod{v}.$$

ولأن $\gcd(u,v)=1$، يوجد معكوس وحيد لـ $u$ بترديد $v$. ولتكن $t_U$ هي القيمة التي تحقق

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}.$$

إذن المرشح الموافق للمجموعة $U$ هو

$$a_U = u\,t_U.$$

إذا كانت $U=\emptyset$ نحصل على $a=1$، وإذا كانت $U=\{1,\dots,k\}$ نحصل على $a=0$. وهذان هما الحلّان التافهان، لذلك فإن القيمة العظمى تُبحث فقط بين المجموعات الجزئية غير الفارغة وغير الكاملة. ومن ثم

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

الحالة $k=1$ تعني أن $n$ نفسه قوة أولية واحدة، وعندها لا توجد إلا البواقي الإيدمبوتنتية $0$ و $1$، وبالتالي $M(n)=1$.

الخطوة 5: مثال محلول

خذ $n=12$. عندئذ تكون كتل القوى الأولية

$$12=4\cdot 3.$$

والأنماط الأربعة الممكنة تعطي

إذن مجموعة الإيدمبوتنتات بترديد $12$ هي $\{0,1,4,9\}$، ومن ثم

$$M(12)=9.$$

وبالطريقة نفسها، عندما $n=6=2\cdot 3$ نحصل على المرشحين غير التافهين $3$ و$4$، لذلك $M(6)=4$.

كيف تعمل الشيفرة

تبدأ تطبيقات C++ وPython وJava ببناء جدول لأصغر عامل أولي حتى الحد الأعلى. وهذا يسمح بتحليل كل $n$ بسرعة، مع تجميع العوامل الأولية المكررة في كتل القوى الأولية $q_i$ المستعملة في الاشتقاق الرياضي.

إذا كان لـ $n$ عامل أولي مميز واحد فقط، تضيف الشيفرة القيمة $1$ مباشرة. وإلا فإنها تستعرض جميع المجموعات الجزئية الحقيقية غير الفارغة لهذه الكتل. ولتسريع العملية، يجري تكوين حاصل الضرب الموافق لكل مجموعة جزئية مسبقًا. بعد ذلك يحتاج كل مرشح فقط إلى حاصل الضرب $u$، والعامل المتمم $v=n/u$، ومعكوس $u$ بترديد $v$، ثم عملية ضرب واحدة لإعادة بناء $a_U$. وتُضاف القيمة العظمى إلى المجموع الكلي. أما تطبيق Java فيستعمل الرياضيات نفسها داخل جمع خارجي متوازٍ.

تحليل التعقيد

بناء جدول أصغر عامل أولي باستخدام غربال خطي يحتاج إلى $O(N)$ زمنًا و$O(N)$ ذاكرة. وبالنسبة إلى $n$ ثابت، فإن التحليل إلى عوامل سريع؛ أما الجزء المسيطر فهو استعراض جميع المجموعات الجزئية لعوامل $n$ الأولية المميزة وعددها $k=\omega(n)$. هذا يعطينا $O(2^k)$ من حواصل الضرب الجزئية، و$O(2^k\log n)$ زمنًا إذا حُسب المعكوس المعياري بخوارزمية إقليدس الموسعة.

لذلك تكون الحدود الكلية الدقيقة

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

للزمن و$O(N)$ للذاكرة. وعند الحد الفعلي $N=10^7$ يتحقق دائمًا $\omega(n)\le 8$، أي إن أي عدد لا يحتاج إلى فحص أكثر من $2^8-2=254$ مجموعة جزئية غير تافهة. وهذا هو السبب العملي في كفاءة الطريقة.

مراجع

صفحة المسألة: https://projecteuler.net/problem=407
نظرية البواقي الصينية: Wikipedia — نظرية البواقي الصينية
الإيدمبوتنتية: Wikipedia — إدمبوتنت
المعكوس الضربي: Wikipedia — معكوس ضربي
المبرهنة الأساسية في الحساب: Wikipedia — المبرهنة الأساسية في الحساب