Solutia problemei Cuantictiori

"Se asigură că se poate demonstra că numărul de progresii geometrice de lungime k care au prima valoare egală cu n este egal cu cel mai mare număr natural X cu proprietatea că X^k este divizor al lui N."
Pentru demonstraţie vedeţi soluţia problemei nambartiori.

Fie gcd_{exp}(x)=\ cel mai mare divizor comun al exponenţilor din descompunerea în factori primi a lui x.

Vom demonstra mai întai că dacă gcd_{exp}(x)=\ 1, atunci x^y \in \N cu y\in \mathds{Q} numai dacă y se află de asemenea şi în \mathds{N} . (Lema 1)

Fie b\in \mathds{N} astfel încât b=\ x^y şi p şi q \in \mathds{N} cu proprietatea că (p,q)=\ 1, astfel încât \frac{p}{q}=\ y .

Atunci b =\ x^{\frac{p}{q}} şi deci b^q =\ x^p .

Dacă e şi f sunt exponenţii factorului prim P din descompunerea în factori primi a numerelor b şi respectiv x, reiese că: e*q =\ f*p.

Ştim că (p,q)=\ 1, deci e va trebui să fie divizibil cu p şi f va trebui să fie divizibil cu q.

Ştiind că acest lucru se aplică pentru orice număr prim P, putem deci spune că toţi exponenţii din descompunerea în factori primi a numărului x vor fi divizibili cu q.

Deci cel mai mare divizor comun al exponenţilor din descompunerea în factori primi a numărului x va fi divizibil cu q.

Din moment ce gcd_{exp}(x)=\ 1, va trebui ca şi q să fie egal cu 1.

Atunci y=\ \frac{p}{q} =\ \frac{p}{1} =\ p \in \mathds{N} , ceea ce trebuia demonstrat.
Dacă n este primul termen, q este raţia şi progresia cuantică are lungimea k, condiţia de existenţă este următoarea:
n^{q^{i}} este natural pentru oricare i \in \{ 0, 1, 2, .... k-1 \} .

Fie m \in \mathds{N} astfel încât m^{gcd_{exp}(n)}=\ n. Intuitiv, gcd_{exp}(m) =\ 1 . Înlocuind mai sus, obţinem:

m^{gcd_{exp}(n)*q^{i}} este natural pentru oricare i \in \{ 0, 1, 2, .... k-1 \} .

Folosing Lema 1, obţinem că:

gcd_{exp}(n)*q^{i} este natural pentru oricare i \in \{ 0, 1, 2, .... k-1 \} .

Observăm astfel că am ajuns la problema nambartiori, doar că aplicata valorii gcd_{exp}(n).

Subtaskul 2

Putem să trecem prin fiecare numar, să-i calculam gcd_{exp}-ul si să-i aplicam functia din nambartiori ca apoi să-l adaugam la rezultat.

Subtaskul 3

Observăm că un numar n ne interesează doar dacă gcd_{exp}(n)>=2 . Asta înseamnă că în loc să trecem prin toate numerele pana la 10^{12}, putem pur şi simplu să mergem prin bazele acestor numere până în 10^6. Prin baze ne referim la numerele n \in \mathds{N} cu proprietatea că gcd_{exp}(n)=\ 1.