Будем вырезать из бумаги в клетку прямоугольники размером w × h клеток, где w и h – натуральные числа. Некоторые из них можно разрезать по клеточкам на две части так, что из этих частей составится новый прямоугольник другого размера.
Например, прямоугольник размером 9 × 4 клетки можно превратить в прямоугольники 18 × 2, 12 × 3 или 6 × 6, как показано на рисунке:

Аналогично, из прямоугольника 9 × 8 можно сделать прямоугольники размером 18 × 4 и 12 × 6 клеток.
Обозначим через F(w, h) количество различных прямоугольников, которые можно получить из прямоугольника размером w × h клеток. При этом прямоугольники с размерами a × b и b × a считаются одинаковыми, а прямоугольники, конгруэнтные исходному, не учитываются.
Тогда получим: F(2,1) = 0, F(2,2) = 1, F(9,4) = 3 и F(9,8) = 2.
Пусть G(N)=Σ F(w, h) для всех 0 < h ≤ w ≤ N.
Можно проверить, что G(10) = 55, G(10³) = 971745, а G(10⁵) = 9992617687.
Найдите ΣG(10^k), где 1≤k≤12. В качестве ответа укажите 8 младших цифр результата.

Пусть  a, b, c – натуральные числа, а функция F(n) определена следующим образом:
F(n) = n - c при n > b
F(n) = F(a + F(a + F(a + F(a + n)))) при n ≤ b. 
Пусть также 

Тогда, например, при a = 50, b = 2000 и c = 40, получим F(0) = 3240, F(2000) = 2040,
а Z(50, 2000, 40) = 5044935.
Найдите остаток от деления Z(21⁷, 7²¹, 12⁷) на 987654321.

Рассмотрим нечетное число 225 = 3² × 5².
225² = 50625 = 3⁴ × 5⁴ = 9² × 25². Поэтому функция Эйлера φ(50625) = 2 × 3³ × 4 × 5³ = 2³ × 3³ × 5³ .
Итак, число  50625 является квадратом, а φ(50625) является кубом.
Найдите сумму нечетных n, 1 < n < 10¹⁰ , для которых функция Эйлера φ(n²) является кубом натурального числа.

Полем игры из этой задачи является полоска из n клеток, а фишками — монеты.
Одна из этих монет — серебряный доллар — ценная, а остальные — медные — ценности не представляют. Игроки могут совершать ходы двух типов:
1. Сдвинуть любую монету влево на одну или несколько клеток. При этом поставить монету можно только на свободную клетку, и перескакивать через занятые клетки нельзя.
2. Забрать с доски монету, ближайшую к левому краю.
Если ходов первого типа нет, игрок обязан забрать самую левую монету.
Выигрывает тот, кто заберет серебряный доллар.

Выигрышной называется позиция, при которой очередной игрок, правильно выбирая ходы, может обеспечить себе победу независимо от действий второго игрока. Остальные позиции называются проигрышными.
Пусть L(n,c) – количество проигрышных позиций для поля из n клеток, на которое расставляют c медных монет и один серебряный доллар.
Можно проверить, что L(10,3)=150 и L(103,13)= 32792060838490304.
Найдите остаток от деления L(1000003,103) на 1000003.

В этой задаче мы будем рассматривать натуральные числа, имеющие ровно три простых делителя. Например, число 240 имеет простые делители 2,3 и 5. Это наибольшее число, не превышающее 250, имеющее эти три простых делителя и не имеющее других.

Для различных простых чисел p, q и r обозначим через M(p,q,r,N) наибольшее натуральное число, не превышающее N, которое делится на p, q и r, но не имеет других простых делителей. Если таких чисел нет, будем считать, что M(p,q,r,N)=0.

Например:

• M(2,3,5,250)=240.
• M(2,3,7,250)=168, а не 210, поскольку число 210 имеет 4 простых делителя.
• M(3,7,13,250)=0, поскольку нет натуральных чисел, не превышающих 250, которые делятся на 3, 7 и 13.

Пусть S(N) – сумма различных значений M(p,q,r,N) для всех сочетаний p, q и r. Так, S(250)= 4588.

Найдите  S(10 000 000).

Космонавты осваивают планету, имеющую радиус r. Они построили две станции на полюсах планеты, имеющих координаты (0,0,r) и (0,0,-r) в системе координат, связанной с центром планеты.
Также они установили несколько промежуточных станций, расположенных во всех точках поверхности планеты, имеющих целые координаты.

Все станции связаны дорогами, проложенными по кратчайшей дуге большого круга, однако путь между станциями требует больших затрат, равных (d/(π r))², где d – протяженность дороги между двумя станциями. Если маршрут включает посещение нескольких промежуточных станций, затраты на все путешествие равны сумме затрат на отдельных участках.
Маршрут, проложенный между полюсами планеты и не проходящий через промежуточные станции, будет иметь длину πr, а затраты будут равны 1. Если же включить в маршрут одну промежуточную станцию с координатами (0,r,0), затраты уменьшатся вдвое:   (½πr/(πr))²+(½πr/(πr))²=0,5.
Будем называть оптимальным маршрут между полюсами планеты, если он требует минимальных затрат.
Например, при r=7 оптимальный маршрут будет проходить через 6 промежуточных станций, а затраты составят примерно 0,1784943998…
Подсчитайте, сколько промежуточных станций посетят космонавты, путешествуя по оптимальному маршруту между полюсами планеты с r=33333.

Пусть a(n) – наибольший корень многочлена P(x) = x³ - 3ⁿx² + n, например a(2)=8,97517184...
Пусть t(n,p)=[a(n)^p], где скобки […] означают округление вниз до целого.

Найдите восемь младших десятичных знаков суммы ∑t(i,333333333) для i=1,2,3,...30.

Возьмем натуральное число n и рассмотрим последовательность s(n)={1+n/1, 2+n/2, 3+n/3, …k+n/k,…}. Если эта последовательность не содержит целых составных чисел, будем говорить, что число n не порождает составных.
Легко проверить, что последовательность s(30)={31, 17, 13, 11.5, 11, 11, …} содержит только простые и нецелые числа. Поэтому число 30 не порождает составных.
Найдите количество восьмизначных чисел, которые не порождают составных.

Для каждого натурального n определим функцию f(n) как количество хорд параболы y=x², концы которых имеют целочисленные координаты, и квадрат длины которых равен n.

Например, f(4)=1, f(2)=2, f(3)=0 и f(50)=4. На рисунке

изображены 4 хорды с целочисленными координатами концов и квадратом длины равным 50.

Найдите наименьшее число n, для которого f(n)=8.