Re: fatoracao

["Luis Lopes" <llopes@xxxxxxxxxxxxx>]

Sauda,c~oes,

Seja N=36. Calculando f(36), obtemos:

36=1.1.36 = 1.2.18 = 1.3.12 = 1.4.9 = 1.6.6 = 2.2.9 = 2.3.6 = 3.3.4 e
f(36)=8.

Usando o resultado do Nicolau, vem:

36=2^2 . 3^2

M0=binom(a+2,2) binom(b+2,2)= binom(2+2,2) binom(2+2,2)=36.
M1 = floor(1 + (a/2)) floor(1 + (b/2)) =floor(1 + (2/2)) floor(1 + (2/2))=4.
M2=0

>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.

As soluções com os três Ni diferentes são: 1.2.18, 1.3.12, 1.4.9 e 2.3.6.
e (M0 - 3 M1 + 2 M2)/6  = 4. Confere.

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

Acho que aqui ele está calculando todas as soluções com dois Ni iguais
e um diferente. São as seguintes: 1.1.36, 2.2.9, 3.3.4 e 6.6.1. Esse número
então seria dado por M1-M2 no original e 3(M1-M2) levando em conta a
ordem.

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

Confere.

>Ou seja, a resposta desejada é:

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

Calculando f(36), vem: 4 + ((4-0)/2) + 0 = 6. Não confere.

Acho que a resposta seria

((M0 - 3 M1 + 2 M2)/6) + (M1 - M2) + M2 para o original e
(M0 - 3 M1 + 2 M2) + 3(M1 - M2) + M2 levando em conta a ordem.

Calculando para f(8), vem:

M0 = binom(5,2) = 10
M1 = 2
M2 = 1

((M0 - 3 M1 + 2 M2)/6) + (M1 - M2) + M2 = 1 + 1 + 1 = 3. Elas são
1.1.8, 1.2.4 e 2.2.2. Confere.

(M0 - 3 M1 + 2 M2) + 3(M1 - M2) + M2 = 6 + 3 + 1 = 10. Elas são
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
Confere.

[ ]'s
Luís

-----Mensagem Original-----
De: Nicolau C. Saldanha <nicolau@mat.puc-rio.br>
Para: OBM <obm-l@mat.puc-rio.br>
Enviada em: Terça-feira, 6 de Março de 2001 17:18
Assunto: Re: fatoracao




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.