Функция Эйлера φ(n) определяется так: для любого натурального n>1 её значение равно количеству натуральных чисел, меньших n и взаимно простых с n, по определению φ(1)=1, в частности φ(9)=6 (числа 1, 2, 4, 5, 7, 8 - взаимно просты с числом 9). 

Необходимо найти число n≤=1000000, для которого отношение n²/φ(n) максимально.

Для каждого p можно посчитать количество пифагоровых треугольников с таким периметром. Например для 12 и 24 таких треугольников ровно по одному: (3,4,5) и (6,8,10) соответственно. А для периметра 120 таких треугольников уже 3: (30,40,50), (20,48,52), (24,45,51).

Найдите количество периметров p ≤ 10000000, для которых число различных пифагоровых треугольников с данным периметром является простым.

Каждому числу сопоставим сумму факториалов его цифр.

Например: 15 → 1! + 5! = 121

Среди всех чисел есть числа которым сопоставлены они сами. Например 145 → 1! + 4! + 5! = 145

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

Оказывается что циклов длиной более одного всего 3:

169 → 363601 → 1454 → 169

871 → 45361 → 871

872 → 45362 → 872

Также известно, что для чисел меньше 1000000 цепочки, прежде чем числа начнут повторяться, будут содержать не более 60 членов.

Найдите все цепочки максимальной длины начинающиеся с чисел меньших 1000000. В ответе укажите сумму всех первых значений таких цепочек.

Попытаемся разложить число 5 в сумму простых:

5 = 5

5 = 2 + 3

5 = 3 + 2

Назовем количеством композиций числа n из простых чисел - количество всех упорядоченных последовательностей простых чисел, в сумме составляющих n. Количество композиций для n = 5: 3, в примере последние две композиции различны.

Назовем количеством разбиений числа n на простые - количество всех неупорядоченных множеств из простых чисел в сумме дающих n. Количество разбиений для n = 5: 2, в примере последние два разбиения считаются одинаковыми.

Найдите минимальное n для которого отношение числа композиций к числу разбиений больше одного миллиарда. В ответе запишите разность числа композиций и разбиений для этого n.

Для каждого натурального n можно найти число раскладываний камней на кучки. Например, для n=5 количество различных раскладываний 7:

ООООО

ОООО О

ООО ОО

ООО О О

ОО ОО О

ОО О О О

О О О О О

Найдите минимальное количество камней, для которого сумма цифр количества различных раскладываний больше 1000.

Одна из систем защиты банковских терминалов устроена следующим образом:

Пользователю сообщается пин-код состоящий из некоторого количества цифр, каждый раз при входе пользователя просят ввести в терминал несколько конкретных символов. Например, для пин-кода 54321 могут попросить ввести 1-й, 3-й и 5-й символы (номера символов всегда возрастают, то есть нужную часть пин-кода можно получить «выкидыванием» оставшихся символов). В этом случае пользователю для авторизации надо ввести '531'. Таким образом просто подсмотрев то, что ввел пользователь злоумышленник не сможет получить доступа. Вам удалось проследить приличное количество авторизаций одного пользователя, хотя Вы и не знаете какие цифры просили вводить. Найдите подходящий пин-код минимальной длины.

Вот лог авторизаций:

'219', '319', '315', '387', '365', '417', '397', '165', '319', '420', '489', '469', '019', '286', '238', '495', '038', '316', '095', '415', '435', '431', '426', '423', '206', '409', '215', '869', '295', '416', '089', '015', '219', '289', '285', '269', '867', '495', '695', '067', '157', '386', '157', '019', '897', '189', '407', '189', '089', '426'

Дана таблица из чисел, надо найти разность минимальных путей от верхней границы до нижней и от левой границы до правой. Для движения от верхней границы возможны только движения: вправо, вниз и влево. Длина пути считается так: сумма всех чисел в клетках через которые мы проходим. Для движения от левой границы к правой возможны движения: вверх, вниз и вправо. Путь от верхней границы до нижней — это путь начинающийся в любой из клеток первой строчки и заканчивающийся в любой из клеток последней строки таблицы. В ответ выведите разность длины минимального прохождения квадрата сверху вниз и слева направо(разность найденных минимальных путей).

Пример для таблицы 4 на 4:

40,35,13,32
60,58,40,20
83,18,11,53
72,50,85,75

Длина минимального пути сверху-вниз: 13+40+11+18+50 = 132. Длина минимального пути слева-направо: 40+35+13+32 = 120. Разность 12.

Найдите разность для таблицы размера 40 на 40:

39,27,46,53,47,35,91,17,91,87,34,83,96,68,62,63,18,16,44,15,48,92,23,98,50,63,59,54,83,65,46,46,68,70,51,96,51,78,48,67

89,15,80,97,44,34,22,43,33,11,69,42,45,46,43,74,58,37,31,66,82,39,77,36,85,15,54,24,84,18,58,57,86,29,50,59,79,30,98,84

30,94,97,70,68,31,56,12,48,78,45,92,80,22,88,36,32,49,29,67,62,15,80,84,72,17,29,17,23,62,40,38,86,39,38,78,46,33,83,13

86,85,73,89,60,19,56,71,31,25,43,52,80,37,77,55,38,60,50,44,69,43,47,32,76,23,45,89,44,82,24,42,75,34,50,93,83,22,22,48

99,63,77,57,77,70,31,39,45,18,95,40,84,97,80,92,31,82,37,79,18,68,71,35,56,15,77,73,99,26,87,10,15,40,45,52,22,10,90,86

97,56,86,80,17,19,76,14,77,66,80,97,89,67,69,26,48,67,98,38,62,94,47,97,35,63,78,80,64,80,28,67,11,18,37,16,36,91,99,32

29,72,28,84,32,47,33,69,37,95,83,10,71,94,30,17,58,75,40,72,68,50,25,27,79,81,77,20,63,44,67,41,86,43,18,70,18,92,39,64

27,16,32,91,94,83,80,60,21,81,21,74,88,66,15,76,86,68,35,87,34,90,52,93,98,16,20,13,17,95,70,85,38,23,19,58,53,52,25,70

93,12,26,98,89,78,64,66,11,91,87,17,70,48,38,30,82,42,63,66,33,31,32,96,13,26,63,82,79,41,95,74,62,70,38,82,84,29,68,97

37,11,94,81,97,67,98,92,15,37,67,55,91,79,50,37,71,93,92,11,24,36,40,63,39,68,81,55,30,39,13,49,54,81,73,44,76,42,52,52

87,29,83,51,32,67,57,26,67,34,57,81,61,98,39,88,63,91,46,40,30,44,57,83,72,48,98,16,84,11,64,43,94,69,28,14,79,12,14,94

35,25,17,84,64,55,75,30,38,63,85,91,11,84,13,69,79,93,16,34,61,36,21,68,86,15,32,86,19,84,34,97,98,16,45,73,61,86,14,91

67,53,68,89,57,93,93,90,78,25,85,74,64,82,26,29,46,15,34,95,87,84,75,89,67,69,87,75,23,49,57,20,42,43,51,30,41,62,85,38

52,38,31,13,35,97,45,99,63,83,20,97,20,68,77,89,29,55,43,71,45,36,19,89,59,54,89,35,56,90,10,55,12,10,31,12,25,61,17,40

95,57,98,21,93,99,36,29,52,68,93,52,27,70,95,66,50,35,21,17,35,94,69,99,98,39,92,23,52,22,24,57,32,82,22,56,33,22,92,53

98,51,78,39,46,69,32,38,20,85,31,44,14,34,35,36,62,36,22,25,43,26,80,53,27,34,46,63,33,49,47,52,34,54,63,30,25,52,10,89

33,56,43,25,63,94,80,51,86,74,12,80,96,71,21,77,68,38,86,89,48,26,83,40,78,12,89,32,14,78,66,71,77,15,17,70,79,83,24,56

59,35,12,84,89,54,87,85,31,46,33,29,20,71,30,86,15,13,31,89,61,52,10,60,96,94,90,44,79,89,63,58,67,14,63,56,21,91,44,65

87,43,40,12,10,96,64,80,96,18,33,34,38,86,43,65,67,54,92,17,52,13,69,88,69,67,31,18,41,73,48,39,23,81,61,24,49,71,32,28

70,26,14,41,70,92,21,88,92,99,52,58,47,75,21,66,39,64,20,77,82,88,62,81,17,45,36,88,22,10,69,70,49,82,15,30,14,29,40,45

27,11,97,27,65,44,38,37,63,13,91,89,29,28,80,89,69,83,17,93,84,84,88,27,28,61,90,83,76,68,83,23,38,14,88,78,35,81,87,29

82,41,69,77,26,23,11,79,29,31,34,90,30,52,38,13,69,17,62,82,87,13,85,47,12,99,12,90,67,23,80,99,52,20,76,33,34,34,89,14

77,11,16,31,71,59,42,99,45,54,91,83,62,49,86,49,75,75,17,63,69,84,77,73,23,44,51,25,39,76,77,13,92,56,60,43,56,54,47,21

48,29,99,67,74,23,93,97,56,86,22,79,34,56,69,32,75,12,55,83,57,42,30,62,33,49,82,65,48,60,93,83,24,98,47,53,58,51,12,40

11,79,29,16,84,86,17,97,47,90,31,50,35,82,77,81,97,67,71,20,60,81,82,28,82,20,99,98,99,31,83,73,13,49,72,58,36,42,74,89

30,54,20,40,33,98,99,88,69,58,77,46,75,23,10,57,72,19,16,25,23,21,87,68,77,91,75,36,61,74,19,54,31,57,91,26,90,42,19,83

89,24,39,90,55,84,58,13,85,59,62,31,42,71,48,37,42,48,78,93,96,53,98,90,75,11,36,51,51,17,54,10,47,74,11,81,29,38,50,76

19,95,10,25,23,50,59,75,18,20,62,16,86,21,86,50,67,32,74,73,49,76,62,84,24,88,40,62,51,75,90,84,54,16,55,78,94,60,24,55

48,80,37,52,29,93,34,56,87,28,36,82,28,60,98,46,94,95,66,39,91,57,94,75,47,65,97,57,78,23,34,77,30,62,20,71,82,56,55,36

10,84,37,60,55,68,59,28,32,44,36,40,32,99,61,85,38,20,51,21,57,75,65,44,52,99,85,16,98,16,39,36,24,25,87,95,34,50,95,17

36,74,37,83,66,25,19,97,92,93,19,67,93,73,45,53,68,71,95,27,17,68,53,60,43,87,78,72,64,61,76,74,66,58,86,42,76,64,13,40

46,14,35,80,40,27,44,76,61,59,77,25,32,72,20,21,31,43,40,28,45,38,59,12,10,26,21,17,90,85,20,43,65,40,49,50,87,70,36,36

97,76,47,93,58,30,31,85,46,86,26,77,81,99,44,33,61,84,33,48,88,23,85,57,75,92,55,24,36,74,52,21,58,50,93,91,27,39,40,44

57,91,68,51,63,54,27,18,28,53,77,74,84,14,94,33,73,85,38,15,37,69,54,83,77,29,77,99,11,30,15,88,18,18,88,51,66,51,77,76

81,42,74,63,79,67,11,74,82,10,25,39,24,74,74,20,42,21,81,75,37,65,82,10,42,87,90,20,29,44,40,41,65,48,43,62,64,71,33,66

33,14,31,17,41,40,81,58,23,39,67,54,61,71,65,49,32,31,98,54,46,65,46,81,44,17,39,47,74,94,45,36,14,65,70,11,42,29,23,12

22,13,50,13,62,99,67,22,72,10,76,89,24,13,30,23,37,86,11,99,58,23,31,95,95,52,95,70,36,13,59,46,61,64,24,78,76,18,94,20

12,57,68,56,10,27,33,20,63,44,47,32,95,60,61,76,27,28,77,76,76,30,97,77,65,70,40,24,63,23,69,26,61,76,15,33,13,92,72,31

68,63,23,84,14,14,83,87,17,56,57,54,61,10,37,85,58,79,89,96,65,80,84,48,97,26,42,41,42,14,45,37,21,14,47,65,98,61,70,36

68,83,10,18,86,22,39,43,64,47,72,27,10,75,22,26,17,36,97,22,47,53,65,49,50,60,99,29,29,82,24,95,60,38,73,70,49,15,53,45

Это усложненная версия задачи 81. Дана таблица из чисел, надо найти минимальный путь от левого верхнего угла до правого нижнего. Возможны движения: вправо, вниз, влево, вверх и по диагонали: влево-вверх, вправо-вверх, вправо-вниз и влево-вниз. Длина пути считается так: число в левом верхнем углу, и каждый ход к данному числу прибавляется число на которое мы переходим, если движения через грань, и удвоенное число на которое мы переходим, если движение по диагонали (через угол).

Пример кратчайшего пути для таблицы 4 на 4:

22,18,28,12

65,76,19,95

90,22,96,84

56,92,27,51

Длина: 22+18+2*19+2*22+2*27+51 = 227

Найдите длину минимального пути в таблице 40 на 40:

47,15,61,49,88,45,40,93,82,96,91,84,34,11,96,60,31,90,59,96,40,16,17,50,65,32,92,24,24,29,33,58,70,96,18,37,97,36,28,34

81,73,99,38,88,91,62,74,60,16,69,22,11,54,10,55,15,75,69,84,96,18,33,72,65,65,35,10,13,73,62,50,78,78,84,19,94,33,28,41

90,21,71,21,89,17,66,47,97,64,27,54,31,99,68,61,10,69,56,98,12,73,47,78,25,55,70,17,52,14,66,51,23,46,39,43,12,67,92,34

51,53,97,18,54,20,10,83,78,32,79,40,29,99,77,34,91,31,14,63,50,64,27,88,34,90,49,16,53,89,94,28,19,82,86,75,69,18,27,56

97,74,97,28,82,62,34,67,15,55,86,50,71,38,58,24,68,69,20,43,16,84,35,41,34,77,23,51,64,56,64,32,15,40,26,89,90,42,14,54

54,49,84,16,32,16,20,73,47,10,32,63,35,59,59,65,65,22,75,98,26,31,92,62,89,98,24,31,70,21,29,91,52,91,69,52,50,85,35,10

16,38,83,77,12,10,54,46,43,12,97,50,28,21,55,31,69,51,22,91,83,77,34,52,37,80,58,59,43,32,53,54,62,34,42,17,83,55,20,75

91,14,88,26,99,14,58,79,97,48,71,97,17,65,37,18,31,15,11,21,74,87,31,26,17,24,65,55,35,42,47,88,58,23,80,88,90,77,15,76

70,85,21,34,94,72,64,94,29,89,19,73,15,70,80,74,50,50,88,26,92,13,38,79,43,35,90,51,32,20,82,12,22,17,74,92,42,76,70,10

34,47,28,35,34,58,53,52,23,64,36,91,63,68,88,28,32,22,43,81,75,72,35,22,94,94,27,67,88,20,78,70,90,94,17,38,29,38,21,11

11,91,11,47,35,60,86,20,23,97,53,54,62,62,19,73,49,40,80,22,98,58,47,69,68,42,65,13,55,57,64,79,11,17,79,15,90,29,59,38

55,77,40,84,79,73,46,57,73,27,88,82,11,79,80,24,70,55,92,17,33,50,52,30,64,40,50,23,89,34,41,92,54,47,42,20,72,67,94,14

33,72,41,60,21,73,20,87,39,26,86,28,30,60,13,74,82,92,26,38,17,52,91,43,87,80,24,55,95,79,70,89,83,40,71,35,76,49,87,16

71,83,65,25,73,56,94,39,51,73,85,21,99,94,10,32,40,60,30,64,86,76,59,29,98,70,20,84,71,88,11,69,95,25,74,23,24,82,40,61

72,80,13,57,90,10,67,27,15,21,12,77,96,14,94,52,18,75,85,90,28,79,41,80,12,82,88,22,48,19,35,55,69,65,38,74,24,80,66,18

54,58,86,47,56,33,80,89,46,10,85,98,98,23,74,96,68,26,72,55,74,53,39,41,12,39,38,84,97,77,20,72,70,66,38,93,96,79,60,65

39,97,74,67,11,29,51,96,81,60,34,19,26,28,58,80,42,26,14,99,84,99,86,40,58,17,76,18,29,43,76,79,74,39,40,35,31,65,18,57

18,46,80,89,99,83,51,91,60,80,15,25,99,20,83,19,45,31,66,20,12,34,44,62,96,31,58,60,29,10,16,51,19,62,74,38,30,12,24,24

56,52,48,91,86,28,91,19,82,91,67,84,99,81,36,67,29,26,34,22,42,71,60,69,71,63,51,78,97,96,40,37,72,73,24,13,76,96,42,15

63,98,25,87,51,95,38,15,87,87,53,24,30,86,47,65,32,72,22,40,53,93,39,53,91,23,13,41,38,32,41,79,35,99,52,37,78,93,27,43

77,46,45,35,92,34,98,66,92,37,70,16,36,29,44,15,54,94,64,16,75,41,90,87,53,25,51,17,29,27,74,58,83,92,87,78,72,42,80,24

89,45,35,97,62,88,35,20,39,54,31,81,19,56,15,99,99,28,20,71,29,81,71,66,21,72,68,96,43,40,14,37,66,61,61,80,60,92,90,88

64,52,88,50,51,68,48,18,43,60,20,18,18,63,36,79,27,41,94,12,16,17,37,53,70,66,63,83,69,66,38,99,44,27,82,94,25,66,82,73

18,82,86,93,71,77,67,22,77,66,60,85,70,93,50,76,63,31,89,51,35,88,47,58,94,17,28,12,84,37,16,40,96,74,91,62,78,78,49,81

96,61,64,40,43,26,70,17,78,66,30,93,87,34,51,85,89,93,44,96,63,25,53,58,96,15,16,47,92,91,86,26,67,48,44,34,82,64,69,57

27,58,64,47,16,18,76,69,80,33,90,30,56,48,80,27,51,71,26,32,81,92,34,46,63,47,97,39,24,26,38,64,28,81,34,86,15,12,35,96

81,47,76,59,19,83,83,83,77,51,67,80,65,31,48,96,76,34,19,68,55,85,95,36,28,53,18,47,68,72,65,64,22,84,40,91,27,99,20,23

14,91,91,78,83,40,19,41,52,94,43,71,56,71,73,18,46,21,39,36,35,21,23,97,86,46,39,64,24,63,88,90,49,28,68,92,32,17,26,95

18,33,89,40,81,12,61,33,54,54,16,40,18,31,89,57,46,64,69,48,98,31,18,92,99,47,18,33,81,73,39,42,96,68,41,88,29,82,23,69

32,65,79,31,28,36,43,10,44,25,66,38,93,10,84,80,75,74,22,89,48,30,18,91,12,30,71,68,37,31,57,89,24,67,44,46,93,47,27,15

74,72,69,42,31,61,30,59,90,31,36,86,97,88,44,71,74,92,18,78,78,41,46,43,42,43,92,25,15,56,45,37,76,73,65,85,98,42,84,32

80,36,98,78,95,24,35,87,61,32,55,79,14,66,29,25,57,93,67,47,84,78,94,35,40,63,77,66,95,83,13,91,30,90,69,27,45,75,21,42

12,32,95,29,15,99,88,89,54,49,13,26,89,89,29,63,64,48,74,37,99,76,15,78,89,26,70,23,31,23,35,32,19,42,26,58,43,19,42,43

31,91,52,22,93,32,98,17,69,77,80,44,84,58,98,18,65,49,92,72,52,76,59,32,61,16,51,20,90,99,49,12,49,37,37,96,22,83,28,28

83,86,38,63,52,65,16,43,91,39,67,66,27,59,22,25,35,55,70,55,11,15,78,97,79,50,69,15,43,98,35,71,95,60,65,92,80,76,97,55

72,53,35,84,17,72,43,23,13,92,23,75,75,34,66,84,96,79,69,73,21,36,11,38,86,24,98,13,76,33,58,42,78,36,87,43,16,36,85,77

88,96,18,39,29,56,29,63,96,10,20,63,95,11,75,97,28,55,38,20,52,53,91,99,14,42,49,11,68,23,12,73,36,18,27,84,75,53,78,16

99,15,88,67,24,77,14,52,37,75,15,13,44,21,70,96,20,99,65,78,73,14,31,71,75,23,91,81,89,87,80,82,82,21,82,29,52,34,52,74

63,16,81,19,64,33,71,73,29,53,31,75,66,78,51,68,48,54,85,22,90,15,84,76,95,45,90,83,66,27,16,17,20,48,27,18,38,72,71,25

38,29,23,16,83,68,83,31,52,33,65,33,95,32,52,69,45,53,65,35,88,94,42,89,48,48,19,40,49,84,33,15,31,96,83,57,76,88,27,36

Рассмотрим игру «монополия». Игровое поле следующее:

Движение происходит следующим образом: каждый игрок своим ходом кидает два 6-гранных кубика, и сдвигает фишку на число клеток в сумме выпавших на кубиках. Исключением является случай, когда игрок три раза подряд выкидывает дубль (одинаковые числа на кубиках), в таком случае он попадает на клетку тюрьмы (JAIL). Также, если игрок сдвинув фишку попадает на «G2J», то он перемещается в тюрьму.

Игрок начинает с клетки GO и каждый ход бросает пару кубиков и свдигает фишку на сумму чисел выпавших на кубиках по часовой. Если бы не было дополнительных правил — ожидаемым было бы, что вероятности попадения на каждую клетку после броска равна 1/40. Но попадания на клетки G2J(Go to jail, отправляйтесь в тюрьму), CC(извещение) и CH(шанс) изменяет это распределение. Также существует правило, согласно которому если игрок выкидывает три раза дубль (одинаковые значения на кубиках), то вместо третьего хода он попадает в тюрьму.

Вначале игры все карты CC и CH перетасованы. Когда игрок становится на одну из таких клеток верхняя карта колоды снимается и после использования кладется под низ. В каждой стопке по 16 карт, часть из которых содержит предписания о перемещении на какую-то из клеток карты, остальные нам не важны. Вот эти карты:

• Извещения (2/16 cards):

  1. к старту (GO)

  2. в тюрьму (JAIL)

• Chance (10/16 cards):

  1. К старту (GO)

  2. В тюрьму (JAIL)

  3. На клетку C1

  4. На клетку E3

  5. На клетку H2

  6. На клетку R1

  7. К следующей клетке R (ЖД компания)

  8. К следующей клетке R

  9. К следующей клетке U (Коммунальное предприятие)

  10. Назад на 3 клетки

Ваша задача определить вероятность закончить ход на каждой из клеток после очередного броска кубиков. Очевидно что вероятность для Jail наибольшая, G2J нулевая. Считается что игрок не задерживается в тюрьме. Пронумеруем все клетки от 0(GO) до 39(H2) и найдем вероятности для каждой клетки. Три макимальные вероятности получаются для клеток JAIL(10), 6.24%; E3(24), 3.18% и GO(0), 3.09%.

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

На каждой из 6 граней кубика изображена одна из цифр от 0 до 9. Так же и на другом кубе. Ставя два кубика рядом можно составить множество двузначных чисел.

Например число 64 будет составлено так:

Подобрав цифры на гранях, можно отобразить все числа которые можно получить суммой двух кубов меньшие сотни ( n = a³ + b³, n < 100, a и b - натуральные). Эти числа: 02, 09, 16, 28, 35, 54, 65, 72, 91. Например, с помощью наборов {5, 4, 3, 2, 1, 0} и {9, 8, 5, 4, 3, 1} могут быть выложены все необходимые числа. При этом надо учесть, что цифры 6 и 9 выглядят одинаково и могут использоваться друг за друга, хотя наборы с этими цифрами считаются различными. Тогда как один и тот же набор цифр расположенный на гранях кубика иным образом считается тем же набором.

То есть,

{1, 2, 3, 4, 5, 6} и {3, 6, 4, 1, 2, 5} - одинаковые наборы;
{1, 2, 3, 4, 5, 6} и {1, 2, 3, 4, 5, 9} - различные наборы.

Сколько различных пар кубиков могут быть сложены во все числа представимые суммой пары кубов?