Olá meus amigos nerds, hoje irei falar de um problema bastante divertido, principalmente se você gosta de coincidências arqueológicas.
Existe uma classe de números conhecidos como números de Dinostratus, que aparecem em várias ruínas antigas. No problema 1747. Números de Dinostratus, iremos aprender a identificar se um número é ou não é um número de Dinostratus.
Mais especificamente, um número n é um número de Dinostratus se existe uma matriz M de dimensão 3 x 3 formada por 9 inteiros distintos com a propriedade que para toda posição (i,j) com i=1,...,3 e j=1,...,3 da matriz o elemento mi,j é múltiplo dos seus vizinhos mi-1,j, mi-1,j-1 e mi,j-1 (quando existirem) e m3,3 = n.
Um exemplo de um número de Dinostratus é 36 pois:
1 2 4
3 6 12
9 18 36
Solução
O exemplo acima nos dá uma pista de como resolver o problema. Observe que, todos os números dá matriz devem ser necessariamente formados por fatores primos de n (ex: m(3,3)=36 tem que ser múltiplo de m(2,2)=6 que por sua vez deve ser múltiplo de m(2,1)=3 e m(1,2)=2). Observe ainda que:
|2^0 * 3^0 =1 | 2^1 * 3^0 =2 | 2^2 * 3^0 =4 |
|2^0 * 3^1 =3 | 2^1 * 3^1 =6 | 2^2 * 3^1 =12 |
|2^0 * 3^2 =9 | 2^1 * 3^2 =18 | 2^2 * 3^2 =36 |
Vamos então tentar a seguinte hipótese: a solução do problema depende de alguma propriedade relacionada ao número de fatores primos de n. Se isso é verdade então é possível classificar um número como sendo de Dinostratus baseado no número de fatores primos.
Bem, já sabemos que se temos 2 fatores primos e ambos tem expoente igual a dois então n é um número de Dinostratus. Ex: 36 = 4 * 9 = 2^2 * 3^2 (observe que eu poderia trocar o 2 e o 3 por outros números e mesmo assim a propriedade da matriz formar um número de Dinostratus se manteria, experiente para ver)
O que eu vou fazer agora é estabelecer se n é um número de Dinostratus quando n tem 1, 2, 3, 4, 5 ... fatores distintos, farei isso através de exemplos.
n tem 1 fator distinto
ex: 256 = 2^8
1 2 4
8 32 128
16 64 256
Então o expoente do fator tem que ser >= 8
n tem 2 fatores
do número 36 já sabemos que ambos os fatores tem que ter expoente mair ou igual a 2, por outro lado
96 = 32 * 3 = 2^5 * 3 também é um número de Dinostratus.
1 2 4
3 12 24
6 48 96
Então se um dos expoentes for maior ou igual a 5 n também será um número de Dinostratus.
n tem 3 fatores
ex: 60 = 4 * 3 * 5 = 2^2 * 3 * 5 = 60
1 2 4
3 6 12
15 30 60
Então o expoente de pelo menos um fator tem que ser >= 2.
n tem 4 ou mais fatores
ex: 210 = 2 * 3 * 5 * 7
1 2 14
3 6 42
15 30 210
Então n sempre será um número de Dinostratus.
Do exposto acima retiramos o seguinte algoritmo
fatore n
if n tem 4 ou mais fatores responda sim
if n tem 3 fatores e um deles tem expoente maior que 1 responda sim
if n tem 2 fatores e um deles tem expoente maior que 4 responda sim
if n tem 2 fatores e ambos tem expoente maior que 1 responda sim
if n tem 1 fatores e um deles tem expoente maior que 7 responda sim
else responda não
