Re: fatoracao

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sun, 4 Mar 2001, josimat wrote:

> De quantos modos podemos escrever um numero natural
> como produto de tres numeros naturais?
> Exemplo:
> O numero 8 pode ser escrito de 3 formas (apenas):
> 1 x 1 x 8
> 1 x 2 x 4
> 2 x 2 x 2
> 
> []s Josimar

O problema fica bem mais fácil se *não* identificarmos 
1 x 1 x 8 com 1 x 8 x 1 e 8 x 1 x 1. Neste caso basta distribuir
os fatores primos entre os três fatores no número.

Assim, se N = 2^a 3^b 5^c 7^d ...
devemos escrever

a = a1 + a2 + a3
b = b1 + b2 + b3
c = c1 + c2 + c3
d = d1 + d2 + d3
...

N1 = 2^a1 3^b1 5^c1 7^d1 ...
N2 = 2^a2 3^b2 5^c2 7^d2 ...
N3 = 2^a3 3^b3 5^c3 7^d3 ...

N = N1 N2 N3

onde todos estes números são naturais (= inteiros não negativos).
Vocês devem saber que o número de formas de decompor a como soma
de três parcelas naturais é binom(a+2,2).
Assim o número de soluções é

M0 = binom(a+2,2) binom(b+2,2) binom(c+2,2) binom(d+2,2) ...

Para N = 8 = 2^3, por exemplo, esta fórmula dá

M0 = binom(5,2) = 10
 
e, de fato,

8 = 1 * 1 * 8
  = 1 * 2 * 4
  = 1 * 4 * 2
  = 1 * 8 * 1
  = 2 * 1 * 4
  = 2 * 2 * 2
  = 2 * 4 * 1
  = 4 * 1 * 2
  = 4 * 2 * 1
  = 8 * 1 * 1

Para resolver o problema original precisamos contar dentre estas soluções
aquelas que tem simetrias especiais, ou seja, aquelas para as quais:

(a) N1 = N2
(b) N1 = N3
(c) N2 = N3
(d) N1 = N2 = N3

A resposta para os itens (a), (b) e (c) é claramente a mesma,
chamemos de M1; chamemos a resposta para o item (d) de M2.
Observe que as soluções contadas em (d) são também contadas
em (a), (b) e (c).

O item (a) corresponde a soluções de

a = 2 a1 + a3
b = 2 b1 + b3
c = 2 c1 + c3
d = 2 d1 + d3
...

N1 = N2 = 2^a1 3^b1 5^c1 7^d1 ...
N3 = 2^a3 3^b3 5^c3 7^d3 ...

N = N1 N2 N3

O número de soluções naturais da equação a = 2 a1 + a3 é claramente
floor(1 + (a/2)) (aqui floor(x) é o maior inteiro menor ou igual a x).
Assim

M1 = floor(1 + (a/2)) floor(1 + (b/2)) floor(1 + (c/2)) floor(1 + (d/2)) ...

Para N = 2^3, esta fórmula dá M1 = 2, o que está correto:

8 = 1 * 1 * 8
  = 2 * 2 * 2

Finalmente, M2 é claramente 1 se N é um cubo e 0 caso contrário.

Temos assim M0 - 3 M1 + 2 M2 soluções com os três Ni diferentes
e portanto (M0 - 3 M1 + 2 M2)/6 soluções correspondentes
na interpretação original.

Temos ainda M1 - M2 soluções com N1 = N2 != N3 que
correspondem a (M1 - M2)/2 soluções na interpretação original.

E finalmente temos M2 soluções com N1 = N2 = N3
em qualquer interpretação.

Ou seja, a resposta desejada é:

((M0 - 3 M1 + 2 M2)/6) + ((M1 - M2)/2) + M2

e isto resolve o problema.



O problema pode ser resolvido pela mesma técnica para
decomposições em qualquer número dado de fatores (aqui 3)
mas vai ficando mais complicado bem rápido.

[]s, N.