Coprimes up to N

Given a number n >= 2, output all the positive integers less than n where gcd(n, k) == 1 (with k being any one of the output numbers).  Numbers of this sort are coprime to each other.

Example: 10 gives the output [1, 3, 7, 9] (in any form you like, as long as the numbers are unambiguously separated and in some sort of list). The list cannot have duplicate entries and doesn't have to be sorted.

More test cases:

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]


We are also not counting numbers above n that are coprime to n, solely because I'm fairly certain there's infinite solutions.

Also note: Numbers that are coprime to each other are also said to be relatively prime or mutually prime to each other.

• Do seperate strings (e.g. 1\n3\n) count as valid output? Dec 27 '16 at 0:37
• @devRicher that works, sure. Dec 27 '16 at 0:53
• The intuition about there being an infinite number of numbers above n that are coprime to n feels correct to me. There are infinitely many primes, and a prime would be coprime with every number below it. Therefore, every prime greater than n (of which there are infinitely many) are also part of the coprime list. Dec 27 '16 at 20:28
• @BrianJ Not just that. If c and n are coprimes, c + kn and n are also coprimes, for all integers k. Dec 28 '16 at 2:12
• Fun fact: these are called totatives. Dec 29 '16 at 15:20

Python 2, 61 47 bytes

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


Try it online!

Background

Consider the ring $$\(Z_n, +_n, \cdot_n)\$$. While this ring is usually defined using residue classes modulo $$\n\$$, it can also be thought of as the set $$\Z_n = \{0, \dots, n - 1\}\$$, where the addition and multiplication operators are defined by $$\a +_n b = (a + b)\:\%\: n\$$ and $$\a \cdot_n b = a \cdot b\:\%\: n\$$, where $$\+,\:\cdot\text{, and } \%\$$ denote the usual addition, multiplication, and modulo operators over the integers.

Two elements $$\a\$$ and $$\b\$$ of $$\Z_n\$$ are called mutual multiplicative inverses modulo $$\n\$$ if $$\a \cdot_n b = 1\:\%\:n\$$. Note that $$\1\:\%\:n = 1\$$ whenever $$\n > 1\$$.

Fix $$\n > 1\$$ and let $$\a\$$ be a coprime of $$\n\$$ in $$\Z_n\$$. If $$\a \cdot_n x = a \cdot_n y\$$ for two elements $$\x\$$ and $$\y\$$ of $$\Z_n\$$, we have that $$\a \cdot x\:\%\:n = a \cdot y\:\%\:n\$$. This implies that $$\a \cdot (x - y)\:\%\:n = a \cdot x\:\%\:n - a \cdot y\:\%\:n = 0\$$, and we follow that $$\n \mid a \cdot (x - y)\$$, i.e., $$\n\$$ divides $$\a \cdot (x - y)\$$ evenly. Since $$\n\$$ shares no prime divisors with $$\a\$$, this means that $$\n \mid x - y\$$. Finally, because $$\-n < x - y < n\$$, we conclude that $$\x = y\$$. This shows that the products $$\a \cdot_n 0, \dots, a \cdot_n (n - 1)\$$ are all different elements of $$\Z_n\$$. Since $$\Z_n\$$ has exactly $$\n\$$ elements, one (and exactly one) of those products must be equal to $$\1\$$, i.e., there is a unique $$\b\$$ in $$\Z_n\$$ such that $$\a \cdot_n b = 1\$$.

Conversely, fix $$\n > 1\$$ and let $$\a\$$ be an element of $$\Z_n\$$ that is not coprime to $$\n\$$. In this case, there is a prime $$\p\$$ such that $$\p \mid a\$$ and $$\p \mid n\$$. If $$\a\$$ admitted a multiplicative inverse modulo $$\n\$$ (let's call it $$\b\$$), we'd have that $$\a \cdot_n b = 1\$$, meaning that $$\a \cdot b\:\%\:n = 1\$$ and, therefore, $$\(a \cdot b - 1)\:\%\:n = a \cdot b\:\%\:n - 1 = 0\$$, so $$\n \mid a \cdot b - 1\$$. Since $$\p \mid a\$$, we follow that $$\p \mid a \cdot b\$$. On the other hand, since $$\p \mid n\$$, we also follow that $$\p \mid a \cdot b - 1\$$. This way, $$\p \mid (a \cdot b) - (a \cdot b - 1) = 1\$$, which contradicts the assumption that $$\p\$$ is a prime number.

This proves that the following statements are equivalent when $$\n > 1\$$.

• $$\a\$$ and $$\n\$$ are coprime.

• $$\a\$$ admits a multiplicative inverse modulo $$\n\$$.

• $$\a\$$ admits a unique multiplicative inverse modulo $$\n\$$.

How it works

For each pair of integers $$\a\$$ and $$\b\$$ in $$\Z_n\$$, the integer $$\k := a \cdot n + b\$$ is unique; in fact, $$\a\$$ and $$\b\$$ are quotient and remainder of $$\k\$$ divided by $$\n\$$, i.e., given $$\k\$$, we can recover $$\a = k/n\$$ and $$\b = k\:\%\: n\$$, where $$\/\$$ denotes integer division. Finally, since $$\a ≤ n - 1\$$ and $$\b ≤ n - 1\$$, $$\k\$$ is an element of $$\Z_{n^2}\$$; in fact, $$\k ≤ (n - 1) \cdot n + (n - 1) = n^2 - 1\$$.

As noted above, if $$\a\$$ and $$\n\$$ are coprime, there will be a unique $$\b\$$ such that $$\a \cdot b\:\%\:n = 1\$$, i.e., there will be a unique $$\k\$$ such that $$\k / n = a\$$ and $$\k / n \cdot k\:\%\:n = (k / n) \cdot (k\:\%\:n)\:\%\:n = 1\$$, so the generated list will contain $$\a\$$ exactly once.

Conversely, if $$\a\$$ and $$\n\$$ are not coprime, the condition $$\k / n \cdot k\:\%\:n = 1\$$ will be false for all values of $$\k\$$ such that $$\a = k / n\$$, so the generated list will not contain $$\a\$$.

This proves that the list the lambda returns will contain all of $$\n\$$'s coprimes in $$\Z_n\$$ exactly once.

• "GCD? Where we're going, we don't need GCD." Dec 26 '16 at 19:31
• Woah. That's all I wanted to write, but apparently I needed 15 characters. Still, woah. Great job. Dec 27 '16 at 8:30

Jelly, 4 bytes

gRỊT


Try it online!

How it works

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.

• Coding in this language takes some gRỊT Dec 26 '16 at 18:33
• I managed to (ab)use the "Minimum link value" quick (ÐṂ) in order to get 3 bytes. Sep 28 '17 at 19:00

Jelly, 3 bytes

gÐṂ


Try it online!

How does this work?

gÐṂ  - (Monadic) Full program.

g    - Greatest common divisor.
ÐṂ  - Keep the elements with minimum link value (i.e. those with GCD == 1)
Note that this automatically creates the range [1, input] (inclusive).


Proof of validity

Since we want to extract the coprimes only, the minimum value of the Greatest-Common-Divisors list has to be 1 for the ÐṂ trick to work. Let's prove that (in two different methods):

1. The implicitly generated range, $$\[1, \text{input}]\$$ contains $$\1\$$ and $$\\gcd(1, x) = 1\:\:\forall\:\:x \in \mathbb{Z}^{*}\$$. The greatest common divisor is always a strictly positive integer, hence $$\1\$$ is guaranteed to occur and will always be the minimum value.

2. Two consecutive positive integers are always coprime. Consider $$\x, y \in \mathbb{Z}^{*}\$$, with $$\y = x + 1\$$. Then we take another positive integer $$\k\$$ such that $$\k \mid x\$$ and $$\k \mid y\$$.

This implies that $$\k \mid (y - x)\$$, so $$\k \mid (x + 1 - x)\$$, thus $$\k \mid 1\$$. The only positive integer to divide $$\1\$$ is $$\1\$$ itself, so it is guaranteed to appear in the list and will always be the minimum value.

• You outgolfed Dennis in his own language after 9 months!
Sep 28 '17 at 19:21
• @Adám I am not sure whether ÐṂ existed back then, anyway I am quite satisfied with this one. Sep 28 '17 at 19:22
• For the record, DṂ did exist, but it only worked for monads. The commit implemented Þ, ÐṂ, ÐṀ for dyads is dated May 9, 2017. Sep 28 '17 at 21:31
• @Dennis I knew there'd be a good reason why you didn't have the 3-byte version. We were wondering about that in chat too, so thanks for the useful information! Sep 29 '17 at 4:21

Mathematica, 25 bytes

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


Slightly weird output format, where each result is wrapped in a separate list, e.g. {{1}, {3}, {7}, {9}}. If that's not okay, I've got two solutions at 30 bytes:

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


Mathematica actually has CoprimeQ but that's way too long.

• What does Q mean in CoprimeQ? Dec 27 '16 at 6:33
• @ConorO'Brien "question" I guess. All decision problem built-ins end in Q like EvenQ, PrimeQ or SubsetQ. Dec 27 '16 at 7:32

2sable, 4 bytes

Code:

ƒN¿–


Explanation:

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


Uses the CP-1252 encoding. Try it online!

• Good job (almost) beating Dennis. (few minutes late though). Dec 31 '16 at 1:15

Python, 9382 74 bytes

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 recursively checks for coprimes, and the second lambda generates them. Outputs a list.

Actually, 8 bytes

;╗R╜┤░


Try it online!

Explanation:

;╗R╜┤░
R  ░  elements of range(1, n+1) where
;╗  ╜     n and the element
┤    are coprime

• I believe you can just do range(1, n) if that saves any bytes. Dec 26 '16 at 19:26
• @ETHproductions It doesn't. The two options are R (range(1, n+1)) and r (range(n)). Since they're equivalent, I chose R (since I accidentally hit caps lock while writing the code).
– user45941
Dec 26 '16 at 19:27
• Yeah, that's what I figured. I didn't see an instruction that seemed dedicated to incrementing, but I thought there might have been one anyway Dec 26 '16 at 19:28

MATL, 7 bytes

:GZd1=f


Try it online!

MATLAB/Octave, 22 bytes

@(n)find(gcd(1:n,n)<2)


Try it online!

JavaScript (ES6), 64 61 bytes

Saved 3 bytes thanks to @user81655

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


Test snippet

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) }]); • Can't you swap a== with a<2? Dec 26 '16 at 18:14 • @EasterlyIrk Not sure, a might be 0 at some point. I'll have to check Dec 26 '16 at 18:25 • You could move the GCD function into the filter to remove the need to receive a b parameter: ...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n)) Dec 27 '16 at 1:22 • @user81655 That's great, thanks! :-) Dec 27 '16 at 1:24 Jellyfish, 19 18 bytes p [# B &~xr1 NnEi  This works by computing the prime factorization of every number in the range and checking whether it intersects that of the input (Jellyfish doesn't have a gcd builtin yet). For golfing reasons, the output is in descending order. Try it online! Explanation First off, i is evaluated input; for input 10, the value of the i-cell is 10. r1 i  Here r (range) is applied to the input and 1. Because the input is greater than 1, the range is in descending order; for input 10, this gives [9 8 7 6 5 4 3 2 1]. [# B &~x Nn  This part is one big function, which is evaluated on i and the above range. ~x n  Intersection (n) of prime factors (x). &~x Nn  Is it empty? (N)  &~x Nn  Thread to level 0, testing for each element of the range. [# B &~x Nn  Filter (#) the range with respect to this list of booleans. The function produced by [ wants to use the argument to # as its own argument, so we put a B to block # from getting any arguments. Otherwise, the value of the ~-cell would be used as the argument of the big function. Finally, p prints the result. Stacked, noncompeting, 24 21 bytes Saved 3 bytes, inspired by Borsunho's ruby. (1 eq to 2<) {!n:>1+:n gcd 2<keep}  Try it here! This is an n-lambda that takes a single argument and yields the array. {!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.  • Why is this noncompeting? Dec 26 '16 at 19:16 • @ZacharyT mainly, keep wasn't working nicely. Dec 26 '16 at 19:17 CJam, 14 bytes {:X{Xmff%:*},}  Try it online! Explanation We don't need to check all possible divisors of a and b to test whether they're coprime. It's sufficient to look at whether any of the prime factors of b divides 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. },  Mathematica, 26 bytes Pick[r=Range@#,r~GCD~#,1]&  • Ohhhh, I've been looking for something like Pick. I guess now I'm glad I didn't find it, though. ;) But it should be very useful for future challenges. Dec 27 '16 at 8:27 Perl 6, 20 bytes {grep 2>* gcd$_,^$_}  Brachylog, 16 13 bytes >.$p'(e:A*?),


This is a function that takes N as input, and generates all integers less than and coprime to it.

Try it online! As is often the case in Brachylog, this has had extra code added to make the function into a full program; Brachylog's interpreter, if given a function rather than a full program, will run it but not print the output, which means you can't really observe its workings.

Explanation:

A Brachylog program is a chain of constraints; typically, the LHS of one constraint is the RHS of the next.

>.$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.)


Golfed down three characters by realising there's no reason to check to see if the common factor (which is already known to be a prime factor of the output) is a prime factor of the input. We already know it's prime, so we can just check if it's a factor. I'm pleasantly surprised here that :A*? doesn't send the interpreter into an infinite loop and doesn't allow a non-integer value for A, but as the interpreter does what I want, I'll take it.

Dyalog APL, 10 bytes.

0~⍨⍳×1=⊢∨⍳


Explanation (input 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.

• I love the way APL code looks like the face you make when you read it. ⍨ Dec 26 '16 at 18:43
• Yep, and it demolishes almost every not code-golf-oriented language. :). Dec 26 '16 at 18:47
• Why only "might" work? Dec 26 '16 at 19:10
• I'm just going to assume it works. Dec 26 '16 at 19:14
• @ZacharyT why can't you test it? When I paste it into try-apl.org, it errors with invalid token. Dec 26 '16 at 19:16

Japt-f, 985 2 bytes

jN


Try it

• 2 bytes saved thanks to ETH pointing out a brainfart, which led to another byte saved.
• You could do o f_jU Oct 12 '17 at 17:39
• Thanks, @ETHproductions. Don't know what I was thinking here! Must've been one of those (many) moments when I forget j can also be used to test if 2 numbers are co-prime. Oct 13 '17 at 10:23

Mathematica, 33 bytes

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


Contains U+F4A1

• What's the unprintable do? Dec 26 '16 at 18:14
• @EasterlyIrk introduces an unnamed function with a named argument. it's rendered as an arrow in Mma. Dec 26 '16 at 18:15
• @MartinEnder oh, cool. Dec 26 '16 at 18:15
• U+F4A1 is a private use character. As Martin said, it's rendered as an arrow in Mathematica. Dec 26 '16 at 18:18

f n=[k|k<-[1..n],gcd n k<2]


Try it online!

Julia 0.5, 23 bytes

!n=1÷gcd.(1:n,n)|>find


Try it online!

memes, 11 bytes non-competing, outdated

Non-competing as iteration of STDIN is new. Uses UTF-8 encoding.

d}}]i=1?ip


Explanation:

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


} accesses the next input item, but last input is looped through when given, so inputting 6 will result as 6 6 6 6 6 ... in STDIN, making it possible for reading two outputs from one.

• Did you just create this lang today? If it's made before the challenge, it has to be non-competing. Dec 26 '16 at 22:16
• @EasterlyIrk It was made 3 days ago, im just constantly working on it. Also, I assume you mean after? Dec 26 '16 at 22:16
• Yeah, typo thanks. And it's okay, as long as the features used in the answer and older than the challenge. Dec 26 '16 at 22:17
• @EasterlyIrk I see, in that case i'll have to edit my answer. Dec 26 '16 at 22:18
• Yeah, sorry. :/ Dec 26 '16 at 22:18

05AB1E, 3 bytes

Lʒ¿


Try it online!

Has new features.

Ruby, 3634

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


Admittedly, this isnt a very inspired answer.

2 bytes saved thanks to Conor O'Brien.

• You can shave off two bytes by removing parentheses around (n) Dec 26 '16 at 18:54

Python 3, 60 bytes

Imports gcd instead of writing a new lambda for it. Golfing suggestions welcome. Try it online!

import math
lambda c:[i for i in range(c)if math.gcd(c,i)<2]

• I don't think you can golf this more. Importing gcd directly or math as m both add bytes. Dec 26 '16 at 19:05

Julia, 30 bytes

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


Anonymous function. filter removes elements from a list that aren't truthy according to a function.

In this case, the function is x->(gcd(n,x)<2) (true if the gcd of the input and the list element is less than 2). The list is the range 1:n.

PARI/GP, 27 bytes

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


This uses the set-notation introduced in version 2.6.0 (2013). In earlier versions, four more bytes were needed:

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


would be needed.

• How does this work? Dec 28 '16 at 18:12
• @EasterlyIrk The same as most of these submissions -- make a range from 1 to n ([1..n]), check if gcd is 1 (gcd(n,k)<2), return the numbers with this property. The -> is function/closure notation, shorter by 2 bytes than normal function syntax and [...|...<-...,...] is the set notation explained in the answer (see section 2.3.14 in the User's Manual, or search for <-). Dec 28 '16 at 18:23

05AB1E, 4 bytes

GN¿–


Try it online!

How it works

     # implicit input
G    # for N in range(1..input)
N   # push N
¿  # gcd(input, N)
– # if 1, print N


C (gcc), 54 bytes

k;f(n){for(k=0;++k/n<n;k/n*k%n-1||printf("%u ",k/n));}


This is a port of my Python answer.

Try it online!

Whispers v2, 65 bytes

> Input
> 1
>> (1]
>> L⊓1
>> L=2
>> Select∘ 4 5 3
>> Output 6


Try it online!

Uses the recently implemented Select∘ command.

How it works

The entire program is built from lines 4, 5 and 6

>> L⊓1
>> L=2
>> Select∘ 4 5 3


This is the first use of any of the three Select statements, this time using the Select∘ statement. All forms of the Select statements take n line references as arguments. The last number references the array to select from (let's say $$\A\$$), and the others reference the functions to iterate over that array (i.e the array of functions, $$\B\$$). However, they differ as follows:

• Select∧ - Only select elements which are truthy under all functions in $$\B\$$:

$$R := [x \in A \: | \: f(x) \top, \forall f \in B]$$

• Select∨ - Only select elements which are truthy under any function in $$\B\$$

$$R := [x \in A \: | \: f(x) \top, \exists f \in B]$$

• Select∘ - Only select elements which, when all functions in $$\B\$$ are composed together, are truthy under this new function:

$$\text{Let }B := [f(x), g(x), h(x)]$$ $$R := [x \in A \: | \: h(g(f(x))) \: \top]$$

In this program, we can define $$\A := [1, 2, ..., \alpha-1, \alpha]\$$, where $$\\alpha\$$ is the input. We then define line 4 (>> L⊓1) as $$\f(x) = \gcd(x, \alpha)\$$ and line 5 (>> L=2) as $$\g(x) := (x = 1)\$$. Finally, we can define $$\B = [f(x), g(x)]\$$. This sets us up for the select statement as shown above.

When we encounter the Select∘ statement, we take $$\R\$$ (the final array) as defined by the third relationship above. To make things slightly easer, we'll define

\begin{align} h(x) & := g(f(x)) \\ & := gcd(x, \alpha) = 1 \end{align}

$$\R\$$ is then equal to the array where $$\\forall x \in R\$$, $$\h(x) \: \top\$$. Finally, on the last line, we output $$\R\$$.

Shorter version, 56 bytes

> Input
> 1
>> (1]
>> L⟂1
>> Select∘ 4 3
>> Output 5
`

Try it online!

This is much less interesting as it uses the co-prime builtin. In this case, any of the three select statements can be used.