Verificatore numeri pratici

Il verificatore di numeri pratici risponde a una domanda classica di teoria dei numeri: ogni intero positivo minore di n può scriversi come somma di divisori positivi distinti di n? Fornisca un intero positivo n e lo strumento restituisce l'elenco completo dei divisori in ordine crescente, il conteggio e la somma dei divisori, un flag booleano practical e—quando la risposta è falsa—il primo intero positivo che non può formarsi in quel modo. Il motore elenca i divisori con divisione di prova deterministica, poi esegue una scansione a sequenza completa che non campiona mai casualità, non chiama mai la rete e non dipende mai dall'orologio, così lo stesso n produce sempre la stessa classificazione.

Che cos'è un numero pratico e cosa contiene la risposta

Un intero positivo n è pratico quando ogni intero positivo minore può esprimersi come somma di divisori positivi distinti di n. Poiché n è sempre un divisore di se stesso, la stessa condizione copre anche tutti gli interi da uno a n. Uno è pratico per vacuità: non c'è un intero positivo minore da rappresentare.

Due è pratico perché uno è un divisore. Dodici è l'esempio standard: i suoi divisori uno, due, tre, quattro, sei e dodici formano ogni intero da uno a dodici con sottoinsiemi distinti. Dieci non è pratico: i suoi divisori uno, due, cinque e dieci formano uno, due, tre uguale a uno più due, cinque, sei, sette, dieci e così via, ma quattro non ha rappresentazione, quindi quattro è il primo valore non rappresentabile.

Gli interi dispari maggiori di uno non sono mai pratici, perché due non può scriversi come somma di divisori dispari. Le etichette perfetto, abbondante e difettivo rispondono a un'altra domanda sulla somma aliquota; un numero può essere pratico senza essere abbondante, e abbondante senza essere pratico.

Come si leggono gli input e come la scansione a sequenza completa resta esatta

Sono ammessi segni più iniziali opzionali per i valori positivi; spazi incorporati, prefissi esadecimali e notazione esponenziale vengono rifiutati affinché una cella errata non diventi un flag sbagliato. Interi negativi e zero sono rifiutati perché i numeri pratici sono definiti qui solo sugli interi positivi. Il motore resta entro gli interi sicuri di JavaScript, più che sufficienti per problemi di aula, gare di programmazione e la maggior parte dei controlli applicati su n moderatamente grandi.

Internamente ogni divisore positivo si raccoglie per divisione di prova: si scorre d da uno fino al pavimento della radice quadrata di n e, ogni volta che d divide n, si registrano sia d sia n diviso d quando quei partner sono distinti, poi si uniscono le metà in un'unica lista crescente. La scansione a sequenza completa mantiene un valore di portata R che significa che ogni intero da uno a R è già una somma di sottoinsieme dei divisori elaborati finora.

Per il divisore successivo d, se d è al più R più uno, l'intervallo coperto si estende a R più d senza buchi; se d supera R più uno, R più uno è il primo intero non rappresentabile e n non è pratico. Quella procedura richiede solo controlli modulari e addizioni intere—mai un passo in virgola mobile che potrebbe inventare un falso esito pratico.

Dove i controlli di numeri pratici rientrano nello studio, nelle demo e nel codice

Gli studenti incontrano i numeri pratici apprendendo le somme di divisori, esplorando la struttura altamente composta e leggendo sulle rappresentazioni in stile frazioni egizie e problema delle monete che usano l'insieme dei divisori come denominazioni. Gli insegnanti possono generare chiavi di risposta per le schede senza fidarsi di calcolatori opachi che nascondono l'argomento di somma di sottoinsiemi.

Gli sviluppatori usano lo stesso contratto per validare dati di esempio per librerie di teoria dei numeri, per condizionare test di proprietà su generatori di interi casuali, o per pre-controllare che un seme appartenga alla classe pratica prima di un passo di simulazione. La pratica di gara spesso richiede una fonte rapida offline di risposte sui numeri pratici per verificare le soluzioni senza scaricare tabelle OEIS.

Lo abbini ai verificatori di somma aliquota e di abbondanza quando serve abbondanza piuttosto che rappresentabilità, a uno strumento di elenco divisori quando servono solo i fattori, e ad aiuti di fattorizzazione prima quando servono le potenze prime di un intero piuttosto che la classificazione di numero pratico.