Re: [obm-l] Recursivas Primitivas

[okakamo kokobongo <okaka_koko@xxxxxxxxxxxx>]

  Oi Edilon,

A)a) Temos: J(x, y) = 1/2 * (x + y) * (x + y + 1) + x;
Vamos provar que J é bijetora:
1) J é sobrejetora: Dado a >= 0 seja m o maior natural
tal que 1/2 * m * (m + 1) <= a.
Como a - 1/2 * m * (m + 1) é certamente menor que m +
1, já que:
 0 + 1 + 2 + 3 + 4 + ... + m = 1/2 * m * (m + 1)
Seja x = a - 1/2 * m * (m + 1) e y = m - x, temos J(x,
y) = a
2) J é injetora: Suponha que J(x0, y0) = J(x1, y1). Se
x0 + y0 > x1 + y1, certamente
J(x0, y0) > J(x1, y1), pois 1/2 * (x0 + y0) * (x0 + y0
+ 1) - 1/2 * (x1 + y1) * (x1 + y1 + 1) > x1 + y1
Logo x0 + y0 = x1 + y1 e fica fácil ver que x0 = x1,
portanto (x0, y0) = (x1, y1)

b) J é claramente recursiva primitiva, pois:
  f(a, b) = a + b é r.p.
  f(a, b) = a * b é r.p.
  f(n) = 1 + 2 + 3 + ... + n é r.p., logo J é r.p.


Para provar que inv (J) é r.p., basta provar que: f é
r.p., onde:
  f: N -> N, definida por
  f(m) := n, onde n é o maior natural tal que 1/2 * n
* (n + 1) <= m
Como a função g(a, b) = min {1, a - b} é r.p. é fácil
compor e usar uma recursão para provar que f é r.p.

B) A função h(a, b) = (a + 1) ^ b é r.p., logo P é
claramente r.p.
A função f(n) = n (mod 2) é r.p. e 
g(n) = n/2 se n é par e g(n) = 0 se n é ímpar são r.p.
a partir daí é fácil retirar a maior potência de dois
que divide um número e fica fácil provar que a inversa
de P é r.p.

Obs.: Definição precisa de r.p.:
  Uma função é dita recursiva primitiva (r.p.) se é
formada pelas seguintes regras:
  1) f = c, onde c é uma constante, é r.p. (função
identicamente constante)
  2) f(n1, n2, ..., nk) = ni é r.p.
  3) f(n) = n + 1 é r.p.
  4) Se f, g1, g2, ..., gk são recursivas primitivas
f(g1, g2, ..., gk) é r.p.
  5) Se f(0, n2, ..., nk) é r.p. e g(m, n1, n2, ...,
nk) é r.p. e
     f(n + 1, n2, ..., nk) = g(f(n, n2, ..., nk), n,
n2, ..., nk) então f é r.p.


Exercício Legal: Prove que a função p(n) = n-ésimo
primo é r.p.

Abraços,
  OKAKAMO KOKOBONGO


_______________________________________________________________________
Busca Yahoo!
O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra.
http://br.busca.yahoo.com/
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================