Учитывая число n >= 2
, выведите все натуральные числа меньше, чем n
где gcd(n, k) == 1
(с k
любым из выходных чисел). Числа такого рода взаимно просты друг с другом.
Пример: 10
дает вывод [1, 3, 7, 9]
(в любой форме, которую вы любите, если числа однозначно разделены и в каком-то списке). Список не может содержать повторяющиеся записи и не должен быть отсортирован.
Больше тестовых случаев:
2 -> [1]
3 -> [1, 2]
6 -> [1, 5]
10 -> [1, 3, 7, 9]
20 -> [1, 3, 7, 9, 11, 13, 17, 19]
25 -> [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24]
30 -> [1, 7, 11, 13, 17, 19, 23, 29]
Мы также не учитываем числа выше n
, которые взаимно просты n
, потому что я уверен, что есть бесконечные решения.
Также обратите внимание: числа, которые взаимно просты друг с другом, также называются взаимно простыми или взаимно простыми.
code-golf
math
number-theory
primes
Rɪᴋᴇʀ
источник
источник
1\n3\n
) допустимым выводом?Ответы:
Желе , 3 байта
Попробуйте онлайн!
Как это работает?
Доказательство действительности
Так как мы хотим , чтобы извлечь только coprimes, минимальное значение Величайшего-Common-делители списка должно быть 1 для
ÐṂ
трюка к работе. Давайте докажем это (двумя разными способами):Неявно сгенерированный диапазон, содержит и . Наибольшим общим делителем всегда является строго положительное целое число, следовательно, гарантированно встречается и всегда будет минимальным значением.1 gcd ( 1 , x ) = 1[ 1 , вход ] 1 gcd ( 1 , x ) = 1∀x ∈ Z* 1
Два последовательных натуральных числа всегда взаимно просты. Рассмотрим , где . Затем мы берем еще одно натуральное число такое что и . y = x + 1 k k ∣ x k ∣ yх , у∈ Z* Y= х + 1 К к ∣ х к | у
Это означает, что , поэтому , следовательно, . Единственное положительное целое число, чтобы разделить - это само , поэтому оно гарантированно появится в списке и всегда будет минимальным значением.k ∣ ( x + 1 - x ) k ∣ 1 1 1к ∣ ( у- х ) k ∣ ( x + 1 - x ) k∣1 1 1
источник
ÐṂ
существовал ли тогда, в любом случае, я вполне доволен этим.DṂ
существует, но он работал только для монад. Коммит реализованыÞ
,ÐṂ
,ÐṀ
для двоек датируется 9 мая 2017 годаPython 2 ,
6147 байтПопробуйте онлайн!
Фон
Рассмотрим кольцо . Хотя это кольцо обычно определяется с использованием классов вычетов по модулю , его также можно рассматривать как множество , где операторы сложения и умножения определяются и , где обозначают обычное добавление, умножение и операторы по модулю над целыми числами.n Z n = { 0 , … , n - 1 } a + n b = ( a + b )( ZN, +N, ⋅N) N ZN= { 0 , … , n - 1 } a ⋅ n b = a ⋅ b+Nб = ( а + б )%N + ,⋅Nb = a ⋅ b%N + ,⋅ и %
Два элемента и в называются взаимными мультипликативными инверсиями по модулю если . Обратите внимание, что всякий раз, когда .b Z n n a ⋅ n b = 1a b Zn n 1a⋅nb=1%n n > 11%n=1 n>1
Зафиксируем и пусть будет взаимно простым в . Если для двух элементов и из , имеем . Это означает, что , и мы следуем этому , т. е. делит равномерно. Поскольку делит простых делителей с , это означает, что . Наконец, потому чтоa n Z n a ⋅ n x = a ⋅ n y x y Z n a ⋅ xn>1 a n Zn a⋅nx=a⋅ny x y Zn a ⋅ ( x - y )a⋅x%n=a⋅y%n n ∣ a ⋅ ( x - y ) n a ⋅ ( x - y ) n a n ∣ x - y - n < x - y < n x = y a ⋅ n 0 , … , a ⋅ n ( n - 1 ) Z n Z n n 1 b Za⋅(x−y)%n=a⋅x%n−a⋅y%n=0 n∣a⋅(x−y) n a⋅(x−y) n a n∣x−y −n<x−y<n , мы заключаем, что . Это показывает, что произведения являются различными элементами . Так имеет ровно элементов, один (и ровно один) из этих продуктов должна быть равна , то есть, есть уникальный в таким образом, что .x=y a⋅n0,…,a⋅n(n−1) Zn Zn n 1 b a ⋅ n b = 1Zn a⋅nb=1
И наоборот, зафиксируем и пусть будет элементом который не взаимно прост с . В этом случае существует такое простое число , что и . Если бы допускал мультипликативный обратный по модулю (назовем это ), мы бы имели , что означает, что и, следовательно, , поэтому . Так как , мы следуем этомуZ п п р р | р | п п б в ⋅ п Ь = 1 в ⋅ бn>1 a Zn n p p∣a p∣n a n b a⋅nb=1 ( a ⋅ b - 1 )a⋅b%n=1 n ∣ a ⋅ b - 1 p ∣ a p ∣ a ⋅ b p ∣ n p ∣ a ⋅ b - 1 p ∣ ( a ⋅ b ) - ( a ⋅ b - 1 ) = 1 p(a⋅b−1)%n=a⋅b%n−1=0 n∣a⋅b−1 p∣a p∣a⋅b . С другой стороны, поскольку , мы также следуем тому, что . Таким образом, , что противоречит предположению, что - простое число.p∣n p∣a⋅b−1 p∣(a⋅b)−(a⋅b−1)=1 p
Это доказывает, что следующие утверждения эквивалентны, когда .n>1
нa и взаимно просты.n
нa допускает мультипликативный обратный по модулю .n
нa допускает единственный мультипликативный обратный по модулю .n
Как это устроено
Для каждой пары целых чисел и в целое число уникально; на самом деле, и являются частными, а остаток от делится на , т.е., учитывая , мы можем восстановить и , где обозначает целочисленное деление. Наконец, так как и , является элементом ; фактически .b Z n k : = a ⋅ n + b a b k n k a = k / n b = ka b Zn k:=a⋅n+b a b k n k a=k/n / a ≤ n - 1 b ≤ n - 1 k Z n 2 k ≤ ( n - 1 ) ⋅ n + ( n - 1 ) = n 2 - 1b=k%n / a≤n−1 b≤n−1 k Zn2 k≤(n−1)⋅n+(n−1)=n2−1
Как отмечено выше, если и взаимно просты, будет уникальный такой что , т. Е. Будет уникальный такой, что и , так что генерируется список будет содержать ровно один раз.n b a ⋅ ba n b k k / n = a k / n ⋅ ka⋅b%n=1 k k/n=a k/n⋅k%n=(k/n)⋅(k%n)%n=1 a
И наоборот, если и являются не взаимно просты, то условие будет ложным для всех значений , таких , что , поэтому сгенерированный список будет не содержать .н к / н ⋅ кa n k a = k / n ak/n⋅k%n=1 k a=k/n a
Это доказывает, что список, который возвращает лямбда, будет содержать все взаимно чисел в ровно один раз.Z nn Zn
источник
Желе , 4 байта
Попробуйте онлайн!
Как это устроено
источник
gRỊT
ÐṂ
), чтобы получить 3 байта .Mathematica, 25 байтов
Немного странный выходной формат, где каждый результат упакован в отдельный список, например
{{1}, {3}, {7}, {9}}
. Если это не хорошо, у меня есть два решения по 30 байтов:Mathematica на самом деле есть,
CoprimeQ
но это слишком долго.источник
Q
значит вCoprimeQ
?EvenQ
,PrimeQ
илиSubsetQ
.2sable , 4 байта
Код:
Объяснение:
Использует кодировку CP-1252 . Попробуйте онлайн!
источник
Python,
938274 байтаf
рекурсивно проверяет на наличие взаимных кодов, а вторая лямбда генерирует их. Выводит список.источник
На самом деле 8 байтов
Попробуйте онлайн!
Объяснение:
источник
range(1, n)
если это экономит какие-либо байты.R
(range(1, n+1)
) иr
(range(n)
). Поскольку они эквивалентны, я выбралR
(так как я случайно нажал Caps Lock во время написания кода).MATL , 7 байт
Попробуйте онлайн!
источник
MATLAB / Octave, 22 байта
Попробуйте онлайн!
источник
JavaScript (ES6),
6461 байтСохранено 3 байта благодаря @ user81655
Тестовый фрагмент
источник
a==
сa<2
?a
может быть 0 в какой-то момент. Я должен проверитьfilter
чтобы устранить необходимость полученияb
параметра:...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
Медуза ,
1918 байтЭто работает, вычисляя простую факторизацию каждого числа в диапазоне и проверяя, пересекает ли оно число ввода (у Jellyfish еще нет встроенного gcd). По причинам, связанным с игрой в гольф, результат находится в порядке убывания. Попробуйте онлайн!
объяснение
Во-первых,
i
оценивается вход; для ввода10
значениеi
-cell равно10
.Здесь
r
(диапазон) применяется к входу и 1. Поскольку вход больше 1, диапазон находится в порядке убывания; для ввода10
, это дает[9 8 7 6 5 4 3 2 1]
.Эта часть представляет собой одну большую функцию, которая оценивается по
i
вышеуказанному диапазону.Пересечение (
n
) простых факторов (x
).Это пусто? (
N
)Поток до уровня 0, тестирование для каждого элемента диапазона.
Filter (
#
) диапазон относительно этого списка логических значений. Созданная функцией функция[
хочет использовать аргумент to в#
качестве своего собственного аргумента, поэтому мы ставимB
блокировку#
получения каких-либо аргументов. В противном случае значение~
-cell будет использоваться в качестве аргумента большой функции. Наконец,p
печатает результат.источник
С накоплением, неконкурентный,
2421 байтСохранено 3 байта, навеянное рубином Борсунью . (
1 eq
к2<
)Попробуй это здесь!
Это n-лямбда, которая принимает один аргумент и возвращает массив.
источник
keep
не работал хорошо.CJam , 14 байтов
Попробуйте онлайн!
объяснение
Нам не нужно проверять все возможные делители
a
иb
проверять, являются ли они взаимно простыми. Достаточно посмотреть,b
разделяется ли какой-либо из главных факторовa
.источник
Mathematica, 26 байтов
источник
Perl 6 , 20 байт
источник
Брахилог ,
1613 байтЭто функция, которая принимает N в качестве входных данных и генерирует все целые числа меньше и взаимно просты с ним.
Попробуйте онлайн! Как часто бывает в Brachylog, для этого был добавлен дополнительный код, чтобы превратить функцию в полноценную программу; Интерпретатор Brachylog, если ему дана функция, а не полная программа, запустит ее, но не распечатает вывод, что означает, что вы не можете реально наблюдать за ее работой.
Объяснение:
Программа на брахилоге представляет собой цепочку ограничений; обычно LHS одного ограничения - это RHS следующего.
Обыграв трех персонажей, осознав, что нет причин проверять, является ли общий фактор (который, как известно, является основным фактором выхода) основным фактором ввода. Мы уже знаем, что это главное, поэтому мы можем просто проверить, является ли это фактором. Я приятно удивлен здесь тем, что
:A*?
не отправляет интерпретатор в бесконечный цикл и не допускает нецелое значение для A , но, поскольку интерпретатор делает то, что я хочу, я возьму его.источник
ДЯЛОГ АПЛ, 10 байт .
Объяснение (ввод
n
):источник
⍨
Japt
-f
,9852 байтаПопробуй
источник
o f_jU
j
также можно использовать для проверки, если 2 числа совпадают.Mathematica, 33 байта
Содержит U + F4A1
источник
Haskell, 27 байт
Попробуйте онлайн!
источник
Юлия 0,5 , 23 байта
Попробуйте онлайн!
источник
мемы , 11 байт неконкурентные , устаревшие
Неконкурентоспособность, так как итерация STDIN является новой. Использует кодировку UTF-8.
Объяснение:
}
получает доступ к следующему элементу ввода, но последний вход циклически повторяется, когда он задан, поэтому ввод6
будет выполнен как6 6 6 6 6 ...
в STDIN, что позволяет считывать два выхода из одного.источник
05AB1E , 3 байта
Попробуйте онлайн!
Имеет новые функции.
источник
Руби,
3634Правда, это не очень вдохновенный ответ.
2 байта сохранены благодаря Конору О'Брайену.
источник
(n)
Python 3 , 60 байт
Импортирует gcd вместо того, чтобы писать для него новую лямбду. Предложения по игре в гольф приветствуются. Попробуйте онлайн!
источник
Юлия, 30 байт
Анонимная функция.
filter
удаляет элементы из списка, которые не соответствуют действительности в соответствии с функцией.В этом случае функция имеет значение
x->(gcd(n,x)<2)
(истина, если gcd входных данных и элемента списка меньше 2). Список это диапазон1:n
.источник
PARI / GP , 27 байт
При этом используется набор-нотация, представленная в версии 2.6.0 (2013). В более ранних версиях требовалось еще четыре байта:
будет необходимо.
источник
[1..n]
), проверьте, равен ли 1 (gcd(n,k)<2
) gcd , верните числа с этим свойством. Это->
обозначение функции / замыкания, которое на 2 байта короче, чем обычный синтаксис функции, и[...|...<-...,...]
это обозначение набора, объясненное в ответе (см. Раздел 2.3.14 в Руководстве пользователя или поиск<-
).05AB1E , 4 байта
Попробуйте онлайн!
Как это устроено
источник
C (gcc) , 54 байта
Это порт моего ответа Python .
Попробуйте онлайн!
источник
Pyth , 5 байт
Попробуйте онлайн!
Как это устроено
Обратите внимание, что Pyth использует 0-индексирование.
источник