Question

Мальчик лёша на уроке узнал о системах счисления. он понял, что вместо по-
следовательности 1, 10, 100, 1000, . . для десятичной системы счисления или последовательности

1, 2, 4, 8, 16, . . для двоичной системы счисления можно рассматривать произвольную возрастаю-
щую неограниченную последовательность натуральных чисел

q = (q1, q2, q3, . .)

с условием q1 = 1. назовём её базой. по базе q можно, как и в обычных системах счисления,
представить любое натуральное число n. для этого нужно сначала выбрать натуральное число

k, для которого выполняется неравенство qk ¬ n < qk+1. разложением числа n по базе q можно
назвать набор натуральных чисел εk, εk−1, . . , ε1, который определяется следующим образом. для
начала, εk = bn/qkc, где bxc обозначает наибольшее целое число, меньшее x. остальные числа εj ,
где 1 ¬ j < k, определяются по правилу
εj =
$
n −
pk
i=j+1 εi
· qi
qj
%

сумму чисел pk

j=1 εi из разложения числа n по базе q обозначим через s(n, q). кроме того,

определим c(n, q) : = s(1, q) + s(2, q) + . . + s(n − 1, q).
пусть t ∈ n. будем говорить, что база q является t–большой, если существует положительная
константа α ∈ r такая, что для всех n 2 верно c(n, q) ¬ α · nt
.

1. пусть q является арифметической прогрессией. верно ли, что q является 1–большой? до-
кажите или опровергните.

2. рассмотрим базу q = (1, 2, 4, 8, 16, . .) = (2n−1
)
+∞
n=1.

(a) верно ли, что q является 1–большой? докажите или опровергните.
(b) верно ли, что q является 2–большой? докажите или опровергните.
(c) найдите наименьшую константу α ∈ r такую, что для всех n 2 верно c(n, q) ¬ α·n2
.
3. для каждого натурального m ∈ n исследуйте вопросы предыдущего пункта для базы q =
(1, m, m2
, m3
, . .) = (mn−1
)
+∞
n=1.

4. рассмотрим последовательность fn, определенную условием: f0 = 0, f1 = 1 и fn = fn−1 +
fn−2 для всех n 2. для базы q = (1, 2, 3, 5, 8, . .) = (fn+1)
+∞
n=1 найдите наименьшее t ∈ n и

наименьшую положительную константу α ∈ r такую, что c(n, q) ¬ α · nt
.
5. (a) пример базы, которая не является t–большой ни для какого t ∈ n.
(b) для каждого t ∈ n пример базы, которая является t–большой, но не является
(t−1)–большой. найдите для них соответствующие константы (минимально возможные).