Smallest unused number sharing a factor

Question

This is a pretty run of the mill question. I will define a sequence and you golf some code to output a entry given a index.

• The first item in the sequence is 2.

• The nth item in the sequence is the smallest positive integer other than n and 1 sharing at least one factor with n (other than 1) that has not already appeared in the list.

Test cases

Here are the first 25 items in the sequence:

1  2
2  4
3  6
4  8
5  10
6  3
7  14
8  12
9  15
10 5
11 22
12 9
13 26
14 7
15 18
16 20
17 34
18 16
19 38
20 24
21 27
22 11
23 46
24 21
25 30

Related (offset by one) OEIS

Answer 1

Jelly, 19 bytes

R»2ɓ²Rg⁸>1Tḟ⁸ḟḢṭµ/Ṫ

Try it online!

Answer 2

Python 3, 118 117 bytes

^{-1 byte thanks to Cameron Aavik!}

import math
def f(n,i=3):
 if n<2:return 2
 while 1:
  if math.gcd(n,i)>1>(i in map(f,range(n)))<i!=n:return i
  i+=1

Try it online!

The code is pretty inefficient (it brute-forces a value that doesn't exist in the previous results, and calculates the previous results again on every new value), so it works properly but I wouldn't recommend running it on large numbers.

Answer 3

Haskell, 60 59 bytes

EDIT:

• -1 byte: @xnor pointed out all(/=x) was shorter than x`notElem`.

f takes an integer and returns an integer.

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:map f[1..n-1]]!!0

Try it online!

This is very exponential time, so TIO times out after 21, while my interpreted GHCi got up to 22 before I stopped it just now. The following 9 bytes longer version memorizing into a list easily goes up into the thousands:

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:take(n-1)l]!!0
l=f<$>[1..]

Try it online!

• f n uses a list comprehension to generate candidates x, taking the first passing one with !!0.
• gcd x n>1 checks that x and n have common factors.
• ||n<2 exempts n==1 from the factor requirement.
• all(/=x)$n:map f[1..n-1] checks that x is neither n nor a preceding sequence element.

Answer 4

No built-in for GCD in C#, so...

C# (.NET Core), 197 196 194 bytes

n=>{if(n<2)return 2;var p=new int[n-1];int i=0,a,b;for(;i<n-1;)p[i]=f(++i);for(i=2;;i++)if(n!=i){for(a=n,b=i;a*b>0;)if(a>b)a%=b;else b%=a;if(b!=1&a!=1&!System.Array.Exists(p,e=>e==i))return i;}}

Try it online!

Once again, refrain from using this code to calculate numbers in the sequence for n>30...

• -1 byte by changing the GCD while loop for a for loop.
• -2 bytes thanks to Kevin Cruijssen! Nice one!

Answer 5

APL (Dyalog), 46 bytes

{⍺←2⋄1=⍵:2⋄(~∨/⍺∊∇¨⍳⍵-1)∧(1<⍺∨⍵)∧⍺≠⍵:⍺⋄⍵∇⍨1+⍺}

Try it online!