projecteuler solutions - Kirill Dikalin

Бильярд

Диаграмма ниже показывает бильярдный стол особой четырехугольной формы. Четыре угла $A, B, C, D$ равны $120^{\circ}, 90^{\circ}, 60^{\circ}, 90^{\circ}$ соответственно, а длины $A B$ и $A D$ равны между собой.

Диаграмма слева показывает траекторию бесконечного малого бильярдного шара, начавшего движение из точки $A$ , дважды отбившегося от бортов стола и вернувшегося обратно в точку $A$ . Диаграмма справа показывает другую такую траекторию, но на этот раз шар отбился от бортов восемь раз:

На столе отсутствует трение и все отскоки являются идеально эластичными столкновениями.
Заметим, что ни один отскок не должен происходить в любом из углов стола, так как поведение шара в таком случае будет непредсказуемым.

Пусть $B (N)$ будет количеством возможных траекторий шара, начавшего движение из точки $A$ , отбившегося не более $N$ раз от бортов и вернувшегося обратно в точку $A$ .

Например, $B (10) = 6$ , $B (100) = 478$ , $B (1000) = 45790$ .

Найдите $B (10^{9})$ .

Решение

Итак, чтобы понять решение нам необходимо ознакомиться с некоторыми понятиями.

Функция Мёбиуса - это функция, которая используется в теории чисел для изучения свойств деления чисел и факторизации. Она задается для каждого положительного целого числа и зависит от количества различных простых множителей в разложении этого числа на множители. Если число содержит повторяющиеся простые множители, то функция Мёбиуса равна 0. Если число содержит нечетное число различных простых множителей, то функция Мёбиуса равна -1. Если число содержит четное число различных простых множителей, то функция Мёбиуса равна 1.

В простых словах, функция Мёбиуса позволяет описывать, как происходит разложение числа на простые множители. Она является важным инструментом в теории чисел и находит применение в различных задачах, связанных с делением чисел и факторизацией.

Мертенсова функция — это функция, которая определяется для каждого натурального числа n как сумма знаков функции Мёбиуса от 1 до n. Знак функции Мёбиуса зависит от того, сколько простых множителей имеет число. Если число имеет четное количество простых множителей, то знак равен 1. Если число имеет нечетное количество простых множителей, то знак равен -1. Если число делится на квадрат простого числа, то знак равен 0.

В простых словах, Мертенсова функция позволяет считать количество простых чисел на интервале от 1 до n, а также содержит информацию о распределении простых и составных чисел на этом интервале. Она является важным инструментом в теории чисел и находит применение в различных задачах, связанных с простыми числами.

Мы знаем, что вероятность того, что два числа будут взаимно простыми, равна $\frac{6}{π^{2}}$ таким образом, исключая случай, когда $3 | y$ даёт $p - \frac{p}{3} + \frac{p}{9} - \frac{p}{27} + \cdot \cdot \cdot = \frac{6}{π^{2}}$ поэтому $p = \frac{9}{2 π^{2}}$

Поскольку $4 (\sum_{18 x + 10 y \leq 3 n + 6, x > 0, y > 0}^{} 1) + 2 \approx 4 (\sum_{x = 1}^{(n + 2) / 6} \frac{3 n + 6 - 18 x}{10}) \approx \frac{n^{2}}{10} ο (n)$ мы получаем:

$\lim_{N \to \infty} \frac{B (N)}{N^{2}} = \frac{9}{20 π^{2}} \approx 0, 045594532639051997$

Код решения:


          from functools import lru_cache
          from math import sqrt,floor
          
          N=1000000000
          z=0
          
          def sqrttrick(n):
              f=floor(sqrt(n))
              for i in range(1,n//(f+1)+1):
                  yield (i,i,n//i)
              for i in range(f,0,-1):
                  yield (n//(i+1)+1,n//i,i)
                  
          def calcN(a, b, c): 
              if ac: return 0
              m = c//a
              if a == b:
                  return m*(m - 1)//2;
              else:
                  k = (a - 1)//b
                  h = (c - a*m)//b
                  return calcN(b, a - b*k, c - b*(k*m + h)) + k*m*(m - 1)//2 + m*h        
              
          @lru_cache(maxsize=None)
          def mertens(n):
              if n<=1: return n
              z=1
              for a,b,c in sqrttrick(n):
                  if c< n: z-=mertens(c)*(b-a+1)
              return z
          
          def mertens3(n):
              z=0
              while(n):
                  z+=mertens(n)
                  n//=3
              return z
          
          for a,b,g in sqrttrick(3*N+6):
              q = calcN(18,10,g) - calcN(18,30,g)
              if q==0: break
              z+=(mertens3(b) - mertens3(a-1))*q
              
          print (z*4+2)

Разберём теперь что тут происходит

Этот код вычисляет Мертенсову функцию M(n), которая определяется как сумма значений функции μ(k) (функция Мёбиуса) на отрезке [1,n], где μ(1) = 1, а для k > 1 равна 0, если k имеет квадратный делитель, и (-1)^r, если k является произведением r различных простых чисел.

1. Импортируем необходимые модули:

functools.lru_cache используется для создания декоратора мемоизации функций.

math.sqrt используется для вычисления квадратного корня.

math.floor используется для округления вниз.

2. Задаем константу N = 1000000000 и переменную z = 0.

3. Определяем функцию sqrttrick(n), которая используется для генерации троек (a, b, c), где a × b = n и a ≤ b ≤ c. Эта функция использует "метод квадратного корня", чтобы генерировать эти тройки. Первый цикл for используется для генерации всех троек, где b ≤ sqrt(n), а второй цикл for используется для генерации оставшихся троек. Функция возвращает каждую тройку в виде кортежа (i, j, k) с помощью генератора yield.

4. Определяем функцию calcN(a, b, c), которая используется для вычисления количества чисел на отрезке [a, c], которые делятся на b. Эта функция используется для вычисления суммы значений функции μ(k) на отрезке [a, c]. Функция использует рекурсию для расчета значения суммы, пока a ≤ c. Функция возвращает сумму значений μ(k) на отрезке [a, c].

5. Определяем функцию mertens(n), которая вычисляет значение Мертенсовой функции для n. Для этого функция использует цикл for для перебора всех троек (a, b, c), которые генерируются функцией sqrttrick(n). Если c < n, то значение Мертенсовой функции для c умножается на (b - a + 1) и вычитается из z. Функция возвращает z.

6. Определяем функцию mertens3(n), которая используется для вычисления значения Мертенсовой функции для каждого третьего числа в интервале [1, n]. Функция использует цикл while для перебора каждого третьего числа и вызывает функцию mertens для каждого третьего числа. Значения Мертенсовой функции для каждого третьего числа складываются в z, который затем возвращается.

7. Декоратор lru_cache используется для кэширования результатов вызовов функции mertens. Это позволяет избежать повторных вычислений для одного и того же значения аргумента функции.

8. В основной части программы используется цикл for для перебора всех троек (a, b, g), которые генерируются функцией sqrttrick(3*N+6). Затем вызывается функция calcN(18, 10, g) - calcN(18, 30, g) для вычисления количества чисел на отрезке [10, g], которые делятся на 18, но не делятся на 30. Это значение сохраняется в переменную q.

9. Затем выполняется вычисление мертенсовой функции для каждого числа в интервале [a, b] с помощью функции mertens3(b) - mertens3(a-1). Разница значений мертенсовой функции между b и a-1 умножается на q и добавляется к переменной z.

10. Наконец, значение z умножается на 4 и прибавляется 2, и результат выводится на экран с помощью функции print.