Взаимно до N

51

Учитывая число n >= 2, выведите все натуральные числа меньше, чем nгде gcd(n, k) == 1kлюбым из выходных чисел). Числа такого рода взаимно просты друг с другом.

Пример: 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, потому что я уверен, что есть бесконечные решения.

Также обратите внимание: числа, которые взаимно просты друг с другом, также называются взаимно простыми или взаимно простыми.

Rɪᴋᴇʀ
источник
Считают ли отдельные строки (например 1\n3\n) допустимым выводом?
devRicher
@devRicher, который работает, конечно.
Rɪᴋᴇʀ
Интуиция о существовании бесконечного числа чисел выше n, взаимно простых с n, кажется мне правильной. Существует бесконечно много простых чисел, и простое число будет взаимно простым с каждым числом под ним. Следовательно, каждое простое число, большее n (которых их бесконечно много), также является частью списка взаимно простых чисел.
Брайан Джей
@BrianJ Не только это. Если c и n являются взаимно простыми числами, c + kn и n также взаимно просты для всех целых чисел k .
Деннис
1
Забавный факт: они называются тативами .
Wojowu

Ответы:

17

Желе , 3 байта

gÐṂ

Попробуйте онлайн!

Как это работает?

gÐṂ - (Monadic) Полная программа.

г - наибольший общий делитель.
 ÐṂ - сохранить элементы с минимальным значением ссылки (то есть элементы с GCD == 1)
       Обратите внимание, что это автоматически создает диапазон [1, вход] (включительно).

Доказательство действительности

Так как мы хотим , чтобы извлечь только coprimes, минимальное значение Величайшего-Common-делители списка должно быть 1 для ÐṂтрюка к работе. Давайте докажем это (двумя разными способами):

  1. Неявно сгенерированный диапазон, содержит и . Наибольшим общим делителем всегда является строго положительное целое число, следовательно, гарантированно встречается и всегда будет минимальным значением.1 gcd ( 1 , x ) = 1[1,input]1gcd(1,x)=1xZ1

  2. Два последовательных натуральных числа всегда взаимно просты. Рассмотрим , где . Затем мы берем еще одно натуральное число такое что и . y = x + 1 k k x k yx,yZy=x+1kkxky

    Это означает, что , поэтому , следовательно, . Единственное положительное целое число, чтобы разделить - это само , поэтому оно гарантированно появится в списке и всегда будет минимальным значением.k ( x + 1 - x ) k 1 1 1k(yx)k(x+1x)k111

Мистер Xcoder
источник
2
Вы переиграли Денниса на его родном языке через 9 месяцев!
Адам
@ Adám Я не уверен, ÐṂсуществовал ли тогда, в любом случае, я вполне доволен этим.
г-н Xcoder
2
Для записи, DṂсуществует, но он работал только для монад. Коммит реализованы Þ, ÐṂ, ÐṀдля двоек датируется 9 мая 2017 года
Dennis
@ Денис Я знал, что будет веская причина, почему у тебя не было 3-байтовой версии. Мы тоже интересовались этим в чате, так что спасибо за полезную информацию!
Мистер Кскодер
56

Python 2 , 61 47 байт

lambda n:[k/n for k in range(n*n)if k/n*k%n==1]

Попробуйте онлайн!

Фон

Рассмотрим кольцо . Хотя это кольцо обычно определяется с использованием классов вычетов по модулю , его также можно рассматривать как множество , где операторы сложения и умножения определяются и , где обозначают обычное добавление, умножение и операторы по модулю над целыми числами.n Z n = { 0 , , n - 1 } a + n b = ( a + b )(Zn,+n,n)nZn={0,,n1}a n b = a ba+nb=(a+b)%n+ ,anb=ab%n+,, and %

Два элемента и в называются взаимными мультипликативными инверсиями по модулю если . Обратите внимание, что всякий раз, когда .b Z n n a n b = 1abZnn1anb=1%nn > 11%n=1n>1

Зафиксируем и пусть будет взаимно простым в . Если для двух элементов и из , имеем . Это означает, что , и мы следуем этому , т. е. делит равномерно. Поскольку делит простых делителей с , это означает, что . Наконец, потому чтоa n Z n a n x = a n y x y Z n a xn>1anZnanx=anyxyZna ( x - y )ax%n=ay%nn 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(xy)%n=ax%nay%n=0na(xy)na(xy)nanxyn<xy<n , мы заключаем, что . Это показывает, что произведения являются различными элементами . Так имеет ровно элементов, один (и ровно один) из этих продуктов должна быть равна , то есть, есть уникальный в таким образом, что .x=yan0,,an(n1)ZnZnn1 b a n b = 1Znanb=1

И наоборот, зафиксируем и пусть будет элементом который не взаимно прост с . В этом случае существует такое простое число , что и . Если бы допускал мультипликативный обратный по модулю (назовем это ), мы бы имели , что означает, что и, следовательно, , поэтому . Так как , мы следуем этомуZ п п р р | р | п п б в п Ь = 1 в бn>1aZnnppapnanbanb=1( a b - 1 )ab%n=1n a b - 1 p a p a b p n p a b - 1 p ( a b ) - ( a b - 1 ) = 1 p(ab1)%n=ab%n1=0nab1papab . С другой стороны, поскольку , мы также следуем тому, что . Таким образом, , что противоречит предположению, что - простое число.pnpab1p(ab)(ab1)=1p

Это доказывает, что следующие утверждения эквивалентны, когда .n>1

  • нa и взаимно просты.n

  • нa допускает мультипликативный обратный по модулю .n

  • нa допускает единственный мультипликативный обратный по модулю .n

Как это устроено

Для каждой пары целых чисел и в целое число уникально; на самом деле, и являются частными, а остаток от делится на , т.е., учитывая , мы можем восстановить и , где обозначает целочисленное деление. Наконец, так как и , является элементом ; фактически .b Z n k : = a n + b a b k n k a = k / n b = kabZnk:=an+babknka=k/n/ a n - 1 b n - 1 k Z n 2 k ( n - 1 ) n + ( n - 1 ) = n 2 - 1b=k%n/an1bn1kZn2k(n1)n+(n1)=n21

Как отмечено выше, если и взаимно просты, будет уникальный такой что , т. Е. Будет уникальный такой, что и , так что генерируется список будет содержать ровно один раз.n b a banbk k / n = a k / n kab%n=1kk/n=ak/nk%n=(k/n)(k%n)%n=1a

И наоборот, если и являются не взаимно просты, то условие будет ложным для всех значений , таких , что , поэтому сгенерированный список будет не содержать .н к / н кank a = k / n ak/nk%n=1ka=k/na

Это доказывает, что список, который возвращает лямбда, будет содержать все взаимно чисел в ровно один раз.Z nnZn

Деннис
источник
26
«GCD? Куда мы идем, нам не нужен GCD».
Rɪᴋᴇʀ
1
Ого. Это все, что я хотел написать, но, видимо, мне нужно было 15 символов. Тем не менее, вау. Отличная работа.
Эрик Лагергрен
24

Желе , 4 байта

gRỊT

Попробуйте онлайн!

Как это устроено

gRỊT  Main link. Argument: n

 R    Range; yield [1, ..., n].
g     Compute the GCD of n and each k in [1, ..., n].
  Ị   Insignificant; return 1 for GCDs less or equal to 1.
   T  Truth; yield the indices of all truthy elements.
Деннис
источник
33
Кодирование на этом языке занимает немногоgRỊT
ETHproductions
1
Мне удалось (ab) использовать «Минимальное значение ссылки» quick ( ÐṂ), чтобы получить 3 байта .
г-н Xcoder
14

Mathematica, 25 байтов

Range@#~GCD~#~Position~1&

Немного странный выходной формат, где каждый результат упакован в отдельный список, например {{1}, {3}, {7}, {9}}. Если это не хорошо, у меня есть два решения по 30 байтов:

Select[Range[x=#],#~GCD~x<2&]&
#&@@@Range@#~GCD~#~Position~1&

Mathematica на самом деле есть, CoprimeQно это слишком долго.

Мартин Эндер
источник
1
Что Qзначит в CoprimeQ?
Конор О'Брайен,
2
@ ConorO'Brien "вопрос", я думаю. Все встроенные решения проблем заканчиваются на Q вроде EvenQ, PrimeQили SubsetQ.
Мартин Эндер
10

2sable , 4 байта

Код:

ƒN¿–

Объяснение:

ƒ       # For N in the range [0, input]..
 N¿     #   Compute the GCD of N and the input
   –    #   If 1, print N with a newline

Использует кодировку CP-1252 . Попробуйте онлайн!

Аднан
источник
Хорошая работа (почти), победив Денниса. (хотя несколько минут позже).
Захари
10

Python, 93 82 74 байта

f=lambda a,b:f(b,a%b)if b else a<2
lambda c:[i for i in range(c)if f(i,c)]

fрекурсивно проверяет на наличие взаимных кодов, а вторая лямбда генерирует их. Выводит список.

Rɪᴋᴇʀ
источник
7

На самом деле 8 байтов

;╗R`╜┤`░

Попробуйте онлайн!

Объяснение:

;╗R`╜┤`░
  R`  `░  elements of range(1, n+1) where
;╗  ╜     n and the element
     ┤    are coprime
Мего
источник
1
Я считаю, что вы можете просто сделать, range(1, n)если это экономит какие-либо байты.
ETHproductions
1
@ETHproductions Это не так. Два варианта R( range(1, n+1)) и r( range(n)). Поскольку они эквивалентны, я выбрал R(так как я случайно нажал Caps Lock во время написания кода).
Mego
Да, это то, что я понял. Я не видел инструкции, которая, казалось бы, была посвящена инкременту, но я подумал, что она могла быть в любом случае
ETHproductions
6

JavaScript (ES6), 64 61 байт

Сохранено 3 байта благодаря @ user81655

n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))

Тестовый фрагмент

f=n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))

for(var i = 2; i < 50; i++) console.log(i + ":", `[${ f(i) }]`);

ETHproductions
источник
Не можете ли вы поменяться a==с a<2?
Rɪᴋᴇʀ
@EasterlyIrk Не уверен, aможет быть 0 в какой-то момент. Я должен проверить
ETHproductions
Вы можете переместить функцию GCD в, filterчтобы устранить необходимость получения bпараметра:...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
user81655
@ user81655 Отлично, спасибо! :-)
ETHproductions
6

Медуза , 19 18 байт

p
[#
`B
&~xr1
NnEi

Это работает, вычисляя простую факторизацию каждого числа в диапазоне и проверяя, пересекает ли оно число ввода (у Jellyfish еще нет встроенного gcd). По причинам, связанным с игрой в гольф, результат находится в порядке убывания. Попробуйте онлайн!

объяснение

Во-первых, iоценивается вход; для ввода 10значение i-cell равно 10.

r1
i

Здесь r(диапазон) применяется к входу и 1. Поскольку вход больше 1, диапазон находится в порядке убывания; для ввода 10, это дает [9 8 7 6 5 4 3 2 1].

[#
`B
&~x
Nn

Эта часть представляет собой одну большую функцию, которая оценивается по iвышеуказанному диапазону.

~x
n

Пересечение ( n) простых факторов ( x).

&~x
Nn

Это пусто? ( N)

`
&~x
Nn

Поток до уровня 0, тестирование для каждого элемента диапазона.

[#
`B
&~x
Nn

Filter ( #) диапазон относительно этого списка логических значений. Созданная функцией функция [хочет использовать аргумент to в #качестве своего собственного аргумента, поэтому мы ставим Bблокировку #получения каких-либо аргументов. В противном случае значение ~-cell будет использоваться в качестве аргумента большой функции. Наконец, pпечатает результат.

Zgarb
источник
5

С накоплением, неконкурентный, 24 21 байт

Сохранено 3 байта, навеянное рубином Борсунью . ( 1 eqк 2<)

{!n:>1+:n gcd 2<keep}

Попробуй это здесь!

Это n-лямбда, которая принимает один аргумент и возвращает массив.

{!n:>1+:n gcd 2<keep}
{!                  }  n-lambda
  n                    push n
   :>                  range [0, n)
     1+                range [1, n]
       :               duplicate
        n gcd          element-wise gcd with n
              2<       element-wise equality with 1
                       this yields the range [1, n] and a boolean mask of coprime numbers
                keep   then, we simply apply the mask to the range and keep coprimes.
Конор О'Брайен
источник
Почему это неконкурентоспособно?
Zacharý
@ZacharyT в основном, keepне работал хорошо.
Конор О'Брайен
5

CJam , 14 байтов

{:X{Xmff%:*},}

Попробуйте онлайн!

объяснение

Нам не нужно проверять все возможные делители aи bпроверять, являются ли они взаимно простыми. Достаточно посмотреть, bразделяется ли какой-либо из главных факторов a.

:X     e# Store the input in X.
{      e# Filter the list [0 1 ... X-1] by the results of this block...
  Xmf  e#   Get the prime factors of X.
  f%   e#   Take the current value modulo each of those prime factors.
  :*   e#   Multiply the results. Iff any of them divide the current
       e#   value, there's a 0 in the list, and the result of the product
       e#   is also 0, dropping the value from the resulting list.
},
Мартин Эндер
источник
5

Mathematica, 26 байтов

Pick[r=Range@#,r~GCD~#,1]&
alephalpha
источник
1
Оооо, я искал что-то вроде Пика. Думаю, теперь я рад, что не нашел его, хотя. ;) Но это должно быть очень полезно для будущих задач.
Мартин Эндер
4

Брахилог , 16 13 байт

>.$p'(e:A*?),

Это функция, которая принимает N в качестве входных данных и генерирует все целые числа меньше и взаимно просты с ним.

Попробуйте онлайн! Как часто бывает в Brachylog, для этого был добавлен дополнительный код, чтобы превратить функцию в полноценную программу; Интерпретатор Brachylog, если ему дана функция, а не полная программа, запустит ее, но не распечатает вывод, что означает, что вы не можете реально наблюдать за ее работой.

Объяснение:

Программа на брахилоге представляет собой цепочку ограничений; обычно LHS одного ограничения - это RHS следующего.

>.$p'(e:A*?),
>              The input is greater than
 .             the output, whose
  $p           prime factorisation does
    '(     )   not obey the following constraint:
      e        it has an element which
       :A*     can be multiplied by something to
          ?    produce the input.
            ,  (This comma turns off an unwanted implicit constraint.)

Обыграв трех персонажей, осознав, что нет причин проверять, является ли общий фактор (который, как известно, является основным фактором выхода) основным фактором ввода. Мы уже знаем, что это главное, поэтому мы можем просто проверить, является ли это фактором. Я приятно удивлен здесь тем, что :A*?не отправляет интерпретатор в бесконечный цикл и не допускает нецелое значение для A , но, поскольку интерпретатор делает то, что я хочу, я возьму его.

Сообщество
источник
4

ДЯЛОГ АПЛ, 10 байт .

0~⍨⍳×1=⊢∨⍳

Объяснение (ввод n):

0~⍨⍳×1=⊢∨⍳
         ⍳ - 1 ... n (Thus, ⎕IO is 1)
       ⊢∨  - Each GCD'd by n
     1=    - Test equality with 1 on each element
   ⍳×      - multiplied by its index
0~⍨        - without 0.
Zachary
источник
3
Мне нравится, как код APL выглядит как лицо, которое вы делаете, когда читаете его.
DJMcMayhem
Да, и это уничтожает почти каждый не ориентированный на код язык. :).
Захари
Почему только "может" работать?
Rɪᴋᴇʀ
Я просто собираюсь предположить, что это работает.
Захари
@ZacharyT почему ты не можешь это проверить? Когда я вставляю его в try-apl.org, он ошибается неверным токеном.
Rɪᴋᴇʀ
4

Japt -f , 9 8 5 2 байта

jN

Попробуй

  • 2 байта сохранены благодаря ETH, указывающему на брэйнфарт, который привел к сохранению другого байта.
мохнатый
источник
Вы могли бы сделатьo f_jU
ETHproductions
Спасибо, @ETHproductions. Не знаю, о чем я думал здесь! Должно быть, это был один из тех (многих) моментов, когда я забыл, jтакже можно использовать для проверки, если 2 числа совпадают.
Лохматый
3

Mathematica, 33 байта

xSelect[Range@x,x~CoprimeQ~#&]

Содержит U + F4A1

Юнг Хван Мин
источник
Что делать непечатным?
Rɪᴋᴇʀ
3
@EasterlyIrk представляет безымянную функцию с именованным аргументом. это отображается как стрела в Mma.
Мартин Эндер
@MartinEnder о, круто.
Rɪᴋᴇʀ
U + F4A1 - персонаж личного пользования. Как сказал Мартин, в Mathematica он отображается как стрела.
Захари
3

мемы , 11 байт неконкурентные , устаревшие

Неконкурентоспособность, так как итерация STDIN является новой. Использует кодировку UTF-8.

d`}}]i=1?ip

Объяснение:

d     Set program to not output result
`}    Loop next input-times
}]i   GCD of input and loop index
=1?   Is it equal to 1? If yes,
ip    Print out loop index

}получает доступ к следующему элементу ввода, но последний вход циклически повторяется, когда он задан, поэтому ввод 6будет выполнен как 6 6 6 6 6 ...в STDIN, что позволяет считывать два выхода из одного.

devRicher
источник
Вы только что создали этот язык сегодня? Если он сделан до испытания, он должен быть неконкурентным.
Rɪᴋᴇʀ
@EasterlyIrk Это было сделано 3 дня назад, я просто постоянно работаю над этим. Кроме того, я полагаю, вы имеете в виду после ?
devRicher
Да, опечатка спасибо. И это нормально, пока функции, используемые в ответе, и старше, чем вызов.
Rɪᴋᴇʀ
@EasterlyIrk Я вижу, в этом случае мне придется редактировать свой ответ.
devRicher
Да жаль. : /
Rɪᴋᴇʀ
2

Руби, 36 34

->n{n.times{|i|p i if i.gcd(n)<2}}

Правда, это не очень вдохновенный ответ.

2 байта сохранены благодаря Конору О'Брайену.

Borsunho
источник
Вы можете сбрить два байта, убрав круглые скобки(n)
Конор О'Брайен
2

Python 3 , 60 байт

Импортирует gcd вместо того, чтобы писать для него новую лямбду. Предложения по игре в гольф приветствуются. Попробуйте онлайн!

import math
lambda c:[i for i in range(c)if math.gcd(c,i)<2]
Sherlock9
источник
Я не думаю, что вы можете играть в гольф больше. Импорт gcd напрямую или математика как m добавляет байты.
Rɪᴋᴇʀ
2

Юлия, 30 байт

n->filter(x->(gcd(n,x)<2),1:n)

Анонимная функция. filterудаляет элементы из списка, которые не соответствуют действительности в соответствии с функцией.

В этом случае функция имеет значение x->(gcd(n,x)<2)(истина, если gcd входных данных и элемента списка меньше 2). Список это диапазон 1:n.

Rɪᴋᴇʀ
источник
2

PARI / GP , 27 байт

n->[k|k<-[1..n],gcd(k,n)<2]

При этом используется набор-нотация, представленная в версии 2.6.0 (2013). В более ранних версиях требовалось еще четыре байта:

n->select(k->gcd(k,n)<2,[1..n])

будет необходимо.

Чарльз
источник
Как это работает?
Rɪᴋᴇʀ
1
@EasterlyIrk Так же, как и большинство этих представлений - введите диапазон от 1 до n ( [1..n]), проверьте, равен ли 1 ( gcd(n,k)<2) gcd , верните числа с этим свойством. Это ->обозначение функции / замыкания, которое на 2 байта короче, чем обычный синтаксис функции, и [...|...<-...,...]это обозначение набора, объясненное в ответе (см. Раздел 2.3.14 в Руководстве пользователя или поиск <-).
Чарльз
1

Pyth , 5 байт

x1iLQ

Попробуйте онлайн!

Как это устроено

Обратите внимание, что Pyth использует 0-индексирование.

x1iLQ   Q = eval(input())

x1iLQQ  implicit Q at the end
  iLQQ  [gcd(Q,0), gcd(Q,1), ..., gcd(Q,Q-1)]
x1      all occurences of 1 in the above list (return their indices)
Дрянная Монахиня
источник