поправка про экспоненциал

[thedeemon]

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

(напоминаю, что стрелки тут означают делимость, "произведение" - наименьшее общее кратное двух чисел, и смысл в том, что для любого числа С, для которого СхА кратно В, С должно быть кратно exp(A,B))

Я тогда сказал, что exp(А,В) = lcm(А,В) / А. (lcm - наименьшее общее кратное)
Это неправильная функция, она работает во многих случаях, но не во всех.
Правильная функция выглядит так: нужно взять В, разложить на простые множители в соответствующих им степенях, и убрать те из них, которые встречаются в аналогичном разложении А со степенью большей или равной той, что в В.

Примеры:
А = 30 = 2*3*5
В = 35 = 5*7
простой множитель 5 в А в той же степени, что и В, его убираем, остается 7. exp(A,B)=7

A = 70 = 2*5*7
B = 100 = 2*2 * 5*5
тут в В степени общих с А простых множителей больше, чем в А, поэтому убирать нечего, exp(A,B)=100.
На этом примере как раз изначально предложенная формула неправильный ответ дает.

Вопрос: можно ли эту функцию выразить без явного разложения на множители? Например, через формулу с gcd, lcm и арифметическими операциями.

Comments

[udpn.livejournal.com]

sharpc сказал, что из gcd, lcm и степеней a, b это сделать невозможно, и полил меня каким-то функаном про бесконечномерное пространство представлений, и про то, что с помощью конечной формулы можно представить только подпространство, построенное на конечном количестве векторов. Я ничего не понял и не поверил за отсутствием формального доказательства.

Некоторое упрощение скрипта. Теперь я пытаюсь только найти представление if(a < b, b, 0) через min, max, _+_, _-_. Попробуй запустить под нормальным хаскеллом, у меня на кодепаде таймаут.

http://codepad.org/q17DtVh5