Choose \(X\) uniformly from the interval \([0,1]\), and for each positive integer \(N\) define
$$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$$
where \(\{y\}=y-\lfloor y\rfloor\) is the fractional part. The problem asks for the expected smallest fractional part among the first \(N\) multiples of a random \(x\), with the target case \(N=10000\).
A brute-force viewpoint would be hopelessly inefficient: for each \(x\) one would have to compare \(N\) different fractional parts, and doing that over a dense mesh still would not give an exact answer. The implementations avoid sampling entirely and instead partition \([0,1]\) into Farey intervals on which \(f_N(x)\) becomes a simple linear function.
The key observation is that \(\{mx\}=mx-\lfloor mx\rfloor\) measures how far \(mx\) lies above the nearest smaller integer. So minimizing \(\{mx\}\) over \(1\le m\le N\) is equivalent to finding the best rational approximation to \(x\) from below with denominator at most \(N\).
Because \(X\) is uniform on \([0,1]\), the expected value in the title is exactly the integral of \(f_N(x)\). There is no probability machinery beyond that: once we know the graph of \(f_N\), the answer is its area under the curve.
For a fixed denominator \(m\), the quantity \(\{mx\}\) can be written as
$$\{mx\}=mx-p \qquad\text{with}\qquad p=\lfloor mx\rfloor,$$
so every candidate minimum is attached to a rational number \(p/m\le x\). This turns the original question into a geometric one about rationals of bounded denominator.
Let
$$\frac{a}{b} \lt \frac{c}{d}$$
be consecutive terms of the Farey sequence of order \(N\), denoted \(\mathcal{F}_N\). If \(x\) lies in the interval
$$\frac{a}{b}\le x\le \frac{c}{d},$$
then there is no reduced fraction with denominator at most \(N\) strictly between those endpoints. In particular, the best rational from below with denominator at most \(N\) stays fixed throughout the whole interval and is exactly \(a/b\).
That means the minimum fractional part is attained by the denominator \(b\):
$$f_N(x)=bx-a \qquad \text{for } x\in\left[\frac{a}{b},\frac{c}{d}\right].$$
At the left endpoint this value is \(0\), and as \(x\) moves rightward it rises linearly until the next Farey boundary is reached. The graph of \(f_N\) is therefore a chain of line segments, one segment for each adjacent Farey pair.
Adjacent Farey fractions satisfy the unimodular relation
$$bc-ad=1.$$
Consequently, the interval width is
$$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd},$$
and the value of the linear segment at the right endpoint is
$$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}.$$
So each Farey interval contributes the area of a triangle with base \(1/(bd)\) and height \(1/d\):
$$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$$
This is the exact closed form accumulated by the implementations.
Summing over all consecutive pairs in \(\mathcal{F}_N\) gives
$$\boxed{F(N)=\sum_{\substack{a/b \lt c/d\\ \text{consecutive in }\mathcal{F}_N}} \frac{1}{2bd^2}.}$$
Nothing is approximated in the mathematics: the only numerical issue is how to add many small positive terms stably when \(N\) is large.
The Farey sequence of order \(4\) is
$$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1.$$
Therefore \(f_4(x)\) is piecewise linear:
$$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $$
The interval contributions are
$$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8},$$
and they add up to
$$F(4)=\frac14.$$
This matches the checkpoint used by the implementations and shows exactly how the Farey partition turns the expectation into a finite sum of triangle areas.
The C++, Python, and Java implementations all follow the same mathematical plan: enumerate the consecutive Farey fractions of order \(N\), convert each interval into the exact term \(1/(2bd^2)\), and accumulate those terms carefully.
The sweep starts from the first two neighbors, \(0/1\) and \(1/N\). If the current neighboring pair is \(a/b \lt c/d\), the next Farey term is generated by the standard recurrence
$$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$$
After processing the interval \([a/b,c/d]\), the pair advances to \(c/d \lt e/f\). Repeating this step walks through the entire Farey sequence in increasing order without building a table of all fractions in advance.
For each current interval, the implementation adds
$$\frac{1}{2bd^2}$$
to the running total. Since the terms become very small near the end of the sweep, all three versions use compensated summation to reduce the loss of low-order digits. The C++ version keeps the running total in extended precision, while the Python and Java versions use standard floating-point arithmetic with the same compensation idea.
Once the right endpoint reaches \(1/1\), the next Farey update jumps past the unit interval and the traversal stops. The final decimal output is just the numerical form of the exact Farey sum above.
Each neighboring Farey interval is visited exactly once, and each visit performs only constant-time arithmetic. The total running time is therefore linear in the number of intervals in the Farey sequence of order \(N\), which is \(\Theta(N^2)\).
The memory usage is \(O(1)\): the implementation stores only the current neighboring fractions, the running sum, and the compensation term. No large arrays, sieves, or dynamic programming tables are needed.
Wähle \(X\) gleichverteilt aus dem Intervall \([0,1]\) und definiere für jedes positive \(N\)
$$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$$
wobei \(\{y\}=y-\lfloor y\rfloor\) den Nachkommateil bezeichnet. Gesucht ist also der Erwartungswert des kleinsten Nachkommateils unter den ersten \(N\) Vielfachen eines zufälligen \(x\), im Zielproblem für \(N=10000\).
Eine direkte numerische Behandlung wäre unattraktiv: Für jedes \(x\) müsste man \(N\) verschiedene Werte \(\{mx\}\) vergleichen, und selbst ein dichtes Gitter würde die Struktur nicht exakt erfassen. Der entscheidende Schritt ist deshalb, \([0,1]\) in Farey-Intervalle zu zerlegen, auf denen \(f_N(x)\) jeweils linear ist.
Die Größe \(\{mx\}=mx-\lfloor mx\rfloor\) misst, um wie viel \(mx\) die nächstkleinere ganze Zahl übersteigt. Das Minimum über \(1\le m\le N\) ist daher äquivalent zur besten rationalen Approximation von \(x\) von unten mit Nenner höchstens \(N\).
Weil \(X\) auf \([0,1]\) gleichverteilt ist, ist der gesuchte Erwartungswert genau das Integral von \(f_N\). Sobald die Gestalt des Graphen bekannt ist, reduziert sich das Problem auf eine Flächenberechnung.
Für einen festen Nenner \(m\) gilt
$$\{mx\}=mx-p \qquad\text{mit}\qquad p=\lfloor mx\rfloor,$$
also gehört jede mögliche Kandidatenfunktion zu einem Bruch \(p/m\le x\). Das verlagert die Aufgabe von einer punktweisen Suche zu einer geordneten Beschreibung aller relevanten rationalen Zahlen.
Seien
$$\frac{a}{b} \lt \frac{c}{d}$$
zwei aufeinanderfolgende Glieder der Farey-Folge \(\mathcal{F}_N\). Liegt \(x\) im Intervall
$$\frac{a}{b}\le x\le \frac{c}{d},$$
dann gibt es keinen vollständig gekürzten Bruch mit Nenner höchstens \(N\), der strikt zwischen diesen beiden Endpunkten liegt. Damit bleibt die beste Approximation von unten auf dem ganzen Intervall konstant und ist genau \(a/b\).
Folglich wird der kleinste Nachkommateil von dem Nenner \(b\) geliefert:
$$f_N(x)=bx-a \qquad \text{für } x\in\left[\frac{a}{b},\frac{c}{d}\right].$$
Am linken Rand ist dieser Wert \(0\); danach wächst er linear bis zum nächsten Farey-Rand. Der Graph von \(f_N\) ist also eine Kette linearer Abschnitte, je einer pro benachbartem Farey-Paar.
Benachbarte Farey-Brüche erfüllen die unimodulare Relation
$$bc-ad=1.$$
Daraus folgt die Intervallbreite
$$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd},$$
und am rechten Rand hat die lineare Funktion den Wert
$$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}.$$
Jeder Abschnitt liefert also die Fläche eines Dreiecks mit Grundseite \(1/(bd)\) und Höhe \(1/d\):
$$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$$
Genau dieser geschlossene Ausdruck wird in den Implementierungen aufsummiert.
Über alle benachbarten Paare der Farey-Folge ergibt sich damit
$$\boxed{F(N)=\sum_{\substack{a/b \lt c/d\\ \text{benachbart in }\mathcal{F}_N}} \frac{1}{2bd^2}.}$$
Die Mathematik selbst ist exakt; numerisch heikel ist nur die stabile Addition vieler kleiner positiver Summanden für großes \(N\).
Die Farey-Folge der Ordnung \(4\) lautet
$$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1.$$
Daher ist \(f_4(x)\) stückweise linear:
$$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $$
Die sechs Flächenbeiträge sind
$$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8},$$
und ihre Summe ist
$$F(4)=\frac14.$$
Genau diese Zerlegung wird im großen Fall \(N=10000\) nicht durch Probieren, sondern systematisch über die Farey-Nachbarschaft ausgenutzt.
Die C++-, Python- und Java-Implementierungen setzen denselben mathematischen Plan um: Sie durchlaufen die benachbarten Farey-Brüche der Ordnung \(N\), wandeln jedes Intervall in den exakten Term \(1/(2bd^2)\) um und summieren diese Beiträge sorgfältig auf.
Der Durchlauf beginnt bei den ersten beiden Nachbarn \(0/1\) und \(1/N\). Für ein aktuelles Nachbarpaar \(a/b \lt c/d\) wird das nächste Farey-Glied durch die Standardrekurrenz erzeugt:
$$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$$
Nach der Bearbeitung von \([a/b,c/d]\) rückt das Paar zu \(c/d \lt e/f\) weiter. So wird die gesamte Farey-Folge in aufsteigender Reihenfolge durchlaufen, ohne sie vorher vollständig zu speichern.
Zu jedem aktuellen Intervall addiert die Implementierung den Beitrag
$$\frac{1}{2bd^2}$$
zur laufenden Summe. Weil die Summanden gegen Ende sehr klein werden, verwenden alle drei Versionen eine kompensierte Summation, um den Verlust niederwertiger Stellen zu verringern. Die C++-Version arbeitet dabei mit erweiterter Gleitkommapräzision; die Python- und Java-Versionen nutzen dieselbe Kompensationsidee mit Standardpräzision.
Sobald der rechte Endpunkt \(1/1\) erreicht ist, springt die nächste Farey-Aktualisierung über das Einheitsintervall hinaus und der Durchlauf endet. Die ausgegebene Dezimalzahl ist daher direkt die numerische Darstellung der exakten Farey-Summe.
Jedes benachbarte Farey-Intervall wird genau einmal besucht, und jeder Besuch benötigt nur konstante Zeit. Die Gesamtlaufzeit ist also linear in der Anzahl der Intervalle der Farey-Folge der Ordnung \(N\), mithin \(\Theta(N^2)\).
Der Speicherverbrauch ist \(O(1)\): Gespeichert werden nur die aktuellen Nachbarbrüche, die laufende Summe und der Kompensationsterm. Große Tabellen, Siebe oder dynamische Programme kommen nicht vor.
\(X\) rastgele değişkenini \([0,1]\) aralığında düzgün dağılımdan seçelim ve her pozitif \(N\) için
$$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$$
tanımını yapalım; burada \(\{y\}=y-\lfloor y\rfloor\) kesir kısmıdır. Problem, rastgele bir \(x\) için ilk \(N\) katın kesir kısımları arasındaki en küçük değerin beklenen değerini, özellikle \(N=10000\) için istemektedir.
Doğrudan yaklaşım verimsizdir: her \(x\) için \(N\) ayrı kesir kısmını karşılaştırmak gerekir ve yoğun bir örnekleme bile kesin sonuç vermez. Çözüm bunun yerine \([0,1]\) aralığını Farey komşularına göre parçalayarak \(f_N(x)\)'i her parçada basit bir doğrusal fonksiyona indirger.
\(\{mx\}=mx-\lfloor mx\rfloor\) ifadesi, \(mx\)'in hemen altındaki tam sayıdan ne kadar yukarıda olduğunu gösterir. Dolayısıyla \(1\le m\le N\) üzerindeki minimumu aramak, \(x\)'i alttan en iyi yaklaşık veren ve paydası \(N\)'i aşmayan rasyoneli aramakla aynıdır.
\(X\) düzgün dağıldığı için başlıktaki beklenen değer doğrudan \(f_N\)'in integrali olur. Yani yapılması gereken şey, \(f_N\)'in grafiğini anlayıp altında kalan alanı hesaplamaktır.
Sabit bir \(m\) için
$$\{mx\}=mx-p \qquad\text{ve}\qquad p=\lfloor mx\rfloor,$$
olduğundan her aday değer bir \(p/m\le x\) rasyoneline karşılık gelir. Böylece problem, noktadan noktaya minimizasyon olmaktan çıkıp sınırlı paydalı rasyonellerin düzenine dönüşür.
\(\mathcal{F}_N\) ile \(N\). mertebeden Farey dizisini gösterelim ve
$$\frac{a}{b} \lt \frac{c}{d}$$
iki ardışık terim olsun. Eğer
$$\frac{a}{b}\le x\le \frac{c}{d}$$
ise, paydası \(N\)'i aşanmadan bu iki uç arasında kalan başka indirgenmiş bir rasyonel yoktur. Bu yüzden \(x\)'in altında kalan en iyi rasyonel yaklaşım, bütün aralık boyunca sabit biçimde \(a/b\) olur.
Böylece minimum kesir kısmı payda \(b\) tarafından elde edilir:
$$f_N(x)=bx-a \qquad \text{için } x\in\left[\frac{a}{b},\frac{c}{d}\right].$$
Sol uçta bu değer \(0\)'dır; sağa gidildikçe doğrusal biçimde artar ve bir sonraki Farey sınırında yeni bir doğru parçasına geçilir. Yani \(f_N\)'in grafiği, Farey komşularının ürettiği doğrusal parçaların birleşimidir.
Farey komşuları şu unimodüler bağıntıyı sağlar:
$$bc-ad=1.$$
Bundan aralık genişliği
$$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd}$$
çıkar; ayrıca sağ uçta fonksiyonun değeri
$$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}$$
olur. Demek ki her Farey aralığı, tabanı \(1/(bd)\) ve yüksekliği \(1/d\) olan bir üçgen alanı verir:
$$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$$
Kodun her döngüde eklediği kapalı form tam olarak budur.
Bütün ardışık Farey çiftleri üzerinden toplarsak
$$\boxed{F(N)=\sum_{\substack{a/b \lt c/d\\ \text{\(\mathcal{F}_N\) içinde ardışık}}} \frac{1}{2bd^2}.}$$
Matematiksel ifade tamdır; sayısal dikkat gerektiren tek nokta, büyük \(N\) için çok sayıda küçük pozitif terimi kararlı biçimde toplamaktır.
\(4\). mertebeden Farey dizisi
$$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1$$
şeklindedir. Buna göre \(f_4(x)\) parçalı doğrusal olur:
$$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $$
Bu altı aralığın katkıları
$$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8}$$
olur ve toplamları
$$F(4)=\frac14$$
eder. Uygulamaların kullandığı kontrol noktası da budur; küçük örnek, genel yöntemin nasıl çalıştığını açıkça gösterir.
C++, Python ve Java uygulamaları aynı matematiksel planı izler: \(N\). mertebeden Farey komşularını sırayla üretir, her aralığı \(1/(2bd^2)\) terimine çevirir ve bu terimleri dikkatle toplar.
Tarama ilk iki komşu olan \(0/1\) ve \(1/N\) ile başlar. Güncel komşu çift \(a/b \lt c/d\) ise bir sonraki Farey terimi standart bağıntıyla bulunur:
$$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$$
\([a/b,c/d]\) aralığı işlendiğinde çift \(c/d \lt e/f\) biçimine kaydırılır. Böylece tüm Farey dizisi artan sırada dolaşılır; önceden büyük bir kesir listesi oluşturmak gerekmez.
Her aralık için uygulama
$$\frac{1}{2bd^2}$$
değerini koşan toplama ekler. Taramanın sonlarına doğru bu terimler çok küçüldüğü için üç sürüm de kompanse toplam kullanır. C++ sürümü daha yüksek kayan nokta hassasiyeti tutar; Python ve Java sürümleri ise aynı fikri standart hassasiyet üzerinde uygular.
Sağ uç \(1/1\)'e ulaştığında bir sonraki Farey güncellemesi birim aralığın dışına sıçrar ve döngü biter. Yazdırılan ondalık değer, yukarıdaki tam Farey toplamının sayısal karşılığıdır.
Her Farey komşu aralığı tam bir kez ziyaret edilir ve her ziyaret sabit zamanlı aritmetik içerir. Bu nedenle toplam süre, \(N\). mertebeden Farey dizisindeki aralık sayısıyla doğrusal, yani \(\Theta(N^2)\) düzeyindedir.
Bellek kullanımı \(O(1)\)'dir: yalnızca güncel komşu kesirler, koşan toplam ve kompanse terimi saklanır. Büyük diziler, eleme yapıları veya dinamik programlama tabloları yoktur.
Sea \(X\) una variable uniforme en \([0,1]\) y definamos, para cada entero positivo \(N\),
$$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$$
donde \(\{y\}=y-\lfloor y\rfloor\) es la parte fraccionaria. El objetivo es hallar el valor esperado de la menor parte fraccionaria entre los primeros \(N\) múltiplos de un \(x\) aleatorio, en particular para \(N=10000\).
Un enfoque ingenuo sería muy costoso: para cada \(x\) habría que comparar \(N\) valores distintos y luego integrar numéricamente sobre \([0,1]\). La solución real evita cualquier muestreo y aprovecha que \(f_N\) se vuelve lineal en cada intervalo determinado por fracciones vecinas de Farey.
La identidad \(\{mx\}=mx-\lfloor mx\rfloor\) muestra que cada término mide cuánto supera \(mx\) al entero inmediatamente inferior. Por tanto, minimizar \(\{mx\}\) para \(1\le m\le N\) equivale a buscar la mejor aproximación racional de \(x\) por debajo, con denominador acotado por \(N\).
Como \(X\) es uniforme en \([0,1]\), el valor esperado pedido coincide exactamente con el área bajo la curva \(f_N(x)\). El problema se convierte así en describir esa curva de forma exacta.
Para un denominador fijo \(m\), se tiene
$$\{mx\}=mx-p \qquad\text{con}\qquad p=\lfloor mx\rfloor,$$
de modo que cada candidato al mínimo está asociado con una fracción \(p/m\le x\). Eso traslada el problema a la geometría de los racionales de denominador limitado.
Sea
$$\frac{a}{b} \lt \frac{c}{d}$$
un par consecutivo de la sucesión de Farey de orden \(N\), \(\mathcal{F}_N\). Si
$$\frac{a}{b}\le x\le \frac{c}{d},$$
entonces no existe ninguna fracción reducida con denominador a lo sumo \(N\) entre esos extremos. Por ello, la mejor aproximación racional por debajo permanece fija en todo el intervalo y es precisamente \(a/b\).
En consecuencia, la menor parte fraccionaria la produce el denominador \(b\):
$$f_N(x)=bx-a \qquad \text{para } x\in\left[\frac{a}{b},\frac{c}{d}\right].$$
En el extremo izquierdo el valor es \(0\); luego crece linealmente hasta el siguiente borde de Farey. El gráfico completo de \(f_N\) es, por tanto, una cadena de segmentos rectos.
Las fracciones vecinas de Farey satisfacen
$$bc-ad=1.$$
De ahí se obtiene el ancho del intervalo:
$$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd},$$
y el valor del segmento en el extremo derecho:
$$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}.$$
Cada intervalo aporta entonces el área de un triángulo de base \(1/(bd)\) y altura \(1/d\):
$$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$$
Ésta es la fórmula cerrada exacta que suman las implementaciones.
Al sumar sobre todos los pares consecutivos de \(\mathcal{F}_N\), se obtiene
$$\boxed{F(N)=\sum_{\substack{a/b \lt c/d\\ \text{consecutivos en }\mathcal{F}_N}} \frac{1}{2bd^2}.}$$
La parte matemática es exacta; la única cuestión numérica real es sumar de manera estable muchos términos positivos muy pequeños cuando \(N\) es grande.
La sucesión de Farey de orden \(4\) es
$$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1.$$
Por tanto, \(f_4(x)\) queda descrita por tramos:
$$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $$
Las contribuciones de las seis regiones son
$$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8},$$
y su suma vale
$$F(4)=\frac14.$$
Este ejemplo pequeño reproduce exactamente la lógica usada para \(N=10000\): sustituir una minimización continua por una suma finita de áreas triangulares.
Las implementaciones en C++, Python y Java siguen el mismo esquema: recorren las fracciones vecinas de Farey de orden \(N\), convierten cada intervalo en el término exacto \(1/(2bd^2)\) y acumulan esos términos con cuidado numérico.
El barrido comienza con los dos primeros vecinos, \(0/1\) y \(1/N\). Si el par actual es \(a/b \lt c/d\), el siguiente término de Farey se obtiene con la recurrencia estándar
$$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$$
Tras procesar \([a/b,c/d]\), el par avanza a \(c/d \lt e/f\). Así se recorre toda la sucesión en orden creciente sin construir previamente una lista completa de fracciones.
En cada paso se añade
$$\frac{1}{2bd^2}$$
a la suma acumulada. Como los términos finales son muy pequeños, las tres versiones usan suma compensada para limitar la pérdida de precisión en los dígitos bajos. La versión en C++ conserva más precisión interna; las de Python y Java aplican la misma idea con aritmética de coma flotante estándar.
Cuando el extremo derecho alcanza \(1/1\), la siguiente actualización de Farey sale del intervalo unitario y el recorrido termina. El número decimal final no es una aproximación heurística, sino la evaluación numérica de la suma exacta deducida arriba.
Cada intervalo entre vecinos de Farey se visita una sola vez y cada visita requiere tiempo constante. Por ello, el tiempo total es lineal en el número de intervalos de la sucesión de Farey de orden \(N\), es decir, \(\Theta(N^2)\).
La memoria es \(O(1)\): sólo se mantienen las fracciones vecinas actuales, la suma acumulada y el término de compensación. No hacen falta tablas grandes ni estructuras auxiliares pesadas.
设 \(X\) 在区间 \([0,1]\) 上均匀分布。对每个正整数 \(N\)，定义
$$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$$
其中 \(\{y\}=y-\lfloor y\rfloor\) 表示小数部分。题目的含义就是：随机取一个 \(x\)，考察 \(x,2x,\dots,Nx\) 的小数部分，其中最小的那个的期望值是多少；目标情形是 \(N=10000\)。
如果直接做，会变成双重困难：对每个 \(x\) 都要比较 \(N\) 个值，而对整个 \([0,1]\) 又必须积分。代码真正利用的结构是，\(f_N(x)\) 并不是杂乱无章的，它会在 Farey 序列划出的每个小区间上退化成一条非常简单的直线。
\(\{mx\}=mx-\lfloor mx\rfloor\) 表示 \(mx\) 超过其下方最近整数的那一小段距离。因此，在 \(1\le m\le N\) 中寻找最小的小数部分，本质上是在寻找一个分母不超过 \(N\)、从下方最贴近 \(x\) 的有理数。
因为 \(X\) 在 \([0,1]\) 上均匀分布，所以题目中的期望值就是函数 \(f_N(x)\) 在 \([0,1]\) 上的积分。换句话说，只要能够精确描述 \(f_N\) 的图像，就能把问题变成纯粹的面积计算。
对固定的 \(m\)，有
$$\{mx\}=mx-p \qquad\text{其中}\qquad p=\lfloor mx\rfloor.$$
于是每一个候选值都对应一个满足 \(p/m\le x\) 的有理数。原问题因此从“连续函数取最小值”转化为“按分母上界组织这些有理数”。
记 \(\mathcal{F}_N\) 为 \(N\) 阶 Farey 序列。设
$$\frac{a}{b} \lt \frac{c}{d}$$
是其中一对相邻分数。如果
$$\frac{a}{b}\le x\le \frac{c}{d},$$
那么在这两个端点之间，不存在分母不超过 \(N\) 的既约分数。也就是说，整个区间内“从下方最接近 \(x\)”的有理数都固定为 \(a/b\)。
因此最小小数部分由分母 \(b\) 给出，并且有
$$f_N(x)=bx-a \qquad \text{在 } x\in\left[\frac{a}{b},\frac{c}{d}\right] \text{ 上成立。}$$
这个表达式在左端点处等于 \(0\)，随后随 \(x\) 线性增长，直到碰到下一个 Farey 边界才切换到新的线段。所以 \(f_N\) 的整个图像由一串相接的线性片段组成。
Farey 相邻分数满足经典关系
$$bc-ad=1.$$
因此区间宽度为
$$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd},$$
而右端点处函数值为
$$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}.$$
所以这一段曲线下面积就是一个底为 \(1/(bd)\)、高为 \(1/d\) 的三角形面积：
$$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$$
这正是三份实现每一步累加的闭式项。
对 \(\mathcal{F}_N\) 中全部相邻分数求和，就得到
$$\boxed{F(N)=\sum_{\substack{a/b \lt c/d\\ \text{在 }\mathcal{F}_N\text{ 中相邻}}} \frac{1}{2bd^2}.}$$
数学上这里没有近似。真正需要数值技巧的地方，只是当 \(N\) 很大时，如何稳定地累加大量很小的正项。
\(4\) 阶 Farey 序列为
$$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1.$$
因此 \(f_4(x)\) 的分段形式是
$$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $$
对应的六个面积分别是
$$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8},$$
总和为
$$F(4)=\frac14.$$
这个小例子已经完整展示了大问题的结构：不是对每个 \(x\) 暴力比较，而是先用 Farey 邻接关系切分区间，再把每段化成一个可直接求面积的三角形。
C++、Python 和 Java 实现采用完全相同的思路：按顺序遍历 \(N\) 阶 Farey 序列中的相邻分数，把每个区间转换成精确项 \(1/(2bd^2)\)，然后稳定地把这些项相加。
遍历从最前面的两个邻项 \(0/1\) 和 \(1/N\) 开始。如果当前相邻分数是 \(a/b \lt c/d\)，那么下一个 Farey 项由标准递推式给出：
$$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$$
处理完区间 \([a/b,c/d]\) 后，相邻对向前推进为 \(c/d \lt e/f\)。这样就能按升序走完整个 Farey 序列，而不需要事先把所有分数存进数组。
每一步加入的都是
$$\frac{1}{2bd^2}$$
这个精确公式。由于扫描后段的项会越来越小，三份实现都采用了补偿求和来减少浮点舍入误差。C++ 版本使用更高的内部精度；Python 和 Java 版本则用标准浮点数配合同样的补偿思想。
当右端点到达 \(1/1\) 后，再做一次 Farey 更新就会跳出单位区间，循环结束。最终输出的十进制数，就是上面那个 Farey 精确求和公式的数值结果。
每一个 Farey 相邻区间只会访问一次，而且每次访问只做常数次算术运算。因此总时间与 \(N\) 阶 Farey 序列中的区间数成正比，也就是 \(\Theta(N^2)\)。
空间复杂度为 \(O(1)\)：程序只保存当前相邻分数、运行中的总和以及补偿项，不需要大数组、筛法表或动态规划结构。
Пусть \(X\) равномерно распределена на \([0,1]\). Для каждого положительного \(N\) определим
$$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$$
где \(\{y\}=y-\lfloor y\rfloor\) обозначает дробную часть. Требуется найти математическое ожидание наименьшей дробной части среди чисел \(x,2x,\dots,Nx\), в задаче интересует случай \(N=10000\).
Лобовое вычисление было бы неудобным: для каждого \(x\) пришлось бы сравнивать \(N\) значений, а затем ещё численно интегрировать по всему отрезку. Реальное решение использует тот факт, что функция \(f_N(x)\) разбивается на простые линейные куски, задаваемые соседними дробями Фарея.
Равенство \(\{mx\}=mx-\lfloor mx\rfloor\) показывает, насколько \(mx\) находится выше ближайшего меньшего целого. Поэтому минимизация \(\{mx\}\) по \(1\le m\le N\) эквивалентна поиску наилучшего рационального приближения числа \(x\) снизу с ограничением на знаменатель.
Так как \(X\) равномерна на \([0,1]\), искомое ожидание в точности равно интегралу от \(f_N\). Значит, задача сводится к тому, чтобы точно описать график этой функции.
Для фиксированного \(m\) имеем
$$\{mx\}=mx-p \qquad\text{при}\qquad p=\lfloor mx\rfloor,$$
то есть каждый кандидат на минимум связан с рациональным числом \(p/m\le x\). После этого исходная задача превращается в задачу о рациональных точках с ограниченным знаменателем.
Пусть
$$\frac{a}{b} \lt \frac{c}{d}$$
это соседние члены последовательности Фарея порядка \(N\), обозначаемой \(\mathcal{F}_N\). Если
$$\frac{a}{b}\le x\le \frac{c}{d},$$
то между этими концами нет ни одной несократимой дроби со знаменателем не больше \(N\). Следовательно, на всём таком интервале лучшая рациональная аппроксимация снизу остаётся одной и той же, а именно \(a/b\).
Отсюда минимальная дробная часть достигается при знаменателе \(b\):
$$f_N(x)=bx-a \qquad \text{на } \left[\frac{a}{b},\frac{c}{d}\right].$$
В левом конце этот кусок равен нулю, затем линейно возрастает до следующей границы Фарея. Значит, график \(f_N\) состоит из цепочки линейных отрезков.
Для соседних дробей Фарея выполняется соотношение
$$bc-ad=1.$$
Из него следует ширина интервала
$$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd},$$
а значение функции в правом конце равно
$$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}.$$
Значит, каждый такой участок даёт площадь треугольника с основанием \(1/(bd)\) и высотой \(1/d\):
$$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$$
Именно этот замкнутый вид накапливают реализации.
Суммируя по всем соседним парам в \(\mathcal{F}_N\), получаем
$$\boxed{F(N)=\sum_{\substack{a/b \lt c/d\\ \text{соседи в }\mathcal{F}_N}} \frac{1}{2bd^2}.}$$
Математическая часть здесь точна; единственный численный вопрос состоит в устойчивом суммировании большого числа очень маленьких положительных слагаемых.
Последовательность Фарея порядка \(4\) имеет вид
$$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1.$$
Отсюда функция \(f_4(x)\) задаётся по частям:
$$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $$
Соответствующие площади равны
$$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8},$$
а их сумма даёт
$$F(4)=\frac14.$$
Этот небольшой пример полностью иллюстрирует общий метод: вместо перебора значений по \(x\) задача сводится к конечной сумме площадей по интервалам Фарея.
Реализации на C++, Python и Java используют один и тот же план: последовательно проходят соседние дроби Фарея порядка \(N\), для каждого интервала вычисляют точный член \(1/(2bd^2)\) и аккуратно прибавляют его к общей сумме.
Обход начинается с первой пары соседей \(0/1\) и \(1/N\). Если текущая пара равна \(a/b \lt c/d\), следующий член последовательности Фарея находится по стандартной рекуррентной формуле
$$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$$
После обработки интервала \([a/b,c/d]\) пара сдвигается к \(c/d \lt e/f\). Так можно пройти всю последовательность Фарея по возрастанию, не сохраняя заранее большой список дробей.
На каждом шаге добавляется величина
$$\frac{1}{2bd^2}.$$
Поскольку ближе к концу прохода слагаемые становятся очень малыми, все три реализации используют компенсированное суммирование, уменьшающее потерю точности. Версия на C++ хранит сумму с повышенной внутренней точностью; версии на Python и Java применяют ту же идею с обычной плавающей точкой.
Когда правый конец достигает \(1/1\), следующее обновление Фарея уже выводит процесс за пределы единичного интервала, и цикл завершается. Итоговое десятичное число является численным значением точной формулы, полученной выше.
Каждый интервал между соседями Фарея посещается ровно один раз, и на каждый визит требуется только постоянное число арифметических операций. Поэтому общее время линейно по числу интервалов в последовательности Фарея порядка \(N\), то есть \(\Theta(N^2)\).
Память равна \(O(1)\): хранятся только текущие соседние дроби, накопленная сумма и компенсирующий член. Никаких больших таблиц или вспомогательных структур не требуется.
لنأخذ \(X\) موزعًا بانتظام على الفترة \([0,1]\)، ولأي عدد صحيح موجب \(N\) نعرّف
$$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$$
حيث \(\{y\}=y-\lfloor y\rfloor\) تمثل الجزء الكسري. المطلوب هو القيمة المتوقعة لأصغر جزء كسري بين القيم \(x,2x,\dots,Nx\)، والحالة المستهدفة في المسألة هي \(N=10000\).
الطريقة المباشرة غير مناسبة: لكل \(x\) يجب مقارنة \(N\) قيم مختلفة، ثم يلزم تكامل عددي على كامل الفترة. الفكرة الحاسمة في الحل هي أن الدالة \(f_N(x)\) تصبح خطية على كل فترة يحددها زوج متجاور من كسور Farey، ولذلك يمكن تحويل التوقع إلى مجموع مغلق من مساحات بسيطة.
لدينا \(\{mx\}=mx-\lfloor mx\rfloor\)، أي أن هذا المقدار يقيس المسافة بين \(mx\) وأقرب عدد صحيح أصغر منه. لذا فإن تصغير \(\{mx\}\) على المجال \(1\le m\le N\) يكافئ البحث عن أفضل تقريب نسبي للعدد \(x\) من الأسفل بحيث لا يتجاوز المقام \(N\).
بما أن \(X\) موزع بانتظام على \([0,1]\)، فإن القيمة المتوقعة المطلوبة تساوي تمامًا تكامل \(f_N\) على هذه الفترة. إذن جوهر المسألة هو وصف شكل \(f_N(x)\) بدقة.
ولكل مقام ثابت \(m\) نحصل على
$$\{mx\}=mx-p \qquad\text{with}\qquad p=\lfloor mx\rfloor,$$
وبذلك يرتبط كل مرشح للقيمة الدنيا بكسر نسبي \(p/m\le x\). بهذه الصياغة تتحول المسألة إلى دراسة منظومة الكسور ذات المقامات المحدودة.
لنرمز إلى متتالية Farey من الرتبة \(N\) بالرمز \(\mathcal{F}_N\)، ولنفترض أن
$$\frac{a}{b} \lt \frac{c}{d}$$
هما حدان متجاوران فيها. إذا كان
$$\frac{a}{b}\le x\le \frac{c}{d},$$
فلا يوجد كسر مختزل مقامه لا يتجاوز \(N\) يقع بين هذين الحدين. لذلك يبقى أفضل تقريب نسبي من الأسفل ثابتًا على كامل الفترة، وهو بالضبط \(a/b\).
إذن يتحقق أصغر جزء كسري عند المقام \(b\)، ويكون
$$f_N(x)=bx-a,\qquad x\in\left[\frac{a}{b},\frac{c}{d}\right].$$
هذه الدالة تساوي الصفر عند الطرف الأيسر، ثم ترتفع خطيًا حتى تصل إلى الحد التالي في Farey. ومن ثم فإن الرسم الكامل لـ \(f_N\) هو سلسلة من القطع الخطية المتصلة.
الكسور المتجاورة في Farey تحقق العلاقة
$$bc-ad=1.$$
ومنها نحصل على عرض الفترة
$$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd},$$
كما أن قيمة الدالة عند الطرف الأيمن هي
$$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}.$$
لذلك فإن مساهمة كل فترة هي مساحة مثلث قاعدته \(1/(bd)\) وارتفاعه \(1/d\):
$$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$$
وهذا هو الحد المغلق الذي تجمعه التطبيقات مباشرة.
بجمع هذه المساهمات على جميع الأزواج المتجاورة في \(\mathcal{F}_N\) نحصل على
$$\boxed{F(N)=\sum_{a/b \lt c/d} \frac{1}{2bd^2}.}$$
الصياغة الرياضية هنا دقيقة تمامًا؛ أما التحدي العددي الوحيد فهو جمع عدد كبير من الحدود الصغيرة الموجبة بطريقة مستقرة.
متتالية Farey من الرتبة \(4\) هي
$$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1.$$
ومن ثم تكون \(f_4(x)\) دالة خطية على مقاطع:
$$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $$
ومساهمات الفترات الست هي
$$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8},$$
ومجموعها يساوي
$$F(4)=\frac14.$$
هذا المثال الصغير يوضح الفكرة كاملة: بدلًا من تجربة قيم كثيرة لـ \(x\)، نقسم الفترة باستخدام جيران Farey ثم نحول كل جزء إلى مساحة مثلث معروفة بدقة.
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها: توليد الكسور المتجاورة في متتالية Farey من الرتبة \(N\)، تحويل كل فترة إلى الحد الدقيق \(1/(2bd^2)\)، ثم جمع هذه الحدود بعناية عددية.
تبدأ العملية بأول زوج متجاور، وهو \(0/1\) و\(1/N\). إذا كان الزوج الحالي هو \(a/b \lt c/d\)، فإن الحد التالي في Farey يعطى بالعلاقة القياسية
$$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$$
بعد معالجة الفترة \([a/b,c/d]\) ينتقل الزوج إلى \(c/d \lt e/f\). بهذه الطريقة يتم اجتياز المتتالية كلها بترتيب تصاعدي من غير الحاجة إلى بناء جدول كامل مسبقًا.
في كل خطوة يضاف الحد
$$\frac{1}{2bd^2}$$
إلى المجموع الجاري. ولأن الحدود تصبح صغيرة جدًا قرب نهاية المسار، تستخدم النسخ الثلاث الجمع المعوَّض لتقليل فقدان الدقة في الأرقام الدنيا. نسخة C++ تحتفظ بدقة داخلية أعلى، أما نسختا Python وJava فتستخدمان الفكرة نفسها مع الأعداد العائمة القياسية.
عندما يصل الطرف الأيمن إلى \(1/1\)، تدفع خطوة Farey التالية الزوج إلى خارج الفترة الواحدة، وعندها تنتهي الحلقة. العدد العشري النهائي هو التقييم العددي المباشر للمجموع الدقيق المستنتج أعلاه.
تُزار كل فترة بين جارين في Farey مرة واحدة فقط، وكل زيارة تحتاج إلى عدد ثابت من العمليات الحسابية. لذلك فالزمن الكلي يتناسب مع عدد فترات متتالية Farey من الرتبة \(N\)، أي يساوي \(\Theta(N^2)\).
أما الذاكرة فهي \(O(1)\): لا يُخزَّن إلا الزوج الحالي من الكسور، والمجموع الجاري، وحد التعويض. لا توجد مصفوفات كبيرة ولا جداول مساعدة معقدة.