The candidates are the 1200 dates of the form \((y,m,1)\) with \(1901 \le y \le 2000\) and \(1 \le m \le 12\). We must count how many of those first-of-month dates are Sundays, assuming the Gregorian leap-year rule and the given anchor that 1900-01-01 was a Monday.
This makes the problem completely discrete: each month contributes exactly one candidate date, and the only arithmetic we need is how far that date lies from a known epoch.
The implementations treat calendar arithmetic as modular counting. Once the number of elapsed days is known, the weekday is determined modulo \(7\).
Encode weekdays by
$$\text{Monday}=0,\ \text{Tuesday}=1,\ \dots,\ \text{Sunday}=6.$$
If a date is \(\Delta\) days after 1900-01-01, then its weekday code is simply \(\Delta \bmod 7\), because each extra day advances the weekday by one step in \(\mathbb{Z}/7\mathbb{Z}\).
Let the leap-year indicator be
$$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y\ \text{and}\ 100\nmid y,\\0,&\text{otherwise}.\end{cases}$$
Then the length of year \(y\) is \(365+\lambda(y)\). For months, define \(L(y,m)\) by the usual Gregorian table:
$$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}.$$
The only variable month is February, whose length is \(28+\lambda(y)\).
For any date \((y,m,d)\), the number of elapsed days after 1900-01-01 is
$$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1).$$
The weekday code is therefore
$$w(y,m,d)\equiv D(y,m,d)\pmod 7.$$
Problem 19 only needs \(d=1\). If we define
$$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{otherwise},\end{cases}$$
then the required count is
$$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m).$$
The same mathematics can be written recursively. Let \(s_{y,m}=w(y,m,1)\). Moving from one month to the next adds exactly the length of the current month, so
$$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7.$$
Crossing a year boundary gives
$$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7.$$
These recurrences are not a different method; they are just the elapsed-day formula written incrementally.
Because 1900 is not a leap year, it has \(365\) days, so
$$s_{1901,1}\equiv 365\equiv 1\pmod 7,$$
which means 1901-01-01 is a Tuesday. Advancing month by month gives:
January 1 Tuesday, February 1 Friday, March 1 Friday, April 1 Monday, May 1 Wednesday, June 1 Saturday, July 1 Monday, August 1 Thursday, September 1 Sunday, October 1 Tuesday, November 1 Friday, December 1 Sunday.
So the year 1901 contributes exactly two qualifying months. Continuing the same count through December 2000 gives the final total \(S=171\).
The C++, Python, and Java implementations use the elapsed-day formula directly. For each first day of a month in the target interval, the implementation sums the lengths of all complete years from 1900 up to the previous year, then the lengths of all complete months in the current year, then reduces the result modulo \(7\).
An outer loop scans the inclusive year range and all twelve months in each year. Whenever the weekday code of \((y,m,1)\) is \(6\), the answer counter is incremented.
The implementations also include small internal checks derived from the statement and the recurrence above: 1900-01-01 maps to Monday, 1901-01-01 maps to Tuesday, and the year 1901 contributes exactly two Sunday-first months.
Let \(Y\) be the number of years in the queried interval. There are \(12Y\) candidate months, but each weekday computation recomputes the elapsed-day total from the 1900 epoch. Summing the year-loop work over the full interval gives a quadratic total:
$$12\sum_{t=1}^{Y} t = O(Y^2).$$
The month-loop inside each date computation contributes only \(O(Y)\) overall, and the memory usage is \(O(1)\). For the Project Euler century this cost is tiny in practice, even though a purely incremental implementation could reduce the running time to \(O(Y)\).
Betrachtet werden die 1200 Daten der Form \((y,m,1)\) mit \(1901 \le y \le 2000\) und \(1 \le m \le 12\). Gesucht ist, bei wie vielen dieser Monatsersten der Wochentag Sonntag ist, unter der gregorianischen Schaltjahrregel und der Vorgabe, dass der 01.01.1900 ein Montag war.
Damit ist der Zustandsraum sehr konkret: Jeder Monat liefert genau einen Kandidaten, und das gesamte Problem reduziert sich auf die Frage, wie viele Tage seit einem bekannten Bezugspunkt vergangen sind.
Die Implementierungen behandeln den Kalender als Modulo-7-Zählproblem. Kennt man die Zahl der vergangenen Tage, ist der Wochentag sofort bestimmt.
Wir codieren
$$\text{Montag}=0,\ \text{Dienstag}=1,\ \dots,\ \text{Sonntag}=6.$$
Liegt ein Datum \(\Delta\) Tage nach dem 01.01.1900, dann ist sein Wochentagscode gleich \(\Delta \bmod 7\), denn jeder weitere Tag erhöht den Code um \(1\) in \(\mathbb{Z}/7\mathbb{Z}\).
Sei die Schaltjahrfunktion
$$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y\ \text{und}\ 100\nmid y,\\0,&\text{sonst}.\end{cases}$$
Dann hat das Jahr \(y\) genau \(365+\lambda(y)\) Tage. Für die Monatslängen gilt die übliche gregorianische Tabelle
$$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}.$$
Nur der Februar hängt also vom Schaltjahrstatus ab.
Für ein beliebiges Datum \((y,m,d)\) ist die Zahl der seit dem 01.01.1900 vergangenen Tage
$$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1).$$
Der Wochentagscode erfüllt damit
$$w(y,m,d)\equiv D(y,m,d)\pmod 7.$$
In dieser Aufgabe ist immer \(d=1\). Mit
$$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{sonst}\end{cases}$$
ergibt sich die gesuchte Anzahl als
$$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m).$$
Dieselbe Struktur kann auch inkrementell geschrieben werden. Sei \(s_{y,m}=w(y,m,1)\). Dann gilt beim Übergang zum nächsten Monat
$$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7,$$
und beim Übergang zum nächsten Jahr
$$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7.$$
Diese Rekursion ist keine andere Mathematik, sondern genau dieselbe Tageszählung in kompakter Form.
Da 1900 kein Schaltjahr ist, hat es \(365\) Tage, also
$$s_{1901,1}\equiv 365\equiv 1\pmod 7,$$
und der 01.01.1901 ist ein Dienstag. Monat für Monat erhält man:
1. Januar Dienstag, 1. Februar Freitag, 1. März Freitag, 1. April Montag, 1. Mai Mittwoch, 1. Juni Samstag, 1. Juli Montag, 1. August Donnerstag, 1. September Sonntag, 1. Oktober Dienstag, 1. November Freitag, 1. Dezember Sonntag.
Das Jahr 1901 liefert also genau zwei passende Monate. Führt man dieselbe Rechnung bis Dezember 2000 fort, erhält man insgesamt \(S=171\).
Die C++-, Python- und Java-Implementierungen verwenden die Formel für vergangene Tage direkt. Für jeden Monatsersten im Zielintervall summiert die Implementierung zunächst alle vollständigen Jahre seit 1900 und danach alle vollständigen Monate des aktuellen Jahres; anschließend wird modulo \(7\) reduziert.
Eine äußere Schleife läuft durch das inklusive Jahresintervall und durch alle zwölf Monate jedes Jahres. Immer wenn der Wochentagscode von \((y,m,1)\) gleich \(6\) ist, wird der Zähler erhöht.
Zusätzlich enthalten die Implementierungen kleine Plausibilitätsprüfungen: Der 01.01.1900 ist Montag, der 01.01.1901 ist Dienstag, und im Jahr 1901 fallen genau zwei Monatserste auf einen Sonntag.
Sei \(Y\) die Anzahl der Jahre im abgefragten Intervall. Es gibt \(12Y\) Kandidatenmonate, aber jede Wochentagsberechnung summiert erneut vom Bezugspunkt 1900 aus. Über das gesamte Intervall entsteht daher quadratischer Aufwand:
$$12\sum_{t=1}^{Y} t = O(Y^2).$$
Die Monatssumme innerhalb einer einzelnen Datumsberechnung trägt insgesamt nur \(O(Y)\) bei, und der Speicherverbrauch bleibt \(O(1)\). Für das Project-Euler-Intervall ist das praktisch sehr klein, obwohl eine rein inkrementelle Variante asymptotisch \(O(Y)\) erreichen könnte.
İncelenen tarihler, \(1901 \le y \le 2000\) ve \(1 \le m \le 12\) için \((y,m,1)\) biçimindeki 1200 ay başı tarihidir. Soru, Gregoryen artık yıl kuralı ve 1900-01-01 tarihinin Pazartesi olduğu bilgisi altında, bu ay başlarından kaç tanesinin Pazar gününe denk geldiğini saymaktır.
Dolayısıyla problem çok somuttur: her ay tam bir aday üretir ve gereken tek şey, bu tarihin seçilen epoktan kaç gün sonra geldiğini doğru saymaktır.
Uygulamalar takvim hesabını mod \(7\) aritmetiği olarak ele alır. Geçen gün sayısı bilindiğinde haftanın günü doğrudan bulunur.
Haftanın günlerini
$$\text{Pazartesi}=0,\ \text{Salı}=1,\ \dots,\ \text{Pazar}=6$$
şeklinde kodlayalım. Bir tarih 1900-01-01'den \(\Delta\) gün sonraysa, gün kodu \(\Delta \bmod 7\) olur; çünkü her yeni gün kodu mod \(7\)'de bir artırır.
Artık yıl göstergesini
$$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y\ \text{ve}\ 100\nmid y,\\0,&\text{aksi halde}.\end{cases}$$
olarak tanımlayalım. O zaman \(y\) yılının uzunluğu \(365+\lambda(y)\) gündür. Ay uzunluklarını da
$$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}$$
şeklinde yazarız. Değişken olan tek ay Şubat'tır.
Herhangi bir \((y,m,d)\) tarihi için 1900-01-01'den beri geçen gün sayısı
$$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1)$$
olur. Buna karşılık haftanın günü kodu
$$w(y,m,d)\equiv D(y,m,d)\pmod 7$$
eşitliğiyle bulunur. Bu problemde yalnızca \(d=1\) gerekir. Eğer
$$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{aksi halde}\end{cases}$$
tanımlanırsa, aranan toplam
$$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m)$$
olur.
Aynı fikir artımlı olarak da yazılabilir. \(s_{y,m}=w(y,m,1)\) olsun. Bir sonraki aya geçerken tam olarak mevcut ayın uzunluğu kadar ilerleriz:
$$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7.$$
Yeni yılın ilk gününe geçişte ise
$$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7$$
geçerlidir. Bu bağıntılar ayrı bir yöntem değil, aynı gün sayımının artımlı biçimidir.
1900 artık yıl olmadığı için \(365\) gündür; dolayısıyla
$$s_{1901,1}\equiv 365\equiv 1\pmod 7,$$
yani 1901-01-01 Salı'dır. Ay ay ilerleyince şu tablo oluşur:
1 Ocak Salı, 1 Şubat Cuma, 1 Mart Cuma, 1 Nisan Pazartesi, 1 Mayıs Çarşamba, 1 Haziran Cumartesi, 1 Temmuz Pazartesi, 1 Ağustos Perşembe, 1 Eylül Pazar, 1 Ekim Salı, 1 Kasım Cuma, 1 Aralık Pazar.
Böylece 1901 yılı tam iki kez Pazar gününe gelen ay başı üretir. Aynı sayımı 2000 Aralık sonuna kadar sürdürdüğümüzde toplam \(S=171\) elde edilir.
C++, Python ve Java uygulamaları geçen gün formülünü doğrudan uygular. Hedef aralıktaki her ay başı için önce 1900'den bir önceki yıla kadar tüm tam yılların gün sayılarını, sonra ilgili yıl içindeki tamamlanmış ayların gün sayılarını toplar ve sonucu mod \(7\)'ye indirger.
Dış döngü kapsayıcı yıl aralığını ve her yılın on iki ayını dolaşır. \((y,m,1)\) tarihinin gün kodu \(6\) ise sayaç bir artırılır.
Uygulamalarda ayrıca küçük doğrulama kontrolleri bulunur: 1900-01-01 Pazartesi olmalıdır, 1901-01-01 Salı olmalıdır ve 1901 yılı tam iki uygun ay üretmelidir.
\(Y\) sorgulanan yıl sayısı olsun. \(12Y\) aday ay vardır; fakat her hafta-günü hesabı 1900 epokundan başlayarak gün toplamını yeniden kurar. Bu yüzden toplam yıl toplama maliyeti kareseldir:
$$12\sum_{t=1}^{Y} t = O(Y^2).$$
Her tarih hesabındaki ay kısmı toplamda yalnızca \(O(Y)\) katkı yapar ve bellek kullanımı \(O(1)\)'dir. Project Euler aralığında bu maliyet çok küçüktür; yine de tamamen artımlı bir sürüm asimptotik olarak \(O(Y)\) zamanda çalışabilirdi.
Se consideran las 1200 fechas de la forma \((y,m,1)\) con \(1901 \le y \le 2000\) y \(1 \le m \le 12\). Hay que contar cuántos de esos primeros días de mes son domingo, usando la regla gregoriana de años bisiestos y el dato de que 1900-01-01 fue lunes.
Por tanto, el espacio de estados es muy pequeño: cada mes aporta un único candidato, y toda la dificultad consiste en calcular correctamente cuántos días han pasado desde una fecha base conocida.
Las implementaciones convierten el calendario en un problema de conteo modular. Una vez conocido el número de días transcurridos, el día de la semana queda fijado módulo \(7\).
Codificamos
$$\text{lunes}=0,\ \text{martes}=1,\ \dots,\ \text{domingo}=6.$$
Si una fecha está a \(\Delta\) días de 1900-01-01, entonces su código semanal es \(\Delta \bmod 7\), porque cada día adicional desplaza el calendario un paso dentro de \(\mathbb{Z}/7\mathbb{Z}\).
Definimos el indicador de año bisiesto por
$$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y\ \text{y}\ 100\nmid y,\\0,&\text{en otro caso}.\end{cases}$$
La longitud del año \(y\) es entonces \(365+\lambda(y)\). Para los meses usamos la tabla gregoriana habitual:
$$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}.$$
El único mes variable es febrero.
Para una fecha \((y,m,d)\), el número de días transcurridos desde 1900-01-01 es
$$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1).$$
Por tanto, el día de la semana viene dado por
$$w(y,m,d)\equiv D(y,m,d)\pmod 7.$$
Aquí solo importa \(d=1\). Si definimos
$$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{en otro caso},\end{cases}$$
la cantidad buscada es
$$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m).$$
La misma idea puede escribirse de forma incremental. Si \(s_{y,m}=w(y,m,1)\), entonces pasar al mes siguiente suma exactamente la longitud del mes actual:
$$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7.$$
Y pasar al primer día del año siguiente produce
$$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7.$$
Estas relaciones no son otro método distinto; son la misma fórmula de días transcurridos escrita como recurrencia.
Como 1900 no es bisiesto, tiene \(365\) días, así que
$$s_{1901,1}\equiv 365\equiv 1\pmod 7,$$
de modo que 1901-01-01 fue martes. Avanzando mes a mes se obtiene:
1 de enero martes, 1 de febrero viernes, 1 de marzo viernes, 1 de abril lunes, 1 de mayo miércoles, 1 de junio sábado, 1 de julio lunes, 1 de agosto jueves, 1 de septiembre domingo, 1 de octubre martes, 1 de noviembre viernes y 1 de diciembre domingo.
Por consiguiente, 1901 aporta exactamente dos meses válidos. Extender el mismo conteo hasta diciembre de 2000 produce el total final \(S=171\).
Las implementaciones en C++, Python y Java aplican directamente la fórmula de días transcurridos. Para cada primer día de mes del intervalo objetivo, la implementación suma todas las longitudes anuales completas desde 1900 hasta el año anterior y luego las longitudes de los meses ya terminados en el año actual; al final reduce módulo \(7\).
Un bucle exterior recorre el intervalo inclusivo de años y los doce meses de cada año. Cada vez que el código semanal de \((y,m,1)\) vale \(6\), se incrementa el contador de respuesta.
Las implementaciones también incluyen comprobaciones pequeñas pero significativas: 1900-01-01 corresponde a lunes, 1901-01-01 corresponde a martes y el año 1901 contiene exactamente dos domingos en primer día de mes.
Sea \(Y\) el número de años del intervalo. Hay \(12Y\) meses candidatos, pero cada cálculo de día de la semana reconstruye de nuevo el total de días desde la época 1900. Al sumar ese trabajo a lo largo del intervalo, el coste total es cuadrático:
$$12\sum_{t=1}^{Y} t = O(Y^2).$$
La parte correspondiente a los meses dentro de cada fecha solo aporta \(O(Y)\) en total, y el uso de memoria es \(O(1)\). Para el siglo de Project Euler este coste es minúsculo, aunque una versión puramente incremental podría bajar a \(O(Y)\).
要考察的对象是所有形如 \((y,m,1)\) 的日期，其中 \(1901 \le y \le 2000\)，\(1 \le m \le 12\)。也就是说，一共只有 1200 个“每月第一天”的候选日期。题目要求在公历闰年规则下，并利用 1900-01-01 是星期一这一已知锚点，统计其中有多少个落在星期日。
因此这道题并不是在复杂日期结构上做搜索，而是在一个非常有限的日期集合上做严格计数。关键是把每个候选日期与参考日之间的天数差准确地写出来。
三种实现都把问题转化为模 \(7\) 的日数计算。只要知道某个日期距离 1900-01-01 有多少天，它对应的星期几就立刻确定。
先规定编码方式：
$$\text{星期一}=0,\ \text{星期二}=1,\ \dots,\ \text{星期日}=6.$$
如果某个日期比 1900-01-01 晚 \(\Delta\) 天，那么它的星期编码就是 \(\Delta \bmod 7\)。原因很简单：每前进一天，星期值就在 \(\mathbb{Z}/7\mathbb{Z}\) 中加 \(1\)。
设闰年指示函数为
$$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y\ \text{且}\ 100\nmid y,\\0,&\text{否则}.\end{cases}$$
于是年份 \(y\) 的总天数就是 \(365+\lambda(y)\)。每个月的长度记为 \(L(y,m)\)，公历表可以写成
$$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}.$$
唯一会变化的月份是二月；平年是 28 天，闰年是 29 天。
对任意日期 \((y,m,d)\)，从 1900-01-01 起累计经过的天数为
$$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1).$$
因此星期编码满足
$$w(y,m,d)\equiv D(y,m,d)\pmod 7.$$
本题只需要考察每月第一天，所以始终取 \(d=1\)。如果定义指示函数
$$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{否则},\end{cases}$$
那么题目要求的答案就是
$$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m).$$
把同样的结构写成递推也很自然。令 \(s_{y,m}=w(y,m,1)\) 表示某年某月一号的星期编码。由于从本月一号走到下月一号，恰好跨过本月的全部天数，所以有
$$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7.$$
跨年时同理得到
$$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7.$$
这并不是另一套算法，而是把上面的累计公式改写成逐月推进的形式。题目的本质不变：星期只取决于总天数对 \(7\) 的余数。
因为 1900 年不是闰年，所以它有 \(365\) 天，从而
$$s_{1901,1}\equiv 365\equiv 1\pmod 7,$$
这说明 1901-01-01 是星期二。随后按月份长度依次推进：
1 月 1 日星期二，2 月 1 日星期五，3 月 1 日星期五，4 月 1 日星期一，5 月 1 日星期三，6 月 1 日星期六，7 月 1 日星期一，8 月 1 日星期四，9 月 1 日星期日，10 月 1 日星期二，11 月 1 日星期五，12 月 1 日星期日。
因此，1901 年恰好贡献两个满足条件的月份，即 9 月和 12 月。把同样的计数过程一直做到账目区间的末尾 2000 年 12 月，就得到最终总数 \(S=171\)。
C++、Python 和 Java 的实现都直接使用“从 1900-01-01 起累计天数”的写法。对于目标区间内的每一个月初日期，程序先把从 1900 到前一整年的天数全部加起来，再把当前年份中已经走完的月份天数加上去，最后对 \(7\) 取模得到星期编码。
外层逻辑只做一件事：枚举给定年份区间中的所有月份，并把日期固定为该月的第一天。当星期编码等于 \(6\) 时，说明这一天是星期日，于是答案计数器加一。
实现中还包含了几个很小但很关键的自检条件：1900-01-01 必须对应星期一，1901-01-01 必须对应星期二，而 1901 全年应当恰好出现两个“月初是星期日”的月份。
设查询区间包含 \(Y\) 个年份。候选月份只有 \(12Y\) 个，但每次计算某个月初的星期时，程序都会重新从 1900 年开始累加完整年份的天数。因此，把整个区间的工作量加总起来后，年份部分是平方级的：
$$12\sum_{t=1}^{Y} t = O(Y^2).$$
每次日期计算中对月份的那一小段累加，总体只贡献 \(O(Y)\)，额外空间始终是 \(O(1)\)。对本题的 100 年范围来说，这个代价非常小；不过如果采用纯递推方式逐月推进，时间复杂度还可以进一步降到 \(O(Y)\)。
Рассматриваются все даты вида \((y,m,1)\), где \(1901 \le y \le 2000\) и \(1 \le m \le 12\). Таких первых чисел месяца ровно 1200. Нужно посчитать, сколько из них приходится на воскресенье, если использовать григорианское правило високосных лет и известный факт, что 1900-01-01 был понедельником.
Здесь нет сложного перебора по календарю. Каждый месяц даёт ровно одну кандидатную дату, и задача сводится к точному подсчёту числа дней от фиксированной эпохи.
Все три реализации строят решение на модульной арифметике по модулю \(7\). Как только известно количество прошедших дней, день недели определяется автоматически.
Будем кодировать дни недели так:
$$\text{понедельник}=0,\ \text{вторник}=1,\ \dots,\ \text{воскресенье}=6.$$
Если дата находится на \(\Delta\) дней позже 1900-01-01, её код дня недели равен \(\Delta \bmod 7\), потому что каждый переход на один день вперёд увеличивает код на единицу в \(\mathbb{Z}/7\mathbb{Z}\).
Введём индикатор високосного года
$$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y\ \text{и}\ 100\nmid y,\\0,&\text{иначе}.\end{cases}$$
Тогда длина года \(y\) равна \(365+\lambda(y)\). Длины месяцев описываются стандартной григорианской таблицей
$$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}.$$
Меняется только февраль: 28 дней в обычный год и 29 дней в високосный.
Для произвольной даты \((y,m,d)\) число дней, прошедших после 1900-01-01, равно
$$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1).$$
Следовательно, код дня недели удовлетворяет соотношению
$$w(y,m,d)\equiv D(y,m,d)\pmod 7.$$
В задаче нужен только случай \(d=1\). Если задать индикатор
$$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{иначе},\end{cases}$$
то искомое количество равно
$$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m).$$
Ту же идею удобно записать рекуррентно. Пусть \(s_{y,m}=w(y,m,1)\). Тогда переход к следующему месяцу даёт
$$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7,$$
а переход к первому января следующего года даёт
$$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7.$$
Это не новая техника, а та же формула суммирования дней, только записанная в пошаговом виде.
Поскольку 1900 год не високосный, в нём \(365\) дней, и потому
$$s_{1901,1}\equiv 365\equiv 1\pmod 7,$$
то есть 1901-01-01 был вторником. Дальше последовательность первых чисел месяцев такова:
1 января вторник, 1 февраля пятница, 1 марта пятница, 1 апреля понедельник, 1 мая среда, 1 июня суббота, 1 июля понедельник, 1 августа четверг, 1 сентября воскресенье, 1 октября вторник, 1 ноября пятница, 1 декабря воскресенье.
Значит, 1901 год даёт ровно два подходящих месяца. Если продолжить тот же подсчёт до декабря 2000 года, получится итог \(S=171\).
Реализации на C++, Python и Java напрямую используют формулу накопленных дней. Для каждого первого числа месяца в целевом интервале программа сначала суммирует длины всех полных лет от 1900 до предыдущего года, затем добавляет длины уже завершившихся месяцев текущего года и после этого берёт остаток по модулю \(7\).
Внешний цикл перебирает все годы из заданного включительного интервала и все двенадцать месяцев внутри каждого года. Если код дня недели для \((y,m,1)\) равен \(6\), счётчик ответа увеличивается на единицу.
В коде есть и небольшие контрольные проверки: 1900-01-01 должен быть понедельником, 1901-01-01 должен быть вторником, а в 1901 году должно быть ровно два месяца, начинающихся с воскресенья.
Пусть \(Y\) обозначает число лет в рассматриваемом интервале. Кандидатных месяцев всего \(12Y\), но для каждого из них вычисление дня недели заново суммирует дни от эпохи 1900 года. Поэтому суммарная стоимость по всем годам оказывается квадратичной:
$$12\sum_{t=1}^{Y} t = O(Y^2).$$
Вклад суммирования месяцев внутри одной даты даёт в сумме только \(O(Y)\), а дополнительная память равна \(O(1)\). Для столетнего диапазона из задачи это совсем немного, хотя чисто рекуррентная версия могла бы работать за \(O(Y)\).
التواريخ التي نهتم بها هي جميع التواريخ من الشكل \((y,m,1)\) حيث \(1901 \le y \le 2000\) و\(1 \le m \le 12\). أي إن لدينا 1200 تاريخاً يمثّل كل واحد منها اليوم الأول من شهر ما. المطلوب هو عدّ كم واحد من هذه التواريخ يقع يوم أحد، مع اعتماد قاعدة السنوات الكبيسة في التقويم الغريغوري، ومع المعلومة المعطاة بأن 1900-01-01 كان يوم اثنين.
إذن المسألة ليست بحثاً مفتوحاً في فضاء كبير، بل هي حساب منظم على مجموعة محددة جداً من التواريخ. ما نحتاجه حقاً هو حساب عدد الأيام المنقضية من تاريخ مرجعي معلوم.
تعتمد الحلول الثلاثة على فكرة واحدة: يوم الأسبوع يتحدد بالكامل من خلال عدد الأيام المنقضية بترديد \(7\). ما إن نعرف هذا العدد حتى يصبح تحديد الأحد مسألة مباشرة.
نرمّز أيام الأسبوع بالأعداد من \(0\) إلى \(6\)، مع اعتبار الاثنين \(=0\) والأحد \(=6\).
إذا كان تاريخ ما يأتي بعد 1900-01-01 بمقدار \(\Delta\) يوم، فإن رمزه الأسبوعي يساوي \(\Delta \bmod 7\)، لأن الانتقال يوماً واحداً إلى الأمام يزيد الرمز بمقدار واحد داخل \(\mathbb{Z}/7\mathbb{Z}\).
لنعرّف دالة السنة الكبيسة بالصيغة
$$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y,\ 100\nmid y,\\0,&\text{otherwise}.\end{cases}$$
وعندها يكون طول السنة \(y\) هو \(365+\lambda(y)\) يوماً. أما أطوال الأشهر فنكتبها على الشكل
$$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}.$$
الشهر الوحيد الذي يتغير هو فبراير، إذ يساوي \(28\) يوماً في السنة العادية و\(29\) في السنة الكبيسة.
لكل تاريخ \((y,m,d)\)، يكون عدد الأيام المنقضية منذ 1900-01-01 هو
$$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1).$$
ومن ثم فإن رمز يوم الأسبوع يحقق
$$w(y,m,d)\equiv D(y,m,d)\pmod 7.$$
في هذه المسألة لا نحتاج إلا إلى الحالة \(d=1\). وإذا عرّفنا دالة المؤشر
$$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{otherwise},\end{cases}$$
فإن العدد المطلوب هو
$$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m).$$
يمكن كتابة الفكرة نفسها بصيغة تزايدية. لنضع \(s_{y,m}=w(y,m,1)\). عند الانتقال من أول شهر إلى أول الشهر التالي نضيف طول الشهر الحالي بالكامل، ولذلك
$$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7.$$
وعند الانتقال إلى أول يناير من السنة التالية نحصل على
$$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7.$$
هذه ليست طريقة مختلفة، بل هي الصيغة نفسها لعدّ الأيام ولكن مكتوبة كتحديث شهري مباشر.
بما أن سنة 1900 ليست كبيسة، فطولها \(365\) يوماً، وبالتالي
$$s_{1901,1}\equiv 365\equiv 1\pmod 7,$$
أي إن 1901-01-01 كان يوم ثلاثاء. وإذا تقدمنا شهراً بعد شهر نحصل على السلسلة التالية:
1 يناير ثلاثاء، 1 فبراير جمعة، 1 مارس جمعة، 1 أبريل اثنين، 1 مايو أربعاء، 1 يونيو سبت، 1 يوليو اثنين، 1 أغسطس خميس، 1 سبتمبر أحد، 1 أكتوبر ثلاثاء، 1 نوفمبر جمعة، 1 ديسمبر أحد.
إذن سنة 1901 تعطي شهرين فقط يبدأان بيوم أحد. وعند متابعة العد بالطريقة نفسها حتى ديسمبر 2000 نحصل على المجموع النهائي \(S=171\).
تطبّق نسخ C++ وPython وJava صيغة الأيام المنقضية كما هي. فلكل يوم أول من شهر داخل الفترة المطلوبة، يجمع التنفيذ أولاً أطوال كل السنوات الكاملة من 1900 حتى السنة السابقة، ثم يجمع أطوال الأشهر المكتملة داخل السنة الحالية، ثم يأخذ الباقي بترديد \(7\).
تقوم حلقة خارجية بالمرور على جميع السنوات في المجال الشامل وعلى الأشهر الاثني عشر في كل سنة. وإذا كان رمز يوم الأسبوع للتاريخ \((y,m,1)\) يساوي \(6\)، فهذا يعني أن التاريخ يوم أحد، وعندها يزاد العداد.
كما تتضمن الحلول اختبارات تحقق صغيرة لكنها مهمة: 1900-01-01 يجب أن يكون يوم اثنين، و1901-01-01 يجب أن يكون يوم ثلاثاء، وسنة 1901 يجب أن تحتوي على حالتين فقط من نوع "أول الشهر يوم أحد".
إذا رمزنا بعدد السنوات في المجال بـ \(Y\)، فلدينا \(12Y\) شهراً مرشحاً. لكن كل حساب ليوم الأسبوع يعيد بناء مجموع الأيام ابتداءً من سنة 1900، ولذلك يصبح مجموع العمل الكلي من رتبة تربيعية:
$$12\sum_{t=1}^{Y} t = O(Y^2).$$
أما جزء جمع الأشهر داخل كل تاريخ فلا يضيف إلا \(O(Y)\) على المستوى الكلي، واستهلاك الذاكرة هو \(O(1)\). وبالنسبة لفترة Project Euler ذات المئة سنة فهذه الكلفة صغيرة جداً عملياً، رغم أن تنفيذًا تزايديًا خالصاً كان يمكن أن يصل إلى \(O(Y)\).