Generarea resturilor impartirilor succesiva, definitii, aplicatii referat

Metoda de generare a resturilor unor impartiri succesive

        Fie x si b doua numere naturale, cu b 2. Notam prin [a] partea intreaga a unui numar real a, adica cel mai mare intreg mai mic sau egal cu a.
        Propozitia 1: Restul impartirii lui x la b este x - b[x/b].
        Demonstratie: Vom folosi proprietatea cunoscuta a partii intregi a unui numar real, si anume:

aI R, a-1 < [a] a.

        Conform acestei proprietati avem, pentru a = x/b,

x/b-1 < [x/b] x/b

si, inmultind aceasta dubla inegalitate cu b, gasim

x-b < b[x/b] x

de unde rezulta imediat ca

0 x - b[x/b] < b.

        Conform teoremei impartirii cu rest, exista in mod unic doua numere c (cat) si r (rest), luand in cazul nostru:

c = [x/b]    si    r = x-b[x/b]

        Catul si restul astfel alese verifica conditia de existenta.

        Consideram un numar xI N, cu  0 x bⁿ-1.
        Definitie: Expresia f_k = [x/b^n-k]-b[x/b^n-k+1] se numeste restul de ordin k al impartirii succesive a lui x prin puteri ale lui b, k = 1, 2, , n.
        Propozitia 2:     0 f_k b-1, k, k = 1, 2, , n.
        Demonstratie: Fie un k fixat, k = 1, 2, , n.  Notam cu y_k = [x/b^n-k]. Atunci f_k = y_k - b[y_k/b] este un rest de ordin k conform definitiei si conform propozitiei 1 avem 0 f_k b-1.

        Propozitia 3: Pentru orice x natural cu 0 x bⁿ-1  si  b 2 avem
        Demonstratie: Suma din dreapta se mai poate scrie:

f₁b^n-1 + f₂b^n-2 ++ f_n-1b¹ + f_nb⁰ =
= ([x/b^n-1]-b[x/bⁿ])b^n-1 + ([x/b^n-2]-b[x/b^n-1])b^n-2 ++ ([x/b]-b[x/b²])b + ([x/b⁰]-b[x/b])b⁰ =
= [x] - bⁿ[x/bⁿ] = x - bⁿ[x/bⁿ].

        Dar x bⁿ-1 < bⁿ, deci [x/bⁿ] = 0, ceea ce demonstreaza formula data.

       Aplicatii:

            1.  Din scrierea lui x de mai sus se poate deduce ca f_k reprezinta simbolurile numerice de reprezentare a numarului x in baza de numeratie b, in ordinea data. Asadar, daca f₁, f₂, , f_n sunt aceste simboluri numerice, numarul x se mai poate scrie:

        Se poate spune deci ca f_k este a k-a cifra(simbol) de reprezentare in baza de numeratie b a numarului x, unde x,bI N, 0 x bⁿ-1, b 2 iar

f_k = [x/b^n-k]-b[x/b^n-k+1], k = 1, 2, , n.

            2.  Functia f_k este o cale mai scurta de a determina prin calcul simbolurile de reprezentare a unui numar intr-o baza de numeratie oarecare b.

            Ca amuzament matematic se poate concepe un algoritm simplu pentru a 'ghici' un numar ales de cineva, urmand pasii urmatori:
 

 

        P1: Fixati un numar natural b 2 si un numar natural n.
        P2: Cereti unei persoane sa-si aleaga un numar natural x, care sa fie cuprins intre 0 si bⁿ-1. Desi numarul ales nu va va fi comunicat, instiintati persoana ca puteti sa-i ghiciti exact numarul ales daca este dispusa sa va comunice primele n rezultate ale unor calcule folosind o fomula'magica' pe care i-o veti da.
        P3: Dati-i functia f_k = [x/b^n-k]-b[x/b^n-k+1] si cereti-i sa va furnizeze valorile ei pentru k = 1, 2, , n. Nu uitati sa-i explicati cum sa efectueze calculele necesare.
        P4. Daca f₁, f₂, , f_n sunt cele n rezultate, atunci veti face propriul dvs. calcul pe baza formulei

        Algoritmul de mai sus poate fi inlocuit cu un altul echivalent, bazat pe formula: 'Dati, pe rand, restul impartirilor succesive ale numarului y_k la b, unde y_k = [x/b^n-k], k luand valorile 1, 2, , n'.

        O forma echivalenta cu cea de la punctul 4 se poate rezuma la n intrebari succesive de forma: 'Imparte fara rest numarul ales la b^n-k si spune restul impartirii acestuia la b', unde k ia, pe rand, valorile 1, 2, , n. Totusi, in practica este indicat sa se apeleze la formule mai atractive. Pentru diversitate, de exemplu in cazul in care baza b = 3, se poate cere doar suma cifrelor impartirii fara rest, urmand ca restul sa-l aflati chiar dvs. din acest numar. Mult mai simplu poate fi tratat cazul b = 2 in care se poate intreba daca rezultatul impartirii fara rest este un numar par sau impar.