55
\$\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\$
5
  • \$\begingroup\$ Do seperate strings (e.g. 1\n3\n) count as valid output? \$\endgroup\$
    – devRicher
    Dec 27, 2016 at 0:37
  • \$\begingroup\$ @devRicher that works, sure. \$\endgroup\$
    – Riker
    Dec 27, 2016 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, 2016 at 20:28
  • 1
    \$\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, 2016 at 2:12
  • 3
    \$\begingroup\$ Fun fact: these are called totatives. \$\endgroup\$
    – Wojowu
    Dec 29, 2016 at 15:20

50 Answers 50

67
+100
\$\begingroup\$

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.

\$\endgroup\$
2
  • 32
    \$\begingroup\$ "GCD? Where we're going, we don't need GCD." \$\endgroup\$
    – Riker
    Dec 26, 2016 at 19:31
  • 3
    \$\begingroup\$ Woah. That's all I wanted to write, but apparently I needed 15 characters. Still, woah. Great job. \$\endgroup\$ Dec 27, 2016 at 8:30
24
\$\begingroup\$

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.
\$\endgroup\$
2
  • 35
    \$\begingroup\$ Coding in this language takes some gRỊT \$\endgroup\$ Dec 26, 2016 at 18:33
  • 3
    \$\begingroup\$ I managed to (ab)use the "Minimum link value" quick (ÐṂ) in order to get 3 bytes. \$\endgroup\$
    – Mr. Xcoder
    Sep 28, 2017 at 19:00
19
\$\begingroup\$

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.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ You outgolfed Dennis in his own language after 9 months! \$\endgroup\$
    – Adám
    Sep 28, 2017 at 19:21
  • \$\begingroup\$ @Adám I am not sure whether ÐṂ existed back then, anyway I am quite satisfied with this one. \$\endgroup\$
    – Mr. Xcoder
    Sep 28, 2017 at 19:22
  • 5
    \$\begingroup\$ For the record, DṂ did exist, but it only worked for monads. The commit implemented Þ, ÐṂ, ÐṀ for dyads is dated May 9, 2017. \$\endgroup\$
    – Dennis
    Sep 28, 2017 at 21:31
  • 2
    \$\begingroup\$ @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! \$\endgroup\$
    – Mr. Xcoder
    Sep 29, 2017 at 4:21
14
\$\begingroup\$

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.

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

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!

\$\endgroup\$
1
  • \$\begingroup\$ Good job (almost) beating Dennis. (few minutes late though). \$\endgroup\$
    – Adalynn
    Dec 31, 2016 at 1:15
10
\$\begingroup\$

Python, 93 82 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.

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

Actually, 8 bytes

;╗R`╜┤`░

Try it online!

Explanation:

;╗R`╜┤`░
  R`  `░  elements of range(1, n+1) where
;╗  ╜     n and the element
     ┤    are coprime
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I believe you can just do range(1, n) if that saves any bytes. \$\endgroup\$ Dec 26, 2016 at 19:26
  • 1
    \$\begingroup\$ @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). \$\endgroup\$
    – user45941
    Dec 26, 2016 at 19:27
  • \$\begingroup\$ 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 \$\endgroup\$ Dec 26, 2016 at 19:28
6
\$\begingroup\$

MATL, 7 bytes

:GZd1=f

Try it online!

\$\endgroup\$
6
\$\begingroup\$

MATLAB/Octave, 22 bytes

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

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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) }]`);

\$\endgroup\$
4
  • \$\begingroup\$ Can't you swap a== with a<2? \$\endgroup\$
    – Riker
    Dec 26, 2016 at 18:14
  • \$\begingroup\$ @EasterlyIrk Not sure, a might be 0 at some point. I'll have to check \$\endgroup\$ Dec 26, 2016 at 18:25
  • \$\begingroup\$ 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)) \$\endgroup\$
    – user81655
    Dec 27, 2016 at 1:22
  • \$\begingroup\$ @user81655 That's great, thanks! :-) \$\endgroup\$ Dec 27, 2016 at 1:24
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ Why is this noncompeting? \$\endgroup\$
    – Adalynn
    Dec 26, 2016 at 19:16
  • \$\begingroup\$ @ZacharyT mainly, keep wasn't working nicely. \$\endgroup\$ Dec 26, 2016 at 19:17
5
\$\begingroup\$

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.
},
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 26 bytes

Pick[r=Range@#,r~GCD~#,1]&
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Dec 27, 2016 at 8:27
4
\$\begingroup\$

Perl 6, 20 bytes

{grep 2>* gcd$_,^$_}
\$\endgroup\$
4
\$\begingroup\$

Julia 0.5, 23 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ julia 1.0+ version: !n=findall(gcd.(1:n,n).<2) - no find and findall needs boolean. \$\endgroup\$ Jul 3, 2022 at 14:51
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
14
  • 3
    \$\begingroup\$ I love the way APL code looks like the face you make when you read it. \$\endgroup\$
    – DJMcMayhem
    Dec 26, 2016 at 18:43
  • \$\begingroup\$ Yep, and it demolishes almost every not code-golf-oriented language. :). \$\endgroup\$
    – Adalynn
    Dec 26, 2016 at 18:47
  • \$\begingroup\$ Why only "might" work? \$\endgroup\$
    – Riker
    Dec 26, 2016 at 19:10
  • \$\begingroup\$ I'm just going to assume it works. \$\endgroup\$
    – Adalynn
    Dec 26, 2016 at 19:14
  • \$\begingroup\$ @ZacharyT why can't you test it? When I paste it into try-apl.org, it errors with invalid token. \$\endgroup\$
    – Riker
    Dec 26, 2016 at 19:16
4
\$\begingroup\$

Japt -f, 9 8 5 2 bytes

jN

Try it

  • 2 bytes saved thanks to ETH pointing out a brainfart, which led to another byte saved.
\$\endgroup\$
2
  • \$\begingroup\$ You could do o f_jU \$\endgroup\$ Oct 12, 2017 at 17:39
  • \$\begingroup\$ 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. \$\endgroup\$
    – Shaggy
    Oct 13, 2017 at 10:23
3
\$\begingroup\$

Mathematica, 33 bytes

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

Contains U+F4A1

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

Haskell, 27 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 3 bytes

Lʒ¿

Try it online!

Has new features.

\$\endgroup\$
3
\$\begingroup\$

memes, 11 bytes

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.

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

Ruby, 3634

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

Admittedly, this isn`t a very inspired answer.

2 bytes saved thanks to Conor O'Brien.

\$\endgroup\$
1
  • \$\begingroup\$ You can shave off two bytes by removing parentheses around (n) \$\endgroup\$ Dec 26, 2016 at 18:54
2
\$\begingroup\$

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]
\$\endgroup\$
1
  • \$\begingroup\$ I don't think you can golf this more. Importing gcd directly or math as m both add bytes. \$\endgroup\$
    – Riker
    Dec 26, 2016 at 19:05
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ -2bytes: x->(gcd(n,x)<2) could be x->gcd(n,x)<2. \$\endgroup\$ Jul 3, 2022 at 14:55
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ How does this work? \$\endgroup\$
    – Riker
    Dec 28, 2016 at 18:12
  • 1
    \$\begingroup\$ @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 <-). \$\endgroup\$
    – Charles
    Dec 28, 2016 at 18:23
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ 50 bytes. It outputs in reverse order (allowed by the author), and clutters stdin and stderr \$\endgroup\$
    – c--
    Jul 5, 2023 at 5:05
2
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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