Add some comments on how psi[s](p/q) is computed.
[maxima.git] / doc / info / pt / Number.texi
blob15b5a1d639df120db488e30b9508bb7952672e89
1 @c /Number.texi/1.22/Sat Nov 25 04:02:55 2006/-ko/
2 @c end concepts Number Theory
3 @menu
4 * Definições para Teoria dos Números::  
5 @end menu
7 @node Definições para Teoria dos Números,  , Teoria dos Números, Teoria dos Números
8 @section Definições para Teoria dos Números
10 @deffn {Função} bern (@var{n})
11 Retorna o @var{n}'ésimo número de Bernoulli para o inteiro @var{n}.
12 @c WELL, ACTUALLY bern SIMPLIFIES, LIKE FACTORIAL -- DO WE WANT TO GET INTO THAT ???
13 @c OR JUST PRETEND IT'S "RETURNED" ???
14 Números de Bernoulli iguais a zero são suprimidos se @code{zerobern} for @code{false}.
16 Veja também @code{burn}.
18 @example
19 (%i1) zerobern: true$
20 (%i2) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
21                   1  1       1      1        1
22 (%o2)       [1, - -, -, 0, - --, 0, --, 0, - --]
23                   2  6       30     42       30
24 (%i3) zerobern: false$
25 (%i4) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
26             1  1    1   5     691   7    3617  43867
27 (%o4) [1, - -, -, - --, --, - ----, -, - ----, -----]
28             2  6    30  66    2730  6    510    798
29 @end example
31 @end deffn
33 @deffn {Função} bernpoly (@var{x}, @var{n})
34 Retorna o @var{n}'ésimo polinómio de Bernoulli na
35 variável @var{x}.
37 @end deffn
39 @deffn {Função} bfzeta (@var{s}, @var{n})
40 Retorna a função zeta de Riemann para o argumento @var{s}.
41 O valor de retorno é um grande inteiro em ponto flutuante (bfloat);
42 @var{n} é o número de dígitos no valor de retorno.
44 @code{load ("bffac")} chama essa função.
46 @end deffn
48 @deffn {Função} bfhzeta (@var{s}, @var{h}, @var{n})
49 Retorna a função zeta de Hurwitz para os argumentos @var{s} e @var{h}.
50 O valor de retorno é um grande inteiro em ponto flutuante (bfloat);
51 @var{n} é o números de dígitos no valor de retorno.
53 A função zeta de Hurwitz é definida como
55 @example
56 sum ((k+h)^-s, k, 0, inf)
57 @end example
59 @code{load ("bffac")} chama essa função.
61 @end deffn
63 @deffn {Função} binomial (@var{x}, @var{y})
64 O coeficiente binomial @code{@var{x}!/(@var{y}! (@var{x} - @var{y})!)}.
65 Se @var{x} e @var{y} forem inteiros, então o valor numérico do coeficiente
66 binomial é calculado.
67 Se @var{y}, ou @var{x - y}, for um inteiro,
68 o the coeficiente binomial é expresso como um polinómio.
70 Exemplos:
72 @c ===beg===
73 @c binomial (11, 7);
74 @c 11! / 7! / (11 - 7)!;
75 @c binomial (x, 7);
76 @c binomial (x + 7, x);
77 @c binomial (11, y);
78 @c ===end===
79 @example
80 (%i1) binomial (11, 7);
81 (%o1)                          330
82 (%i2) 11! / 7! / (11 - 7)!;
83 (%o2)                          330
84 (%i3) binomial (x, 7);
85         (x - 6) (x - 5) (x - 4) (x - 3) (x - 2) (x - 1) x
86 (%o3)   -------------------------------------------------
87                               5040
88 (%i4) binomial (x + 7, x);
89       (x + 1) (x + 2) (x + 3) (x + 4) (x + 5) (x + 6) (x + 7)
90 (%o4) -------------------------------------------------------
91                                5040
92 (%i5) binomial (11, y);
93 (%o5)                    binomial(11, y)
94 @end example
96 @end deffn
98 @deffn {Função} burn (@var{n})
99 Retorna o @var{n}'ésimo número de Bernoulli para o inteiro @var{n}.
100 @code{burn} pode ser mais eficitente que @code{bern} para valores grandes e isolados de @var{n}
101 (talvez @var{n} maior que 105 ou algo parecido), @c CLAIM MADE IN bffac.usg !!!
102 como @code{bern} calcula todos os números de Bernoulli até o índice @var{n} antes de retornar.
104 @c STATEMENTS ABOUT TIMING NEED VERIFICATION !!!
105 @c CAN'T VERIFY NOW AS burn IS BROKEN IN 5.9.1 AND CVS BUILD AT PRESENT !!!
106 @c (BERN(402) takes about 645 secs vs 13.5 secs for BURN(402).
107 @c The time to compute @code{bern} is approximately exponential,
108 @c while the time to compute @code{burn} is approximately cubic.
109 @c But if next you do BERN(404), it only takes 12 secs,
110 @c since BERN remembers all in an array, whereas BURN(404) will take
111 @c maybe 14 secs or maybe 25, depending on whether Maxima needs to
112 @c BFLOAT a better value of %PI.)
114 @code{burn} explora a observação que números de Bernoulli (racionais) podem ser
115 aproximados através de zetas (transcendentes) com eficiência tolerável.
117 @code{load ("bffac")} chama essa função.
119 @end deffn
121 @deffn {Função} cf (@var{expr})
122 Converte @var{expr} em uma fração contínua.
123 @var{expr} é uma expressão
124 compreendendo frações contínuas e raízes quadradas de inteiros.
125 Operandos na expressão podem ser combinados com operadores aritméticos.
126 Com excessão de frações contínuas e raízes quadradas,
127 factores na expressão devem ser números inteiros ou racionais.
128 Maxima não conhece operações sobre frações contínuas fora de @code{cf}.
130 @code{cf} avalia seus argumentos após associar @code{listarith} a @code{false}.
131 @code{cf} retorna uma fração contínua, representada como uma lista.
133 Uma fração contínua @code{a + 1/(b + 1/(c + ...))}
134 é representada através da lista @code{[a, b, c, ...]}.
135 Os elementos da lista @code{a}, @code{b}, @code{c}, ... devem avaliar para inteiros. 
136 @var{expr} pode também conter @code{sqrt (n)} onde @code{n} é um inteiro.
137 Nesse caso @code{cf} fornecerá tantos
138 termos de fração contínua quantos forem o valor da variável
139 @code{cflength} vezes o período.
141 Uma fração contínua pode ser avaliada para um número
142 através de avaliação da representação aritmética
143 retornada por @code{cfdisrep}.
144 Veja também @code{cfexpand} para outro caminho para avaliar uma fração contínua.
146 Veja também @code{cfdisrep}, @code{cfexpand}, e @code{cflength}.
148 Exemplos:
150 @itemize @bullet
151 @item
152 @var{expr} é uma expressão compreendendo frações contínuas e raízes quadradas de inteiros.
154 @example
155 (%i1) cf ([5, 3, 1]*[11, 9, 7] + [3, 7]/[4, 3, 2]);
156 (%o1)               [59, 17, 2, 1, 1, 1, 27]
157 (%i2) cf ((3/17)*[1, -2, 5]/sqrt(11) + (8/13));
158 (%o2)        [0, 1, 1, 1, 3, 2, 1, 4, 1, 9, 1, 9, 2]
159 @end example
161 @item
162 @code{cflength} controla quantos períodos de fração contínua
163 são computados para números algébricos, números irracionais.
165 @example
166 (%i1) cflength: 1$
167 (%i2) cf ((1 + sqrt(5))/2);
168 (%o2)                    [1, 1, 1, 1, 2]
169 (%i3) cflength: 2$
170 (%i4) cf ((1 + sqrt(5))/2);
171 (%o4)               [1, 1, 1, 1, 1, 1, 1, 2]
172 (%i5) cflength: 3$
173 (%i6) cf ((1 + sqrt(5))/2);
174 (%o6)           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
175 @end example
177 @item
178 Um fração contínua pode ser avaliado através da avaliação da representação aritmética
179 retornada por @code{cfdisrep}.
181 @example
182 (%i1) cflength: 3$
183 (%i2) cfdisrep (cf (sqrt (3)))$
184 (%i3) ev (%, numer);
185 (%o3)                   1.731707317073171
186 @end example
188 @item
189 Maxima não conhece operações sobre frações contínuas fora de @code{cf}.
191 @example
192 (%i1) cf ([1,1,1,1,1,2] * 3);
193 (%o1)                     [4, 1, 5, 2]
194 (%i2) cf ([1,1,1,1,1,2]) * 3;
195 (%o2)                  [3, 3, 3, 3, 3, 6]
196 @end example
198 @end itemize
199 @end deffn
201 @c NEEDS CLARIFICATION -- MAKE EXPLICIT HOW list IS RELATED TO a, b, c, ...
202 @c ALSO, CAN list CONTAIN ANYTHING OTHER THAN LITERAL INTEGERS ??
203 @deffn {Função} cfdisrep (@var{list})
204 Constrói e retorna uma expressão aritmética comum
205 da forma @code{a + 1/(b + 1/(c + ...))}
206 a partir da representação lista de uma fração contínua @code{[a, b, c, ...]}.
208 @example
209 (%i1) cf ([1, 2, -3] + [1, -2, 1]);
210 (%o1)                     [1, 1, 1, 2]
211 (%i2) cfdisrep (%);
212                                   1
213 (%o2)                     1 + ---------
214                                     1
215                               1 + -----
216                                       1
217                                   1 + -
218                                       2
219 @end example
221 @end deffn
223 @deffn {Função} cfexpand (@var{x})
224 Retorna uma matriz de numeradores e denominadores dos
225 último (columa 1) e penúltimo (columa 2) convergentes da fração contínua @var{x}.
227 @example
228 (%i1) cf (rat (ev (%pi, numer)));
230 `rat' replaced 3.141592653589793 by 103993/33102 = 3.141592653011902
231 (%o1)                  [3, 7, 15, 1, 292]
232 (%i2) cfexpand (%); 
233                          [ 103993  355 ]
234 (%o2)                    [             ]
235                          [ 33102   113 ]
236 (%i3) %[1,1]/%[2,1], numer;
237 (%o3)                   3.141592653011902
238 @end example
240 @end deffn
242 @defvr {Variável de opção} cflength
243 Valor por omissão: 1
245 @code{cflength} controla o número de termos da fração
246 contínua que a função @code{cf} fornecerá, como o valor de @code{cflength} vezes o
247 período.  Dessa forma o padrão é fornecer um período.
249 @example
250 (%i1) cflength: 1$
251 (%i2) cf ((1 + sqrt(5))/2);
252 (%o2)                    [1, 1, 1, 1, 2]
253 (%i3) cflength: 2$
254 (%i4) cf ((1 + sqrt(5))/2);
255 (%o4)               [1, 1, 1, 1, 1, 1, 1, 2]
256 (%i5) cflength: 3$
257 (%i6) cf ((1 + sqrt(5))/2);
258 (%o6)           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
259 @end example
261 @end defvr
263 @deffn {Função} divsum (@var{n}, @var{k})
264 @deffnx {Função} divsum (@var{n})
266 @code{divsum (@var{n}, @var{k})} retorna a adição dos divisores de @var{n}
267 elevados à @var{k}'ésima potência.
269 @code{divsum (@var{n})} retorna a adição dos divisores de @var{n}.
271 @example
272 (%i1) divsum (12);
273 (%o1)                          28
274 (%i2) 1 + 2 + 3 + 4 + 6 + 12;
275 (%o2)                          28
276 (%i3) divsum (12, 2);
277 (%o3)                          210
278 (%i4) 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2;
279 (%o4)                          210
280 @end example
282 @end deffn
284 @deffn {Função} euler (@var{n})
285 Retorna o @var{n}'ésimo número de Euler para o inteiro @var{n} não negativo.
287 Para a constante de Euler-Mascheroni, veja @code{%gamma}.
289 @example
290 (%i1) map (euler, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
291 (%o1)    [1, 0, - 1, 0, 5, 0, - 61, 0, 1385, 0, - 50521]
292 @end example
294 @end deffn
296 @defvr {Constante} %gamma
297 @ifinfo
298 @vrindex Constante de Euler-Mascheroni
299 @end ifinfo
300 A constante de Euler-Mascheroni, 0.5772156649015329 ....
301 @c DOUBTLESS THERE IS MORE TO SAY HERE.
303 @end defvr
305 @deffn {Função} factorial (@var{x})
306 Representa a função factorial. Maxima trata @code{factorial (@var{x})} da mesma forma que @code{@var{x}!}.
307 Veja @code{!}.
309 @end deffn
311 @deffn {Função} fib (@var{n})
312 Retorna o @var{n}'ésimo número de Fibonacci.
313 @code{fib(0)} igual a 0 e @code{fib(1)} igual a 1,
315 @code{fib (-@var{n})} igual a @code{(-1)^(@var{n} + 1) * fib(@var{n})}.
317 Após chamar @code{fib},
318 @code{prevfib} é iguala @code{fib (@var{x} - 1)},
319 o número de Fibonacci anterior ao último calculado.
321 @example
322 (%i1) map (fib, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
323 (%o1)         [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
324 @end example
326 @end deffn
328 @deffn {Função} fibtophi (@var{expr})
329 Expressa números de Fibonacci que aparecem em @var{expr} em termos da constante @code{%phi},
330 que é @code{(1 + sqrt(5))/2}, aproximadamente 1.61803399.
332 Exemplos:
334 @c ===beg===
335 @c fibtophi (fib (n));
336 @c fib (n-1) + fib (n) - fib (n+1);
337 @c fibtophi (%);
338 @c ratsimp (%);
339 @c ===end===
341 @example
342 (%i1) fibtophi (fib (n));
343                            n             n
344                        %phi  - (1 - %phi)
345 (%o1)                  -------------------
346                            2 %phi - 1
347 (%i2) fib (n-1) + fib (n) - fib (n+1);
348 (%o2)          - fib(n + 1) + fib(n) + fib(n - 1)
349 (%i3) fibtophi (%);
350             n + 1             n + 1       n             n
351         %phi      - (1 - %phi)        %phi  - (1 - %phi)
352 (%o3) - --------------------------- + -------------------
353                 2 %phi - 1                2 %phi - 1
354                                           n - 1             n - 1
355                                       %phi      - (1 - %phi)
356                                     + ---------------------------
357                                               2 %phi - 1
358 (%i4) ratsimp (%);
359 (%o4)                           0
360 @end example
362 @end deffn
364 @deffn {Função} ifactors (@var{n})
365 Para um inteiro positivo @var{n} retorna a factoração de @var{n}. Se
366 @code{n=p1^e1..pk^nk} for a decomposição de @var{n} em factores
367 primos, @code{ifactors} retorna @code{[[p1, e1], ... , [pk, ek]]}.
369 Os métodos de factoração usados são divisões triviais por primos até 9973,
370 o método rho de Pollard e o método da curva elíptica.
372 @example
373 (%i1) ifactors(51575319651600);
374 (%o1)     [[2, 4], [3, 2], [5, 2], [1583, 1], [9050207, 1]]
375 (%i2) apply("*", map(lambda([u], u[1]^u[2]), %));
376 (%o2)                        51575319651600
377 @end example
379 @end deffn
381 @deffn {Função} inrt (@var{x}, @var{n})
382 Retorna a parte inteira da @var{n}'ésima raíz do valor absoluto de @var{x}.
384 @example
385 (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
386 (%i2) map (lambda ([a], inrt (10^a, 3)), l);
387 (%o2) [2, 4, 10, 21, 46, 100, 215, 464, 1000, 2154, 4641, 10000]
388 @end example
390 @end deffn
392 @deffn {Função} inv_mod (@var{n}, @var{m})
393 Calcula o  inverso de @var{n} módulo @var{m}. 
394 @code{inv_mod (n,m)} retorna @code{false}, 
395 se @var{n} modulo @var{m} for zero.
397 @example
398 (%i1) inv_mod(3, 41);
399 (%o1)                           14
400 (%i2) ratsimp(3^-1), modulus=41;
401 (%o2)                           14
402 (%i3) inv_mod(3, 42);
403 (%o3)                          false
404 @end example
406 @end deffn
408 @deffn {Função} jacobi (@var{p}, @var{q})
409 Retorna símbolo de Jacobi de @var{p} e @var{q}.
411 @example
412 (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
413 (%i2) map (lambda ([a], jacobi (a, 9)), l);
414 (%o2)         [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]
415 @end example
417 @end deffn
419 @deffn {Função} lcm (@var{expr_1}, ..., @var{expr_n})
420 Retorna o menor múltiplo comum entre seus argumentos.
421 Os argumentos podem ser expressões gerais também inteiras.
423 @code{load ("functs")} chama essa função.
425 @end deffn
427 @deffn {Função} minfactorial (@var{expr})
428 Examina @var{expr} procurando por ocorrências de dois factoriais
429 que diferem por um inteiro.  
430 @code{minfactorial} então converte um em um polinómio vezes o outro.
432 @c I CAN'T TELL WHAT THIS IS SUPPOSED TO MEAN. !!!
433 @c minfactorial DOESN'T SEEM TO DO ANYTHING binomial DOESN'T DO BY ITSELF !!!
434 @c LOOKING AT THE minfactorial CODE DOESN'T HELP !!!
435 @c If exp involves binomial coefficients then they will be
436 @c converted into ratios of factorials.
438 @example
439 (%i1) n!/(n+2)!;
440                                n!
441 (%o1)                       --------
442                             (n + 2)!
443 (%i2) minfactorial (%);
444                                 1
445 (%o2)                    ---------------
446                          (n + 1) (n + 2)
447 @end example
449 @end deffn
451 @deffn {Função} next_prime (@var{n})
452 Retorna o menor primo maior que @var{n}.
454 @example
455 (%i1) next_prime(27);
456 (%o1)                       29
457 @end example
459 @end deffn
461 @deffn {Função} partfrac (@var{expr}, @var{var})
462 Expande a expressão @var{expr} em frações parciais
463 com relação à variável principal @var{var}.  @code{partfrac} faz uma decomposição
464 completa de fração parcial.  O algoritmo utilizado é baseado no
465 facto que os denominadores de uma expansão de fração parcial (os
466 factores do denominador original) são relativamente primos.  Os
467 numeradores podem ser escritos como combinação linear dos denominadores, e
468 a expansão acontece.
470 @example
471 (%i1) 1/(1+x)^2 - 2/(1+x) + 2/(2+x);
472                       2       2        1
473 (%o1)               ----- - ----- + --------
474                     x + 2   x + 1          2
475                                     (x + 1)
476 (%i2) ratsimp (%);
477                                  x
478 (%o2)                 - -------------------
479                          3      2
480                         x  + 4 x  + 5 x + 2
481 (%i3) partfrac (%, x);
482                       2       2        1
483 (%o3)               ----- - ----- + --------
484                     x + 2   x + 1          2
485                                     (x + 1)
486 @end example
488 @end deffn
490 @deffn {Função} power_mod (@var{a}, @var{n}, @var{m})
491 Usa um algoritmo modular para calcular @code{a^n mod m} 
492 onde @var{a} e @var{n} são inteiros e @var{m} é um inteiro positivo. 
493 Se @var{n} for negativo, @code{inv_mod} é usada para encontrar o inverso modular.
495 @example
496 (%i1) power_mod(3, 15, 5);
497 (%o1)                          2
498 (%i2) mod(3^15,5);
499 (%o2)                          2
500 (%i3) power_mod(2, -1, 5);
501 (%o3)                          3
502 (%i4) inv_mod(2,5);
503 (%o4)                          3
504 @end example
506 @end deffn
508 @deffn {Função} primep (@var{n})
509 Teste de primalidade. Se @code{primep (n)} retornar @code{false}, @var{n} é um
510 número compostro e se esse teste retornar @code{true}, @var{n} é um número primo
511 com grande probabilidade.
513 Para @var{n} menor que 3317044064679887385961981 uma versão deterministra do teste de 
514 Miller-Rabin é usada. Se @code{primep (n)} retornar @code{true}, então @var{n} é um
515 número primo.
517 Para @var{n} maior que 34155071728321 @code{primep} usa
518 @code{primep_number_of_tests} que é os testes de pseudo-primalidade de Miller-Rabin
519 e um teste de pseudo-primalidade de Lucas. A probabilidade que @var{n} irá
520 passar por um teste de Miller-Rabin é menor que 1/4. Usando o valor padrão 25 para
521 @code{primep_number_of_tests}, a probabilidade de @var{n} passar no teste sendo
522 composto é muito menor que 10^-15.
524 @end deffn
526 @defvr {Variável de opção} primep_number_of_tests
527 Valor por omissão: 25
529 Número de testes de Miller-Rabin usados em @code{primep}.
530 @end defvr
532 @deffn {Função} prev_prime (@var{n})
533 Retorna o maior primo menor que @var{n}.
535 @example
536 (%i1) prev_prime(27);
537 (%o1)                       23
538 @end example
539 @end deffn
541 @deffn {Função} qunit (@var{n})
542 Retorna a principal unidade do campo dos números quadráticos reais
543 @code{sqrt (@var{n})} onde @var{n} é um inteiro,
544 i.e., o elemento cuja norma é unidade.
545 Isso é importante para resolver a equação de Pell @code{a^2 - @var{n} b^2 = 1}.
547 @example
548 (%i1) qunit (17);
549 (%o1)                     sqrt(17) + 4
550 (%i2) expand (% * (sqrt(17) - 4));
551 (%o2)                           1
552 @end example
554 @end deffn
556 @deffn {Função} totient (@var{n})
557 Retorna o número de inteiros menores que ou iguais a @var{n} que
558 são relativamente primos com @var{n}.
560 @end deffn
562 @defvr {Variável de opção} zerobern
563 Valor por omissão: @code{true}
565 Quando @code{zerobern} for @code{false},
566 @code{bern} exclui os números de Bernoulli que forem iguais a zero. 
567 Veja @code{bern}.
569 @end defvr
571 @deffn {Função} zeta (@var{n})
572 Retorna a função zeta de Riemann se @var{x} for um inteiro negativo, 0, 1,
573 ou número par positivo,
574 e retorna uma forma substantiva @code{zeta (@var{n})} para todos os outros argumentos,
575 incluindo não inteiros racionais, ponto flutuante, e argumentos complexos.
577 Veja também @code{bfzeta} e @code{zeta%pi}.
579 @example
580 (%i1) map (zeta, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]);
581                                      2              4
582            1        1     1       %pi            %pi
583 (%o1) [0, ---, 0, - --, - -, inf, ----, zeta(3), ----, zeta(5)]
584           120       12    2        6              90
585 @end example
587 @end deffn
589 @defvr {Variável de opção} zeta%pi
590 Valor por omissão: @code{true}
592 Quando @code{zeta%pi} for @code{true}, @code{zeta} retorna uma expressão
593 proporcional a @code{%pi^n} para inteiro par @code{n}.
594 De outra forma, @code{zeta} retorna uma forma substantiva @code{zeta (n)}
595 para inteiro par @code{n}.
597 @example
598 (%i1) zeta%pi: true$
599 (%i2) zeta (4);
600                                  4
601                               %pi
602 (%o2)                         ----
603                                90
604 (%i3) zeta%pi: false$
605 (%i4) zeta (4);
606 (%o4)                        zeta(4)
607 @end example
609 @end defvr