# Smallest unused number sharing a factor

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

# Jelly, 19 bytes

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


Try it online!

• I was so happy that I had you out-golfed on the Lyndon word factorization question but then you hit me with this... (in all seriousness though this is a great answer) – notjagan Jun 20 '17 at 2:50

# 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.

• Small tip: You can save a newline by making it def f(n,i=3): and removing the i=3 line – Cameron Aavik Jun 20 '17 at 6:09
• – Jonathan Frech Sep 25 '17 at 3:29

EDIT:

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

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.
• @WheatWizard Hm, probably no difference in that case. Just used to doing it by default. It's one of the few alphanumerical functions that has a fixity defined to fit well that way. – Ørjan Johansen Jun 20 '17 at 3:41
• all(/=x)\$ is 1 shorter there – xnor Jun 20 '17 at 5:34

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!
• a>0&b>0 can be golfed to a*b>0 – Kevin Cruijssen Sep 25 '17 at 7:21

# APL (Dyalog), 46 bytes

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


Try it online!