Номер эйлера проекта 338

Я застрял в Project Euler проблема 338. Вот что я сделал до сих пор...

Обозначим прямоугольник с шириной и высотой x и y соответственно (x,y). Чтобы сформировать новые прямоугольники, вы можете рассмотреть возможность прорезания лестницы по диагонали (как показано в описании проблемы) с помощью d шагов. Но для формирования нового прямоугольника должно быть выполнено следующее: d|x и либо (d-1)|y, либо (d+1)|y. Новый прямоугольник затем станет либо (x/d*(d-1), y/(d-1)*d), либо (x/d*(d+1), y/(d+1)*d). Очевидно, что область новых прямоугольников такая же, как у старого прямоугольника.

Этого было достаточно, чтобы подтвердить, что G(10)=55 и G(1000)=971745 путем прокрутки всех соответствующих d и добавления всех новых прямоугольников в набор, чтобы быть уверенным, что они будут считать (x,y) и (y,x) только один раз.

Основная проблема с этим методом заключается в том, что можно создать новый прямоугольник двумя разными способами. Например, (9,8) может преобразовываться как в (6,12), так и в (12,6) с d=3 и либо d-1, либо d+1, делящем y. Или другой пример (4,4) преобразуется в (2,8) и (8,2) с d=2 и d=1 соответственно.

Мне посчастливилось прочитать этот пост в блоге. Это устраняет необходимость проверки дубликатов путем поиска одной из сторон.

def F(w, h):
    if w&1 and h&1: return 0
    if w<h: w,h = h,w

    r = 0
    x = 1
    while x**2 <= w*h:
        if (w*h)%x!=0 or x==h:
            x += 1
            continue

        if w%(w-x)==0 or x%(x-h)==0:
            r += 1

        x += 1

    return r

def G(N):
    s = 0
    for w in range(1, N+1):
        for h in range(1, w+1):
            s += F(w,h)

    return s

G (10 12) потребовалось бы слишком долго, чтобы решить, независимо от того, насколько быстро F. Я думаю, что необходимо либо использовать какой-то алгоритм просеивания, где мы прокручиваем все x < 10 12 считая, сколько (w, h) удовлетворяют h <= w <= 10 12 x | (w * h), x!= H и ( wx) | w или (xh) | x.

Я думаю, что алгоритм O (n 2/3) должен быть возможен... но я застрял здесь!

Изменить. У меня нет доступа к форуму, так как я не могу его решить. Вот почему я прошу о помощи. Я выполнил большинство других вопросов и хочу решить этот вопрос сейчас!

Изменить 2. Я думаю, что рассмотрение областей с помощью простых факторов является тупиком. Это потому, что есть 10 24 разных областей. Прямоугольники с основными областями имеют 0 решений, прямоугольники с полупервыми областями имеют 1 решение, если один из простых чисел равен 2, в противном случае они имеют 0 решений. Но считать все полупростые решения в одиночку потребует слишком много времени, так как нам нужно будет пересчитать все простые числа р так, что 2 * p < 10 24 что невозможно.

Изменить 3: я удалил код:

def G(N):
    s = 0
    for x in range(1, N):
        for h in range(1, N+1):
            if x==h: continue
            for w in range(max(h, x**2//h), N+1):
                if (w*h)%x==0 and x%(w-x)==0 and x%(x-h)==0:
                    s -= 1

    for x in range(1, N):
        for h in range(1, N+1):
            if x==h: continue
            for w in range(max(h, x**2//h), N+1):
                if (w*h)%x==0 and w%(w-x)==0:
                    s += 1

    for x in range(1, N):
        for h in range(1, N+1):
            if x==h: continue
            for w in range(max(h, x**2//h), N+1):
                if (w*h)%x==0 and h%(x-h)==0:
                    s += 1

    return s

Я не думаю, что нарушение кода грубой силы будет работать. Запомните это достаточно, чтобы просто считать решения (x, w, h) каждой из этих трех подзадач. Последнее такое суммирование должно иметь ограничения 0 < x < N, h < N + 1, x!= H, max (h, x 2/h) w < N + 1, x | wh и x-h | h.

Я думаю, что мы должны начать с предположения, что некоторые простые числа p делят x, w, h или даже x-h, а затем видят, что мы можем вывести о других переменных. Если это хорошо работает, возможно, рассмотрим p k для любого k.

Ответы

Ответ 1

У меня пока нет решения, но что-то интересное для Python. Я понял, что Python можно использовать как удобный инструмент для обозначения алгоритмов! В основном я записал программу, похожую на вашу, и начал логически преобразовывать программу, оставляя результаты неизменными. Я придумал

def order(x,y):
    if x>=y:
        return (x,y)
    else:
        return (y,x)

N=1000
num=set()
for n in range(1, N+1):
    for a in range(1,N//n+1):
        for b in range(1,N//(n+1)+1):
            if a==b: continue
            num.add((order(a*n,b*(n+1)), order(b*n,a*(n+1))))

print(N, len(num))

Очевидно, что грубая сила или даже простой цикл над 10 ^ 12 невозможен, но, возможно, с этим алгоритмом в некоторой точке можно найти выражение замкнутой формы. Если бы это не было для заданного символа num, это было бы выполнимо. Может быть, здесь можно найти дубликат.

Это может быть тупик, но все же довольно круто, что Python можно использовать для обозначения и работы с алгоритмами:)

Прогресс на вашей стороне?