(Следовательно, системы со смешанным целочисленным основанием обладают этим свойством. Наиболее общими системами такого типа являются системы со смешанным основанием, у которых pi = (со + 1)0, р2 = (с, + 1)(со + 1)ро, р-1= ро/(с-1 + 1), ..) 27. [М21] Покажите, что любое ненулевое число имеет единственное "знакопеременное двоичное представление"

20 21 + ... + ( i)t2=<

где ео < ei < • < et.

► 28. [М24] Покажите, что любое неотрицательное комплексное число вида а + Ы, где а и b - целые числа, обладает единственным "периодическим двоичным представлением"

(1 + гГ° + i(l + ir - (1 + гГ - i(l + + г)",

где ео < ei < • • < et (ср. с упр. 27).

29. [МЗЗ] (Н. Г. де Брейн (N. G. de Bruijn),) Пусть So, Si, S2, ... - множества неотрицательных целых чисел; говорят, что совокупность {So, Si, S2, •.} обладает свойством В, если любое неотрицательное целое число п может быть единственным способом записано в виде

п = So + Si -Ь S2 Н----, Sj & Sj.

(Свойство В означает, что О 6 Sj для всех j, поскольку п = О может быть представлено только как 0-I-0-I-0-I-- .) Любая система счисления со смешанным основанием Ьо, bi,b2, дает пример совокупности множеств, удовлетворяющих свойству В, если положить Sj = {О, Bj,... ,{bj - l)Bj}, где Bj = bobi .. .bj-i. В таком случае представление п = so -I-si -- S2 -Ь • • очевидным образом соответствует представлению (9) этого числа по смешанному основанию. Далее, если совокупность {So, Si, S2,. .} Ао, Ai, А2, ... обладает свойством В, то, каково бы ни было разбиение Ао, Ai, А2, ... неотрицательных целых чисел (т. е. Ао и Ai и 2 и • • = {0,1, 2,...} и А; П Aj =0 при i ф j, некоторые из множеств Aj могут быть пустыми), этим свойством обладает и полученная из нее путем "стягивания" совокупность {То, Ti, Т2,...}, где множество Tj состоит из всех сумм вида Si, взятых

по всевозможным выборкам элементов s; € Si.

Докажите, что у!?оая последовательность {Го, Ti, Т2, ...}, удовлетворяющая свойству В, может быть получена посредством "стягивания" некоторой совокупности {So, Si, S2, . •.}, соответствующей системе счисления по смешанному основанию.

30. [М39] (Н. Г. де Брейн.) Пример системы счисления по основанию -2 показывает, что любое целое число (положительное, отрицательное или нуль) имеет единственное представление в виде

+ (-2У + + {-2У, ei>e2>--->et>0, t>Q. Назначение данного упражнения - несколько обобщить это свойство.

a) Пусть последовательность целых чисел bo, bi, 62, • • • такова, что любое целое число п допускает единственное представление в виде

П = Ье+Ье2-\-----\-bet, 61 > 62 > > > О, t > 0.

(Данная последовательность (Ьп) называется бинарным базисом.) Покажите, что найдется такое значение индекса j, что bj нечетно, а для всех к ф j числа bj четны.

b) Докажите, что бинарный базис (Ьп) всегда может быть преобразован в последовательность вида do, 2di, 4d2, ... = (2"d„), где каждое из чисел dk нечетно.

c) Докажите, что если каждое из чисел do, di, d2, ... из п. (b) равно ±1, то последовательность {Ьп) образует бинарный базис тогда и только тогда, когда существует бесконечно много dj, равных -Ы, и бесконечно много dj, равных -1.

d) Докажите, что последовательность 7, -13 • 2, 7 • 2, -13 • 2*, ..., 7 • 2*, -13 • 2*+, ... является бинарным базисом, и найдите представление числа п = 1.

► 31. [Л/55] Одно обобщение представления чисел в обратном двоичном коде, известное как "2-адические числа", было предложено в работе К. Hensel, Crelle 127 (1904), 51-84. (В действительности К. Гензель предложил р-адические числа для любого простого числа р.) 2-адическое число можно рассматривать как двоичное число

и= {.. . U3U2UlUo-U-i . . . U-„)2,

представление которого бесконечно продолжается влево и лишь на конечное количество знаков вправо от разделяющей точки. Сложение, вычитание и умножение 2-адических чисел выполняются в соответствии с алгоритмом обычных арифметических операций, которые, в принципе, допускают возможность неограниченного продолжения влево. Например,

7- (...000000000000111)2 f = (...110110110110111)2

-7= (...111111111111001)2 = (...001001001001001)2

i = (...000000000000001.11)2 = (...110011001100110.1)2

л/=Т= (...100000010110101)2 или (...011111101001011)2.

Здесь число 7 - обычное число "семь" в двоичном представлении, а -7 - обратный код, неограниченно продолженный влево. Легко проверить, что обычная процедура сложения двоичных чисел дает -7 -1- 7 = (... 00000)2 = О, если ее выполнение продолжать неограниченно долго. Значения у и -у представляют собой единственные 2-адические числа, которые после формального умножения на 7 дают соответственно 1 и -1. Значения i и есть примеры 2-адических чисел, не являющихся 2-адическими "целыми", так как они имеют ненулевые биты справа от разделяющей точки. Приведенные два значения л/, получающиеся одно из другого в результате пере.мены знака, являются единственными 2-адическими числами, которые после формального возведения в квадрат дают (...111111111111001)2.

a) Докажите, что любое 2-адическое число и можно разделить на произвольное ненулевое 2-адическое число и, чтобы вычислить 2-адическое число w, удовлетворяющее равенству и = vw. (Следовательно, множество 2-адических чисел образует поле; см. раздел 4.6.1.)

b) Докажите, что 2-адическое представление рационального числа -1/{2п + 1), где п - положительное целое число, можно получить следующим образом. Сначала находим обычное двоичное разложение числа --1/(2п + 1), которое имеет вид периодической дроби (О.ааа ... )2 (а - некоторая строка из нулей и единиц). Тогда (... ааа)2 будет 2-адическим представлением числа -1/(2п -- 1).

c) Докажите, что 2-адическое представление числа и периодично (т. е. кл+а = un для всех больших N при некотором Л > 1) тогда и только тогда, когда и рационально (т. е. и = т/п для некоторых целых чисел тип).

d) Докажите, что если п - целое число, то л/п является 2-адическим числом только в том случае, если для некоторого неотрицательного целого числа п оно удовлетворяет условию nmod2"" = 2*. (Таким образом, либо nmodS = 1, либо п mod 32 = 4, и т. д.)

32. [М40] (И. 3. Руца (I. Z. Ruzsa).) Сформируйте бесконечно много целых чисел, в троичных представлениях которых используются только нули и единицы, а в четверичном представлении - только нули, единицы и двойки.

33. [М40] (д. А. Кларнер (D. А. Юагпег).) Пусть множество D - произвольное множество целых чисел, b-любое положительное целое число, а кп-количество различных целых чисел, которые могут быть записаны как п-разрядные числа (Un-i aiao)b по основанию b с цифрами а; в D. Докажите, что последовательность (кп) удовлетворяет линейному рекуррентному соотношению, и поясните, как вычислить производящую функцию k„z". Проиллюстрируйте разработанный алгоритм, показав, что в случае, когда Ь = 3 и D = {-1,0,3}, число кп есть число Фибоначчи.

► 34. [22] (Г. В. Райтвайзнер (G. W. Reitwiesner), 1960.) Поясните, как представить заданное целое число п в виде (...020100)2, где каждое из aj есть -1, О либо 1, используя наименьшую ненулевую цифру.