giovedì 8 aprile 2010

Quiz veloce

Qual'è il resto della seguente divisione intera?
21001 mod 31
(dove l'operazione mod indica appunto il resto della divisione fra i due numeri interi. Ad esempio, 16 mod 7 = 2).

Se volete, potete mettete la risposta nei commenti, insieme al tempo che ci avete messo a ricavarla (per un mia personalissima statistica! anzi per una sorta di scommessa con un mio collega). Domani sera la soluzione.

10 commenti:

  1. 31 è 32-1, ossia 2^5-1.
    Più in là non riesco ad andare.

    RispondiElimina
  2. @Ivo: quello è il primo passo. Scomponi 2^1001 ...

    RispondiElimina
  3. Dato che dovevo dare una risposta pubblica, ci ho messo più tempo del necessario, visto che dovevo controllare per bene il risultato :-)

    Comunque, qualche minuto. Prima ho scritto un po' di potenze, giusto per verifica, poi ho notato che ogni 5 fattori 2, il modulo risulta 1 (cioè, 2^5 = 1 modulo 31). Quindi, dato che 2^1001 = 2^1000 * 2, risulta che 2^1001 mod 31 = 2^1000 * 2 mod 31 = 2.

    RispondiElimina
  4. $ python
    Python 2.6.4 (r264:75706, Dec 7 2009, 18:45:15)
    [GCC 4.4.1] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> 2**1001 % 31
    2L
    >>> exit()
    OK, lo so che così non vale! Ma alle 8:00 di sera, dai ;-)

    RispondiElimina
  5. 2...

    2 alla 1000 è uguale a 2 alla 5 per 200 quindi modulo 2 alla 5 risulta 2 semplificabile, insomma per chi gioca con i kilo, mega, giga... bastano circa 2 alla 1006 mod 31 secondi

    Ciao

    RispondiElimina
  6. Ciao,
    io avevo ottenuto quella che penso sia la soluzione giusta (cioe' 2) in pochi minuti con il classico carta+penna+neuroni ... poi ho avuto la malaugurata idea di fare un check con Matlab per vedere se fosse la risposta giusta ... ed ecco cosa ha detto Matlab:

    >> mod(2^1001, 2^5-1)

    ans =

    0

    ... e mi sono quindi scervellato un'ora per capire come mai il risultato di Matlab fosse diverso dal mio (ed assumendo che quello di Matlab fosse giusto) ... a quel punto ho ricordato una frase del mitico Francaviglia (te lo ricordi? ... il Superciuk di Analisi I e II! :-) ) "il computer ci prende in giro. Ci vuole fare credere di avere a che fare con i numeri reali quando abbiamo invece a che fare con un sottoinsieme dei razionali!" ... ed ho capito che l'esempio che avevi fatto tu era fatto apposta per fare "uscire scemo" un algoritmo puramente numerico operante su numeri limitati (cioe' o fino a 2^32 o fino a 2^64). Peppe MALEDETTO!!! :-) la prossima volta dillo prima di NON usare il computer per controllare il risultato ... cosi' non ci perdo un'ora di tempo!!!!! :-)

    RispondiElimina
  7. @ Antonino
    Dissento! E prendo la difesa d'ufficio del 'puter.
    Dove ci sono applicazioni serie e altre meno (OK, s/serie/adatte/). Per dire io ormai sono python dipendente e dunque:

    $ python
    Python 2.6.4 (r264:75706, Dec 7 2009, 18:45:15)
    [GCC 4.4.1] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> 2**1001
    21430172143725346418968500981200036211228096234110672148875007767407021022498722449863967576313917162551893458351062936503742905713846280871969155149397149607869135549648461970842149210124742283755908364306092949967163882534797535118331087892154125829142392955373084335320859663305248773674411336138752L
    >>>

    Comunque c'ero arrivato con il metodo descritto da Zar; solo che lui è arrivato prima a vedere il post, stizza, rabbia...

    Questo quiz me ne ha fatto tornare in mente uno di tanto tempo fa. C'era in palio un piccolo premio e siccome non ho vinto io non mi sono degnato di sentire la soluzione. La domanda era: "Qual'è l'ultima cifra non zero di 1000!"?

    RispondiElimina
  8. @tonino: eh eh, il superciuck! quello sì che aveva capito tutto della vita (a parte la fase alcolica). Matlab è basato su delle librerie scritte in fortran, vedi un po' che cacciucco può venir fuori con i numeri interi fuori range!

    @juhan: l'ultima cifra non zero di 1000? In che base? :)

    RispondiElimina
  9. @ Knulp (Peppe?)
    1000 fattoriale. Per la base credo vadano bene quelle solite 10, 16 e 8. Ma questa cosa risale all'inizio degli anni '80, allora anch'io usavo il Fortran, principalmente il IV (1966). Poi quando si è reso disponibile il 77 è stato un periodo di confusione: i common disallineati e i cicli DO con controllo all'inizio. Ero giovane allora.

    RispondiElimina
  10. Peppe va benissimo!

    L'ultima cifra non nulla di 1000! (non avevo capito, scusa)

    Una risposta un po' complicata la trovi qui:
    http://mathforum.org/library/drmath/view/71768.html

    Non so se ci sia un metodo più semplice (suggestions anyone?)

    Per il fortran: massimo rispetto, è stato un ottimo linguaggio, finché non ne è uscito uno migliore! Ma non gli si può chiedere di controllare l'overflow degli interi... :)

    RispondiElimina

I commenti vengono gestiti tramite Disqus. Siete pregati di autentificarvi prima di commentare.