Formula di Luhn

Giochini matematici elementari ma non olimpici.
Rispondi
Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Formula di Luhn

Messaggio da Enrico Leon » 14 giu 2009, 22:29

Solo stasera ho scoperto questo bell'algoritmo:
http://it.wikipedia.org/wiki/Formula_di_Luhn
Ho provato con la mia Carta, funziona!
Visto che "la formula è stata studiata per rilevare errori di digitazione", mi sono allora posto le seguenti domande:

a) Se parto da un codice valido e modifico esattamente una cifra, posso ottenere un altro codice valido?

b) La stessa cosa se scambio tra loro due cifre adiacenti.

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 14 giu 2009, 23:19

la formula di luhn in pratica e'
sia $ ~(x_i) $, sequenza di n numeri naturali e $ $m=\lfloor\frac{n}{2}\rfloor $
se n pari
$ $L=\sum_{k=1}^{m}[2x_{2k}\!\!\!\!\mod{9}]+\sum_{k=1}^{m}x_{2k-1} $
se n dispari
$ $L=\sum_{k=1}^{m}[2x_{2k}\!\!\!\!\mod{9}]+\sum_{k=1}^{m+1}x_{2k-1} $

(perdonate la notazione, ma non ricordo quella corretta)
$ ~L\equiv 0 \mod{10} $ indica la validita'

cambiando una cifra per avere di nuovo un valore valido devo variare la sua aggiunta alla somma di 10 e non e' possibile
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Re: Formula di Luhn

Messaggio da julio14 » 15 giu 2009, 00:11

Enrico Leon ha scritto:a) Se parto da un codice valido e modifico esattamente una cifra, posso ottenere un altro codice valido?

b) La stessa cosa se scambio tra loro due cifre adiacenti.
a) visto che la trasformazione è iniettiva, è un po' impossibile
b) 09 - 90, ma è l'unica, che la differenza tra ogni cifra e la sua permutazione è diversa per ogni cifra (0 e 9 esclusi: c'è due volte la differenza 0, e nessuna volta la 5)
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Rispondi