Metodi di generazione dei numeri di Smith

S è un numero di Smith se considerando con T la somma dei digit di S, con F la somma della lista dei fattori di S, allora F è uguale a T.

Esempio 729
T=18
S=3^6=3*3*3*3*3*3
F=3+3+3+3+3+3=18
F=T
S è un numero di Smith.

Nella base 10, i primi numeri di Smith sono

4, 22, 27, 58, 85,   94, 121, 166, 202, 265, 274, 319, 346, 355, 378,   382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, ... (Sequenza A006753 dell'OEIS)

Metodi per generare i numeri di Smith
1.mo metodo

Se p è un primo Repunit allora posso generare numero di Smith con la moltiplicazione S=k*p dove k può assumere ad esempio uno dei seguenti valori: 1.540, 1.720, 2.170, 2.440, 3.304, 5.590, 6.040,
7.930, 8.344, 8.470, 8.920, 23.590, 24.490, 25.228, 29.080, 31.528, 31.780, 33.544, 34.390, 35.380.

Alcuni esempi:

R(2)=11
S=3304*R(2)=36344
T=3+6+3+4+4=2+0=2
L=2^3*7*11*59
F=2+2+2+7+11+59=24+59=8+3=1+1=2
-->Si Notare che il repunit primo appare anche nella scomposizione

R(3)=111
S=3304*R(3)=366744
T=3+6+6+7+4+4=30=3
S=2^3*3*7*37*59
F=2+2+2+3+7+37+59=16+37+59=112=1+1+2=4
-->No

R(19)
S=3671111111111111110744
T=3+6+7+15+15=16+15+15=46=4+6=1
S=2^3*7*59*1111111111111111111
F=2+2+2+7+59+19=13+59+19=91=9+1=1
-->Si Notare che il repunit primo appare anche nella scomposizione

I numeri di Smith di questa formas sono, quindi, legati ai numeri Repunit primi.

2.do metodo
Nel 1984, Pat Costello generò numeri di Smith con la formula P*Q*10^M dove P è un piccolo primo e Q è un numero primo di Mersenne noto.  Come si deve scegliere M nella formula P*Q*10^M?

Un metodo è il seguente:
 a) Si sceglie il numero primo di Mersenne e si calcola la somma dei suoi digit
 b) Si un numero primo piccolo P e si fanno i seguenti passi:
    b1) si calcola ps = somma dei digit di Q + la somma dei digit di P;
    b2) si calcola il prodotto P*Q;
    b3) si calcola ds = somama dei digit di P*Q;
          se ds<ps, si torna a b) e si sceglie un nuovo P;
          se ds=ps, allora P*Q è un numero di Smith;
          se ds>ps, allora si calcola  (ds-ps) mod 7;
                    se (ds-ps) mod 7 = 0 allora M = (ds-ps)/7 e P*Q*10^M è un numero di Smith
                    altrimenti si torna a b) e si sceglie un nuovo P.
 Esempio:
      Scegliamo Q = 2^17-1 = 131071 scegliamo  P = 5011.
      ps = 20.
      P*Q = 656796781.
      ds = 55.
      ds-ps = 35 divisibile per 7. M=35/7=5.
      P*Q*10^5 = 65679678100000 è un numero di Smith secondo la definizione iniziale
 
Costello individuò 65 numeri di Smith in questo modo, incluso uno da record:
191*(2^216091-1)*10^266 con 65319 digit.

3.zo metodo 
Nel 1987, Wayne McDaniel generalizzò il concetto di numeri di Smith e introdusse i k-Smith numbers e provò che sono infiniti. Con k=1 ci si riduce ai numeri di Smith, allora anche i numeri di Smith sono infiniti.

McDaniel  generò i numeri di Smith della forma t*9Rn*10^M dove t è nell'insieme {2, 3, 4, 5, 7, 8, 15}, con Rn repunit primo.

4.to metodo
Dovuto a Yates.Di forma 9Rn*QS*10^M  con Rn repunit primo e Q un primo palindromo di forma
10^2K +A*10K + 1. 

Si suppone che esistono molte altre forme generatrici di numeri di Smith. 

Tuttavia è bene sottolineare che alcuni numeri possono avere più proprietà, ad esmpio è possibile trovare un numero di Fibonacci Smith e così via. Esistono i numeri di Smith palindromi, fratelli etc (http://it.wikipedia.org/wiki/Numero_di_Smith)

L'utilità dei numeri di Smith? Si può cercare di appoggiarsi ad essi per semplificare la primalità di un altro tipo di numero. Ad esempio abbiamo visto che i numeri di Smith sono composti, ma legati ai Mersenne primi o a Repunit primi. Questo vuol dire che se si crea un algoritmo con cui generare un numero di Smith di una certa forma, allora si potrebbe risalire ad un Mersenne primo o a un Repunit primo.

P.S: Se usate la forma S=K*p vi renderete conto che avrete bisogno della fattorizzazione di S, che è lenta; oppure di sapere dato un p se esso è un fattore primo di S senza fattorizzare S (problema oggi non risolto).

Alla prox