Question

10 numere prime, fiecare fiind <= 3000, formeazã o progresie aritmeticã. Care sînt acestea?

Answer 1

Am scris un mic progrămel (offf, iarăși?) cu care am făcut următoarele operații:

1. Am generat un șir cu toate numerele prime mai mici decît 3000. Au ieșit 430 numere prime; cel mai mic e 2 și cel mai mare e 2999. (Din șirul obținut l-aș fi putut ignora pe 2, pentru că el nu poate intra în progresii aritmetice de 10 termeni cu numere impare. Dar din comoditate l-am lăsat acolo.)

2. Am generat toate progresiile aritmetice posibile care au termenii între 2 și 2999 și rații numere pare (rațiile nu au cum să fie numere impare).

3. Pentru fiecare progresie generată am verificat dacă toți termenii ei se regăsesc în șirul de numere prime. Dacă da, am afișat progresia respectivă.

Rezultatul este că pînă la 3000 există o singură progresie aritmetică de 10 termeni numere prime, și anume cea care pornește de la 199 și are rația 210. Iat-o în toată splendoarea ei:

199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089.

Pentru curioși: deși programul are de făcut multe încercări, rularea durează pe laptopul meu sub 1,4 s. Memoria ocupată de variabile e neglijabilă: un șir de 430 de numere plus alte cîteva chestii infime. Complexitatea programului e minoră (am avut un singur bug). Lungimea programului: 30 de linii, din care unele goale și cîteva care se ocupă cu cronometrarea și cu afișarea. Calculul efectiv se face în numai 5 linii de program.

Comments

Credeam şi speram că nimeni nu-i dă de capăt. Of, uitasem de AdiJapan.

---

Există o proprietate foarte interesantă a progresiilor aritmetice de numere prime. Ideea este că rația unei progresii aritmetice formată din k numere prime trebuie să fie multiplu de k# = 2·3·5·...·j, unde j este cel mai mare număr prim ≤ k, atunci când progresia aritmetică nu începe cu numărul prim k (la noi e cazul, 10 nefiind prim). De aici rezultă că rația progresiei va trebui să fie multiplu de 2*3*5*7=210. Aș fi curios cum s-ar modifica programul dvs. ținând cont de această proprietate (un pic de teorie poate economisi o mulțime de resurse computaționale)...

https://en.wikipedia.org/wiki/Primes_in_arithmetic_progression#Properties

---

Goguv, e superbă sugestia! Am modificat programul și acum rulează mult mai rapid. Mai exact de circa 100 de ori mai rapid. Eu eram mulțumit și cu o rulare de o secundă și jumătate, dar acum îi trebuie doar 16 milisecunde. E ceva.

---

Cu proprietatea asta la dispoziție rezultă imediat că rația trebuie să fie exact 210 (dublu sau mai mult ar exclude existența a 10 numere mai mici de 3000 în progresie). Așa că nu mai rămâne decât să generăm șirul de 10 numere ale progresiei pentru fiecare număr prim mai mare sau egal cu 3 și să vedem care îndeplinește condițiile problemei. Cred că așa ar fi mulțumită și autoarea întrebării! :)

---

Speram ca exista si o metoda fara computer. Asa sa fie? Acum ca stim numerele, ati putea sa ne "dezvaluiti" metoda?

---

mircea_p: Se mai poate apela la:

t_k+1 = t₁ + 210*k = 11*19*k + (t₁ + k) => t₁ nu poate avea ca rest în urma împărțirii la 11 orice număr de la 2 la 10. Rămîn numai numerele prime care au rest %11 numai numărul 1 sau t₁ ete chiar 11.
t_k+1 = t₁ + 210*k = 13*16*k + (t₁ + 2k) => t₁  nu poate avea ca rest în urma împărțirii la  13, numerele 1, 3, 5, 7, 9 sau 11  (de ex. dacă t₁%13 = 5 atunci t5 se divide cu 13 și nu ar fi prim.
Punînd cap la cap aceste informații se scurtează lista numerelor prime, mai bine spus a primului termen al progresiei. 
Doar atît.

---

Ma gandeam totusi la algoritmul pe care l-ai folosit; sa il mai simplificam. Cred ca o idee ar fi urmatoarea: sa determinam siruri de tripleti pe ideea a,b,c in progresie daca b e medie aritmetica a lui a si c si dupa care cred ca ar merge concatenarea tripletilor.

---

Felicitări.