11
\$\begingroup\$

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

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

Jelly, 19 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – notjagan Jun 20 '17 at 2:50
3
\$\begingroup\$

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.

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

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.
\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Ørjan Johansen Jun 20 '17 at 3:41
  • 1
    \$\begingroup\$ all(/=x)$ is 1 shorter there \$\endgroup\$ – xnor Jun 20 '17 at 5:34
2
\$\begingroup\$

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

APL (Dyalog), 46 bytes

{⍺←2⋄1=⍵:2⋄(~∨/⍺∊∇¨⍳⍵-1)∧(1<⍺∨⍵)∧⍺≠⍵:⍺⋄⍵∇⍨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.