51
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do seperate strings (e.g. 1\n3\n) count as valid output? \$\endgroup\$ – devRicher Dec 27 '16 at 0:37
  • \$\begingroup\$ @devRicher that works, sure. \$\endgroup\$ – Rɪᴋᴇʀ Dec 27 '16 at 0:53
  • \$\begingroup\$ 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. \$\endgroup\$ – Brian J Dec 27 '16 at 20:28
  • \$\begingroup\$ @BrianJ Not just that. If c and n are coprimes, c + kn and n are also coprimes, for all integers k. \$\endgroup\$ – Dennis Dec 28 '16 at 2:12
  • 1
    \$\begingroup\$ Fun fact: these are called totatives. \$\endgroup\$ – Wojowu Dec 29 '16 at 15:20

43 Answers 43

1
\$\begingroup\$

C (gcc), 99 bytes

#include<stdio.h>
g(a,b){return b>0?g(b,a%b):a;}c(n,i){for(i=1;i<n;i++)g(n,i)<2?printf("%i ",i):0;}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Java 8, 98 bytes

import java.util.*;n->{Set r=new HashSet();for(int i=0;++i/n<n;)r.add(i/n*i%n==1?i/n:1);return r;}

Port of @Dennis' amazing Python answer.

Explanation:

Try it here.

import java.util.*;     // Required import for Set and HashSet

n->{                    // Method with integer parameter and Set return-type
  Set r=new HashSet();  //  Result-Set
  for(int i=0;          //  Index-integer (starting at 0)
      ++i/n<n;)         //  Loop as long as `i/n` is smaller than `n`
                        //  (starting `i` at 1 by first increasing it by 1 with `++i`)
    r.add(i/n           //   If `i/n`,
          *i%n          //   multiplied by `i` modulo-`n`,
              ==1?      //   is exactly 1:
           i/n          //    Add `i/n` to the Set
          :             //   Else:
           1            //    Add 1 to the Set
  );                    //  End of loop
  return r;             //  Return the result-Set
}                       // End of method
\$\endgroup\$
1
\$\begingroup\$

Gaia, 2 bytes

S⁇

Try it online!

I seem to have outgolfed myself.

S⁇  - Full program.

 ⁇  - Filter-Keep (operates on the automatically generated range).
S   - Check if the input and the current element are coprime.
\$\endgroup\$
1
\$\begingroup\$

Husk, 7 6 bytes

§foε⌋ḣ

-1 thanks @Leo!

Try it online!

Explanation

        -- implicit input N
§f   ḣ  -- filter the range [1..N] with
  oε⌋   --   is gcd(N,·) at most 1
\$\endgroup\$
1
\$\begingroup\$

Funky, 59 bytes

g=(a,b)=>b?g(b,a%b):(a>1)ort[#t]=i
f=n=>fort={}n>i++g(n,i)t

This defines the function f, which generates a list of all co-primes from 1 to n.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C 177 , 150 , 135 , 102 bytes

Not very golfy but...

p,i,t,x,y,N;f(n){
int A[9]={};
for(i=0,N=n;p<n;n/=p){
for(p=2+(n&1);n%p;)p+=2;
A[i++]=p;
}
for(y=0;y++<N;){
for(i=t=0;x=A[i++];)
t|=!(y%x);
if(!t)printf("%d ",y);
}
}

EDIT: one line 150

p,i,t,x,y,N;f(n){int A[9]={};for(i=0,N=n;p<n;n/=A[i++]=p)for(p=2+(n&1);n%p;)p+=2;for(y=0;y++<N;){for(i=t=0;x=A[i++];)t|=!(y%x);printf("\0 %d"+!t,y);}}

EDIT2:

f(n){int p,t,x,i=0,y=0,N=n,A[9]={};for(;p<n;n/=A[i++]=p)for(p=2;n%p;)p++;for(;y++<N;printf("\0 %d"+!t,y))for(i=t=0;x=A[i++];)t|=y%x<1;}

Stores array of primefactors of N,
Then prints numbers < N that don't divide those.

EDIT3:
Got rid of Array, recalulating primefactors instead

f(n){int p,t,i=0,N=n;for(;i++<N;printf("\0 %d"+!t,i))for(n=N,p=t=0;p<n;n/=p,t|=i%p<1)for(p=1;n%++p;);}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I'm pretty sure you can remove the newlines in C \$\endgroup\$ – Post Rock Garf Hunter Nov 14 '17 at 20:09
  • \$\begingroup\$ 95 bytes \$\endgroup\$ – ceilingcat Dec 21 '18 at 3:47
1
\$\begingroup\$

Pari/GP, 28 bytes

n->[x|x<-[0..n],gcd(x,n)==1]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

SNOBOL4 (CSNOBOL4), 149 bytes

	DEFINE('G(A,B)')
	N =INPUT
I	X =X + 1
	EQ(X,N)	:S(END)
	K =G(N,X)
	OUTPUT =EQ(K,1) X :(I)
G	T =REMDR(A,B)
	A =B
	B =T
	G =EQ(B) A	:F(G)S(RETURN)
END

Try it online!

Uses the Euclidean algorithm in the function G to calculate the GCD; prints values with newlines between them.

	DEFINE('G(A,B)')		;*let the interpreter know a function G is available
	N =INPUT			;*read input
I	X =X + 1			;*increment step
	EQ(X,N)	:S(END)			;*if X==N, end
	K =G(N,X)			;*K =GCD(N,X)
	OUTPUT =EQ(K,1) X :(I)		;*if K==1, output X. goto I
G	T =REMDR(A,B)			;*function body: euclidean algorithm
	A =B
	B =T
	G =EQ(B) A	:F(G)S(RETURN)	;*if B==0, G=A and return.
END
\$\endgroup\$
1
\$\begingroup\$

J, 16 Bytes

C=:I.@(1:=]+.i.)

C for coprime.

How it works:

C=:                | Define the verb C
             i.    | Integers between 0 and n-1 inclusive
          ]+.      | GCD with n. Gets applied to each element of i.n
       1:=         | Test whether each element of the array is 1. If it is, put 1, otherwise 0
   I.              | Return the indexes of the 1s. If there are none (i.e., on input 1) returns 0.

Parenthesis and @ are just so it gets executed in the right order.

Step by step example:

    (]+.i.) 10
10 1 2 1 2 5 2 1 2 1

    (1:=]+.i.) 10
0 1 0 1 0 0 0 1 0 1

    I.@(1:=]+.i.) 10
1 3 7 9

    C 10
1 3 7 9
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Firefox 30-57), 53 bytes

n=>[for(i of Array(n*n).keys())if(i*(i=i/n|0)%n==1)i]

Port of @Dennis's amazing Python answer. 60 bytes in ES6:

n=>[...Array(n*n)].map((_,i)=>i/n|0).filter((i,j)=>i*j%n==1)

Similar idea of looking for the multiplicative inverse, also 60 bytes in ES6:

n=>[...Array(n).keys()].filter((i,_,a)=>a.some(j=>i*j%n==1))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Wonder, 35 bytes

@(!>@=1len inx 'fac#0fac#1).'rng1#0

Usage:

(@(!>@=1len inx 'fac#0fac#1).'rng1#0)3

Basically filters over a range from 1 to the input with a predicate:

  • Find all factors of both the current mapped item and the input.
  • Find the intersection of both arrays.
  • Check if the result is of length 1. If the 2 numbers are coprime, then their factors' intersection set should only contain 1.
\$\endgroup\$
0
\$\begingroup\$

Julia 1.0, 33 bytes

(n)->[k for k=1:n if gcd(n,k)==1]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.