Verificador de número prático

O verificador de número prático responde a uma pergunta clássica da teoria dos números: todo inteiro positivo menor que n pode ser escrito como soma de divisores positivos distintos de n? Informe um inteiro positivo n e a ferramenta devolve a lista completa de divisores em ordem crescente, a contagem e a soma dos divisores, um indicador booleano practical e—quando a resposta for falsa—o primeiro inteiro positivo que não pode ser formado dessa forma. O motor lista os divisores por divisão de prova determinística e em seguida executa uma varredura de sequência completa que nunca usa aleatoriedade, nunca chama a rede e nunca depende do relógio, de modo que o mesmo n produz sempre a mesma classificação.

O que é um número prático e o que a resposta contém

Um inteiro positivo n é prático quando todo inteiro positivo menor pode ser expresso como soma de divisores positivos distintos de n. Como n é sempre divisor de si mesmo, a mesma condição cobre também todos os inteiros de um até n. O um é prático por vacuidade: não há inteiro positivo menor a representar.

O dois é prático porque um é divisor. Doze é o exemplo padrão: seus divisores um, dois, três, quatro, seis e doze formam todo inteiro de um a doze com subconjuntos distintos. Dez não é prático: seus divisores um, dois, cinco e dez formam um, dois, três igual a um mais dois, cinco, seis, sete, dez e assim por diante, mas quatro não tem representação, de modo que quatro é o primeiro valor não representável.

Inteiros ímpares maiores que um nunca são práticos, porque dois não pode ser escrito como soma de divisores ímpares. Os rótulos perfeito, abundante e deficiente respondem a outra pergunta sobre a soma alíquota; um número pode ser prático sem ser abundante, e abundante sem ser prático.

Como as entradas são lidas e como a varredura de sequência completa permanece exata

Sinais de mais iniciais opcionais são permitidos em valores positivos; espaços embutidos, prefixos hexadecimais e notação exponencial são rejeitados para que uma célula ruim não se torne um indicador errado. Inteiros negativos e zero são rejeitados porque aqui os números práticos se definem apenas sobre inteiros positivos. O motor permanece dentro dos inteiros seguros de JavaScript, mais do que suficiente para problemas de sala de aula, competições de programação e a maioria das verificações aplicadas sobre n moderadamente grandes.

Internamente todos os divisores positivos são coletados por divisão de prova: percorre-se d de um até o piso da raiz quadrada de n e, sempre que d dividir n, registram-se tanto d quanto n dividido por d quando esses pares forem distintos; em seguida as metades são fundidas em uma única lista crescente. A varredura de sequência completa mantém um valor de alcance R significando que todo inteiro de um a R já é uma soma de subconjunto dos divisores processados até o momento.

Para o próximo divisor d, se d for no máximo R mais um, o intervalo coberto se estende a R mais d sem lacunas; se d ultrapassar R mais um, R mais um é o primeiro inteiro não representável e n não é prático. Esse procedimento precisa apenas de verificações modulares e somas inteiras—nunca um passo de ponto flutuante que pudesse inventar um falso resultado prático.

Onde as verificações de número prático se encaixam no estudo, demos e código

Alunos encontram números práticos ao aprender somas de divisores, ao explorar a estrutura altamente composta e ao ler sobre representações no estilo de frações egípcias e do problema das moedas que usam o conjunto de divisores como denominações. Professores podem gerar gabaritos para listas sem confiar em calculadoras opacas que escondem o argumento de soma de subconjuntos.

Desenvolvedores usam o mesmo contrato para validar dados de amostra em bibliotecas de teoria dos números, para condicionar testes de propriedades em geradores de inteiros aleatórios ou para pré-verificar se uma semente está na classe prática antes de um passo de simulação. A prática de competições costuma precisar de uma fonte rápida offline de respostas de números práticos para conferir soluções sem baixar tabelas OEIS.

Combine com os verificadores de soma alíquota e de abundância quando precisar de abundância em vez de representabilidade, com uma ferramenta de lista de divisores quando precisar apenas dos fatores, e com auxiliares de fatoração prima quando precisar das potências primas de um inteiro em vez da classificação de número prático.