1747. Números de Dinostratus

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

Implementação