В некотором городе построили телефонную сеть на миллион абонентов с шестизначными телефонными номерами. Данные о телефонных звонках фиксировали в базе данных. Перед вами несколько первых записей из нее:

Номера абонентов S_2n-1 и S_2n для данной таблицы мы получили с помощью генератора псевдослучайных чисел Фибоначчи с запаздыванием:
При 1 ≤k≤55, S_k = [100003 - 200003k + 300007k³] (mod 1000000)
При 56 ≤k, S_k = [S_k-24 + S_k-55] (mod 1000000)
(p(mod q) означает остаток от деления p на q)
При необходимости полученные числа дополняли до шести знаков нулями слева.
Мы будем считать, что если X позвонил Y, или наоборот, Y позвонил X, X и Y становятся друзьями. Если X является другом Y, а Y другом Z, то мы также считаем X и Z друзьями, и так далее для сколь угодно длинных цепочек.
Телефонный номер мэра города – 100000. После очередного звонка количество друзей мэра превысило половину населения города. Сколько в этот момент у него оказалось друзей (включая его самого)?

Полупростым называется натуральное число, представимое в виде произведения двух простых чисел (не обязательно различных), например, 15 = 3 × 5; 9 = 3 × 3; 22 = 2 × 11.
Существует ровно десять полупростых чисел, не превышающих 30: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26. Их сумма равна 152.
Найдите сумму полупростых чисел, не превышающих 10⁸.

Рассмотрим различные тройки взаимно простых натуральных чисел x < y  < z < 10⁷ таких, что x²+y²=z². Найдите количество натуральных чисел p < 10⁷, которые не входят ни в одну такую тройку.

В ряду 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,... представлены числа, которые имеют простые делители только числа 2, 3 и 5. Продолжите этот ряд и найдите число в этом ряду, которое находится на месте с номером 10000. 

Операция возведения в сверхстепень, или тетрация, обозначается как a↑↑b или ^ba, и определяется для натуральных a и b следующим образом:
a↑↑1 = a,
a↑↑(k+1) = a (a↑↑k).
Так, 3↑↑2 = 3³ = 27, отсюда 3↑↑3 = 3²⁷ = 7625597484987, а 3↑↑4 примерно равно 10^{3638334640024,1}.
Найдите 8 последних цифр числа 2011 ↑↑ (2011 ↑↑ 2011).

Правильный треугольник со стороной 8 можно разбить на 64 одинаковых правильных треугольника, как показано на рисунке:

Раскрасим теперь то, что получилось, в три цвета: красный, синий и зеленый. Будем считать допустимой такую раскраску, при которых никакие два соседних (имеющих общую сторону) единичных треугольника раскрашены в разные цвета. Треугольники, имеющие общую вершину, но не имеющие общей стороны, не считаются соседними.
Вот пример допустимой раскраски для треугольника со стороной 8:

Обозначим через f(n) число различных допустимых раскрасок для треугольника со стороной n.
Если для получения одной раскраски из другой необходимы преобразования симметрии или повороты, мы будем считать такие раскраски различными.
Тогда f(1)=3, f(2)=24, f(3)=528.
∑f(n)=555 для 1 ≤ n ≤ 3.
Найдите ∑ f(n) для 1 ≤ n ≤ 8.

В одном университете очень строго следят за посещаемостью и дисциплиной. Если в контрольный  период студент хотя бы дважды опаздывает или в течение любых трех дней подряд хотя бы дважды прогуливает, то его лишают стипендии.
Если контрольный период продолжается n дней, то его можно зашифровать строкой из n символов, используя букву L для опозданий, A для прогулов и O для дней, когда студент приходил на занятия вовремя.
Из 81 возможной строки для 4-дневного зачетного периода стипендиальным требованиям удовлетворяют 24 строки:

OOOO OOOA OOOL OOAO OOAL OOLO OOLA OAOO OAOL OALO OLOO OLOA OLAO AOOO AOOA AOOL AOLO AOLA ALOO ALOA LOOO LOOA LOAO LAOO

А сколько строк удовлетворяет стипендиальным требованиям для 30-дневного зачетного периода?

На Олимпиаде в Индии, которую проводил Маугли, в забегах приняли участие все животные - и жалкие дождевые черви, и вожак стаи старый Акелла, и даже злобный Шер-Хан. Их оказалось очень много - ровно 1 миллиард. Все животные получили последовательные номера от единицы и до одного миллиарда.

После первого забега победили участники у которых были нечетные номера, их заново пронумеровали - 1-й сохранил свой номер, участник с номером 3-й номер стал 2-м, с номером 5 - стал 3-м и так далее, проигрывшие выбыли из соревнования.

Во втором забеге победили все участники, которые имели четные номера, их также заново пронумеровали: 2-й стал 1-м, 4-й - 2-м, 6-й - 3-м и так далее.

Как потом выяснилось, и далее в нечетных забегах побеждали участники с нечетными номерами, а в четных - с четными, и каждый раз после очередного забега участников перенумеровывали по той же схеме.

В конце концов победила хитрая Багира. Выясните какой у нее был номер в начале сревнований?

Автоморфные числа - это числа, десятичная запись квадрата которых оканчивается цифрами самого этого числа. Например, число 5 (5²=25) или 6 (6²=36). Эти числа составляют последовательность: 1, 5, 6, 25, 76, 376, 625, 9 376, 90 625, 109 376, 890 625,... (0 не считается).

В системе счисления с основанием 14 также имеются автоморфные числа. Рассмотрим ряд из этих чисел. Найдите число, находящееся на 28-м месте в этом ряду.

Ответ запишите в десятичной системе счисления.

Известная задача от компании Google звучит так: найдите первое 10-значное простое число, состоящее из последовательных цифр в записи числа e. Немного усложним условие - найдите первое 11-значное число.