1 @c /Number.texi/1.22/Sat Nov 25 04:02:55 2006/-ko/
2 @c end concepts Number Theory
4 * Definições para Teoria dos Números::
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}.
20 (%i2) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
22 (%o2) [1, - -, -, 0, - --, 0, --, 0, - --]
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
33 @deffn {Função} bernpoly (@var{x}, @var{n})
34 Retorna o @var{n}'ésimo polinómio de Bernoulli na
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.
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
56 sum ((k+h)^-s, k, 0, inf)
59 @code{load ("bffac")} chama essa função.
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
67 Se @var{y}, ou @var{x - y}, for um inteiro,
68 o the coeficiente binomial é expresso como um polinómio.
74 @c 11! / 7! / (11 - 7)!;
76 @c binomial (x + 7, x);
80 (%i1) binomial (11, 7);
82 (%i2) 11! / 7! / (11 - 7)!;
84 (%i3) binomial (x, 7);
85 (x - 6) (x - 5) (x - 4) (x - 3) (x - 2) (x - 1) x
86 (%o3) -------------------------------------------------
88 (%i4) binomial (x + 7, x);
89 (x + 1) (x + 2) (x + 3) (x + 4) (x + 5) (x + 6) (x + 7)
90 (%o4) -------------------------------------------------------
92 (%i5) binomial (11, y);
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.
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}.
152 @var{expr} é uma expressão compreendendo frações contínuas e raízes quadradas de inteiros.
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]
162 @code{cflength} controla quantos períodos de fração contínua
163 são computados para números algébricos, números irracionais.
167 (%i2) cf ((1 + sqrt(5))/2);
168 (%o2) [1, 1, 1, 1, 2]
170 (%i4) cf ((1 + sqrt(5))/2);
171 (%o4) [1, 1, 1, 1, 1, 1, 1, 2]
173 (%i6) cf ((1 + sqrt(5))/2);
174 (%o6) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
178 Um fração contínua pode ser avaliado através da avaliação da representação aritmética
179 retornada por @code{cfdisrep}.
183 (%i2) cfdisrep (cf (sqrt (3)))$
185 (%o3) 1.731707317073171
189 Maxima não conhece operações sobre frações contínuas fora de @code{cf}.
192 (%i1) cf ([1,1,1,1,1,2] * 3);
194 (%i2) cf ([1,1,1,1,1,2]) * 3;
195 (%o2) [3, 3, 3, 3, 3, 6]
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, ...]}.
209 (%i1) cf ([1, 2, -3] + [1, -2, 1]);
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}.
228 (%i1) cf (rat (ev (%pi, numer)));
230 `rat' replaced 3.141592653589793 by 103993/33102 = 3.141592653011902
231 (%o1) [3, 7, 15, 1, 292]
236 (%i3) %[1,1]/%[2,1], numer;
237 (%o3) 3.141592653011902
242 @defvr {Variável de opção} cflength
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.
251 (%i2) cf ((1 + sqrt(5))/2);
252 (%o2) [1, 1, 1, 1, 2]
254 (%i4) cf ((1 + sqrt(5))/2);
255 (%o4) [1, 1, 1, 1, 1, 1, 1, 2]
257 (%i6) cf ((1 + sqrt(5))/2);
258 (%o6) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
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}.
274 (%i2) 1 + 2 + 3 + 4 + 6 + 12;
276 (%i3) divsum (12, 2);
278 (%i4) 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2;
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}.
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]
296 @defvr {Constante} %gamma
298 @vrindex Constante de Euler-Mascheroni
300 A constante de Euler-Mascheroni, 0.5772156649015329 ....
301 @c DOUBTLESS THERE IS MORE TO SAY HERE.
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}!}.
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.
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]
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.
335 @c fibtophi (fib (n));
336 @c fib (n-1) + fib (n) - fib (n+1);
342 (%i1) fibtophi (fib (n));
345 (%o1) -------------------
347 (%i2) fib (n-1) + fib (n) - fib (n+1);
348 (%o2) - fib(n + 1) + fib(n) + fib(n - 1)
351 %phi - (1 - %phi) %phi - (1 - %phi)
352 (%o3) - --------------------------- + -------------------
353 2 %phi - 1 2 %phi - 1
356 + ---------------------------
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.
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]), %));
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}.
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]
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.
398 (%i1) inv_mod(3, 41);
400 (%i2) ratsimp(3^-1), modulus=41;
402 (%i3) inv_mod(3, 42);
408 @deffn {Função} jacobi (@var{p}, @var{q})
409 Retorna símbolo de Jacobi de @var{p} e @var{q}.
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]
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.
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.
443 (%i2) minfactorial (%);
445 (%o2) ---------------
451 @deffn {Função} next_prime (@var{n})
452 Retorna o menor primo maior que @var{n}.
455 (%i1) next_prime(27);
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
471 (%i1) 1/(1+x)^2 - 2/(1+x) + 2/(2+x);
473 (%o1) ----- - ----- + --------
478 (%o2) - -------------------
481 (%i3) partfrac (%, x);
483 (%o3) ----- - ----- + --------
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.
496 (%i1) power_mod(3, 15, 5);
500 (%i3) power_mod(2, -1, 5);
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
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.
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}.
532 @deffn {Função} prev_prime (@var{n})
533 Retorna o maior primo menor que @var{n}.
536 (%i1) prev_prime(27);
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}.
550 (%i2) expand (% * (sqrt(17) - 4));
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}.
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.
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}.
580 (%i1) map (zeta, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]);
583 (%o1) [0, ---, 0, - --, - -, inf, ----, zeta(3), ----, zeta(5)]
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}.
604 (%i3) zeta%pi: false$