Numere speciale și legătura dintre ele [600173]

1

Numere speciale și legătura dintre ele
Probleme nesoluționate încă
Probleme capcană

Nivel liceal/Clasa a X -a/Informatică/Tehnologii

Tipul documentului: referat științific

Prof. Carmen Mareș
Colegiul Național „Petru Rareș ”, Piatra Neamț

2
Numere speciale ș i legătura dintre ele

Spre deosebire de matematică, dificultatea problemelor de informatică nu este dată de faptul că nu
se cunoaște un algoritm de rezolvare a lor, ci datorită faptului că nu se cunoaște un algoritm eficient
(!) de rezolvare a lor.

Numere perfecte – Numere prietene – Numere tria ngulare

1. Se citește n, să se determine toate numerele perfecte mai mici decât n. Un număr este
perfect dacă este egal cu suma divizorilor săi (de ex. 6=1+2+3).

Analiza probl emei – elaborarea algoritmului:
– pentru a verifica dac ă un număr este perfect trebuie s ă–i determin ăm divizorii și să verific ăm dac ă
suma acestora este egal ă cu n
– se observă că ultimul divizor nu trebuie luat î n calcul pentru c ă este egal cu n
– pentru a afișa toate numerele perfe cte < n folosim un ciclu while în care îl decrement ăm pe n și
verific ăm dacă noul n este un număr perfect, dacă da îl afișăm.
Să se afișeze primele n numere perfecte.

#include<iostream>
#include<cmath>
using namespace std;
unsigned n,i;
int main(){
long int i,n,j,sum,k;
cout<<"n="; cin>>n;
k=0; i=5;
do
{ k=k+1;
do
{ sum=1; i=i+1;
for(j=2;j<=i/2;j++)
if(i%j==0)
sum=sum+j;
} while(sum!=i);
cout<<i<<" ";
}while(k<n);
return 0;}

O variantă destul de incomodă care determină doar primele 4 soluții.
Vechii greci aveau un respect deosebit pentru aceste numere și le numeau “arithmos teleios” –
număr limitat la el însuși.

Euclid ar fi arătat că dacă 2n – 1 este prim , atunci 2n-1(2n – 1) este număr perfect.
Deci vom demonstra că 2n – 1 este prim și construim 2n-1(2n – 1).

#include<iostream>
#include<cmath>
using namespace std;
int main(){

3
long long nr=2,p,n,ok,d,a,b,x;
cin>>n;
int k=1;
while(k<=n)
{ p=pow(2,nr) -1;
ok=1;
for(d=2;d<=p/2;d++)
if(p%d==0)ok=0;
if(ok==1){
a=pow(2,nr -1);
b=pow(2,nr);
x=a*(b -1);
cout<<x<<" ";k++;
}
nr++;
}
return 0;
}

Alte proprietăți ale numerelor perfecte:
a. Toate numerele se termină cu cifra 6 sau 8
b. Primele cinci numere perfecte în reprezentare binară sunt:

Numere perfecte Reprezentare binară
6 110 2 de unu și 1 zero
28 11100 3 de unu și 2 de zero
496 111110000 5 de unu și 4 de zero
8128 [anonimizat] 7 de unu și 6 de zero
33550336 1111111111111000000000000 13 de unu și 12 de
zero

Oare se poate determina o regulă?

Programul de mai jos determină numărul de unu și numărul de zerouri, în scrierea în binar, dar și
timpul de execuție , folosind vectori , pentru orice număr natural citit.

#include<iostream>
#include<cmath>
#include <ctime>
using namespace std;
int v[100];
int main(){
long long nr,r,i,z,u;
double start,stop;
start=clock();
cin>>nr;i=1;z=0;u=0;

4
while(nr){r=nr%2;if(r==0)z++;else u++;v[i]=r;i++;nr=nr/2;}
for(int k=1;k<i;k++)cout<<v[k];
stop=clock();
cout<<endl;
cout<<(stop -start)/CLOCKS_PER_SEC; //am calculat timpul de execuție
cout<<endl;
cout<<u<<" "<<z; //afișează numărul de unu și numărul de zerouri
}

Următorul p rogramul determină scrierea în binar a primelor n numere perfecte folosind operații pe
biți

#include<iostream>
#include<cmath>
using namespace std;
int main(){
long long nr=2,p,n,ok,d,a,b,x;
cin>>n;
int k=1;
while(k<=n)
{ p=(1<<nr) -1;
ok=1;
for(d=2;d<=p/2;d++)
if(p%d==0)ok=0;
if(ok==1){
a=(1<<nr -1);
b=(1<<nr);
x=a*(b -1);
cout<<x<<" ";
k++;
for ( int i=32; i>=0; i –)
if ((x & (1 << i))>0) cout<<1;
else cout<<0;
cout<<endl;

5
}
nr++;
}
return 0;
}

2. Perechile de numere care se “acoperă” reciproc se bucurau de un mare interes în vechea
Grecie. Aici prin “acoperire” înțelegem proprietatea că fiecare dintre cele două numere are
suma divizorilor egală cu celălalt număr. Acum le numim numere prietene.

Prima pereche de astfel de numere este: (220,284)

Matematicianul arab Tabit ibn Korra (secolul X) a găsit un algoritm de generare a unor
numere prietene.

Pas1: se pleacă de la numărul 6
Pas2: se constr uiește, prin dublări succesive ș irul: 6, 12, 24, 48, 96, 192, …
Pas3. d in acest șir se construiesc perechi succesive: (6,12), (12,24), (24,48), …
Pas4: la fiecare pereche se adaugă produsul celor două numere:
(6,12), (12,24), (24,48), …
72 288 1152
Pas5: se scade 1 din fiecare cele trei numere:
(5,11), (11,23), (23,47), …
71 287 1151
Pas6: se construiește seria dublurilor pentru numărul 4: 4, 8, 16, 32, 64, … care se scrie sub
numerele obținute la pasul anterior.
(5,11), (11,23), (23,47), …
71 287 1151
4 8 16
Pas7: luăm doar tripletele de numere prime:
(5,11), (23,47), …
71 1151
4 16
Pas8: se înmulț esc cele două numere ale perechii:
55, 1081, …
71, 1151
4, 16
Pas9: cele două numere scrise deasupra multiplilor lui 4 se înmulțesc cu multiplu
corespunză tor:
220, 17296, …
284, 18416, …
Am obținut astfel perechi de numere prietene.

3. Un număr este triangular dacă există un număr natural n, astfel încât suma primelor n
numere naturale este egală cu numărul dat x:
1+2+3+ …+n=n(n+1)/2=x

Șirul numerelor triangulare este: 1, 3, 6, 10, 15, 21, 28, 36, …

6
Printre acestea se observă și numerele perfecte. De aici (ușor de demonstrat) orice număr
perfect este totodată și triangular.

7
Probleme nesoluționate încă

Există multe probleme în informatică pentru care încă nu se cunosc soluții eficiente. De fapt,
ele apar mai ales în matematică, fiind cunoscute sub numele de conjecturi, și au toate ca specific un
fapt care este de mare interes pentru programatori. Incertitudinea asupra lor ar putea fi definitiv
înlăturată nu numai prin demonstrație matematică ci și cu ajutorul formidabilei puteri de calcul a
computerelor.
Astfel, fiecare di n aceste conjecturi numerice ar putea fi infirmată dacă i s -ar găsi un
contraexemplu. Este necesar doar să se găsească un set de numere pentru care propoziția respectivă
să fie falsă. Ori, acest efort nu este la îndemâna niciunui matematician dar este pos ibil pentru un
programator înzestrat și pasionat. El nu are decât să scrie un program eficient și să pună calculatorul
să caute un contra -exemplu.
Deci fiecare problemă conține aceeași capcană, algoritmii de căutare a contra -exemplelor
pot fi concepuți rapid, relativ simpli și cu efort de programare redus (de exemplu, prin trei -patru
cicluri for imbricate sau printr -o soluție gen backtracking ) dar ei vor deveni în scurt timp total
ineficienți și vor conduce la programe mari consumatoare de timp.

Rezolvând numai una dintre ele veți fi recompensați pe măsură: riscați să deveniți celebri !

Conjectura lui Goldbach

Într-o scrisoare din 7 iunie 1742 expediată lui Euler, Goldbach formulează conjectura: „ orice număr
mai mare decât 2 este suma a trei numere prime “. Euler a reformulat conjectura sub forma „ toate
numere întregi pozitive pare, mai mari decât 4, se pot exprima ca suma a două numere prime “.

#include<iostream>
using namespace std;

void goldenbach(int n)
{int a,b,i,j,ok1,ok2;
for(i=2;i<n;i++)
{ a=i;
b=n-i;
ok1=1,ok2=1;
for(j=2;j<=a/2&&ok1==1;j++)
if(a%j==0) ok1=0;
for(j=2;j<=b/2&&ok2==1;j++)
if(b%j==0) ok2=0;
if(ok1&&ok2) cout<<a<<" -"<<b<<"
";}}

int main()
{int n;
cin>>n;
goldenbach(n);}

În timp ce metoda matematică este c orectă pentru Conjectura lui Goldbach, chiar dacă ea converge
către soluție doar la infinit (!), un algoritm trebuie să întoarcă rezultatul după un număr finit de pași.
Se observă de asemenea că, acolo unde matematica nu oferă dovada, algoritmul nu va fi capabil să
o ofere nici el.

8

Conjectura se referă la orice număr par .
Dar s ă punem problema altfel: ce se întâmplă cu numerele impare? Ele pot fi scrise ca sumă de 2
SAU 3 numere prime ?

Exemple:
4=2+2
5=2+3
6=3+3
7=2+5
8=3+5
9=2+2+5
10=5+5
11=2+2+7
12=5+7

Conjectura lui Catalan

Singur ele puteri naturale succesive su nt 8=23 și 9=32.
Observație: într -o exprimare matematică riguroasă, singura soluție în numere naturale m, n, p, q a
ecuației nm+1=pq este n=2, m=3, p=3 și q=2 .
Comentariu: avem șirul numerelor naturale 1, 2, 3, 4, 5,… ; încercuind toate puterile de gradul 2: 1,
4, 9, 16, 2 5,… apoi toate cele de gradul 3: 1, 8, 27, 64, 125, … apoi cele de grad 4, 5, … vom
constata că singurele două numere încercuite alăturate s unt 8 și 9! Adică puterile obținute, cu c ât
sunt mai mari, cu at ât au tendința să se "împrăștie" și să se "distanțeze" unele de altele tot mai tare.
În mod misterios, ele nu -și suportă vecinătatea unele cu altele! Las în seama cititorului să scrie acest
program.
În teoria numer elor, conjectura lui Catalan se enunță astfel:
Singura soluție în mulțimea numerelor naturale a ecuației 𝒙𝒂−𝒚𝒃=𝟏, pentru x, a, y, b > 1
este x = 3, a = 2, y = 2, b = 3.
A fost enunțată în 1844 de către Eugène Charles Catalan (de unde și numele de teorema lui
Catalan ) și demonstrată abia în 2002 de către matematicianul român Preda Mihăilescu , de aceea
mai este uneori denumită și teorema lui Mihăilescu .

Programul C++ de mai jos verifică corectitudinea conjecturii, pentru x și y luând valori în mulțimea
numerelor naturale în intervalul [2,215].

#include <iostream>
using namespace std;
//valoarea maxima pana la care vom cauta un rezultat
long long MAX = 1LL << 30;
//valoarea maxima pana la care vom cauta puterea (a sau b din enunt)
long long LIMIT = 30;
// functie care calculeaza a^b
long long my_pow(long long a, long long b) {
long long v = 1LL;
for (int i = 1; i <= b; ++i) {
if (v < MAX / a) {
v = v * a;

9
} else {
return MAX;
}
}
return v;
}
//functie care calculeaza radical de ordin x din n, folosind algoritmul de cautare binara
long long my_sqrt(long long n, long long x) {
long long i = 0, cnt = MAX / 2;
for (; cnt; cnt >>= 1) {
if (my_pow(i + cnt, x) <= n) {
i = i + cnt;
}
}
return i;
}
int main() {
for (long long x = 2, lim = my_sqrt(MAX, 2); x <= lim; ++x) {
// in variabila xa vom tine valoarea curenta a lui x^a
long long xa = x;
for (int a = 2; xa <= MAX / x; a++) {
xa = xa * x;
for (int b = 2; b <= LIMIT; ++b) {
long long y = my_sqrt(xa, b);
if (my_pow(y, b) == xa – 1) {
/* am gasit o solutie */
cout << x << '^' << a << " – " << y << '^' << b << " = 1 \n";
}
}
}
}
}
Iată și comanda de compilare a programului de mai sus, timpul de execuție și rezultatul afișat:

10
Conjectura lui Collatz

Se pleacă de la un n întreg pozitiv. Dacă n este par se împarte la doi; dacă n este impar se
înmulțește cu trei și apoi i se adună unu. Repet ând în mod corespunzător doar acești doi pași se va
ajunge întotdeauna la 1 indiferent de la ce valoare n se porneș te ?
Observație: de exemplu, pornind de la n=6 obținem în 8 pași șirul valorilor: 6, 3, 10, 5, 16, 8, 4, 2,
1.
Comentariu: valoarea finală 1 este ca o "gaură neagră" care absoarbe în final șirul obținut. "Raza"
de-a lungul căreia are loc "căderea" în gau ra neagră 1 este dată mereu de șirul puterilor lui 2: 2, 4, 8,
16, 32, 64, … cu ultima valoare de forma 3k+1 , adică 4, 16, 64, 256, … . Se pare că valorile obținute
prin cele două operații nu pot "să nu dea" nicicum peste acest șir care le va face apoi să " cadă în
gaura neagră" 1!

#include<iostream>
#include<math>
using namespace std;
int main(){
long long n;
cout<<"n="; cin>>n;
while(n!=1)
if(n%2==0){n=n/2;cout<<n<<" ";}
else {n=n*3+1;cout<<n<<" ";}
}

11
Probleme capcan ă

1. Să se determine toate numerele de 4 cifre divizibile cu n.

Analiza problemei – elaborarea algoritmului:
– observ ăm că dacă abordă m soluția la "prima mână" numărul pașilor în cadrul cicl ului for este de
8999, pentru că valoarea de intrare în ciclul for e ste 1000 iar valoarea de ieșire este 9999.
– reanalizând problema putem stabili un număr foarte mic de pași care este egal cu numărul de
numere formate din patru cifre divizibile cu n .

#include<iostream>
using namespace std;
unsigned n,i;
int main( ){
cout<<"n=";cin>>n;
if (1000 % n ==0)
for(i=1000 /n; i<=9999 / n; i++) cout<<i*n<<" ";
else
for(i=1000 / n+1; i<= 9999 / n; i++) cout<<i*n<<" ";
return 0 ;
}

2. Să se afișeze numărul cuburilor perfecte mai mici decât n.

Analiza problemei – elaborarea algoritmului:
Capcana problemei constă în tentativa de a parcurge printr -un ciclu for toate numerele de la 1 la n și
de a contoriza cele care sunt cuburi perfecte.
La o a nouă privire, mai atentă, observăm că partea întreag ă a radicalului de ordinul 3 din n ne oferă
acel număr care ridicat la a 3 -a este cel mai apropiat cub de n. Deci, partea întreagă a radicalului de
ordinul 3 din n este egală chiar cu numărul cuburilor mai mici decât n.

(Este suficient să calculăm radica l de ordinul 3 din n pentru a afla câte cuburi mai mici decât n
există.)

#include<iostream>
#include<cmath>
using namespace std;
int main()
{long n;
float x;
cin>>n;
x=pow(n,1.0/3.0);
cout<<x;
}

3. Se citesc a, b, c întregi. Să se determine toate perechile întregi (x,y) soluții ale ecuației
ax+by=c.

Analiza problemei – elaborarea algoritmului;

12
Problema pare la prima vedere imposibilă. Există ecuații , de exemplu: 3x+2y=1 care are o infinitate
de soluții …, (1, -1), (3,-4), (5, -7), (7, -10),…
Cum ar putea fi afișată atunci pe ecran o mulțime infinită de perechi ? Soluția este de a afișa această
mulțime printr -o descriere sintetică a ei ( afișând formula care poate genera toate perechile ce o
compun).
1. daca c=1 atunci exist ă (x0,y0) a.î. ax0+by0=1 doar dac ă [a,b]=1; restul soluțiilor (x,y) au forma
x=x0+kb , y=y0 -ka, cu k întreg .
2. daca c>1 atunci exist ă soluțiile (x0,y0) doar dacă [a,b]|c; restul soluțiilor se construiesc la fel;
3. exista posibilitatea ca, pornind de la perechi (x0,y0) distincte, s ă se obțină soluții noi diferite
(mulțimi infinite de perechi distincte).
4. toate soluțiile (mulțimi infinite de perechi) pleacă de la o pereche
(x0,y0) aflata in dreptunghiul ( -b,-a)x(b,a).

Programul trebuie doar să determine x0 și y0.
Un bun exemplu este ecuația 18x+42y=6.

#include <iostream>
#include <cmath>
using namespace std;
int main(){
int a,b,c,x0=0,y0=0,y,k,v;
cout<<"a,b,c:";cin>>a>>b>>c;
for(y=0;y<=a;y++)
{
v=abs(c -b*y);
if(v % a==0)
{
y0=y;
x0=(c -b*y) / a;
if(x0!=0)
{ cout<<x0<<" "<<y0;cout<<endl;
for(k= -10;k<=10;k++){cout<< x0+k*b<<" "<<y0 -k*a;
cout<<endl;}
}
}
}
if(x0==0 && y0==0 && c)cout<<"Nu exista solutii";
return 0;
}

4. Se citește n o valoare întreagă pozitivă. Să se determine toate descompunerile în
diferență de pătrate ale lui n.

Analiza problemei – elaborarea algoritmului:
Arătăm în continuare cum se poate evita soluția "banală" – capcană ce -ar consta în două cicluri for
imbricate.
Soluția următoare efectuează doar radical din n pași, fată de n2 pași ai soluției "la prima mâna ".
– pentru a determina toate descompunerile in diferență de pătrat e ale lui n pornim de la formula a2-
b2=(a+b)(a -b)=n

13
– observam ca produsul termenilor a+b și a-b este produsul a doi dintre divizorii lui n, unul din
termeni este divizor (d) a lui n celălalt este tot divizor a lui n si îl aflam împărțind -l pe n la d ( n div
x)
– notăm cu x primul divizor a lui n (x=d) ș i cu y= n div x ș i obținem relațiile
a+b=x deci un sistem de două ecuații cu două necunoscute , pe care îl rezolvă m
a-b=y prin metoda reducerii, și avem 2a=x+y => a=(x+y )/2 , b=(y -x)/2,
– pentru ca (x+ y)/2 s ă fie o soluție a ecuației a2-b2=(a+b)(a -b)=n trebuie ca x+y sa fie un număr par
si y-x sa fie un număr par
– dacă această condiție este îndeplinită afișăm soluția care îndeplinește condiția cerută .

#include <iostream>
#include <cmath>
using namespace std;
int main()
{ int n,d,a,b,x,y;
cout<<"n:";cin>>n;
for(d=1;d<=sqrt(n);d++)
if(n%d==0)
{x=d;
y=n/x;
if((x+y)%2==0)
{a=(x+y)/2;
b=(y -x)/2;
cout<<n<<"="<<a<<"^2"<<" – "<<b<<"^2"<<" = "<<a*a<<" – "<<b*b;
}
cout<<endl;
}
return 0;}

5. Se citește n și x1, x2, …, xn rădăcinile întregi ale unui polinom de gradul n. Se cere să
se determine pe baza relațiilor lui Viete coeficienții an, an -1, …, a1, a0 .
Analiza problemei – elaborarea algoritmului;
Cea mai des înt âlnită rezolvare este cea de tip backtracking, aparent mai uș oară, dar în fapt extrem
de ineficientă pentru n nu mare ci doar măricel ! Următoarea soluț ie de tip iterativ este o mică
"bijuterie" de program iterativ și de aceea vă las plăcerea de a -l înțelege sin guri.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
int a[100],x[100],n,i,k;
cout<<"n=";cin>>n;
cout<<"Radacinile:";
for(i=0;i<n;i++)
{
cout<<"x["<<i<<"]=";cin>>x[i];
a[i]=0;

14
}
a[0]=1;a[n]=0;
for(k=1;k<=n;k++)
{
for(i=k;i>0;i –)
a[i]=a[i -1]-a[i]*x[k -1];
a[0]*= -x[k-1];
}
cout<<"coeficientii:";
for(i=n;i>=0;i –)
cout<<"a["<<i<<"]=" <<a[i]<<endl;
}

6. Se citește n. Să se afișeze toate numerele de n cifre, formate numai cu cifrele 1 și 2,
divizibile cu 2n.

Analiza problemei – elaborarea algoritmului:
Abordarea "în forță" a acestei probleme nu duce la nici un rezultat:
– dacă s-ar alege varianta de rezolvare "la prima m ână" ar trebui verificate toate cele 2n posibilit ăți,
adică toate cele 2n numere de n cifre ce se pot forma numai cu cifrele 1 și 2 (c âte 2 posibilit ăți
pentru fiecare poziț ie). În acest caz, programul av ând o complexitate exponen țială, ar dura un timp
exponenț ial, p entru n=50 ar dura cât vâ rsta sistemului nostru solar!

pt. n=1 avem unica soluție numă rul 2;
pt. n=2 avem de asemenea unica soluție 12; observă m că 2-ul este "folosit"
pt. n=3 avem de asemenea unica solu ție 112; observă m că 12 este din nou "folosit"

În general, se deduce c ă numerele de n cifre, ce trebuie s ă se divid ă cu 2n, se divid cu 2n-1; ele se pot
scrie sub forma c*10(n-1)+M=c*2n-1*5n-1+M= Multiplu(2n-1)+M; înseamnă că M (cele n -1 cifre
rămase) trebuie s ă se divid ă cu 2n-1; înseamnă că M este unul din numerele g ăsite ca solu ție la pasul
n-1.
Dacă exist ă o singur ă soluție M p entru cazul n -1 (M se divide cu 2n-1) acest n umăr se poate scrie
M=2(n-1)*par sau 2(n-1)*impar, rezult ă că M mod 2n=0 sau M mod 2n=2(n-1). Deci, în cazul a n cifre
din cele două posibilit ăți (1M sau 2M) se va alege astfel unica solu ție:
dacă M mod 2n=0 atunci solu ția este 2M=2*10(n-1)+M=Multiplu(2n)
dacă M mod 2n=2(n-1) atunci solu ția este 1M=10(n-1)+M=2(n-1)*5(n1)+M=Multiplu(2n)!
Soluția propus ă este una iterativ ă și face maximum n pași !

#include<iostream>
using namespace std;
int main()
{long nr,zece_la_n,n,i;
cout<<"Introduceti n (max.10):";cin>>n;
nr=2;zece_la_n=1;
for( i=2;i<=n;i++)
{
zece_la_n=10*zece_la_n;

15
if( nr % (1 << i)==0 ) nr=2*zece_la_n+nr;
else nr=zece_la_n+nr;
}
cout<<"Solutia este:"<<nr;
return 0;
}