Symmetrische eenheden van ℤC₇

Geplaatst op 4 september 2026 door admin

Voor $C_7=\langle g\rangle$ geldt

$\mathbb QC_7\cong\mathbb Q\oplus\mathbb Q(\zeta_7), \qquad \mathbb QC_7^+\cong\mathbb Q\oplus\mathbb Q(\alpha),$

waar $\alpha=\zeta_7+\zeta_7^{-1}$ voldoet aan

$\alpha^3+\alpha^2-2\alpha-1=0.$

De integrale orde. In $\mathbb Z\oplus\mathbb Z[\alpha]$ komt $\mathbb ZC_7^+$ overeen met

$A=\bigl\{(m,u+v\alpha+w\alpha^2)\mid m\equiv u+2v+4w\pmod7\bigr\}.$

Met $\eta_1=\alpha^2+\alpha-1$ en $\eta_2=\alpha+1$ geldt

$\mathbb Z[\alpha]^\times=\{\pm\eta_1^m\eta_2^n\mid m,n\in\mathbb Z\}.$

Voor genormaliseerde symmetrische eenheden selecteert de congruentie de deelgroep

$H=\operatorname{ev}_2^{-1}(1), \qquad \operatorname{ev}_2(u+v\alpha+w\alpha^2)=u+2v+4w\pmod7.$

De projectie $\rho_2$ geeft $U_1(\mathbb ZC_7)^+\cong H$ . In plaats van de generatoren van $H$ abstract te zoeken, nemen we de trinomiale eenheden

$x_1=-1+g+g^{-1},\qquad x_2=-1+g^2+g^{-2}.$

Hun beelden $\eta_1^{-1}\eta_2^{-1}$ en
$-\eta_1^2\eta_2^{-1}$ zijn multiplicatief onafhankelijk en genereren
heel $H$ .

Structuurfiguur voor de congruentiedeelgroep H bij C7

Eindresultaat

$U_1(\mathbb ZC_7)^+=\langle-1+g+g^{-1},-1+g^2+g^{-2}\rangle.$

Volledige uitwerking (PDF)
Computationele controle (PDF)
Scripts downloaden

Blokken bepaald door de grootste frequentie

Geplaatst op 31 augustus 2026 door admin

De eerste 2026 functiewaarden mogen volledig willekeurig zijn. Toch dwingt het voorschrift daarna steeds langere blokken van gelijke waarden af. De lengte van zo’n blok levert precies de afstand die in de gevraagde gelijkheid voorkomt.

Infobox

Onderwerpen: Functies, combinatoriek, rijen
Probleemoplossingstechnieken: Kleine gevallen onderzoeken, frequenties tellen, blokken herkennen, invariant gebruiken
Moeilijkheid: Moeilijk
Competitie: Indian National Mathematical Olympiad, finale
Jaar: 2026
Opgavenummer: 2

Opgave

Laat $f:\mathbb N\to\mathbb N$ een functie zijn met de volgende eigenschap: voor elke $k>2026$ is $f(k)$ gelijk aan het grootste aantal keer dat een getal voorkomt in de lijst

$f(1),f(2),\ldots,f(k-1).$

Bewijs dat voor oneindig veel $n\in\mathbb N$ geldt

$f(n)=f(n+f(n)).$

Hierbij is $\mathbb N=\{1,2,3,\ldots\}$ de verzameling van de positieve gehele getallen.

Eerste idee

Vervang $2026$ eerst door $4$ . Na vier willekeurige beginwaarden wordt telkens de huidige grootste frequentie toegevoegd. Zodra die frequentie $m$ is, blijft de waarde $m$ verschijnen totdat de grootste frequentie $m+1$ wordt. Voor alle voldoende grote $m$ levert dit een blok van precies $m+1$ gelijke waarden op.

Observatieronde

Een kleine versie met drempel 4

De eerste $2026$ functiewaarden mogen willekeurig zijn. Om het voorschrift zichtbaar te maken, vervangen we $2026$ tijdelijk door $4$ en kiezen we bijvoorbeeld

$f(1),f(2),f(3),f(4)=2,1,2,7.$

In deze lijst komt $2$ tweemaal voor; geen enkel getal komt vaker voor. Daarom is $f(5)=2$ . Nu komt $2$ driemaal voor, zodat $f(6)=3$ . Het getal $3$ kwam nog niet voor en moet vervolgens viermaal worden toegevoegd voordat zijn frequentie $4$ wordt. Daarna wordt $4$ vijfmaal toegevoegd en $5$ zesmaal. De vier beginwaarden zijn zwart; alle waarden die het voorschrift daarna toevoegt, zijn rood:

$2,1,2,7\mid$
$2\mid \underbrace{3,3,3,3}_{4\text{ keer}}\mid \underbrace{4,4,4,4,4}_{5\text{ keer}}\mid \underbrace{5,5,5,5,5,5}_{6\text{ keer}}\mid \underbrace{6,6,6,6,6,6,6}_{7\text{ keer}}\mid\cdots$

In het blok met vier drieën werkt de eerste positie $n=6$ :

$f(6)=3=f(9)=f(6+f(6)).$

In het volgende blok werkt de eerste positie $n=10$ , want $f(10)=4=f(14)$ . Ook $n=15$ en $n=21$ werken. De beginwaarde $7$ zorgt later voor een uitzondering: het blok met zevens loopt van positie $28$ tot en met $34$ en is dus één plaats te kort. Het volledige blok met achten begint op positie $35$ . Elk volgend volledig blok met waarde $m$ begint $m$ plaatsen na het begin van het vorige blok; daaruit volgt dat zijn beginpositie $\frac{m(m+1)}2-1$ is. In dit voorbeeld zijn alle oplossingen daarom

$\boxed{n\in\{1,3,6,10,15,21\}\ \text{ of }\ n=\frac{m(m+1)}2-1\text{ voor }m\geq8.}$

De waarden $n=1$ en $n=3$ komen toevallig uit de gekozen beginwaarden. Het algemene bewijs hoeft zulke vroege toevalligheden niet te beschrijven: het moet aantonen dat er na willekeurige beginwaarden altijd oneindig veel volledige blokken ontstaan.

Twee voorbeelden met drempel 5

Eerst nemen we vijf verschillende beginwaarden: $1,2,3,4,5$ .

Posities	Waarden	Wat gebeurt er?
$1$ – $5$	$1,2,3,4,5$	vijf verschillende beginwaarden
$6$ – $20$	$1,2,2,3,3,3,4,4,4,4,5,5,5,5,5$	elk getal $1$ tot en met $5$ kwam al eenmaal voor; zijn rode blok is daardoor te kort
$21$ – $27$	$6,6,6,6,6,6,6$	$6$ is nieuw, dus dit is een volledig blok van $7$ zessen

Hier werkt $n=21$ , want $f(21)=6=f(27)=f(21+6)$ . Daarna zijn ook alle volgende blokken volledig.

Neem nu als beginwaarden $2,2,2,5,6$ .

Posities	Waarden	Wat gebeurt er?
$1$ – $5$	$2,2,2,5,6$	de grootste frequentie is $3$
$6$ – $9$	$3,3,3,3$	volledig blok; $n=6$ werkt
$10$ – $14$	$4,4,4,4,4$	volledig blok; $n=10$ werkt
$15$ – $19$	$5,5,5,5,5$	te kort, want er stond al een $5$ bij de beginwaarden
$20$ – $25$	$6,6,6,6,6,6$	te kort, want er stond al een $6$ bij de beginwaarden
$26$ – $33$	$7,7,7,7,7,7,7,7$	weer een volledig blok; $n=26$ werkt

Dit voorbeeld toont waarom we in het algemene bewijs alleen naar waarden kijken die groter zijn dan alle beginwaarden.

De juiste grootheid

Voor $k\geq1$ en $a\in\mathbb N$ noteren we met

$c_k(a)=\bigl|\{i\in\{1,\ldots,k\}:f(i)=a\}\bigr|$

het aantal voorkomens van $a$ onder de eerste $k$ functiewaarden. Verder stellen we

$M_k=\max_{a\in\mathbb N}c_k(a).$

Dit maximum bestaat, want in een eindige lijst komen slechts eindig veel verschillende waarden voor. Het gegeven voorschrift wordt nu

$f(k+1)=M_k\qquad(k\geq2026).$

Uitwerking

Stap 1: de grootste frequentie loopt door alle volgende getallen

Wanneer één nieuwe functiewaarde aan de lijst wordt toegevoegd, neemt precies één frequentie met $1$ toe. Daarom geldt voor iedere $k\geq1$

$M_k\leq M_{k+1}\leq M_k+1.$

Stel nu dat $k\geq2026$ en $M_k=m$ . Zolang het maximum gelijk blijft aan $m$ , schrijft het voorschrift telkens opnieuw de waarde $m$ voor. De frequentie van $m$ neemt dus bij elke volgende stap met $1$ toe.

Op het tijdstip $k$ komt het getal $m$ hoogstens $m$ keer voor. Door telkens opnieuw $m$ toe te voegen, komt $m$ na precies

$m+1-c_k(m)$

nieuwe stappen voor het eerst $m+1$ keer voor. Dan wordt de grootste frequentie $m+1$ . Zo gaat de grootste frequentie na een eindig aantal stappen van $m$ naar $m+1$ , zonder een getal over te slaan.

Stap 2: alle voldoende grote waarden vormen volledige blokken

Stel

$r=M_{2026}$

en laat $B$ de grootste waarde onder $f(1),\ldots,f(2026)$ zijn. Uit stap 1 volgt dat de maximale frequentie vanaf $r$ achtereenvolgens de waarden

$r,r+1,r+2,\ldots$

aanneemt.

Neem een geheel getal $m>\max\{B,r\}$ , en laat $t_m$ de eerste index $k\geq2026$ zijn waarvoor $M_k=m$ . Het getal $m$ is dan nog nooit als functiewaarde voorgekomen:

het kwam niet onder de eerste $2026$ waarden voor, want $m>B$ ;
na de eerste $2026$ posities werden vóór het bereiken van maximale frequentie $m$ alleen de waarden $r,r+1,\ldots,m-1$ toegevoegd.

Dus $c_{t_m}(m)=0$ . Vanaf de volgende positie schrijft het voorschrift steeds $m$ . Pas na $m+1$ kopieën komt $m$ precies $m+1$ keer voor en stijgt de grootste frequentie. We krijgen dus het volledige blok

$f(t_m+1)=f(t_m+2)=\cdots=f(t_m+m+1)=m.$

Stap 3: kies de eerste positie van elk volledig blok

Voor ieder $m>\max\{B,r\}$ kiezen we

$n=t_m+1.$

Deze $n$ is de eerste positie van het blok. De laatste positie ligt $m$ plaatsen verder. Omdat $f(n)=m$ , is

$n+f(n)=t_m+1+m=t_m+m+1,$

de laatste positie van hetzelfde blok. Daarom geldt

$f(n)=m=f(n+f(n)).$

Er zijn oneindig veel gehele getallen $m>\max\{B,r\}$ , en hun blokken hebben verschillende eerste posities. We vinden zo oneindig veel verschillende positieve gehele getallen $n$ waarvoor

$\boxed{f(n)=f(n+f(n))}.$

Probleemoplossingstechnieken

Kleine gevallen onderzoeken: De drempel $4$ toont hoe opeenvolgende blokken ontstaan.
Frequenties tellen: De aantallen $c_k(a)$ vertalen het voorschrift naar precieze notatie.
Blokken herkennen: Zodra het maximum $m$ is, wordt uitsluitend $m$ toegevoegd totdat de maximale frequentie stijgt.
Invariant gebruiken: De maximale frequentie daalt nooit en stijgt per stap met hoogstens $1$ .

Bron

40th Indian National Mathematical Olympiad, 18 januari 2026. © Indian National Mathematical Olympiad.

Project Euler 008 – Grootste product in een reeks

Geplaatst op 29 augustus 2026 door admin

Probleemstelling

In het gegeven getal van 1000 cijfers hebben de vier opeenvolgende cijfers met het grootste product het product $9\cdot9\cdot8\cdot9=5832$ .

Bepaal het grootste product van dertien opeenvolgende cijfers in dat getal.

Eerste analyse

Een string van 1000 cijfers bevat $1000-13+1=988$ delen van dertien opeenvolgende cijfers. We bekijken elk deel en bewaren het grootste product. Er is voor deze opgave geen aparte wiskundige formule nodig.

We vergelijken een rechtstreekse aanpak met een variant die een deel overslaat zodra het een nul bevat. Een product met een factor nul kan immers nooit groter worden dan een reeds gevonden positief product.

Een stringdeel omzetten

Met slicing halen we dertien tekens uit de string:

deel = getal[begin : begin + 13]

int(deel) zou van bijvoorbeeld "7316" het getal 7316 maken. Wij willen echter $7\cdot3\cdot1\cdot6$ berekenen. Daarom doorlopen we het deel teken per teken:

product = 1

for teken in deel:
    product *= int(teken)

Een afzonderlijk teken zoals "7" is aanvankelijk tekst. int(teken) zet het om in het gehele getal 7, waarna het kan worden vermenigvuldigd. Het product begint bij 1, het neutrale element van de vermenigvuldiging.

Vergelijking van de methoden

De eerste methode zet voor ieder deel alle dertien tekens om en vermenigvuldigt ze. De tweede methode gebruikt eerst:

if "0" in deel:
    continue

Een deel met een nul wordt dan onmiddellijk overgeslagen. Van de 988 delen bevatten er 731 een nul; in deze invoer kan de tweede methode dus veel werk vermijden. Daar staat tegenover dat de nultest zelf ook tijd kost en dat delen zonder nul tweemaal worden doorlopen.

Om toevallige schommelingen bij zo’n kort programma te beperken, voert het programma elke methode 1.000 keer uit en rapporteert het de gemiddelde uitvoeringstijd. De precieze verhouding is afhankelijk van de computer en Python-versie.

Gemeenschappelijke gegevens

Beide programma’s gebruiken dezelfde variabele getal, die de 1000 cijfers als één aaneengesloten string bevat. In Python worden opeenvolgende strings tussen haakjes automatisch samengevoegd. De volledige invoer hoeft daardoor niet op één onleesbaar lange regel te staan.

getal = (
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450"
)

Programma 1 – Altijd dertien cijfers vermenigvuldigen

Dit eerste programma berekent voor elk van de 988 delen het volledige product, ook wanneer een van de cijfers nul is.

import time


def grootste_product(reeks, lengte):
    grootste = 0

    for begin in range(len(reeks) - lengte + 1):
        deel = reeks[begin : begin + lengte]
        product = 1

        for teken in deel:
            product *= int(teken)

        if product > grootste:
            grootste = product

    return grootste


# Meet 1.000 uitvoeringen en bereken het gemiddelde
starttijd = time.perf_counter()

for _ in range(1_000):
    antwoord = grootste_product(getal, 13)

gemiddelde_tijd = (time.perf_counter() - starttijd) / 1_000

print(f"Het grootste product is: {antwoord}")
print(f"Gemiddelde uitvoeringstijd: {gemiddelde_tijd:.8f} seconden")

Programma 2 – Delen met een nul overslaan

Het tweede programma controleert elk deel eerst op een nul. Alleen wanneer er geen nul aanwezig is, worden de dertien cijfers naar gehele getallen omgezet en vermenigvuldigd.

import time


def grootste_product_zonder_nul(reeks, lengte):
    grootste = 0

    for begin in range(len(reeks) - lengte + 1):
        deel = reeks[begin : begin + lengte]

        if "0" in deel:
            continue

        product = 1
        for teken in deel:
            product *= int(teken)

        if product > grootste:
            grootste = product

    return grootste


# Meet 1.000 uitvoeringen en bereken het gemiddelde
starttijd = time.perf_counter()

for _ in range(1_000):
    antwoord = grootste_product_zonder_nul(getal, 13)

gemiddelde_tijd = (time.perf_counter() - starttijd) / 1_000

print(f"Het grootste product is: {antwoord}")
print(f"Gemiddelde uitvoeringstijd: {gemiddelde_tijd:.8f} seconden")

Beide methoden hebben tijdscomplexiteit $O(nk)$ voor een reeks van $n$ cijfers en delen van lengte $k$ . Voor de vaste waarde $k=13$ is dit $O(n)$ . De nultest verbetert niet de theoretische grootteorde, maar kan wel de werkelijke uitvoeringstijd verkorten.

Concrete tijdsvergelijking

Op dezelfde computer en met telkens 1.000 uitvoeringen werden de volgende gemiddelde tijden gemeten:

Methode	Gemiddelde tijd per uitvoering
Altijd dertien cijfers vermenigvuldigen	0,00116562 seconden
Eerst controleren op een nul	0,00039123 seconden

De verhouding is

$\frac{0{,}00116562}{0{,}00039123}\approx 2{,}98.$

De methode met nultest was bij deze meting dus ongeveer 2,98 keer zo snel. Anders uitgedrukt: de gemiddelde uitvoeringstijd daalde met ongeveer

$\left(1-\frac{0{,}00039123}{0{,}00116562}\right)\cdot100\%\approx66{,}4\%.$

De precieze tijden kunnen bij een volgende uitvoering verschillen door de computer, de Python-versie en andere actieve processen. De vergelijking blijft hier inhoudelijk zinvol omdat beide methoden onder dezelfde omstandigheden en even vaak werden uitgevoerd.

Resultaat

Beide programma’s geven als grootste product

$\boxed{23514624000}.$

Besluit

De rechtstreekse methode is het eenvoudigst, maar voert ook veel overbodige omzettingen en vermenigvuldigingen uit. De nultest is een kleine, duidelijke optimalisatie die gebruikmaakt van de eigenschap dat een product met nul altijd nul is. Omdat 731 van de 988 delen een nul bevatten, leverde deze aanpak in de concrete meting een snelheidswinst van ongeveer factor 2,98 op.

Nootje 78

Geplaatst op 28 augustus 2026 door admin

Antwoord

we veralgemenen de opgave een beetje, want we vermoeden dat 255 en 256 geen specifiek belang hebben.
Wel zijn het opeenvolgende waarden en kunnen we ze voorstellen door x-1 en x.
Dan is $f(x-1)=x^2-x+1$ .
Maar dan is $f(x-1).f(x)=x^4+x^2+1=f(x^2)$ . Bijgevolg is de gezochte $n=256=2^{16}$ .
De som der delers is dan $1+2+2^2+\cdots+2^{16}=2^{17}-1$ .

Symmetrische eenheden van ℤC₅

Geplaatst op 26 augustus 2026 door admin

Voor $C_5=\langle g\rangle$ splitst de rationale groepsalgebra als

$\mathbb QC_5\cong\mathbb Q\oplus\mathbb Q(\zeta_5).$

Voor de symmetrische elementen wordt de cyclotomische component vervangen door haar maximale reële deelveld:

$\mathbb QC_5^+\cong\mathbb Q\oplus\mathbb Q(\alpha), \qquad \alpha=\zeta_5+\zeta_5^{-1}, \qquad \alpha^2+\alpha-1=0.$

De integrale orde. In $\mathbb Z\oplus\mathbb Z[\alpha]$ komt $\mathbb ZC_5^+$ overeen met

$A=\bigl\{(m,u+v\alpha)\mid m\equiv u+2v\pmod 5\bigr\}.$

De componentorde heeft eenhedengroep

$\mathbb Z[\alpha]^\times=\{\pm(1+\alpha)^n\mid n\in\mathbb Z\}.$

De torsievrije rang is $1$ . Voor genormaliseerde symmetrische eenheden moet de triviale component gelijk zijn aan $1$ . Daardoor selecteert de congruentie de deelgroep

$H=\bigl\{u+v\alpha\in\mathbb Z[\alpha]^\times\mid u+2v\equiv1\pmod5\bigr\}.$