Соответствующие ссылки здесь и здесь , но вот краткая версия:
У вас есть входные данные двух целых чисел a
и b
между отрицательной бесконечностью и бесконечностью (хотя при необходимости я могу ограничить диапазон, но функция все равно должна принимать отрицательные входные данные).
Определение символа Кронекера
Вы должны вернуть символ Кронекера (a|b)
для ввода a
и b
где
(a|b) = (a|p_1)^e_1 * (a|p_2)^e_2 * ... * (a|p_n)^e_n
где b = p_1^e_1 * p_2^e_2 * ... * p_n^e_n
, и p_i
и e_i
являются простыми числами и показателями в основной факторизации b
.
Для нечетного простого числа p
, (a|p)=a^((p-1)/2) (mod p)
как определено здесь .
Для b == 2
,(n|2)={0 for n even; 1 for n odd, n=+/-1 (mod 8); -1 for n odd, n=+/-3 (mod 8)
Для b == -1
,(n|-1)={-1 for n<0; 1 for n>0
Если a >= b
, (a|b) == (z|b)
где z == a % b
. Этим свойством и, как объясняется здесь и здесь , a
является квадратичный остаток от b
if z
, хотя a >= b
.
(-1|b)
= 1
если b == 0,1,2 (mod 4)
и -1
если b == 3 (mod 4)
. (0|b)
является , 0
за исключением (0|1)
что 1
, потому что (a|1)
всегда 1
и для отрицательных a
, (-a|b) == (-1|b) * (a|b)
.
Вывод символа Кронекера всегда -1, 0 or 1
, где вывод, 0
если a
и b
имеют какие-либо общие факторы. If b
- нечетное простое число, (a|b) == 1
if a
- квадратичный вычет mod b
, а -1
if - это не квадратичный вычет.
правила
Ваш код должен быть программой или функцией.
Входы должны быть в порядке
a b
.Выход должен быть либо
-1
,0
либо1
.Это кодовый гольф, поэтому ваш код не обязательно должен быть эффективным, просто коротким.
Нет встроенных модулей, которые напрямую вычисляют Кронекера или связанные символы Якоби и Лежандра. Другие встроенные модули (например, для первичной факторизации) являются честной игрой.
Примеры
>>> kronecker(1, 5)
1
>>> kronecker(3, 8)
-1
>>> kronecker(15, 22)
1
>>> kronecker(21, 7)
0
>>> kronecker(5, 31)
1
>>> kronecker(31, 5)
1
>>> kronecker(7, 19)
1
>>> kronecker(19, 7)
-1
>>> kronecker(323, 455625)
1
>>> kronecker(0, 12)
0
>>> kronecker(0, 1)
1
>>> kronecker(12, 0)
0
>>> kronecker(1, 0)
1
>>> kronecker(-1, 5)
1
>>> kronecker(1, -5)
1
>>> kronecker(-1, -5)
-1
>>> kronecker(6, 7)
-1
>>> kronecker(-1, -7)
1
>>> kronecker(-6, -7)
-1
Это сложная функция, поэтому, пожалуйста, дайте мне знать, если что-то неясно.
источник
Ответы:
CJam (70 байт)
Демо онлайн (тестовые случаи, созданные с помощью Mathematica).
рассечение
Я нашел несколько способов оценки
(a|2)
для одного и того же количества символов, и решил использовать тот, который дает наиболее четкое представление.integer array <W=
Это IMO довольно элегантный способ сделать запасные варианты: если целое число больше, чем длина массива, мы выбираем последний элемент.Другие комментарии
Вызывает разочарование то, что для нечетного прайма
p
прямой стиль Ферма(a|p)
настолько короток, потому что есть очень хороший способ найти(a|n)
положительный вариант,n
который я хотел использовать. Основой является лемма Золотарева:Это было усилено Фробениусом, чтобы
и Лерх к
См. Brunyate and Clark, Расширение подхода Золотарева-Фробениуса к квадратичной взаимности , Ramanujan Journal 37.1 (2014): 25-50 для ссылок.
И это может быть легко укреплено еще на один шаг (хотя я не видел этого в литературе), чтобы
Доказательство: если
a
взаимно,b
то мы используем Золотарева-Фробениуса-Лерха; в противном случае карта не является перестановкой, и символ Леви-Чивита является0
желаемым.Это дает вычисление символа Якоби
Но особая обработка требует
(a|-1)
и(a|2)
означает, что я не нашел способ вычисления символа Кронекера, который короче при таком подходе: он короче для разложения и обработки простых чисел индивидуально.источник
Python 3,
747369335 байтВ качестве примера ответ, только слегка гольф, и дать вам представление о том, как ответ будет выглядеть.
И да, основные биты факторизации и кодирования длин серий написаны Pyth с извинениями за isaacg .
источник
Mathematica,
169175165 байтовисточник
LabVIEW, 44 байта Примитивы LabVIEW
Поскольку он симметричный, я поменял местами входы, если a было больше, чем b.Представляет реальную формулу сейчас
считая как всегда согласно
для истинного случая
источник
(a|b) != (b|a)
во всех случаях. В большинстве случаев да, но не во всех. Хотя это будет работать, если вы уменьшите ихa mod b
вместо того, чтобы поменять их местами.Юлия, 195 байт
Это рекурсивная функция,
k
которая принимает два целых числа и возвращает целое число.Ungolfed:
источник
Haskell, 286 байт
Вероятно, не полностью оптимизирован, но отважные усилия. Символ Кронекера определяется как инфиксная функция a # b, т.е.
источник