sabato 27 maggio 2017

Uh! 'na cosa di mate da verificare


Tutto è partito da questo tweet, altamente ispirativo, come si vedrà (forse, anzi probabilmente, almeno secondo me) nel proscieguo.

Prima di subito ecco l'idea: da verificare! 😜
Quando ho cominciato a interagire con i 'puters avrei usato strumenti molto diversi ma --ehi! siamo nel secolo del Pipistrello della Frutta, mica per niente! 🤖-- e allora si usa un linguaggio di scripting, interattivo (volendo), lasciando ai linguaggi più seriosi compiti più impegnativi.

Convinto che tutti (tutti davvero 😎) capiranno subito e finanche diranno "ah! tutto lì? ma allora c'è un gomblotto, perché non me l'hanno detto prima che è così semplice?". È proprio come dico sempre io, a me nessuno dice mai niente (auto-cit.). E adeso scopro di non essere il solo.

Io ho Linux sul mio 'puter ma tutto quanto vale anche per chi ha un 'puter diverso, qualunque esso sia. E userò linguaggi molto conosciuti, di moda, almeno per due su tre; anzi non parto dal mio preferito ma da uno che --a parte il nome, ma tranquilli non stritola-- è semplice-semplice, semplicissimo, Python.

Una cosa prima di cominciare: il tweet dice "any" che possiamo tradurre con "ogni" o "qualunque". Qui bisogna fare attenzione perché i matematti quando dicono "per ogni" intendono che il numero può essere davvero grande; più di quanto pensate; più del googol; più del googolplex, quella è robetta --per loro. Seriamente finiamo dalle parti di 0, chiamiamolo aleph-zero, un numero decisamente esagerato.


Io non voglio arrivare a tanto mi accontento di un milione. Qui 'na cosa: semplificando per il 'puter ci sono due tipi di numeri, quelli interi, giusti e gli altri, quelli con la virgola che sono troppi ma basta approssimarli; anche perché l'approssimazione è (quasi sempre) più di quella richiesta.
Gli interi invece, se non troppo grandi (in valore assoluto) sono esatti, se a un numero aggiungi 1 ottieni il successore di quello stesso numero e fai contento anche Peano. Il numero più grosso di quelli non troppo grossi quando ero piccolo era 65536 (216) ma se vuoi il segno si riduceva a 32767 (215 - 1); poi le cose sono migliorate e il numero più grande non troppo grosso e con il segno è più di 2 miliardi (duemila gianfranchi), non so nemmeno il valore preciso (di 231 - 1) perché non si deve fare sempre attenzione a non superarlo.
E come se non bastasse c'è la precisione arbitraria, come verificheremo.

OK, fine delle premesse, con Python il problema della verifica dell'affermazione del tweet è, nella sua formulazione più semplice questo:

#!/bin/ env pytjon3

'''verifica di kwesto tweet
https://twitter.com/fermatslibrary/status/866641567511195649

'''


def lastdigit(n):
    return n % 10
  
for n in range(1, 1000001): # 1 million
    if not(lastdigit(n) == lastdigit(pow(n, 5))):
        print(n)



fa cioè il test per tutti i numeri da 1 a 1 milione, scrivendo solo quelli che non superano il test. Sulla mia macchina ci mette circa 7 decimi di secondo (wow!).

A dire il vero lo script (un programma corto eseguito in quel modo si chiama così) è la traduzione di un altro, più bello, secondo me, questo:

;; verifica di kwesto tweet
;; https://twitter.com/fermatslibrary/status/866641567511195649


(define (last-digit n)
  (modulo n 10))

(for ([n (in-range 1 1000001)])
  (unless (eq? (last-digit n) (last-digit (expt n 5)))
    (printf "~a " n)))



Vero che Racket, cioè Scheme, cioè il Lisp è più bello?
OK, i pareri possono variare 😊

Ultimamente è diventato ubiquo JavaScript, usatissimo non solo nel Web ma anche come linguaggio introduttivo alla programmazione. Lo script diventa così:

// verifica di kwesto tweet
// https://twitter.com/fermatslibrary/status/866641567511195649


function lastDigit(n) {
  return n % 10
}
  
for(var n = 1; n <= 1000000; n++) { // 1 million
  if (!((lastDigit(n) == lastDigit(Math.pow(n, 5))))) {
    console.log(n);
    break;
  }
}


Notare che c'è una modifica: appena trova un numero che non verifica la condizione si interrompe. Difatti ecco:



OOPS! ma allora quella cosa della precisione arbitraria...
Verifico:


E sì, sembrerebbe davvero che 15535 = 9033525579302993 = 9'033'525'579'302'993 = nove milioni di miliardi abbondanti sia troppo grande per Node, cioè JavaScript.
Ma gli altri linguaggi siamo sicuri che facciano davvero tutte quelle verifiche? Facciamo una piccola modifica: ci facciamo scrivere il numero che stanno testando quando questo è un multiplo di 50mila:

;; verifica di kwesto tweet
;; https://twitter.com/fermatslibrary/status/866641567511195649


(define (last-digit-p n p)
  (when (and p (= (modulo n 50000) 0))
    (printf "~a " n))
  (modulo n 10))

(for ([n (in-range 1 1000001)])
  (unless (eq? (last-digit-p n #t) (last-digit-p (expt n 5) #f))
    (printf "~a " n)))
(printf"\n")


e

#!/bin/ env pytjon3

'''verifica di kwesto tweet
https://twitter.com/fermatslibrary/status/866641567511195649


'''

def lastdigit_p(n, p):
    if p & (n % 50000 == 0):
        print(n, end=" ")
    return n % 10
  
for n in range(1, 1000001): # 1 million
    if not(lastdigit_p(n, True) == lastdigit_p(pow(n, 5), False)):
        print(n)
print("")


Rispetto alla precedente versione (per entrambi) la funzione che controlla l'uguaglianza delle cifre finali ha un parametro in più, p (per print) che attiva la funzione solo se vero (quindi per il numero e non per la potenza). In ogni caso ottengo questo risultato:


Per la versione JavaScript invece di bloccarlo supito al primo numero non verificato si può proseguire, fino a 10 casi, ecco:

// verifica di kwesto tweet
// https://twitter.com/fermatslibrary/status/866641567511195649


function lastDigit(n) {
  return n % 10
}

var noOK = 0, nStr = ""; 
for(var n = 1; n <= 1000000; n++) { // 1 million
  if (!((lastDigit(n) == lastDigit(Math.pow(n, 5))))) {
    nStr += n + " ";
    if(noOK++ == 10) {
      console.log(nStr);
      break;
    }
  }
}



Uhmmm... parecchi, tanti. Ma sono numeri grossi, novemila gianfranchi di gianfranchi 🐙

Nota: siccome non so come togliere l'a-capo a console.log ho memorizzato i numeri in una stringa che ho visualizzato alla fine; decisamente JS non è il mio linguaggio preferito. Anche se lo usano anche a Stanford.

Facile vero? Acchiappa? 😎

5 commenti:

  1. Non ho ancora capito quale linguaggio di programmazione preferisci, forse tutti?
    ;-)

    RispondiElimina
    Risposte
    1. Sono come i figli; mica puoi fare preferenze.
      Anche se, quando ero piccolo mi sono innamorato di: 1) la Ragazzina dai Capelli Rossi; e 2) il Lisp. Niente, in entrambi i casi; ma adesso provo a recuperare. Chissà se qualcuno mi sa dare notizie della ragazzina?

      Elimina
  2. C'è un modo un po' meno aspro per dirlo?
    Guarda in giro, forse i Capelli non sono più Rossi.

    RispondiElimina
  3. beh, sì, la cosa era alla base di un trucco per dimostrare di essere un matematico provetto: prendevi una calcolatrice con dieci cifre di precisione, la davi a qualcuno, gli dicevi di scrivere un numero di due cifre, cliccare x², cliccare di nuovo x², moltiplicare per il numero di partenza e dirti lentamente il risultato (o meglio, fartelo vedere perché la gente si sbaja quando ci sono troppe cifre). Immediatamente davi la risposta: bastava sapere l'ordine di grandezza dei numeri della forma 10n^5 per ricavare le decine, e le unità sono gratis.

    RispondiElimina