For an even deck size \(n\), let \(s(n)\) be the smallest number of perfect riffle shuffles needed to return the deck to its original order. The shuffle used here is the perfect out-shuffle: the deck is cut into two equal halves and the cards are interleaved so that the original top card stays on top.
The task is to compute
$$\sum_{s(n)=60} n.$$
The search space is infinite if treated naively, so the solution turns the shuffle into a modular permutation problem and then filters a finite divisor set.
Number the positions from \(0\) at the top to \(n-1\) at the bottom. Because \(n\) is even, the deck splits into two halves of size \(n/2\), and a perfect out-shuffle interleaves those halves in a rigid, deterministic way.
If a card starts in the top half, at position \(i\) with \(0\le i<n/2\), then after the out-shuffle it moves to position \(2i\).
If a card starts in the bottom half, at position \(i=n/2+j\) with \(0\le j<n/2\), then it moves to position \(2j+1\). Rewriting that in terms of \(i\) gives
$$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$$
Therefore, for every position except the bottom card, the shuffle is described by
$$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2),$$
while the bottom card stays fixed at position \(n-1\). The top card is also fixed, since \(f(0)=0\).
Applying the same permutation \(k\) times multiplies the position index by \(2^k\) modulo \(n-1\):
$$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$$
The deck returns to its original order exactly when every position is restored, so we need
$$2^k i\equiv i\pmod{n-1}$$
for all \(i\). Checking \(i=1\) already forces
$$2^k\equiv 1\pmod{n-1}.$$
Since \(n\) is even, \(n-1\) is odd, so \(\gcd(2,n-1)=1\) and the multiplicative order is defined. Hence
$$\boxed{s(n)=\operatorname{ord}_{n-1}(2).}$$
Set
$$m=n-1.$$
If \(s(n)=60\), then \(\operatorname{ord}_m(2)=60\). By the definition of multiplicative order, that implies
$$2^{60}\equiv 1\pmod m,$$
so \(m\) must divide \(2^{60}-1\):
$$m\mid(2^{60}-1).$$
Therefore every valid deck size has the form \(n=d+1\), where \(d\) is a divisor of \(2^{60}-1\). This is the key reduction: instead of testing all even \(n\), we only test the divisors of one fixed integer.
Dividing \(2^{60}-1\) is only a necessary condition. A divisor \(d\) might satisfy \(2^{60}\equiv 1\pmod d\) but still have order \(1,2,3,4,5,6,10,12,15,20,\) or \(30\).
The prime divisors of \(60\) are \(2\), \(3\), and \(5\). So \(\operatorname{ord}_d(2)=60\) is equivalent to
$$2^{60}\equiv 1\pmod d,$$
$$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d.$$
This prime-divisor test is sufficient because if the true order were a proper divisor \(r\) of \(60\), then \(60/r\) would have at least one prime factor \(p\in\{2,3,5\}\). That would imply \(r\mid 60/p\), and then \(2^{60/p}\equiv 1\pmod d\), contradicting the test.
The implementations include a smaller checkpoint before the order-\(60\) run, so it is useful to see the same method on \(s(n)=8\).
First compute
$$2^8-1=255=3\cdot 5\cdot 17.$$
Its divisors are
$$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255.$$
Now apply the exact-order test. A valid divisor must satisfy \(2^8\equiv 1\pmod d\), but also \(2^4\not\equiv 1\pmod d\) and \(2^2\not\equiv 1\pmod d\).
The divisors that pass are
$$17,\ 51,\ 85,\ 255.$$
Therefore the corresponding deck sizes are
$$18,\ 52,\ 86,\ 256,$$
and their sum is
$$18+52+86+256=412.$$
This is exactly the checkpoint verified by the implementation.
Combining the previous steps, the desired total is
$$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1).}$$
So the entire problem reduces to three finite tasks: factor \(2^{60}-1\), enumerate its divisors, and keep only those divisors for which \(2\) has exact order \(60\).
The C++, Python, and Java implementations all follow the same mathematical pipeline. They first factor \(2^{60}-1\) using fast modular arithmetic, a deterministic primality test suitable for 64-bit integers, and Pollard's rho splitting for composite factors. Once the prime factorization is known, they recursively generate every divisor.
For each divisor, the implementation performs fast modular exponentiation to test the order conditions above. Any divisor that satisfies the exact-order filter contributes \(d+1\) to the running sum. Before computing the target case \(60\), the code also checks the smaller order-\(8\) example whose total is \(412\), providing a direct sanity check that the divisor generation and order filter agree.
The three languages differ only in arithmetic details. The C++ version uses native 128-bit multiplication for safe modular products, Python uses arbitrary-precision integers, and Java uses an overflow-safe modular multiplication routine. The underlying algorithm is otherwise identical.
For this specific problem, the target order \(60\) is fixed, so the total running time is effectively constant. More structurally, the expensive step is factoring \(2^{60}-1\); after that, the algorithm enumerates all divisors and performs a constant number of modular exponentiations for each one.
If \(\tau(2^{60}-1)\) denotes the number of divisors of \(2^{60}-1\), then the filtering phase costs \(O(\tau(2^{60}-1)\log 60)\) modular multiplications after factorization, because each candidate is tested with exponents \(60\), \(30\), \(20\), and \(12\). Memory usage is \(O(\tau(2^{60}-1))\) if the full divisor list is stored, and can be viewed as linear in the number of generated divisors.
Für eine gerade Deckgröße \(n\) sei \(s(n)\) die kleinste Anzahl perfekter Riffle-Shuffles, nach der die Kartenreihenfolge wieder exakt der Ausgangsordnung entspricht. Der hier verwendete Shuffle ist der perfekte Out-Shuffle: Das Deck wird halbiert und dann so verflochten, dass die oberste Karte oben bleibt.
Gesucht ist also
$$\sum_{s(n)=60} n.$$
Direktes Ausprobieren aller geraden \(n\) wäre aussichtslos. Die Lösung übersetzt den Shuffle deshalb in eine modulare Permutation und reduziert die Aufgabe auf endlich viele Teiler eines festen Integers.
Wir nummerieren die Positionen von \(0\) oben bis \(n-1\) unten. Da \(n\) gerade ist, besteht das Deck aus zwei Hälften der Größe \(n/2\), und ein perfekter Out-Shuffle mischt diese Hälften auf vollständig deterministische Weise.
Liegt eine Karte anfangs in der oberen Hälfte an Position \(i\) mit \(0\le i<n/2\), dann landet sie nach dem Shuffle auf Position \(2i\).
Liegt sie in der unteren Hälfte, also an Position \(i=n/2+j\) mit \(0\le j<n/2\), dann wandert sie auf Position \(2j+1\). Umgeschrieben nach \(i\) ist das
$$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$$
Damit gilt für alle Positionen außer der untersten Karte
$$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2),$$
während die unterste Karte an Position \(n-1\) fest bleibt. Die oberste Karte ist ebenfalls fix, da \(f(0)=0\).
Wendet man dieselbe Permutation \(k\)-mal an, wird der Positionsindex modulo \(n-1\) mit \(2^k\) multipliziert:
$$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$$
Das Deck ist genau dann wiederhergestellt, wenn jede Position zurückkehrt. Dafür braucht man
$$2^k i\equiv i\pmod{n-1}$$
für alle \(i\). Bereits \(i=1\) erzwingt
$$2^k\equiv 1\pmod{n-1}.$$
Weil \(n\) gerade ist, ist \(n-1\) ungerade und somit \(\gcd(2,n-1)=1\). Also ist die Ordnung von \(2\) modulo \(n-1\) definiert und es gilt
$$\boxed{s(n)=\operatorname{ord}_{n-1}(2).}$$
Setze
$$m=n-1.$$
Wenn \(s(n)=60\) ist, dann \(\operatorname{ord}_m(2)=60\). Nach Definition der multiplikativen Ordnung folgt daraus
$$2^{60}\equiv 1\pmod m,$$
also muss \(m\) ein Teiler von \(2^{60}-1\) sein:
$$m\mid(2^{60}-1).$$
Jede gültige Deckgröße hat also die Form \(n=d+1\), wobei \(d\) ein Teiler von \(2^{60}-1\) ist. Genau diese Reduktion macht das Problem endlich.
Ein Teiler von \(2^{60}-1\) zu sein, ist nur notwendig, aber noch nicht hinreichend. Es kann sein, dass die Ordnung von \(2\) modulo \(d\) ein echter Teiler von \(60\) ist.
Die Primteiler von \(60\) sind \(2\), \(3\) und \(5\). Daher ist \(\operatorname{ord}_d(2)=60\) äquivalent zu
$$2^{60}\equiv 1\pmod d,$$
$$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d.$$
Warum genügt das? Falls die wahre Ordnung \(r\) ein echter Teiler von \(60\) wäre, hätte \(60/r\) einen Primteiler \(p\in\{2,3,5\}\). Dann würde \(r\mid 60/p\) gelten und damit \(2^{60/p}\equiv 1\pmod d\), im Widerspruch zum Test.
Die Implementierungen prüfen zuerst einen kleineren Kontrollfall, deshalb ist \(s(n)=8\) ein gutes Beispiel.
Zunächst
$$2^8-1=255=3\cdot 5\cdot 17.$$
Die Teiler sind
$$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255.$$
Nun wenden wir den Exakt-Ordnungs-Test an. Ein gültiger Teiler muss \(2^8\equiv 1\pmod d\) erfüllen, aber zugleich \(2^4\not\equiv 1\pmod d\) und \(2^2\not\equiv 1\pmod d\).
Übrig bleiben
$$17,\ 51,\ 85,\ 255.$$
Die zugehörigen Deckgrößen sind also
$$18,\ 52,\ 86,\ 256,$$
und ihre Summe ist
$$18+52+86+256=412.$$
Genau dieser Wert dient im Programm als Kontrollpunkt.
Aus den vorherigen Schritten folgt
$$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1).}$$
Die Aufgabe reduziert sich also auf das Faktorisieren von \(2^{60}-1\), das Erzeugen aller Teiler und das Filtern nach exakter Ordnung \(60\).
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Pipeline. Zuerst wird \(2^{60}-1\) mit schneller modularer Arithmetik, einem deterministischen Primzahltest für 64-Bit-Zahlen und Pollard-Rho-Zerlegung faktorisiert. Aus dieser Primfaktorzerlegung werden anschließend rekursiv alle Teiler erzeugt.
Für jeden Teiler führt die Implementierung schnelle modulare Potenzierung aus, um genau die oben beschriebenen Ordnungstests zu prüfen. Jeder passende Teiler steuert \(d+1\) zur Summe bei. Vor dem Zielwert \(60\) wird außerdem der kleinere Fall mit Ordnung \(8\) überprüft, dessen bekannte Summe \(412\) beträgt; damit wird die Kombination aus Teilererzeugung und Ordnungsfilter direkt validiert.
Die drei Sprachen unterscheiden sich nur in Details der Arithmetik. C++ verwendet native 128-Bit-Multiplikation für sichere modulare Produkte, Python nutzt Ganzzahlen beliebiger Größe, und Java verwendet eine überlaufsichere modulare Multiplikation. Der mathematische Algorithmus ist in allen drei Fassungen identisch.
Für das konkrete Problem ist die Zielordnung \(60\) fest, also ist die gesamte Laufzeit praktisch konstant. Inhaltlich dominiert das Faktorisieren von \(2^{60}-1\); danach werden alle Teiler erzeugt und für jeden Kandidaten nur konstant viele modulare Potenzen berechnet.
Bezeichnet \(\tau(2^{60}-1)\) die Anzahl der Teiler von \(2^{60}-1\), dann kostet die Filterphase nach der Faktorisierung \(O(\tau(2^{60}-1)\log 60)\) modulare Multiplikationen, weil pro Kandidat die Exponenten \(60\), \(30\), \(20\) und \(12\) geprüft werden. Der Speicherbedarf liegt bei \(O(\tau(2^{60}-1))\), wenn die gesamte Teilerliste gespeichert wird.
Çift kart sayısına sahip bir deste için \(s(n)\), desteyi başlangıç düzenine geri döndürmek için gereken en küçük mükemmel riffle shuffle sayısıdır. Bu problemde kullanılan işlem perfect out-shuffle türüdür: deste iki eşit parçaya ayrılır ve kartlar, en üst kart yine en üstte kalacak şekilde iç içe geçirilir.
İstenen büyüklük
$$\sum_{s(n)=60} n$$
toplamıdır. Doğrudan tüm çift \(n\) değerlerini denemek sonsuz bir arama alanı oluşturur; bu yüzden çözüm, shuffle işlemini modüler bir permütasyona çevirip sonlu sayıda bölen üzerinde çalışır.
Pozisyonları en üstten alta doğru \(0,1,\dots,n-1\) diye numaralayalım. \(n\) çift olduğu için deste \(n/2\) kartlık iki yarıya ayrılır ve perfect out-shuffle bu iki yarıyı tamamen belirli bir düzenle örer.
Bir kart başlangıçta üst yarıda, yani \(0\le i<n/2\) konumundaysa, shuffle sonrasında \(2i\) konumuna gider.
Kart alt yarıdaysa, yani \(i=n/2+j\) ve \(0\le j<n/2\) ise, yeni konumu \(2j+1\) olur. Bunu \(i\) cinsinden yazarsak
$$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$$
Dolayısıyla en alttaki kart dışında tüm konumlar için
$$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2)$$
elde edilir. En alttaki kart \(n-1\) konumunda sabit kalır; en üst kart da \(f(0)=0\) olduğundan değişmez.
Aynı permütasyonu \(k\) kez uygularsak, konum indeksi mod \(n-1\) altında \(2^k\) ile çarpılmış olur:
$$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$$
Destenin tamamen eski haline dönmesi için her konumun yerine gelmesi gerekir; yani
$$2^k i\equiv i\pmod{n-1}$$
tüm \(i\) değerleri için sağlanmalıdır. Özellikle \(i=1\) alındığında doğrudan
$$2^k\equiv 1\pmod{n-1}$$
çıkar. \(n\) çift olduğu için \(n-1\) tektir ve \(\gcd(2,n-1)=1\) olur. Bu yüzden
$$\boxed{s(n)=\operatorname{ord}_{n-1}(2)}$$
sonucuna ulaşırız.
Şimdi
$$m=n-1$$
yazalım. Eğer \(s(n)=60\) ise \(\operatorname{ord}_m(2)=60\) demektir. Çarpımsal mertebenin tanımına göre bu
$$2^{60}\equiv 1\pmod m$$
olmasını gerektirir; dolayısıyla \(m\), \(2^{60}-1\)'i bölmelidir:
$$m\mid(2^{60}-1).$$
Böylece her uygun deste boyu \(n=d+1\) biçimindedir; burada \(d\), \(2^{60}-1\)'in bir bölenidir. Sonsuz arama alanı böylece tek bir sabit sayının bölenlerine indirgenmiş olur.
\(d\)'nin \(2^{60}-1\)'i bölmesi sadece gerekli koşuldur. \(2\)'nin mod \(d\) altındaki mertebesi \(60\)'ın uygun bir böleni de olabilir.
\(60\)'ın asal bölenleri \(2\), \(3\) ve \(5\)'tir. Bu nedenle \(\operatorname{ord}_d(2)=60\) olması
$$2^{60}\equiv 1\pmod d,$$
$$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d$$
koşullarına denktir. Bunun yeterli olmasının sebebi şudur: gerçek mertebe \(r\), \(60\)'ın daha küçük bir böleni olsaydı, \(60/r\) sayısının \(\{2,3,5\}\) kümesinden en az bir asal böleni olurdu. O zaman \(r\mid 60/p\) elde edilir ve \(2^{60/p}\equiv 1\pmod d\) çıkardı; bu da testle çelişirdi.
Uygulamalar, asıl \(60\) hedefinden önce daha küçük bir kontrol örneği kullanır; bu yüzden \(s(n)=8\) durumu iyi bir örnektir.
Önce
$$2^8-1=255=3\cdot 5\cdot 17$$
hesaplanır. Bölenler
$$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255$$
şeklindedir. Şimdi tam mertebe filtresini uygularız: geçerli bir bölen için \(2^8\equiv 1\pmod d\) olmalı, fakat aynı zamanda \(2^4\not\equiv 1\pmod d\) ve \(2^2\not\equiv 1\pmod d\) olmalıdır.
Bu testten geçenler
$$17,\ 51,\ 85,\ 255$$
olur. Buna karşılık gelen deste boyları
$$18,\ 52,\ 86,\ 256$$
ve toplamları
$$18+52+86+256=412$$
çıkar. Kodun kontrol değeri tam olarak budur.
Önceki adımları birleştirince istenen büyüklük
$$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1)}$$
şeklinde yazılır. Böylece problem, \(2^{60}-1\)'i çarpanlarına ayırma, tüm bölenleri üretme ve bunlar arasından \(2\)'nin tam mertebesi \(60\) olanları seçme problemine dönüşür.
C++, Python ve Java implementasyonları aynı matematiksel akışı izler. İlk olarak \(2^{60}-1\), hızlı modüler aritmetik, 64 bit tamsayılar için uygun deterministik asal testi ve bileşik sayıları ayırmak için Pollard-Rho yöntemi kullanılarak asal çarpanlarına ayrılır. Ardından bu çarpanlardan tüm bölenler özyinelemeli biçimde üretilir.
Her bölen için implementasyon hızlı modüler üs alma ile yukarıdaki mertebe koşullarını test eder. Tam mertebe filtresini geçen her bölen, toplama \(d+1\) katkısı yapar. Asıl \(60\) çalıştırılmadan önce mertebesi \(8\) olan küçük örneğin toplamı \(412\) olarak doğrulanır; bu da bölen üretimi ile mertebe filtresinin uyumlu çalıştığını gösterir.
Üç dil arasındaki fark yalnızca aritmetik ayrıntılardadır. C++ güvenli modüler çarpım için yerleşik 128 bit çarpımı kullanır, Python keyfi büyüklükte tamsayılarla çalışır, Java ise taşmayı önleyen özel bir modüler çarpım stratejisi kullanır. Temel algoritma aynıdır.
Bu özel problemde hedef mertebe \(60\) sabittir; dolayısıyla toplam çalışma süresi pratikte sabit kabul edilebilir. Yapısal olarak maliyetin en büyük kısmı \(2^{60}-1\)'in çarpanlara ayrılmasıdır. Bunun ardından tüm bölenler listelenir ve her aday için sabit sayıda modüler üs testi yapılır.
\(\tau(2^{60}-1)\), \(2^{60}-1\)'in bölen sayısı olsun. O zaman filtreleme aşaması, çarpanlara ayırmadan sonra \(O(\tau(2^{60}-1)\log 60)\) modüler çarpım gerektirir; çünkü her bölen için üsler \(60\), \(30\), \(20\) ve \(12\) ayrı ayrı sınanır. Tüm bölenler tutulursa bellek kullanımı \(O(\tau(2^{60}-1))\) olur.
Para un mazo de tamaño par \(n\), \(s(n)\) es el número mínimo de riffle shuffles perfectos necesarios para recuperar el orden original. El barajado considerado aquí es el out-shuffle perfecto: el mazo se corta en dos mitades iguales y luego se entrelazan de modo que la carta superior sigue siendo la primera.
Debemos calcular
$$\sum_{s(n)=60} n.$$
Si se prueba cada \(n\) par directamente, la búsqueda es infinita. La solución convierte el barajado en una permutación modular y después solo examina un conjunto finito de divisores.
Numeramos las posiciones desde \(0\) en la parte superior hasta \(n-1\) en la inferior. Como \(n\) es par, el mazo se divide en dos mitades de tamaño \(n/2\), y el out-shuffle perfecto entrelaza esas mitades de forma completamente rígida.
Si una carta comienza en la mitad superior, en la posición \(i\) con \(0\le i<n/2\), después del shuffle pasa a la posición \(2i\).
Si comienza en la mitad inferior, es decir \(i=n/2+j\) con \(0\le j<n/2\), entonces va a la posición \(2j+1\). Reescrito en función de \(i\), eso es
$$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$$
Por tanto, para todas las posiciones salvo la última carta, el efecto del shuffle es
$$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2),$$
mientras que la carta inferior permanece fija en la posición \(n-1\). La carta superior también queda fija porque \(f(0)=0\).
Aplicar la misma permutación \(k\) veces equivale a multiplicar el índice por \(2^k\) módulo \(n-1\):
$$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$$
El mazo vuelve al orden original exactamente cuando todas las posiciones regresan a su lugar, así que necesitamos
$$2^k i\equiv i\pmod{n-1}$$
para todo \(i\). Tomando \(i=1\), ya obtenemos
$$2^k\equiv 1\pmod{n-1}.$$
Como \(n\) es par, \(n-1\) es impar y por tanto \(\gcd(2,n-1)=1\). De ahí se sigue que
$$\boxed{s(n)=\operatorname{ord}_{n-1}(2).}$$
Sea
$$m=n-1.$$
Si \(s(n)=60\), entonces \(\operatorname{ord}_m(2)=60\). Por definición del orden multiplicativo, eso obliga a que
$$2^{60}\equiv 1\pmod m,$$
de modo que \(m\) debe dividir a \(2^{60}-1\):
$$m\mid(2^{60}-1).$$
Así, todo mazo válido tiene la forma \(n=d+1\), donde \(d\) es un divisor de \(2^{60}-1\). La búsqueda infinita queda reducida a los divisores de un único entero fijo.
Ser divisor de \(2^{60}-1\) es solo una condición necesaria. Un divisor \(d\) puede cumplir \(2^{60}\equiv 1\pmod d\) y aun así tener un orden propio menor que \(60\).
Los divisores primos de \(60\) son \(2\), \(3\) y \(5\). Por ello, \(\operatorname{ord}_d(2)=60\) equivale a
$$2^{60}\equiv 1\pmod d,$$
$$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d.$$
Comprobar solo esos tres exponentes menores basta porque, si el orden real fuera un divisor propio \(r\) de \(60\), entonces \(60/r\) tendría al menos un factor primo \(p\in\{2,3,5\}\). En consecuencia \(r\mid 60/p\), y eso forzaría \(2^{60/p}\equiv 1\pmod d\), contradiciendo el filtro.
Las implementaciones incluyen primero una comprobación más pequeña, así que conviene ilustrar el método con \(s(n)=8\).
Calculamos
$$2^8-1=255=3\cdot 5\cdot 17.$$
Sus divisores son
$$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255.$$
Ahora aplicamos el filtro de orden exacto: un divisor válido debe satisfacer \(2^8\equiv 1\pmod d\), pero además \(2^4\not\equiv 1\pmod d\) y \(2^2\not\equiv 1\pmod d\).
Los que pasan son
$$17,\ 51,\ 85,\ 255.$$
Por tanto, los tamaños de mazo correspondientes son
$$18,\ 52,\ 86,\ 256,$$
y su suma vale
$$18+52+86+256=412.$$
Ese es exactamente el valor de comprobación usado por la implementación.
Juntando todo, obtenemos
$$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1).}$$
Así, el problema se convierte en factorizar \(2^{60}-1\), enumerar todos sus divisores y conservar únicamente aquellos para los que \(2\) tiene orden exacto \(60\).
Las implementaciones en C++, Python y Java siguen exactamente la misma idea matemática. Primero factorizan \(2^{60}-1\) mediante aritmética modular rápida, una prueba determinista de primalidad adecuada para enteros de 64 bits y el método rho de Pollard para separar factores compuestos. Una vez obtenida la factorización prima, generan recursivamente todos los divisores.
Para cada divisor, la implementación usa exponenciación modular rápida para comprobar las condiciones de orden anteriores. Todo divisor que supere ese filtro aporta \(d+1\) a la suma acumulada. Antes del cálculo principal con orden \(60\), el código verifica también el caso menor de orden \(8\), cuya suma es \(412\); eso sirve como comprobación directa de que la enumeración de divisores y el filtro de orden son correctos.
Las diferencias entre lenguajes son solo de bajo nivel. La versión en C++ usa multiplicación nativa de 128 bits para productos modulares seguros, Python aprovecha enteros de precisión arbitraria y Java utiliza una multiplicación modular resistente al desbordamiento. El algoritmo matemático es el mismo en los tres casos.
En este problema concreto, el orden objetivo \(60\) es fijo, así que el tiempo total de ejecución es, en la práctica, constante. Desde un punto de vista estructural, la parte dominante es factorizar \(2^{60}-1\); después se enumeran todos los divisores y se hacen solo unas pocas exponenciaciones modulares por candidato.
Si \(\tau(2^{60}-1)\) denota el número de divisores de \(2^{60}-1\), la fase de filtrado cuesta \(O(\tau(2^{60}-1)\log 60)\) multiplicaciones modulares tras la factorización, porque cada candidato se prueba con los exponentes \(60\), \(30\), \(20\) y \(12\). El uso de memoria es \(O(\tau(2^{60}-1))\) si se guarda explícitamente toda la lista de divisores.
对于偶数张牌的牌堆 \(n\)，记 \(s(n)\) 为需要进行多少次完美 riffle shuffle 才会第一次回到原始顺序。这里使用的是完美 out-shuffle：把牌堆平均分成两半，再交错插入，并且最上面的牌仍然保持在最上面。
题目要求计算
$$\sum_{s(n)=60} n.$$
如果直接去枚举所有偶数 \(n\)，搜索空间是无限的。真正可行的做法，是把洗牌过程转写成一个模运算下的置换问题，再把候选范围压缩到某个固定整数的全部因子。
把位置从上到下编号为 \(0,1,\dots,n-1\)。由于 \(n\) 是偶数，牌堆可以分成两个大小同为 \(n/2\) 的半堆，而完美 out-shuffle 会以完全确定的方式把这两半重新交织起来。
如果一张牌原来在上半堆，也就是位置 \(i\) 满足 \(0\le i<n/2\)，那么洗牌后它会到达位置 \(2i\)。
如果它原来在下半堆，即 \(i=n/2+j\) 且 \(0\le j<n/2\)，那么它的新位置是 \(2j+1\)。把这个表达式改写成 \(i\) 的形式：
$$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$$
因此，除了最底下那张牌之外，其余位置都满足
$$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2).$$
最底下的牌固定在位置 \(n-1\)，而最上面的牌也固定，因为 \(f(0)=0\)。这就是整道题最关键的结构：一次洗牌，本质上是在模 \(n-1\) 下把位置乘以 \(2\)。
把同一个置换重复 \(k\) 次后，位置编号就会在模 \(n-1\) 意义下被乘上 \(2^k\)：
$$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$$
牌堆恢复原状，当且仅当所有位置都回到原位，所以我们需要
$$2^k i\equiv i\pmod{n-1}$$
对所有相关位置同时成立。只要看 \(i=1\)，就已经得到必要且充分的条件
$$2^k\equiv 1\pmod{n-1}.$$
由于 \(n\) 为偶数，所以 \(n-1\) 为奇数，从而 \(\gcd(2,n-1)=1\)。因此 \(2\) 在模 \(n-1\) 下的乘法阶存在，于是
$$\boxed{s(n)=\operatorname{ord}_{n-1}(2).}$$
原题就这样被转化成了一个纯数论问题。
记
$$m=n-1.$$
如果 \(s(n)=60\)，那么 \(\operatorname{ord}_m(2)=60\)。按照乘法阶的定义，这会推出
$$2^{60}\equiv 1\pmod m,$$
也就是说 \(m\) 必须整除 \(2^{60}-1\)：
$$m\mid(2^{60}-1).$$
所以所有可能的牌数都可以写成
$$n=d+1,$$
其中 \(d\) 是 \(2^{60}-1\) 的一个因子。因为 \(2^{60}-1\) 是奇数，它的所有因子都是奇数，所以 \(n=d+1\) 会自动是偶数，恰好符合题目对牌数的要求。
仅仅满足 \(d\mid(2^{60}-1)\) 还不够，因为这只说明 \(2^{60}\equiv 1\pmod d\)，却不能排除 \(2\) 的阶其实是 \(60\) 的某个真因子。
\(60\) 的素因子是 \(2\)、\(3\)、\(5\)。因此 \(\operatorname{ord}_d(2)=60\) 当且仅当
$$2^{60}\equiv 1\pmod d,$$
$$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d.$$
为什么只检查这三个更小的指数就够了？如果真实的阶是某个真因子 \(r<60\)，那么 \(r\mid 60\)。此时 \(60/r\) 至少含有一个素因子 \(p\in\{2,3,5\}\)，于是 \(r\mid 60/p\)。这就会导致 \(2^{60/p}\equiv 1\pmod d\)，与上面的排除条件矛盾。所以这组测试恰好筛出“阶正好等于 \(60\)”的因子。
实现中在正式计算 \(60\) 之前，会先验证一个更小的检查点，所以用 \(s(n)=8\) 来演示最直观。
先算
$$2^8-1=255=3\cdot 5\cdot 17.$$
它的全部因子是
$$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255.$$
现在应用“精确阶”过滤条件。一个因子 \(d\) 必须满足 \(2^8\equiv 1\pmod d\)，但同时还要满足 \(2^4\not\equiv 1\pmod d\) 且 \(2^2\not\equiv 1\pmod d\)。
经过筛选，保留下来的因子是
$$17,\ 51,\ 85,\ 255.$$
对应的牌数就是
$$18,\ 52,\ 86,\ 256,$$
它们的和为
$$18+52+86+256=412.$$
这正是实现里使用的校验值，说明“分解因子 + 枚举因子 + 阶过滤”这一整套流程是对的。
把前面的结论合起来，题目要求的总和可以写成
$$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1).}$$
因此这道题最终变成了一个完全有限的问题：先分解 \(2^{60}-1\)，再枚举它的全部因子，最后把那些使 \(2\) 的乘法阶恰好为 \(60\) 的因子各自加上 \(1\) 后求和。
C++、Python 和 Java 三个实现采用的是同一条算法路线。首先，它们利用快速模运算、适用于 64 位整数的确定性素性检测，以及 Pollard rho 分解法，把 \(2^{60}-1\) 分解成素因子。拿到素因子分解之后，再用递归方式生成全部因子。
接着，对每个因子执行快速模幂，检查上面给出的精确阶条件。凡是通过筛选的因子，都把 \(d+1\) 加进总和。正式计算 \(60\) 之前，代码还会先验证阶为 \(8\) 的小例子，其总和是 \(412\)，这样可以直接确认因子生成和阶判定都没有偏差。
三种语言之间的差别只在底层算术细节。C++ 使用原生 128 位乘法来安全地完成模乘，Python 依赖任意精度整数，Java 则用不会溢出的模乘策略。数学算法本身完全一致。
对本题而言，目标阶 \(60\) 是固定常数，因此总运行时间在实践中可以看成常数级。更抽象地说，主要成本来自对 \(2^{60}-1\) 的分解；分解完成后，算法只需枚举它的全部因子，并对每个候选做固定次数的模幂测试。
若用 \(\tau(2^{60}-1)\) 表示 \(2^{60}-1\) 的因子个数，那么在完成分解之后，过滤阶段的代价是 \(O(\tau(2^{60}-1)\log 60)\) 次模乘，因为每个候选都要检查指数 \(60\)、\(30\)、\(20\)、\(12\)。如果把所有因子显式存入列表，空间复杂度就是 \(O(\tau(2^{60}-1))\)。
Для четного числа карт \(n\) обозначим через \(s(n)\) минимальное число идеальных riffle-shuffle, после которого колода впервые возвращается к исходному порядку. В этой задаче используется вариант out-shuffle: колода делится на две равные половины и затем переплетается так, что верхняя карта остается сверху.
Требуется вычислить
$$\sum_{s(n)=60} n.$$
Прямой перебор всех четных \(n\) невозможен по сути, поэтому решение переводит перемешивание в задачу о модульной перестановке и затем рассматривает только конечное множество делителей одного фиксированного числа.
Пронумеруем позиции от \(0\) сверху до \(n-1\) снизу. Так как \(n\) четно, колода распадается на две половины по \(n/2\) карт, а идеальный out-shuffle переплетает их полностью детерминированным образом.
Если карта изначально находится в верхней половине, то есть на позиции \(i\) при \(0\le i<n/2\), после shuffle она попадет на позицию \(2i\).
Если же карта находится в нижней половине, то \(i=n/2+j\) при \(0\le j<n/2\), и новая позиция равна \(2j+1\). В терминах \(i\) это
$$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$$
Следовательно, для всех позиций, кроме самой нижней карты, выполняется
$$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2),$$
а нижняя карта остается на позиции \(n-1\). Верхняя карта тоже фиксирована, потому что \(f(0)=0\).
Если применить ту же перестановку \(k\) раз, индекс позиции умножится на \(2^k\) по модулю \(n-1\):
$$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$$
Колода восстановится тогда и только тогда, когда каждая карта вернется на свое место, то есть нужно
$$2^k i\equiv i\pmod{n-1}$$
для всех \(i\). Уже подстановка \(i=1\) дает необходимое и достаточное условие
$$2^k\equiv 1\pmod{n-1}.$$
Поскольку \(n\) четно, число \(n-1\) нечетно, а значит \(\gcd(2,n-1)=1\). Следовательно, порядок числа \(2\) по модулю \(n-1\) определен, и потому
$$\boxed{s(n)=\operatorname{ord}_{n-1}(2).}$$
Положим
$$m=n-1.$$
Если \(s(n)=60\), то \(\operatorname{ord}_m(2)=60\). По определению мультипликативного порядка это означает
$$2^{60}\equiv 1\pmod m,$$
то есть \(m\) должно делить \(2^{60}-1\):
$$m\mid(2^{60}-1).$$
Итак, любая подходящая длина колоды имеет вид \(n=d+1\), где \(d\) является делителем числа \(2^{60}-1\). Бесконечный перебор сведён к конечному набору делителей.
Само по себе условие \(d\mid(2^{60}-1)\) лишь необходимо. Возможно, что \(2^{60}\equiv 1\pmod d\), но истинный порядок числа \(2\) по модулю \(d\) меньше \(60\).
Простые делители числа \(60\) равны \(2\), \(3\) и \(5\). Поэтому условие \(\operatorname{ord}_d(2)=60\) эквивалентно системе
$$2^{60}\equiv 1\pmod d,$$
$$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d.$$
Этого достаточно, потому что если истинный порядок равен некоторому собственному делителю \(r\) числа \(60\), то число \(60/r\) имеет простой делитель \(p\in\{2,3,5\}\). Тогда \(r\mid 60/p\), а значит \(2^{60/p}\equiv 1\pmod d\), что сразу нарушает фильтр.
В реализациях перед основной задачей используется меньшая проверка, поэтому удобно посмотреть на случай \(s(n)=8\).
Сначала вычисляем
$$2^8-1=255=3\cdot 5\cdot 17.$$
Все делители таковы:
$$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255.$$
Теперь применяем фильтр точного порядка. Подходящий делитель должен удовлетворять \(2^8\equiv 1\pmod d\), но при этом \(2^4\not\equiv 1\pmod d\) и \(2^2\not\equiv 1\pmod d\).
После проверки остаются
$$17,\ 51,\ 85,\ 255.$$
Следовательно, соответствующие размеры колод равны
$$18,\ 52,\ 86,\ 256,$$
а их сумма составляет
$$18+52+86+256=412.$$
Именно это контрольное значение проверяет реализация.
Объединяя все предыдущие шаги, получаем
$$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1).}$$
Тем самым задача сводится к факторизации числа \(2^{60}-1\), перечислению всех его делителей и суммированию \(d+1\) по тем делителям, для которых число \(2\) имеет точный порядок \(60\).
Реализации на C++, Python и Java используют одну и ту же математическую схему. Сначала число \(2^{60}-1\) раскладывается на простые множители при помощи быстрой модульной арифметики, детерминированной проверки простоты, пригодной для 64-битных чисел, и метода Pollard rho для разбиения составных множителей. После этого по простому разложению рекурсивно строятся все делители.
Для каждого делителя выполняется быстрое возведение в степень по модулю, чтобы проверить условия точного порядка. Каждый прошедший фильтр делитель добавляет к ответу величину \(d+1\). Перед расчетом целевого случая с порядком \(60\) программа также проверяет меньший пример с порядком \(8\), где сумма равна \(412\); это служит прямой проверкой корректности генерации делителей и фильтра по порядку.
Различия между языками касаются только низкоуровневой арифметики. В C++ используются встроенные 128-битные произведения, Python опирается на целые произвольной длины, а Java применяет безопасную модульную схему умножения без переполнения. С точки зрения математики все три реализации одинаковы.
Для данной задачи целевой порядок \(60\) фиксирован, поэтому фактическое время работы можно считать константным. Если смотреть на структуру алгоритма, основная стоимость приходится на факторизацию числа \(2^{60}-1\); после этого нужно лишь перебрать все делители и для каждого выполнить постоянное число модульных степеней.
Если \(\tau(2^{60}-1)\) обозначает число делителей числа \(2^{60}-1\), то после факторизации этап фильтрации стоит \(O(\tau(2^{60}-1)\log 60)\) модульных умножений, потому что для каждого кандидата проверяются степени \(60\), \(30\), \(20\) и \(12\). Память составляет \(O(\tau(2^{60}-1))\), если хранить полный список делителей явно.
لعدد أوراق زوجي \(n\)، نرمز بـ \(s(n)\) إلى أقل عدد من خلطات riffle المثالية اللازمة لعودة الرزمة إلى ترتيبها الأصلي. النوع المستخدم هنا هو perfect out-shuffle: نقسم الرزمة إلى نصفين متساويين ثم ندمجهما بالتناوب بحيث تبقى الورقة العليا في الأعلى.
المطلوب هو حساب
$$\sum_{s(n)=60} n.$$
التجريب المباشر لكل قيم \(n\) الزوجية غير عملي، لذلك يحول الحل عملية الخلط إلى تبديل يخضع لحسابات معيارية، ثم يحصر البحث في قواسم عدد ثابت واحد.
نرقم المواضع من \(0\) في الأعلى حتى \(n-1\) في الأسفل. وبما أن \(n\) زوجي، فإن الرزمة تنقسم إلى نصفين من الحجم \(n/2\)، ويقوم perfect out-shuffle بتشابك هذين النصفين بطريقة محددة تمامًا.
إذا كانت الورقة في البداية ضمن النصف العلوي، أي في الموضع \(i\) حيث \(0\le i<n/2\)، فإنها تنتقل بعد الخلط إلى الموضع \(2i\).
أما إذا كانت في النصف السفلي، أي \(i=n/2+j\) مع \(0\le j<n/2\)، فإن موضعها الجديد هو \(2j+1\). وبإعادة كتابة ذلك بدلالة \(i\) نحصل على
$$2j+1=2\left(i-\frac{n}{2}\right)+1=2i-(n-1).$$
إذن، لكل المواضع ما عدا الورقة السفلية، يكون تأثير الخلط هو
$$f(i)\equiv 2i \pmod{n-1}\qquad (0\le i\le n-2).$$
أما الورقة الأخيرة فتظل ثابتة في الموضع \(n-1\)، وكذلك الورقة الأولى لأن \(f(0)=0\).
إذا طبقنا التبديل نفسه \(k\) مرات، فإن فهرس الموضع يُضرب في \(2^k\) بترديد \(n-1\):
$$f^{(k)}(i)\equiv 2^k i \pmod{n-1}\qquad (0\le i\le n-2).$$
تعود الرزمة إلى ترتيبها الأصلي إذا وفقط إذا رجعت كل ورقة إلى مكانها، أي يجب أن يتحقق
$$2^k i\equiv i\pmod{n-1}$$
لكل \(i\). وبمجرد أخذ \(i=1\) نحصل على الشرط الحاسم
$$2^k\equiv 1\pmod{n-1}.$$
ولأن \(n\) زوجي فإن \(n-1\) فردي، وبالتالي \(\gcd(2,n-1)=1\)، فتكون الرتبة الضربية معرفة. ومن ثم
$$\boxed{s(n)=\operatorname{ord}_{n-1}(2).}$$
لنكتب
$$m=n-1.$$
إذا كان \(s(n)=60\)، فهذا يعني أن \(\operatorname{ord}_m(2)=60\). وبتعريف الرتبة الضربية يلزم أن
$$2^{60}\equiv 1\pmod m,$$
ومن ثم يجب أن يقسم \(m\) العدد \(2^{60}-1\):
$$m\mid(2^{60}-1).$$
إذًا كل حجم صالح للرزمة يكون على الصورة \(n=d+1\)، حيث \(d\) قاسم من قواسم \(2^{60}-1\). وبهذا ننتقل من فضاء بحث لا نهائي إلى مجموعة منتهية من القواسم.
كون \(d\) قاسمًا لـ \(2^{60}-1\) شرط لازم فقط، لأنه قد يحدث أن \(2^{60}\equiv 1\pmod d\) بينما تكون الرتبة الحقيقية أصغر من \(60\).
القواسم الأولية للعدد \(60\) هي \(2\) و\(3\) و\(5\). لذلك تكون العلاقة \(\operatorname{ord}_d(2)=60\) مكافئة للشروط
$$2^{60}\equiv 1\pmod d,$$
$$2^{30}\not\equiv 1\pmod d,\qquad 2^{20}\not\equiv 1\pmod d,\qquad 2^{12}\not\equiv 1\pmod d.$$
وهذا كافٍ لأن الرتبة إذا كانت قاسمًا حقيقيًا \(r<60\)، فإن العدد \(60/r\) يملك عاملًا أوليًا واحدًا على الأقل من المجموعة \(\{2,3,5\}\). عندئذٍ يتحقق \(r\mid 60/p\)، وبالتالي \(2^{60/p}\equiv 1\pmod d\)، وهو ما يناقض الاختبار السابق.
تتضمن التطبيقات فحصًا أصغر قبل الحالة الأساسية، لذا من المفيد رؤية الطريقة نفسها عندما يكون \(s(n)=8\).
نحسب أولًا
$$2^8-1=255=3\cdot 5\cdot 17.$$
وقواسم هذا العدد هي
$$1,\ 3,\ 5,\ 15,\ 17,\ 51,\ 85,\ 255.$$
الآن نطبق شرط الرتبة الدقيقة: يجب أن يحقق القاسم \(d\) العلاقة \(2^8\equiv 1\pmod d\)، ولكن مع ذلك يجب أن يبقى \(2^4\not\equiv 1\pmod d\) و\(2^2\not\equiv 1\pmod d\).
القواسم التي تنجح هي
$$17,\ 51,\ 85,\ 255.$$
ومن ثم تكون أحجام الرزم الموافقة
$$18,\ 52,\ 86,\ 256,$$
ومجموعها
$$18+52+86+256=412.$$
وهذه هي قيمة التحقق التي تستخدمها التطبيقات قبل الانتقال إلى الحالة ذات الرتبة \(60\).
بعد جمع النتائج السابقة نحصل على
$$\boxed{\sum_{s(n)=60} n=\sum_{\substack{d\mid(2^{60}-1)\\ \operatorname{ord}_d(2)=60}}(d+1).}$$
أي أن المسألة تختزل إلى تفكيك \(2^{60}-1\)، ثم توليد جميع قواسمه، ثم جمع \(d+1\) لكل قاسم تكون فيه رتبة \(2\) الضربية مساوية تمامًا لـ \(60\).
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. تبدأ أولًا بتفكيك العدد \(2^{60}-1\) إلى عوامله الأولية باستخدام حسابات معيارية سريعة، واختبار أولية حتمي مناسب للأعداد ذات 64 بت، وطريقة Pollard's rho لفصل العوامل المركبة. وبعد الحصول على التحليل الأولي، تُولَّد جميع القواسم بصورة استدعاء ذاتي.
بعد ذلك تُجرى عملية رفع سريع للأسس بترديد كل قاسم من أجل فحص شروط الرتبة الدقيقة المذكورة أعلاه. كل قاسم ينجح في هذا الاختبار يضيف المقدار \(d+1\) إلى المجموع. وقبل حساب الحالة الرئيسية ذات الرتبة \(60\)، تتحقق التطبيقات أيضًا من المثال الأصغر ذي الرتبة \(8\) والذي يعطي المجموع \(412\)، وذلك كاختبار مباشر لصحة توليد القواسم ومرشح الرتبة.
الاختلاف بين اللغات الثلاث يقتصر على تفاصيل الحساب العددي. نسخة C++ تستخدم ضربًا أصليًا بعرض 128 بت، وPython تعتمد على الأعداد الصحيحة ذات الدقة غير المحدودة، بينما تستخدم Java طريقة آمنة للضرب المعياري تمنع الفيض. أما الخوارزمية الرياضية فمتطابقة في الحالات الثلاث.
في هذه المسألة بالذات تكون الرتبة المطلوبة \(60\) ثابتة، ولذلك يمكن اعتبار زمن التنفيذ ثابتًا عمليًا. لكن من حيث البنية، فإن الجزء الأغلى هو تفكيك \(2^{60}-1\). وبعد ذلك لا يبقى سوى تعداد جميع القواسم وإجراء عدد ثابت من اختبارات الأس المعياري لكل مرشح.
إذا رمزنا بعدد قواسم \(2^{60}-1\) بالرمز \(\tau(2^{60}-1)\)، فإن مرحلة التصفية بعد التفكيك تكلف \(O(\tau(2^{60}-1)\log 60)\) من عمليات الضرب المعياري، لأن كل قاسم يُختبر عند الأسس \(60\) و\(30\) و\(20\) و\(12\). واستهلاك الذاكرة هو \(O(\tau(2^{60}-1))\) إذا خُزنت قائمة القواسم كاملة.