AOP_Tom1 (1021736), страница 17
Текст из файла (страница 17)
д. Покажите, что если р — простое число, то у(р) = р — 1, и вычислите у(р'), где е — положительное целое число. ь 28. [Мйб) Покажите, что метод, который использовался для доказательства теоремы Р, можно применить для доказательства следующего ее обобщения, называемого пгеоремой Эйлера: если а .1. гп, то ае~ 1 = 1 (по модулю ог) для любого положительного целого пь (В частности, число и' из упр. 19 можно взять равным ищ ~ ~ аког) пг.) 29. [мйй) Функция 1 (и) от положительного целочисленного аргумента и называется мульигииликатиеной (ти(ггр!гсагте), если 1(гг) = ](г)](г) для любых взаимно простых г и з. Покажите, что каждая нз перечисленных ниже функций является мультипликативной: (а) 1(и) = и', где с — произвольная постоянная; (Ь) 1(и) = [и не делится на к~ для любого целого Й > 1]; (с) 1(и) = с*, где Й вЂ” количество различных простых чисел, которые делят и; (б) произведение любых двух мультипликативных функций.
30. [МЗО) Докажите, что функция р(и) из упр. 27 является мультипликативной. Испоггьзуя этот факт, вычислите р(1000000) н предложите простой метод вычисления гг(и), когда и разложено на простые множители. 31. [МЗО) Докажите, что если функция 1'(и) мультипликативна, то д(и) = 2 г~„~(с() также мультипликативна. 32. [М18) Докажите, что для любой функции 1(к, р) выполняется тождество Е ЕПс,й) =Е Е ф(с,сб) зп /1 лз зг 33. [М13] Для целых чисел пг и и вычислите: (а) [г(и+щц+ [г(и-щ+1).)' (Ь) ]г(и+щ)1+ Гг(и-щ+1)] (Обратите внимание на частный случай гл = О,) ь 34. [Мг1) Какие необходимые и достаточные условия нужно изложить на действительное число Ь > 1, чтобы равенство [1ойг к] = [!ойг[х]] выполнялось для всех действительных г > 1? ь Зб.
[МЯР] Пусть т и и — целые числа и и > О. Докажите, что равенства [(т+ ги)/и] = [([к] + ти)/и] выполняется для всех действительных ж (Заметим, что т = Π— зто очень важный частный случай.) Будет ли справедливо аналогичное равенство для функции "потолок"? Зб. [МЗЯ] Докажите, что ~„", [Ь/2] = [и~/4]; вычислите также сумму 2 ", [6/2] ь 37. [МЯР] Пусть т и и — целые числа, и > О. Покажите, что Е ~тУс+х] (т 1ни 1) о 1 — + + Ы [я/Ы], и 2 2 о<а<.
где 4 — наибольший общий делитель т и и, а х — любое действительное число. 38. [Мйб] (Е. Буше (Е. Внзсбе), 1909.) Докажите, что для всех действительных чисел я и у, причем у > О: [т+ -~ = [ту+ [т+ 1]([у] — у).] 6 о<к<к В частности, если у в целое положительное число, то, обозначив его через и, получим важную формулу: [т]+ [т+ — ~ + + [х+ — ~ = [ит]. 39. [НМЯЯ] Функция /, для которой /(*) + /(т+ -„') + . + /(я+ — "„') = /(ие), где и— любое положительное целое число, называется реиликатиеиой функцией. Из предыдущего упражнения следует, что функция [я] репликативна. Покажите, что репликативны следующие функции: ) /(*) =*-Ы 6) /(я) = [я — целое число]; с) /(т) = [х — положительное целое число], д) /(я) = [существует рациональное число г и целое т, такие, что х = гя+ги]; е) еще три функции, аналогичные функции из (с1), для которых г и/илн т рассматриваются только на множестве положительных чисел; () /(х) = 1об [2 з1пях[, если допускается значение /(к) = -оо; б) сумма любых двух репликативных функций; 6) произведение репликативной функции на константу," !) функция д(х) = /(я — [в]), где /(я) репликативна.
40. [НМЯб] Исследуйте класс репликативных функций; определите все репликативные функции специального типа. Например, является ли функция из и. (а) в упр. 39 единственной непрерывной репликатнвной функцией? Интересно рассмотреть также более общий класс функций, для которых 11 / и — 11 /(х) + / (к 4- — ( +. +/ ~х+ — ) = а„/(ит) +6„ и/ и Здесь а„и Ь вЂ” это числа, которые зависят от и, но не зависят от я. Производные и интегралы от данных функций (если Ь = О) относятся к атому же типу. Если мы потребуем, чтобы 6„= О, то получим, например. многочлены Бернулли, тригонометрические функции соске и сзс~яя, а также обобщенную дзета-функцию Гуркина б(ськ) = 2 > 1/(6+ т)', где з фиксировано. При 6 ф О получим другие хорошимзвестные функции, например пси-функцию.
41. [МЯЯ] Пустьам аи аз, — последовательность 1, 2, У, 3, 3, 3, 4, 4,4, 4,.... Выразите а„как функцию от и с помощью функций "пол'* и/или "потолок', 42. [МОД (а) Докажите, что ае = па„— ~~ Ь(аьы — аь), если и > О. Е (Ь) Предыдущая функция используется для вычисления сумм, в которых присутствует функция "пол". Докажите, что если Ь вЂ” целое число и Ь > 2, то Я[)об,й] = (и+ 1)[(об,п] — (Ь(ии ты — Ь)/(Ь-1).
э=1 43. [МОЯ] Вычислите сумму ~~~, [Л]. 44. [ЛЩ] Покажите, что 2 >о 2„[(п+ /Ь )/Ь +'] = п, если Ь и п — целые числа, п > О и Ь > 2. Чему равна эта сумма при п < О? ь 46. [М28] Результат упр. 37 несколько удивляет, так как из него следует, что .Е 1='-"! =Ь!М Это "соотношение взаимности" — только один пример из множества подобных формул (см. раздел 3.3.3), Покажите, что для любой функции / В частности, докажите,что ( [т//п] + 1) ~~- ~1'и ~ ( 1' ) (т) [Указание. Выполните замену переменных г = [т1/и]. Биномиальные коэффициенты (ь) обсуждаются в разделе 1.2.6.] 46. [Мвр] (Обобщенный закон взаимности.) Обобщите формулу из упр. 45 таким образом, чтобы полУчить выРажение длЯ сУммы 2 е .<„„ /([т//п]), где и — любое положительное действительное число.
ь 47. [МЯ!] Пусть р — нечетное простое число. Определим символ Лежандра, (хр), считая его равным +1, О или — 1, в зависимости от того, чему равно д1р В шойр: 1, О или р — 1. 1р-1рэ (См. упр. 26.) а) Пусть д не кратно р. Покажите, что числа ( — 1)1 '7Р1(2йд шойр), О < й < р/2, сравнимы по модулю с числами 2, 4, ..., р — 1, взятыми в определенном порядке. Следовательно, ф = ( — 1), где а = 2 „ ,[2йд/р].
Ь) Используйте результат (а) для вычисления (р). с) Пусть д — нечетное число. Покажите, что 2 е«ь<?з[2хд/р] ра 2 е<ь< ?з(Ьд/р] (по модулю 2). [Указание. Рассмотрите величину [(р — 1 — 2Ь) д/р] ] 6) Воспользуйтесь общей формулой взаимности из упр. 46, чтобы получить закон квадратичной взаимности (1)(~) = (-1)1Р Ц1е 'В~, если р и д — различные нечетные простые числа. 48.
(лейб] Пусть гп и и — целые числа. Докажите или опровергните следующие тождества: ) ~т+и — 1~ ~т1 (Ь) ~и+2 — (и128] ~ ~8и+24~ 49. [ЛИО) Предположим, что целочисленная функция 1'(х) удовлетворяет следующим двум простым условиям: (1) 1'(х + 1) = у(х) + 1; (й) для всех положительных целых и 1(х) = 1(1(их)/и). Докажите, что для всех рациональных х либо 1(х) = (х], либо 1(х) = (х). 1.2.5. Перестановки и факториапы Перестановкой п обвсктов называется способ последовательного расположения и различных объектов с учетом порядка. Например, для трех объектов (а, Ь, с) существует шесть перестановок: а Ь с, а с Ь, Ь а с, Ь с а, с а Ь, с Ь а. Свойства перестановок играют очень важную роль в анализе алгоритмов; далее в этой книге мы установим много интересных фактов, касающихся перестановок (регшпсагюп)е. А пока наша задача — просто сосчитать их, т.
е. выяснить, сколько имеется возможных перестановок для и объектов. Существует и способов выбора крайнего объекта слева (первого); после того как этот выбор сделан, существует и — 1 способ выбора следующего за ним объекта. Таким образом, получаем и(и — 1) способов выбора объектов для первых двух позиций. Аналогично третий объект можно выбрать п — 2 способами, что в итоге дает и(и — 1)(п — 2) возможных способов выбора первых трех объектов. В общем случае, обозначив через р„ь количество способов выбора Й объектов из и с учетом порядка, получим роа = и(п — 1)...(п — )с + 1). (2) Отсюда вытекает, что общее число перестановок выражается формулой р„„= и(и — 1) ... (1).
Для наших прикладных целей очень важное значение имеет процесс построения всех перестановок из и объектов методом индукции в предположении, что все перестановки из и — 1 объектов уже построены. Давайте перепишем (1), заменив буквы (а, Ь, с) цифрами (1, 2, 3); тогда получим следующие перестановки: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. (3) А теперь давайте подумаем, как из этого набора получить все возможные перестановки из четырех цифр (1.2,3,4).
Существует два основных метода перехода от перестановок из и — 1 объектов к перестановкам из и объектов. Метод 1. Для каждой перестановки агат ... а„ г из (1,2.....,п — 1) объектов построим еще и перестановок, помещая число и на все возможные места, в результате чего получим п аг аз ... а„ ш ага аз ... а„ „ ..., аг аг ..
и а„ м а, аз ., а„ г и. ь В связи с чрезвычайной важностью перестановок Воган пратт (напбьап Ргап) предложил дла краткости называть их 'реггпе". Как только предложение Пратта будет приинто, учебники по прогпаммиооаанию немного "похудеют' (и, возможно, подешевеют). Например, для перестановку 2 3 1 из (3) получим следующее: 423 1, 2431, 2 34 1, 2 3 1 4. Очевидно, это все возможные перестановки нз п объектов, причем ни одна из них не повторяется. Метод 2.
Для каждой перестановки'а1 аг ... а„ 1 из (1, 2,...,п — 1) объектов построим еще и перестановок следующим образом. Сначала построим набор 1 г / 11 аг аг ... а„ г г, аг аг .. а„ г г, ..., аг аг .. а„ г (и — г). Затем заменим элементы каждой перестановки цифрами (1, 2,..., п), сохранял порядок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
