Antwoord: 68323018645
We kunnen alle getallen van 0 tot 1000000 overlopen en kijken welke er aan de voorwaarden voldoen:
68323018645 68323018645 |
Alternatief. De gezochte getallen zijn wel deelbaar zijn door 7, maar niet door 23 (en telkens kleiner dan 1000000). Dan is het duidelijk dat dit de getallen zijn die deelbaar zijn door 7, maar niet door $7\cdot 23$. De som van alle zevenvouden kunnen we berekenen met een rekenkundige rij, waarvan de eerste term 0 is en de laatste $i$, met $i$ het grootste zevenvoud kleiner dan 1000000. Analoog voor de $7\cdot 23$-vouden. Daaruit volgt:
68323018645 68323018645 |
Antwoord: 5478676
We herschrijven de vergelijking als een kwadratische vergelijking in $x$:
$x^2 +x(2y-2012)+y^2+4024y=0$. Deze vergelijking heeft discriminant $D=4^2503^2\left(1-\frac{3y}{503}\right)$. $x$ en $y$ kunnen dus enkel geheel zijn als $y=-530k$, met $k\geq0$ geheel, en dan is $x=503(2+k\pm\sqrt{1+3k})$.
Definieer $s=\sqrt{1+3k}$, we vinden een bovengrens voor $s$ in functie van $n$ (=$300000$) door $503(2+k+2s)=n$ op te lossen, en hierna kunnen we de som berekenen.
5478676 5478676 |
Alternatief:
Stel $a=x+y$ en $b=x-2y$. Dan geldt $x=\frac{2a+b}{3}$ en $y=\frac{a-b}{3}$ en wordt de vergelijking $a^2=2012b$. Merk op dat $(x,y)$ een gehele oplossing is als en slechts als $(a,b)$ een gehele oplossing is met $2a+b$ deelbaar door $3$. De gehele oplossingen van $a^2=2012b$ zijn de koppels $(a,\frac{a^2}{2012})$ met $a$ en $\frac{a^2}{2012}$ geheel. Dit laatste is het geval als en slechts als a deelbaar is door $1006$, dus we kunnen stellen dat $a=1006c$, zodat we de oplossingen kunnen schrijven als $(1006c,503c^2)$. Samen met $x=\frac{2a+b}{3}$ vinden we dat de gezochte som de som is van alle $\frac{2012c+503c^2}{3}$, met $c$ geheel, $2012c+503c^2$ deelbaar door $3$, en $|\frac{2012c+503c^2}{3}|<300000$.
5478676 5478676 |
Antwoord: 3896
Na wat proberen kunnen we vermoeden dat $f(n) \equiv n+1 \pmod{6037}$ voor $n \in \{1,...,3018\}$ en $f(3019) \equiv 1 \pmod{6037}$. We kunnen dit door sage laten controleren:
|
|
1 CPU time: 94.23 s, Wall time: 94.39 s 1 CPU time: 94.23 s, Wall time: 94.39 s |
Nu volgt dat $a_i$, opgevat als element van $\operatorname{GF}(6037)$, gelijk is aan $i\,\mathrm{mod}\,3019$. Schrijven we $100010000001000000000=3019q+r$, vinden we dat het gezochte getal (nog steeds opgevat als element van $\operatorname{GF}(6037)$) gelijk is aan $(3019!)^q\cdot r!$. Rekening houdend met $(3019!)^{6036}\equiv 1$ kunnen we nu het antwoord berekenen:
3896 3896 |
Antwoord: 17
We zoeken eerst de maximale oneven lengte: loop alle mogelijke palindromen van lengte 3 af, en zoek deze in de lijst met cijfers van $(2012^{2012})^{2012}$. Als je er één vindt, kijk dan of de twee cijfers er links en rechts van ook gelijk zijn, indien ja vinden we een palindroom van lengte 5 en kijken we ook naar de cijfers daar rond, enzovoort. De maximale even lengte vinden we analoog (begin met alle mogelijke palindromen met lengte 2).
17 17 |
Alternatief kunnen we de hele lijst van cijfers van $(2012^{2012})^{2012}$ overlopen, en (analoog als hierboven) rond elk van deze cijfers een zolang mogelijk palindroom proberen bouwen. Voor de even palindromen overlopen we dan alle koppels van opeenvolgende getallen, en indien ze gelijk zijn proberen we er een langer palindroom rond te bouwen. Deze aanpak kost wel een pak meer rekentijd (een kleine 3 minuten in totaal).
17 17 |
Antwoord: 3033576902
Zij $l_n$ de lengte van $a_n$. Men kan vinden dat $l_n$ recursief gedefiniëerd is als volgt:
\[ \begin{aligned} l_1 &= 2 \\ l_2 &= 4 \\ l_3 &= 7 \\ l_4 &= 11 \\ l_5 &= 14 \\ l_k &= \begin{cases} l_{k-1} + l_{k-3} + 1 & \text{als $k>5$ even is,}\\ l_{k-1} + l_{k-3} & \text{ als $k>5$ oneven is}\end{cases}\end{aligned} \]
3033576902 CPU time: 1.48 s, Wall time: 1.49 s 3033576902 CPU time: 1.48 s, Wall time: 1.49 s |
Het gaat iets sneller als we niet alle tussenresultaten bijhouden:
3033576902 CPU time: 0.46 s, Wall time: 0.46 s 3033576902 CPU time: 0.46 s, Wall time: 0.46 s |
Door in een $a_i$ tussen elke "$01$" een streep te zetten, verdelen we de $a_n$ in stukjes die we atomen zullen noemen. Een atoom wordt steeds omgezet in één of meerdere atomen, en waarin een atoom wordt omgezet hangt niet af wat er voor of na komt. We kunnen de atomen oplijsten; er zijn er 10:
| Nr. | Atoom | Lengte |
Wordt omgezet in nrs. |
| 1 | 1 | 1 | 2 |
| 2 | 11 | 2 | 3,1 |
| 3 | 10 | 2 | 5 |
| 4 | 110 | 3 | 3,4 |
| 5 | 1110 | 4 | 6 |
| 6 | 11110 | 5 | 7,4 |
| 7 | 100 | 3 | 9 |
| 8 | 1100 | 4 | 3,8 |
| 9 | 11100 | 5 | 10 |
| 10 | 111100 | 6 | 7,8 |
We kunnen het aantal atomen van elke soort in een $a_n$ voorstellen door een vector $v_n$ met lengte 10. Dan is $v_{n+1}=Tv_{n}$, met $T$ de matrix met een $1$ op $(i,j)$ als en slechts als atoom $i$ wordt omgezet in atoom $j$. Samen met $v_2=(0,1,1,0,0,0,0,0,0,0)$ laat dit ons toe om $v_{221112}$ te berekenen, waaruit we eenvoudig de lengte van $a_{221112}$ kunnen halen.
3033576902 CPU time: 0.41 s, Wall time: 0.41 s 3033576902 CPU time: 0.41 s, Wall time: 0.41 s |
Antwoord: 1032069286
Als $m=\prod_{i=1}^l{p_i^{e_i}}$, dan is $\phi(m)=n \iff \prod_{i=1}^l{(p_i-1)p_i^{e_i-1}}=n$. De mogelijke priemfactoren van $m$ zijn dus de priemgetallen $p$ met de eigenschap dat $n$ deelbaar is door $p-1$, en deze priemgetallen kunnen we gemakkelijk oplijsten (we noteren $p_1>p_2>\ldots >p_l$). We zullen nu een lijst opstellen met alle mogelijke waarden van m. Dit kunnen we recursief doen: als $p_i$ de grootste priemfactor van $m$ is, zijn de mogelijke waarden van $\frac{m}{p_i}$ bepaald door de oplossingen van $p_i^{e_i-1}\prod_{j=i+1}^l{(p_j-1)p_j^{e_j-1}}=\frac{n}{p_i-1}$. Dit aantal kunnen we dan recursief bepalen, zoals hieronder uitgewerkt. $\phi^{-1}_k{(n)}$ vinden we dan door de gevonden lijst met $m$-waarden te sorteren en het $k$-de element te nemen.
|
|
1032069286 CPU time: 14.04 s, Wall time: 14.07 s 1032069286 CPU time: 14.04 s, Wall time: 14.07 s |