Periodicità della rappresentazione in base arbitraria

MindFlyerMindFlyer Posts: 436
edited July 2015 in Calcolo numerico
Riprendo da qui.

Dimostrare:
Per ogni intero [tex]b>1[/tex] e ogni reale [tex]r[/tex], [tex]r[/tex] è razionale se e solo se la sua rappresentazione in base [tex]b[/tex] è periodica.

(Dedurre che la rappresentazione di un numero reale è o periodica in ogni base, o aperiodica in ogni base.)

Comments

  • MindFlyerMindFlyer Posts: 436
    edited July 2015
    Ho accidentalmente scoperto anche un'altra cosa mentre cercavo di dimostrare l'inesistenza di Dio:

    La rappresentazione in base [tex]b[/tex] del razionale [tex]p/q[/tex], con [tex]p[/tex] e [tex]q[/tex] coprimi, è puramente periodica (ovvero non ha un antiperiodo dopo la virgola) se e solo se [tex]b[/tex] e [tex]q[/tex] sono coprimi.

    Mentre siete in fila che aspettate il vostro turno per postare la dimostrazione del primo teorema, potete ammazzare il tempo dimostrando anche questo.
  • MindFlyerMindFlyer Posts: 436
    edited July 2015
    Un altro fatterello un po' più profondo, su cui vi invito a ragionare (mi è venuto in mente mentre riflettevo su come Platone sembri incapace di distinguere l'etica dall'estetica):

    Per ogni numero primo [tex]p[/tex], esistono infinite basi in cui la rappresentazione di ogni frazione propria a denominatore [tex]p[/tex] ha periodo esattamente [tex]p-1[/tex] (che è il massimo possibile).

    Esempio:
    Prendiamo p=7. Vogliamo trovare infinite basi in cui le frazioni 1/7, 2/7, 3/7, 4/7, 5/7, 6/7 hanno periodo esattamente 6.
    Un'infinità di queste basi è data per esempio dai numeri della forma 7k+3, con k naturale.
    Infatti:

    1/7 in base 3 è [tex]0.\overline{010212}[/tex], che ha periodo 6.
    2/7 in base 3 è [tex]0.\overline{021201}[/tex], che ha periodo 6.
    3/7 in base 3 è [tex]0.\overline{102120}[/tex], che ha periodo 6.
    4/7 in base 3 è [tex]0.\overline{120102}[/tex], che ha periodo 6.
    5/7 in base 3 è [tex]0.\overline{201021}[/tex], che ha periodo 6.
    6/7 in base 3 è [tex]0.\overline{212010}[/tex], che ha periodo 6.

    1/7 in base 10 è [tex]0.\overline{142857}[/tex], che ha periodo 6.
    2/7 in base 10 è [tex]0.\overline{285714}[/tex], che ha periodo 6.
    3/7 in base 10 è [tex]0.\overline{428571}[/tex], che ha periodo 6.
    4/7 in base 10 è [tex]0.\overline{571428}[/tex], che ha periodo 6.
    5/7 in base 10 è [tex]0.\overline{714285}[/tex], che ha periodo 6.
    6/7 in base 10 è [tex]0.\overline{857142}[/tex], che ha periodo 6.

    1/7 in base 17 è [tex]0.\overline{274E9C}[/tex], che ha periodo 6.
    2/7 in base 17 è [tex]0.\overline{4E9C27}[/tex], che ha periodo 6.
    3/7 in base 17 è [tex]0.\overline{74E9C2}[/tex], che ha periodo 6.
    4/7 in base 17 è [tex]0.\overline{9C274E}[/tex], che ha periodo 6.
    5/7 in base 17 è [tex]0.\overline{C274E9}[/tex], che ha periodo 6.
    6/7 in base 17 è [tex]0.\overline{E9C274}[/tex], che ha periodo 6.

    1/7 in base 24 è [tex]0.\overline{3A6KDH}[/tex], che ha periodo 6.
    2/7 in base 24 è [tex]0.\overline{6KDH3A}[/tex], che ha periodo 6.
    3/7 in base 24 è [tex]0.\overline{A6KDH3}[/tex], che ha periodo 6.
    4/7 in base 24 è [tex]0.\overline{DH3A6K}[/tex], che ha periodo 6.
    5/7 in base 24 è [tex]0.\overline{H3A6KD}[/tex], che ha periodo 6.
    6/7 in base 24 è [tex]0.\overline{KDH3A6}[/tex], che ha periodo 6.

    Etc...
  • Lucio MessinaLucio Messina Posts: 139
    edited July 2015
    Il mio tentativo per il teorema del primo post:

    Dimostrare:
    Per ogni intero b>1 e ogni reale r, r è razionale se e solo se la sua rappresentazione in base b è periodica.

    (*) Considero razionale un numero che può essere ottenuto dalla divisione fra due numeri interi, indipendentemente dalla base.
    (**) assumo che la finitezza di un numero sia una forma particolare di periodicità: 0.6 = [tex]0.6\overline{0}[/tex]

    r razionale => rappresentazione di r periodica

    Se r è razionale, scrivo r=N/D dove N e D sono numeratore e denominatore interi della frazione generatrice di r, eventualmente semplificati.
    Sia N che D hanno rappresentazione finita in qualsiasi base b>1 in quanto interi (le cifre dopo la virgola sono tutte uguali a zero in qualsiasi base).
    Converto quindi N e D in base b ed eseguo la divisione. Il risultato m (= r in base b) non può che essere razionale, perché generato dalla divisione fra due numeri, indipendentemente dalla base.
    Essendo m razionale, la sua rappresentazione non può che essere finita, oppure periodica. Il tutto vale in qualsiasi base, compresa la base di partenza di r.
    #

    rappresentazione di r periodica = r razionale
    Se la rappresentazione in base b>1 di r è finita o periodica, è possibile trovare due numeri N e D interi tali per chi r=N/D.
    Questo basta a dedurre che r è razionale, perché N e D sono interi in qualsiasi base vengano espressi.
    #

    (;
  • MindFlyerMindFlyer Posts: 436
    edited July 2015
    Oh bene. Qualche commento alla soluzione:


    Essendo m razionale, la sua rappresentazione non può che essere finita, oppure periodica.
    Ok, ma perché? E' precisamente quello che chiedevo, hai solo parafrasato l'enunciato... Vorrei una dimostrazione di questo.



    Il tutto vale in qualsiasi base, compresa la base di partenza di r.
    Nota che la razionalità di un numero è un fatto intrinseco, non relativo a una base. Quindi tutto il discorso iniziale può essere omesso. Voglio dire che un numero è tale indipendentemente dalla base in cui è scritto, e per la verità non deve nemmeno essere per forza scritto in una qualche base per esistere in quanto numero.



    è possibile trovare due numeri N e D interi tali per chi r=N/D.

    Sì, il metodo che si impara alle medie e che wikipedia diligentemente riporta è corretto. Nota che wikipedia italiana non ne dà una gran dimostrazione, ma si limita a farlo in un caso particolare (insomma ne dà quella che Paolo Cignoni chiamerebbe una "dimostrazione dell'oste"). Cerchiamo di dimostrarlo un po' dignitosamente e in generale... :D
  • Lucio MessinaLucio Messina Posts: 139
    edited July 2015
    MindFlyer wrote: »
    è possibile trovare due numeri N e D interi tali per chi r=N/D.

    Sì, il metodo che si impara alle medie e che wikipedia diligentemente riporta è corretto. Nota che wikipedia italiana non ne dà una gran dimostrazione, ma si limita a farlo in un caso particolare (insomma ne dà quella che Paolo Cignoni chiamerebbe una "dimostrazione dell'oste"). Cerchiamo di dimostrarlo un po' dignitosamente e in generale... :D

    Sì, ce l'ha fatto vedere il professore di analisi, ma avevo poco tempo e non mi sono dilungato a scrivere il metodo.
    In pratica si tratta di sottrarre ad r r stesso moltiplicato per b^k (dove k è la lunghezza del periodo) per far scomparire il periodo.

    { Suppongo sia 0<r<1, per i numeri è sostanzialmente uguale }
    [tex]r = 0.\overline{a_1}\overline{a_2}\overline{a_k}[/tex]
    [tex]r*b^k = a_1a_2a_k.\overline{a_1}\overline{a_2}\overline{a_k}[/tex]
    [tex]r*b^k - r = a_1a_2a_k[/tex]

    raccolgo r e divido per il suo coefficiente:
    [tex]r(b^k - 1) = a_1a_2a_k[/tex]
    [tex]r = a_1a_2a_k/(b^k - 1)[/tex]

    Quindi N = a_1a_2a_k (intero) e D = b^k - 1 (intero)

    Se è presente antiperiodo, la dimostrazione è molto simile, r*b^k è periodico:
    - sua la parte intera sarà uguale alle prime cifre dell'antiperiodo, seguita eventualmente da qualche cifra del periodo
    - il suo antiperiodo sarà composta dalle rimanenti cifre di antiperiodo e periodo.
    - il suo periodo è uguale al periodo di r.
    Il risultato della sottrazione sarà decimale, possiamo renderlo intero moltiplicando entrambi i membri dell'equazione per la b^lunghezza dell'antiperiodo.
    Dopo di che si ricavano N e D.
    Essendo m razionale, la sua rappresentazione non può che essere finita, oppure periodica.
    Ok, ma perché? E' precisamente quello che chiedevo, hai solo parafrasato l'enunciato... Vorrei una dimostrazione di questo.

    Ci riprovo: dimostro che m=N/D ha rappresentazione finita con N,D interi e coprimi fra loro, D!=0.
    m = q + r/D con 0<r<D
    q è intero (eventualmente 0) e non da problemi perché la sua rappresentazione è finita.
    Quindi la dimostrazione si riconduce nel dimostrare che anche r/D ha rappresentazione periodica, con r<D ovvero r/D<1

    chiamo x(n) l'ennesima cifra decimale del risultato della divisione in colonna fra r(n-1) e D, ed r(n) il resto della stessa operazione.
    Si pone r(0)=r
    Al passo i>0, x(i) è l'i-esima cifra della rappresentazione di r/D, mentre r(i) è compresa fra 0 e D.

    Se x(i) = x(j), allora anche r(i+1) = r(j+1), perché lo stesso numeratore diviso per D genera stesso risultato e stesso resto.
    r(n) è compreso fra 0 e D per ogni n, quindi può assumere al massimo n valori. Supponiamo che ne assuma k<=n .
    Ne segue che la successione x(n) assumerà i valori x(1) x(2)...x(k) x(1) x(2)....
    Quindi la rappresentazione di r/D è periodica. Se per un certo n* r(n*)=0, allora x(n>n*)=0 e r/D ha rappresentazione finita (tutte le cifre dopo la n*-esima sono = 0)

    Ti ho convinto con una dimostrazione delle elementari?
    Altrimenti c'è quella a pagina 12 di questo documento.

    (;
  • MindFlyerMindFlyer Posts: 436
    edited July 2015
    r(n) è compreso fra 0 e D per ogni n, quindi può assumere al massimo n valori. Supponiamo che ne assuma k<=n .
    Ne segue che la successione x(n) assumerà i valori x(1) x(2)...x(k) x(1) x(2)....

    Tutto benissimo fino a qui. Stai escludendo il caso di un antiperiodo seguito da un periodo...
    Per concludere correttamente basta dire che, dopo al più D resti diversi, se ne ritrova uno già visto. Ma questo resto non è necessariamente il primo della sequenza! In generale diciamo che è il j-esimo. Quindi la successione che hai chiamato x(n) sarà x(1), x(2), ..., x(j), x(j+1), ... x(k), x(j), x(j+1), ... x(k), x(j), ...
    Dunque l'antiperiodo è x(1), x(2), ..., x(j-1), e il periodo è x(j), x(j+1), ... x(k).
    Bene bene. :)



    Altrimenti c'è quella a pagina 12 di questo documento.

    Non direi proprio: lì si parla di rappresentazione fattoriale, che è una cosa completamente diversa da quella in base b.
  • MindFlyer wrote: »
    Altrimenti c'è quella a pagina 12 di questo documento.

    Non direi proprio: lì si parla di rappresentazione fattoriale, che è una cosa completamente diversa da quella in base b.

    Scusami, ieri ero fuso.
    Dopo l'esame proverò a scrivere le altre due dimostrazioni
  • MindFlyerMindFlyer Posts: 436
    Dopo l'esame proverò a scrivere le altre due dimostrazioni

    Grande!! :)
    Per l'ultimo serve un po' di teoria. Potrei dare qualche esercizio preliminare in modo da arrivarci per gradi.
Sign In or Register to comment.