19
2
Let us define a sequence. We will say that \$a(n)\$ is the smallest number, \$x\$, that has the following properties:
\$x\$ and \$n\$ are co-prime (they share no factor)
\$x\$ does not appear earlier in the sequence
\$|n - x| > 1\$
Unlike most sequences the domain and range of our sequence are the integers greater than 1.
Let us calculate the first couple of terms.
\$a(2)\$, must be at least 4, but 4 and 2 share a factor of 2 so \$a(2)\$ must be 5.
\$a(3)\$, must be at least 5 but 5 is taken by \$a(2)\$, so it is at least 6, but 6 shares a factor with 3 so it must be at least 7, 7 fulfills all three requirements thus \$a(3)=7\$.
\$a(4)\$
- 2 Shares a factor
- 3 Too close
- 4 Too close
- 5 Too close
- 6 Shares a factor
- 7 Taken by a(3)
- 8 Shares a factor
- 9 is good
\$a(5)\$
- 2 is good
Task
In this challenge you are to write a program that takes a number greater than 1 and returns \$a(n)\$.
This is a code-golf question so answers will be scored in bytes, with fewer bytes being better.
Test Cases
Here are the first couple terms of the sequence (They are of course 2 indexed):
5,7,9,2,11,3,13,4,17,6,19,8,23,22,21,10,25,12,27,16,15,14
Bonus Fun fact
As proven by Robert Israel on Math.se (link) this sequence is its own inverse, that means that \$a(a(n)) = n\$ for all n.
OEIS
After asking this question I submitted this sequence to the OEIS and after a few days it was added.
How many values did you compute? (Talking about the bonus) – Socratic Phoenix – 2017-07-21T15:05:27.843
@SocraticPhoenix I've been doing it by hand so only the ones shown in the test cases. I'm currently debugging a program to check larger values. – Post Rock Garf Hunter – 2017-07-21T15:06:18.560
1As am I... it's not working right now though, my indexing is off (edit:) aand now it's working... the first 1000 are safe xD – Socratic Phoenix – 2017-07-21T15:06:46.420
Do you know an upper bound for a(x)? E.g. a(x) < u*x for some u. Btw the first few million values are safe. – nimi – 2017-07-21T16:52:51.837
@nimi I do not know of an upper bound. – Post Rock Garf Hunter – 2017-07-21T16:54:40.753
a = {1, 5}; Do[k = 2; While[Nand[CoprimeQ[n, k], ! MemberQ[a, k], Abs[n - k] >= 2], k++]; AppendTo[a, k], {n, 3, 96}]; Rest@ a (* Michael De Vlieger, Jul 21 2017 *)
- Wow, they're fast, you'd think it'd take longer to post AND implement a sequence for them. – Magic Octopus Urn – 2017-07-24T19:50:23.497