Soma dos totativos

Os totativos de um inteiro positivo n são os resíduos no intervalo de um até n que não compartilham nenhum fator primo com n. A contagem é a função totiente de Euler φ(n); a soma é um invariante aritmético próximo que aparece em enumerações de frações, identidades ciclotômicas e exercícios de grupos modulares. Esta calculadora recebe um único inteiro positivo n, o fatora de forma determinística, avalia φ(n) pela fórmula do produto sobre primos e devolve a soma exata dos totativos — a forma fechada clássica n vezes φ(n) sobre dois quando n é maior que um, e o valor especial um quando n é igual a um. Não há chamada de rede, nem chute em ponto flutuante, nem modelo de linguagem entre a sua entrada e a resposta inteira.

O que a soma dos totativos mede

Dois inteiros positivos são coprimos quando o máximo divisor comum é um. O conjunto dos totativos de n é exatamente o dos inteiros k com um menor ou igual a k, k menor ou igual a n, e gcd(k, n) igual a um. A totiente de Euler φ(n) conta esse conjunto; a soma dos totativos adiciona seus membros.

Para um primo p os totativos vão de um até p menos um, de modo que a soma é (p menos um) vezes p sobre dois, o que coincide com p vezes φ(p) sobre dois. Para um n composto a mesma ideia de pareamento vale sempre que n for maior que um: se k é coprimo com n, também o é n menos k; os dois são distintos e a média é n sobre dois, portanto a soma total é n vezes φ(n) sobre dois.

Estudantes encontram a soma ao conferir tabelas de totativos, ao verificar que frações reduzidas com denominador n têm numeradores com média n sobre dois, e ao comparar φ(n) com uma lista manual de coprimos. Engenheiros a usam em pipelines de teoria dos números que precisam da contagem e da soma como invariantes baratos de um módulo. Uma capacidade determinística que devolve n, a soma, φ(n) e os fatores que produziram φ(n) remove erros de deslocamento unitário em corretores de exercícios e suítes de teste inteiras.

Como esta calculadora avalia a soma

Chame a capacidade com um campo inteiro positivo n. A implementação primeiro valida que n é um inteiro no intervalo publicado de um até um trilhão. Em seguida fatora n por divisão de tentativa: remove fatores de dois, depois candidatos ímpares até a raiz quadrada e, por fim, qualquer cofator primo restante.

A partir dessa lista ordenada aplica a forma inteira exata do produto de Euler: começa com phi igual a n e, para cada primo distinto p que divide n, substitui phi pelo piso de phi dividido por p, vezes p menos um. Quando n é um a soma define-se como um, porque o único totativo é um e a fórmula da metade produziria incorretamente um meio.

Quando n é maior que um a soma é n multiplicado por phi e depois dividido por dois; para todo inteiro n maior que um o produto n vezes φ(n) é par, logo o resultado é sempre um inteiro exato sem resto. A resposta inclui n, sum, phi, a lista de fatores como pares primo e expoente, e uma string formula curta do caso aplicado.

Uso prático, limites, preço e entrega

Use a ferramenta do navegador quando quiser a soma dos totativos de imediato ao estudar, corrigir um exercício de teoria dos números ou cruzar uma enumeração manual de coprimos. O intervalo aceito são inteiros de um até um trilhão, o que mantém cada produto intermediário dentro do território de inteiros seguros do JavaScript e ainda cobre tamanhos típicos de competição, sala de aula e aplicação. Os resultados são totalmente determinísticos: o mesmo n sempre produz a mesma soma, o mesmo phi e a mesma lista de fatores.

Não há modelo de linguagem, nem serviço externo de fatoração, nem aleatoriedade, portanto a capacidade é segura para fixar em testes automatizados.