Encontre os inteiros positivos menores que 10000 e com 60 divisores positivos.

Passo 1

O enunciado pede: encontrar todos os inteiros positivos <10000 que têm exatamente 60 divisores positivos.
Informações dadas (o que sabemos do enunciado):
  • Queremos números n tais que \tau(n)=60, onde \tau(n) é o número de divisores positivos de n.
  • E também queremos apenas os n com n<10000.

Passo 2

Fórmula fundamental que vou usar (explicando devagar): se
n = p_{1}^{a_{1}} p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}
é a fatoração em primos distintos, então o número de divisores de n é
\tau(n)=\prod_{i=1}^{k} (a_{i}+1).
Aqui cada a_{i} é o expoente do primo p_{i}. A razão: para cada primo p_i podemos escolher o expoente de 0 a a_i na construção de um divisor, e multiplicando as opções obtemos \tau(n).
Portanto precisamos achar todas as tuplas de inteiros positivos (a_1,\dots,a_k) tais que
\prod_{i=1}^{k} (a_i+1) = 60,
e depois verificar quais dessas tuplas, atribuídas a primos, geram n<10000.

Passo 3

Fazer as “partições multiplicativas” de 60 em fatores inteiros \ge2 (cada fator será um a_i+1). As decomposições (não ordenadas) possíveis são:
  • 60 (um fator) → (a)=(59).
  • 30\cdot 2 (29,1).
  • 20\cdot 3 (19,2).
  • 15\cdot 4 (14,3).
  • 12\cdot 5 (11,4).
  • 10\cdot 6 (9,5).
  • 15\cdot2\cdot2 (14,1,1).
  • 10\cdot3\cdot2 (9,2,1).
  • 6\cdot5\cdot2 (5,4,1).
  • 5\cdot4\cdot3 (4,3,2).
  • 5\cdot3\cdot2\cdot2 (4,2,1,1).
Cada tupla acima significa que os expoentes possíveis são os valores correspondentes (por exemplo (4,2,1,1) corresponde a um número com forma p^4 q^2 r^1 s^1 com primos distintos).

Passo 4

Critério prático para eliminar muitas tuplas rapidamente: dado um padrão de expoentes (a_1,\dots,a_k), o menor n que ele pode gerar é obtido atribuindo o maior expoente ao menor primo 2, o segundo maior ao 3, e assim por diante. Se esse menor n já for >10000, então todas as outras atribuições (que colocam expoentes grandes em primos maiores) também serão >10000. Vou usar isso repetidamente.
Observação rápida e útil: 2^{14}=16384>10000. Assim qualquer padrão que force um expoente \ge14 em algum primo dá um n maior que 10000 independentemente de outros fatores, porque pelo menos 2^{14} já ultrapassa 10000.

Passo 5

Eliminar padrões com expoente muito grande:
  • (59), (29,1), (19,2), (14,3), (14,1,1) têm um expoente \ge14, logo impossíveis porque 2^{14}>10000.
  • Verificar (11,4): o menor n aqui é 2^{11}\cdot 3^{4}=2048\cdot81=165888>10000. Impossível.
  • Verificar (9,5): o menor n é 2^{9}\cdot3^{5}=512\cdot243=124416>10000. Impossível.
  • Verificar (9,2,1): menor n é 2^{9}\cdot3^{2}\cdot5 =512\cdot9\cdot5=23040>10000. Impossível.
  • Verificar (5,4,1): menor n é 2^{5}\cdot3^{4}\cdot5 =32\cdot81\cdot5=12960>10000. Impossível.
  • Verificar (4,3,2): menor n é 2^{4}\cdot3^{3}\cdot5^{2}=16\cdot27\cdot25=10800>10000. Impossível.
Depois dessas eliminações, sobrou apenas o padrão
(4,2,1,1),
isto é, números da forma
n = p^{4}q^{2} r s
com p,q,r,s primos distintos. Esse é o único padrão que pode produzir n<10000.

Passo 6

Agora vamos enumerar todos os números da forma
n = p^{4} q^{2} r s
com p,q,r,s primos distintos e n<10000. Como sugeri antes, para tornar a busca eficiente, tomo p (o primo com expoente 4) e verifico quais escolhas de q,r,s cabem no limite. Para cada escolha, calculo diretamente n.
Reescrevendo a condição:
q^{2} r s \le \frac{10000}{p^{4}}.
Vou testar p em ordem crescente (começando em 2).

Passo 7

Caso p=2. Temos 2^{4}=16, então
q^{2} r s \le \frac{10000}{16}=625.
Os primos q,r,s devem ser distintos entre si e distintos de 2. Vamos testar possibilidades para q (o primo com expoente 2):
  • Se q=3 então q^{2}=9 e precisamos de r s \le \lfloor 625/9\rfloor =69. Os primos possíveis para r,s (distintos de 2,3) são 5,7,11,13,17,\dots. Procuramos pares distintos r<s com r s \le 69. Esses pares são:
    • (5,7) com r s=35.
    • (5,11) com r s=55.
    • (5,13) com r s=65.
      Para cada par calculo n=16\cdot 9\cdot r s =144\cdot r s:
    • r s=35\Rightarrow n=144\cdot35=5040.
    • r s=55\Rightarrow n=144\cdot55=7920.
    • r s=65\Rightarrow n=144\cdot65=9360.
  • Se q=5 então q^{2}=25 e precisamos de r s \le \lfloor 625/25\rfloor =25. Primos disponíveis (não 2,5) começam em 3,7,11,\dots. Pares distintos possíveis com produto \le25:
    • (3,7) com r s=21. Assim n=16\cdot25\cdot21=400\cdot21=8400.
    Não há outros pares porque 3\cdot11=33>25.
  • Se q\ge7 então q^{2}\ge49 e r s \le \lfloor625/49\rfloor =12, mas o menor produto de dois primos distintos (diferentes de 2 e q) é 3\cdot5=15>12. Logo não há soluções para q\ge7.
Portanto, para p=2 encontramos os valores n=5040,7920,9360,8400.

Passo 8

Verificar p=3. Aqui 3^{4}=81, então
q^{2} r s \le \frac{10000}{81}\approx 123{,}456\Rightarrow q^{2} r s \le 123.
Testar q possíveis (primos distintos de 3):
  • q=2: q^{2}=4 e r s \le \lfloor123/4\rfloor=30. Mas os dois menores primos disponíveis são 5 e 7 e 5\cdot7=35>30. Logo não há pares.
  • q=5: q^{2}=25 e r s \le \lfloor123/25\rfloor=4, impossível.
  • q\ge7: q^{2}\ge49 e o resto ainda menor, impossível.
Logo não há soluções com p=3.

Passo 9

Verificar p=5. Temos 5^{4}=625, então
q^{2} r s \le \frac{10000}{625}=16.
Mesmo com q=2 (o menor possível), q^{2}=4 e então r s \le 4, o que não é possível para dois primos distintos (o menor produto é 3\cdot7=21 se excluímos 2 e 5). Portanto nenhuma solução com p=5.
Para p\ge7 temos p^{4}\ge 7^{4}=2401 e então \frac{10000}{p^{4}}<5, impossível obter q^{2} r s inteiro \ge 6. Assim não há soluções adicionais.

Passo 10

Conclusão da enumeração: as únicas soluções são as encontradas no caso p=2. Vou listar os valores finais (ordenei em ordem crescente para ficar mais legível).

Resposta

5040
7920
8400
9360

Exercícios relacionados