Verificatore numeri di Smith

Il verificatore di numeri di Smith risponde a una classica domanda ricreativa di teoria dei numeri: per un intero composto n, la somma delle cifre decimali di n è uguale alla somma delle cifre decimali dei suoi fattori primi contati con molteplicità? Fornisci un n composto e lo strumento restituisce la somma delle cifre di n, la somma delle cifre della fattorizzazione in primi, i fattori in potenze prime, e un flag booleano smith che è true esattamente quando quelle due somme corrispondono. Esempi famosi includono ventidue (due più due è uguale a due più uno più uno dai fattori due e undici) e ventisette (due più sette è uguale a tre più tre più tre). Il motore usa divisione per tentativi deterministica e percorsi esatti sulle cifre intere, così il risultato è privo di derive in virgola mobile e identico a ogni esecuzione. Non chiama mai la rete, non campiona mai casualità e non dipende mai dall'orologio.

Cos'è un numero di Smith e cosa contiene la risposta

Un numero di Smith è un intero composto n tale che la somma delle sue cifre decimali è uguale alla somma delle cifre decimali di tutti i fattori primi di n, con ogni primo ripetuto secondo il suo esponente nella fattorizzazione. I primi sono esclusi per definizione: la fattorizzazione di un primo è il primo stesso, così le somme delle cifre corrisponderebbero banalmente e la proprietà sarebbe priva di interesse.

Il più piccolo numero di Smith è quattro: la somma delle cifre quattro è uguale a due più due dalla fattorizzazione due al quadrato. Ventidue è l'esempio a due cifre più noto: due più due è uguale a due più uno più uno da due per undici. Ventisette funziona perché due più sette fa nove e tre al cubo contribuisce con tre più tre più tre.

Sei è composto ma non di Smith: somma delle cifre sei contro due più tre uguale cinque. I composti non di Smith sono risposte valide riuscite con smith false; non sono errori. Se ti serve solo la fattorizzazione in primi di un intero senza il confronto di Smith, usa uno strumento di fattorizzazione dedicato; questa pagina risponde alla domanda sui numeri di Smith con entrambe le somme delle cifre.

Come vengono letti gli input e come le somme delle cifre restano esatte

Il segno più iniziale opzionale è ammesso per valori positivi; spazi incorporati, prefissi esadecimali e notazione esponenziale vengono respinti così che una cella sbagliata non diventi un flag errato. Gli interi negativi e i valori sotto due vengono respinti perché i numeri di Smith sono definiti su interi positivi composti in questo verificatore. Il motore resta entro gli interi sicuri di JavaScript, il che è più che sufficiente per problemi in classe, gare di programmazione e la maggior parte delle verifiche applicate su n moderatamente grandi.

Internamente il numero viene fattorizzato per divisione per tentativi: rimuovi i fattori di due, poi percorri i candidati dispari fino alla radice quadrata del cofattore rimanente, e concludi con qualunque resto primo maggiore di uno. Per ciascuna potenza prima p elevato a e, la somma delle cifre dei fattori aggiunge e volte la somma delle cifre decimali di p. La somma delle cifre di n stesso viene calcolata tramite divisioni ripetute per dieci.

Non c'è alcun passaggio in virgola mobile che potrebbe arrotondare un quasi-intero in una falsa dichiarazione di Smith.

Dove si usano i controlli di Smith nello studio, nelle dimostrazioni di ricerca e nel codice

Gli studenti incontrano i numeri di Smith esplorando la teoria dei numeri ricreativa, le proprietà basate sulle cifre e le curiosità sui numeri composti insieme a numeri perfetti, abbondanti e harshad. Gli insegnanti possono generare chiavi di risposta per schede di esercizi senza fidarsi di app di calcolo opache che nascondono il passaggio di fattorizzazione.

Gli sviluppatori usano lo stesso contratto per validare dati campione per librerie di teoria dei numeri, per bloccare test di proprietà su generatori di interi casuali, o per pre-verificare che un seme rientri nella classe di Smith prima di un passaggio dimostrativo. La pratica in gare ha spesso bisogno di una fonte veloce e offline di risposte di Smith così le soluzioni possono essere verificate senza scaricare tabelle OEIS.

Abbinalo alla fattorizzazione in primi quando ti servono solo le potenze prime, a un verificatore di numeri abbondanti quando ti serve la classificazione per somma di divisori, e a un verificatore di coprimalità quando ti servono test di MCD a coppie invece di somme di cifre.