3 Теория чисел

Округление, целые и дробные части

Функция floor(x) округляет число x вниз, то есть возвращает наибольшее целое число, не превосходящее x, функция ceiling(x) округляет число вверх. Дробную часть числа x можно вычислить, как x-floor(x).

Целочисленное деление и остатки

Для нахождения частного при целочисленном делении следует использовать функцию floor, а для нахождения остатка от деления - функцию mod. Примеры: 

(%i1) floor(100/3);
(%o1) 33
(%i2) mod(100,3);
(%o2) 1

НОД, НОК

Для нахождения наибольшего общего делителя двух чисел используется функция gcd, для нахождения наименьшего общего кратного – функция lcm. Пример: 

(%i3) igcd(57,179);
(%o3) 1;

Расширенный алгоритм Евклида используется для нахождения по данным n и m таких чисел u и v, что un+vm=d, где d – наибольший общий делитель m и n. Для этого используется функция gcdex(n,m,x), где m, n – исходные числа, а x - произвольная переменная. На самом деле, расширенный алгоритм Евклида (да и обычный алгоритм Евклида) работает не только для чисел, но и для многочленов, поэтому для работы расширенного алгоритма Евклида для натуральных чисел, а не для многочленов, нужно задать формальную переменную в многочлене. 

(%i4) gcdex(57,179,x);
(%o4) [22,-7,1]
Последний вывод означает, что НОД(57, 179)=1 и 22*57-7*179=1.
 

Проверка на простоту, разложение на множители, построение простых чисел

Для проверки числа на простоту используется функция primep, которая возвращает true, если число простое и false – если составное. Для разложения числа на множители используются функции factor и ifactors. Первая функция возвращает результат в виде произведения степеней простых чисел, вторая – в виде списка простых чисел и их степеней. Все эти функции работают значительно эффективней простого подбора делителей, проверка на простоту осуществляется быстрее полного разложения на множители.

Для построения простых чисел используются функции prev_prime, next_prime. Функция prev_prime(n) возвращает наибольшее простое число, которое меньше n, функция next_prime(n) возвращает наименьшее простое число, которое больше n. 

(%i5) primep(7!);
(%o5) false
(%i6) factor(7!);
(%o6) 24 32 5 7
(%i7) ifactors(7!);
(%o7) [[2, 4], [3, 2], [5, 1], [7, 1]]
(%i8) next_prime(7!);
(%o8) 5051
(%i9) primep(%);
(%o9) true

Специальные функции

Функия divsum(n) (сигма-функция) возвращает сумму делителей делителей числа n. Функция divsum(n,k) возвращает сумму k-х степеней делителей числа n.

Функция totient(n) (фи-функция Эйлера) возвращает количество чисел, меньших n и взаимно простых с n.

Производные и интегралы

Производная функции вычисляется  при помощи фукнции diff(f(x),x):
(%i10) diff(sin(x),x);
(%o10) cos(x)
(%i11) diff(%,x);
(%o11) -sin(x)
Производную второй и более высокой степени можно посчитать, указав степень производной в виде третьего параметра функции diff:
(%i12) diff(sin(x),x,2);
(%o12) -sin(x)
Для вычисления неопределенного интеграла используется функция integrate(f(x),x):
(%i13) integrate(sin(x),x);
(%o13) -cos(x)
(%i14) integrate(log(x),x);
(%o14) x*log(x)-x
Для вычисления определенного интеграла функции integrate необходимо передать еще два параметра: пределы интегрирования:
(%i15) integrate( sqrt(1-x^2),x,-1,1);
(%o15) %pi/2

Упражнения

  1. Разложите на множители число 1010+1.
  2. Проверьте, является ли число 101000+1 простым.
  3. Найдите наибольший общий делитель чисел 1010+1 и 1018+1.
  4. Пьер Ферма считал, что все числа вида 22n+1, где n целое неотрицательное число – простые. Опровергните утверждение Ферма.
  5. Найдите ближайшие сверху и снизу простые числа к 10100.
  6. Найдите общий вид решения в целых числах уравнения 3x+5y=179.
  7. Вычислите производные для функций xx, xxx.
  8. Вычислите неопределенные интегралы для следующих функций: xln(x), ln2(x), sin3(x), tg(x). 
  9. Вычислите определенный интеграл по всей числовой прямой от функции e-x2/2.