For each prime
$$p\in[10^7,2\cdot 10^7),$$
we form its digital-root chain
$$n_0=p,\qquad n_{i+1}=s(n_i),$$
until a single digit is reached. Two seven-segment clocks display this chain:
Sam always turns everything off and then lights the next number from scratch.
Max only toggles the segments that actually change.
We must sum
$$\Delta(p)=C_{\text{Sam}}(p)-C_{\text{Max}}(p)$$
over all primes in the interval.
1) Seven-segment bitmasks.
Each digit \(d\in\{0,\dots,9\}\) is encoded by a 7-bit mask \(M_d\). For example, in the segment convention used by the code, digit \(1\) has 2 lit segments, digit \(7\) has 4, digit \(8\) has 7, and so on.
Let
$$\sigma(d)=\operatorname{popcount}(M_d)$$
be the number of lit segments in one digit. For a whole number \(n\) with decimal digits \(d_j\), define
$$\Sigma(n)=\sum_j \sigma(d_j).$$
This is the cost of lighting \(n\) from a blank display, and also the cost of turning \(n\) fully off.
2) Sam's cost.
Sam never tries to reuse lit segments. If the chain is
$$n_0\to n_1\to\cdots\to n_t,$$
then each displayed value contributes once to turn it on and once to turn it off. Therefore
$$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i).$$
3) Max's cost as a Hamming distance.
To go directly from number \(a\) to number \(b\), Max flips only the segments whose states differ. Align the numbers by decimal place from the right; missing digits are treated as a blank digit with mask \(0\), not as the numeral \(0\).
Thus the transition cost is
$$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j}),$$
where an absent digit contributes mask \(0\).
This is exactly the bitwise Hamming distance between the two displayed numbers.
4) Max's total chain cost.
Max starts from a blank display, walks through the digital-root chain, then returns to blank at the end:
$$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$$
Finally, for one prime we add
$$\Delta(n_0)=C_{\text{Sam}}(n_0)-C_{\text{Max}}(n_0).$$
5) Worked example: \(137\to11\to2\).
The chain is
$$137\to 1+3+7=11\to 1+1=2.$$
Segment counts are
$$\Sigma(137)=\sigma(1)+\sigma(3)+\sigma(7)=2+5+4=11,$$
$$\Sigma(11)=2+2=4,\qquad \Sigma(2)=5.$$
So Sam spends
$$C_{\text{Sam}}=2(11+4+5)=40.$$
For Max, the code computes
$$D(0,137)=11,$$
$$D(137,11)=7,$$
$$D(11,2)=7,$$
$$D(2,0)=5.$$
Hence
$$C_{\text{Max}}=11+7+7+5=30,$$
and therefore
$$\Delta(137)=40-30=10.$$
This is exactly the checkpoint embedded in the C++ solution.
6) Why the chain is tiny in this problem.
All primes lie between \(10^7\) and \(2\cdot10^7\), so they have at most 8 digits. The first digit sum is therefore at most
$$1+7\cdot 9=64.$$
After one application of digit sum, the chain is already at most two digits long. After another application it is at most \(10\), and then immediately a single digit. So each prime contributes only a handful of transitions.
7) Prime accumulation.
The rest of the problem is just iteration over primes in the interval. The code uses a sieve to mark all primes in
$$[10^7,2\cdot10^7),$$
builds the digital-root chain for each prime, and accumulates the difference \(\Delta(p)\).
1) Predefine the 7-segment masks for digits \(0\) through \(9\).
2) Sieve the interval to find all primes.
3) For each prime, build the chain \(p\to s(p)\to s(s(p))\to\cdots\).
4) Compute Sam's cost as
$$2\sum \Sigma(n_i).$$
5) Compute Max's cost using transition XOR distances.
6) Add the difference.
The sieve costs
$$O(B\log\log B)$$
time and
$$O(B)$$
memory for upper bound \(B\). After that, each prime contributes only a tiny constant amount of work because its digital-root chain is extremely short in this range.
The implementation checks:
For \(137\), Sam costs \(40\) and Max costs \(30\).
For a single-digit chain such as \(7\), Sam and Max coincide.
The final answer for the full interval is
$$13625242.$$
Fuer jede Primzahl
$$p\in[10^7,2\cdot10^7)$$
wird die Quersummen-Kette bis zu einer einzelnen Ziffer gebildet. Zwei 7-Segment-Uhren schalten diese Folge verschieden:
Sam schaltet immer komplett aus und wieder an.
Max schaltet nur geaenderte Segmente.
Gesucht ist die Summe von \(C_{\text{Sam}}-C_{\text{Max}}\).
1) Bitmaskenmodell. Jede Ziffer \(d\) besitzt eine 7-Bit-Maske \(M_d\). Mit
$$\sigma(d)=\operatorname{popcount}(M_d)$$
und
$$\Sigma(n)=\sum_j \sigma(d_j)$$
zaehlt man die leuchtenden Segmente einer Zahl.
2) Sams Kosten. Da Sam nie etwas wiederverwendet, gilt fuer eine Kette \(n_0\to\cdots\to n_t\):
$$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i).$$
3) Max als XOR-Distanz. Fehlende Stellen werden als leere Anzeige mit Maske \(0\) behandelt, nicht als Ziffer \(0\). Fuer zwei Zahlen ist die Umschaltkostenfunktion daher
$$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j}).$$
Damit
$$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$$
4) Beispiel \(137\to11\to2\). Hier ist
$$\Sigma(137)=11,\qquad \Sigma(11)=4,\qquad \Sigma(2)=5,$$
also
$$C_{\text{Sam}}=2(11+4+5)=40.$$
Die Max-Uebergaenge sind
$$D(0,137)=11,\quad D(137,11)=7,\quad D(11,2)=7,\quad D(2,0)=5,$$
also
$$C_{\text{Max}}=30.$$
Der Beitrag ist also \(10\).
5) Warum die Ketten kurz sind. Zahlen in diesem Bereich haben hoechstens 8 Stellen, also ist die erste Quersumme hoechstens \(64\). Danach ist man sofort bei hoechstens zwei Stellen, dann bei hoechstens \(10\), dann einstellig. Pro Primzahl ist also nur sehr wenig Arbeit noetig.
Das Primzahlsieb kostet \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Danach ist der Aufwand pro Primzahl praktisch konstant.
Der Code prueft insbesondere \(137\mapsto(40,30)\) fuer Sam/Max. Das Endergebnis lautet
$$13625242.$$
Her asal
$$p\in[10^7,2\cdot10^7)$$
icin dijital kok zinciri kurulur ve iki farkli 7-segment stratejisinin maliyet farki toplanir.
Sam her sayiyi tamamen sondurup siradakini sifirdan yakar.
Max sadece degisen segmentleri cevirir.
1) Bitmask modeli. Her rakam \(d\) icin bir 7-bit maske \(M_d\) vardir. Tek rakamin yanan segment sayisi
$$\sigma(d)=\operatorname{popcount}(M_d)$$
ve bir sayi icin toplam aktif segment sayisi
$$\Sigma(n)=\sum_j \sigma(d_j)$$
olarak tanimlanir.
2) Sam maliyeti. Zincir
$$n_0\to n_1\to\cdots\to n_t$$
ise Sam'in toplam maliyeti
$$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i)$$
olur; cunku her gosteri bir kez yakilir, bir kez de tamamen sondurulur.
3) Max maliyeti neden XOR mesafesi? Max iki sayi arasinda sadece degisen segmentleri cevirir. Basamaklar sagdan hizalanir ve eksik basamaklar “bos” olarak, yani maske \(0\) ile ele alinir; rakam \(0\) degil. Bu nedenle gecis maliyeti
$$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j})$$
olur. Toplam zincir maliyeti de
$$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$$
4) Calisan ornek: \(137\to11\to2\). Zincir
$$137\to 11\to 2$$
seklindedir. Segment sayilari:
$$\Sigma(137)=11,\qquad \Sigma(11)=4,\qquad \Sigma(2)=5.$$
Bu yuzden
$$C_{\text{Sam}}=2(11+4+5)=40.$$
Max icin kodun hesapladigi gecisler:
$$D(0,137)=11,\quad D(137,11)=7,\quad D(11,2)=7,\quad D(2,0)=5.$$
Toplam
$$C_{\text{Max}}=30$$
ve dolayisiyla fark
$$\Delta(137)=10$$
olur.
5) Zincir neden cok kisa? Bu araliktaki sayilar en fazla 8 basamaklidir. Ilk rakam toplami en fazla \(64\) olur. Sonraki adim en fazla iki basamak, bir sonraki en fazla \(10\), sonra tek basamak. Yani her asal icin sadece cok az sayida gecis vardir.
1) Rakam maskelerini sabitle.
2) \([10^7,2\cdot10^7)\) araligindaki asallari elek ile bul.
3) Her asal icin dijital kok zincirini uret.
4) Sam ve Max maliyetlerini yukaridaki formullerle hesapla.
5) Farki toplama ekle.
Elek
$$O(B\log\log B)$$
zaman ve
$$O(B)$$
bellek kullanir. Sonrasi, her asal icin cok kisa bir zincir oldugundan pratikte sabit zamana yakindir.
Kod, \(137\) icin Sam maliyetini \(40\), Max maliyetini \(30\) olarak dogrular. Nihai cevap
$$13625242$$
olarak bulunur.
Para cada primo
$$p\in[10^7,2\cdot10^7),$$
se construye la cadena de raiz digital hasta llegar a una sola cifra. Luego se compara el coste de dos relojes de siete segmentos: Sam y Max.
1) Mascaras de bits. Cada digito \(d\) tiene una mascara \(M_d\) de 7 bits. Definimos
$$\sigma(d)=\operatorname{popcount}(M_d),\qquad \Sigma(n)=\sum_j \sigma(d_j).$$
2) Coste de Sam. Sam apaga completamente el numero anterior y enciende completamente el siguiente. Por eso
$$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i).$$
3) Coste de Max. Max solo cambia los segmentos que difieren. Las cifras ausentes se tratan como pantalla en blanco, con mascara \(0\). Entonces
$$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j}),$$
y
$$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$$
4) Ejemplo \(137\to11\to2\). Se tiene
$$\Sigma(137)=11,\qquad \Sigma(11)=4,\qquad \Sigma(2)=5,$$
de modo que
$$C_{\text{Sam}}=40.$$
Ademas,
$$D(0,137)=11,\quad D(137,11)=7,\quad D(11,2)=7,\quad D(2,0)=5,$$
asi que
$$C_{\text{Max}}=30$$
y el aporte es \(10\).
5) Por que la cadena es corta. En este intervalo los numeros tienen a lo sumo 8 cifras, asi que la primera suma de digitos es como mucho \(64\). Luego ya se cae a dos cifras, despues a lo sumo \(10\), y enseguida a una sola cifra. El trabajo por primo es muy pequeno.
La criba cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. Tras eso, el coste adicional por primo es practicamente constante.
La respuesta final es
$$13625242.$$
对每个素数
$$p\in[10^7,2\cdot10^7),$$
构造它的数根链，直到变成一位数。然后比较两种七段数码管策略 Sam 与 Max 的切换成本。
1) 数字掩码。 每个数字 \(d\) 对应一个 7 位掩码 \(M_d\)。定义
$$\sigma(d)=\operatorname{popcount}(M_d),\qquad \Sigma(n)=\sum_j \sigma(d_j).$$
2) Sam 的成本。 Sam 每次都把旧数字全灭，再把新数字全亮，因此
$$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i).$$
3) Max 的成本。 Max 只切换真正变化的段。缺失位按“空白位”处理，也就是掩码 \(0\)，不是数字 \(0\)。于是
$$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j}),$$
并且
$$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$$
4) 例子 \(137\to11\to2\).
有
$$\Sigma(137)=11,\qquad \Sigma(11)=4,\qquad \Sigma(2)=5,$$
所以
$$C_{\text{Sam}}=40.$$
而 Max 的四次切换分别是
$$11,\ 7,\ 7,\ 5,$$
总计
$$C_{\text{Max}}=30,$$
故差值为 \(10\)。
5) 为什么链很短。 这个区间内的素数最多 8 位，因此第一次数位和至多为 \(64\)。下一步就降到两位数，再下一步至多 \(10\)，随后立刻变成一位数。所以每个素数只会产生很少的转移。
筛法复杂度为 \(O(B\log\log B)\)，空间为 \(O(B)\)。之后每个素数只需极少量常数时间运算。
最终答案为
$$13625242.$$
Для каждого простого
$$p\in[10^7,2\cdot10^7)$$
строится цепочка цифрового корня до одной цифры. Затем сравниваются затраты двух 7-сегментных часов: Sam и Max.
1) Битовые маски цифр. Каждая цифра \(d\) кодируется маской \(M_d\). Пусть
$$\sigma(d)=\operatorname{popcount}(M_d),\qquad \Sigma(n)=\sum_j \sigma(d_j).$$
2) Стоимость Sam. Sam всегда полностью выключает старое число и полностью включает новое, поэтому
$$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i).$$
3) Стоимость Max. Max меняет только те сегменты, которые действительно различаются. Отсутствующие цифры трактуются как пустой разряд с маской \(0\). Тогда
$$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j}),$$
и
$$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$$
4) Пример \(137\to11\to2\). Здесь
$$\Sigma(137)=11,\qquad \Sigma(11)=4,\qquad \Sigma(2)=5,$$
поэтому
$$C_{\text{Sam}}=40.$$
Для Max переходы стоят \(11,7,7,5\), то есть
$$C_{\text{Max}}=30,$$
а разность равна \(10\).
5) Почему цепочка короткая. В этом диапазоне числа имеют не более 8 цифр, значит первая сумма цифр не превосходит \(64\). После этого число уже двузначное, затем не больше \(10\), а потом одноцифровое. Работа на один простой очень мала.
Решето требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. После этого на каждый простой приходится лишь константный объем работы.
Итоговое значение равно
$$13625242.$$
لكل عدد أولي
$$p\in[10^7,2\cdot10^7),$$
نبني سلسلة الجذر الرقمي حتى نصل إلى رقم واحد، ثم نقارن كلفة التبديل بين ساعتين سباعيتي المقاطع: Sam وMax.
1) أقنعة المقاطع. كل رقم \(d\) يملك قناعًا ثنائيًا \(M_d\) من 7 مقاطع. نعرف
$$\sigma(d)=\operatorname{popcount}(M_d),\qquad \Sigma(n)=\sum_j \sigma(d_j).$$
2) كلفة Sam. Sam يطفئ كل شيء ثم يشغل العدد التالي من الصفر، ولذلك
$$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i).$$
3) كلفة Max. Max يبدل فقط المقاطع التي تغيرت. والخانة الناقصة تُعامل كخانة فارغة قناعها \(0\)، لا كرقم \(0\). ومن ثم
$$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j}),$$
و
$$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$$
4) المثال \(137\to11\to2\). هنا
$$\Sigma(137)=11,\qquad \Sigma(11)=4,\qquad \Sigma(2)=5,$$
ومن ثم
$$C_{\text{Sam}}=40.$$
أما Max فيدفع على الترتيب \(11,7,7,5\)، أي
$$C_{\text{Max}}=30,$$
فتكون المساهمة
$$10.$$
5) لماذا السلسلة قصيرة جدًا. الأعداد في هذا المجال لا تتجاوز 8 خانات، لذلك أول مجموع للأرقام لا يتجاوز \(64\). بعد ذلك يصبح العدد من خانتين، ثم لا يتجاوز \(10\)، ثم يصبح خانة واحدة. لذا فالكلفة الإضافية لكل أولي صغيرة جدًا.
المنخل يكلف \(O(B\log\log B)\) زمنًا و\(O(B)\) ذاكرة. بعد ذلك يكون العمل لكل عدد أولي شبه ثابت.
القيمة النهائية هي
$$13625242.$$