19
\$\begingroup\$

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

OEIS A290151

\$\endgroup\$
  • \$\begingroup\$ How many values did you compute? (Talking about the bonus) \$\endgroup\$ – Socratic Phoenix Jul 21 '17 at 15:05
  • \$\begingroup\$ @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. \$\endgroup\$ – Sriotchilism O'Zaic Jul 21 '17 at 15:06
  • 1
    \$\begingroup\$ As 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 \$\endgroup\$ – Socratic Phoenix Jul 21 '17 at 15:06
  • \$\begingroup\$ 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. \$\endgroup\$ – nimi Jul 21 '17 at 16:52
  • \$\begingroup\$ @nimi I do not know of an upper bound. \$\endgroup\$ – Sriotchilism O'Zaic Jul 21 '17 at 16:54
8
\$\begingroup\$

Haskell, 61 bytes

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0

Try it online!

I'm fairly new to Haskell, so any golfing tips are appeciated.

Thanks to Wheat Wizard for 2 bytes and nimi for 4 bytes

Explanation:

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0
f n=                                                          -- define a function f :: Int -> Int
    [i|i<-[2..],                                              -- out of positive integers greater than two
                gcd i n<2,                                    -- gcd of i and n is 1
                          all((/=i).f)[2..n-1],               -- i isn't already in the sequence
                                               abs(n-i)>1]    -- and |n-i| > 1
                                                          !!0 -- take the first element
\$\endgroup\$
2
\$\begingroup\$

Alice, 42 bytes

/oi
\1@/2-&whq&[]w].q-H.t*n$K.qG?*h$KW.!kq

Try it online!

Explanation

/oi
\1@/.........

This is a standard template for programs that take a number as input, and output a number, modified to place a 1 on the stack below the input number.

The main part of the program places each number k in slot a(k) on the tape. The inner loop computes a(k), and the outer loop iterates over k until a(n) is computed.

1       push 1
i       take input
2-&w    repeat n-1 times (push return address n-2 times)
h       increment current value of k
q&[     return tape to position 0
]       move right to position 1
w       push return address to start inner loop
]       move to next tape position
.q-     subtract tape position from k
H       absolute value
.t*     multiply by this amount minus 1
n$K     if zero (i.e., |k-x| = 0 or 1), return to start of inner loop
.qG     GCD(k, x)
?       current value of tape at position: -1 if x is available, or something positive otherwise
*       multiply
h$K     if not -1, return to start of inner loop
W       pop return address without jumping (end inner loop)
.!      store k at position a(k)
k       end outer loop
q       get tape position, which is a(n)
o       output
@       terminate
\$\endgroup\$
1
\$\begingroup\$

VB.NET (.NET 4.5), 222 bytes

Function A(n)
Dim s=New List(Of Long)
For i=2To n
Dim c=2
While Math.Abs(i-c)<2Or g(c,i)>1Or s.Contains(c)
c+=1
End While
s.Add(c)
Next
Return s.Last
End Function
Function g(a, b)
Return If(b=0,a,g(b,a Mod b))
End Function

I had to roll your own GCD. I also couldn't figure out how to get it to not be an entire function.

GCD is always >= 1, so only need to ignore 1

Took out short-circuiting in the golf because it's shorter

Un-golfed

Function Answer(n As Integer) As Integer
    Dim seqeunce As New List(Of Integer)
    For i As Integer = 2 To n
        Dim counter As Integer = 2
        ' took out short-circuiting in the golf because it's shorter
        ' GCD is always >= 1, so only need to ignore 1
        While Math.Abs(i - counter) < 2 OrElse GCD(counter, i) > 1 OrElse seqeunce.Contains(counter)
            counter += 1
        End While
        seqeunce.Add(counter)
    Next
    Return seqeunce.Last
End Function

' roll your own GCD
Function GCD(a, b)
    Return If(b = 0, a, GCD(b, a Mod b))
End Function
\$\endgroup\$
  • \$\begingroup\$ It blows my mind that .NET doesn't have a GCD built in outside of the BigInteger class. \$\endgroup\$ – Mego Jul 22 '17 at 0:56
1
\$\begingroup\$

Mathematica, 111 bytes

(s={};Table[m=2;While[m<3#,If[CoprimeQ[i,m]&&FreeQ[s,m]&&Abs[i-m]>1,s~AppendTo~m;m=3#];m++],{i,2,#}];s[[#-1]])&


Try it online! 2..23 (range mode)

Try it online! or 150 (distinct values)

\$\endgroup\$
1
\$\begingroup\$

Japt, 33 bytes (non-competing?)

ò2 rÈc_aY >1«XøZ «Yk øZk}a+2}[] o

Try it online!

I fixed a bug in the Japt Interpreter while working on this solution. This meta post from a year ago deems this answer non-competing, but this newer meta post is pushing for more freedom in this. Regardless, I spent too much time on this to scrap it.

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

05AB1E, 26 bytes

2IŸεDU°2Ÿ¯KʒX¿}ʒXα1›}θDˆ}θ

Try it online or output the first \$n\$ terms as list. (NOTE: ° is obviously extremely slow, so replaced with T* in the TIO links (\$10*n\$ instead of \$10^n\$).)

Explanation:

2IŸ               # Create a list in the range [2, input]
   ε              # Map each value `y` to:
    DU            #  Store a copy of `y` in variable `X`
    °2Ÿ           #  Create a list in the range [10**`y`,2]
       ¯K         #  Remove all values already in the global_array
       ʒX¿}       #  Only keep values with a greatest common divider of 1 with `X`
       ʒXα1›}     #  Only keep values with an absolute difference larger than 1 with `X`
             θ    #  After these filters: keep the last (the smallest) element
              Dˆ  #  And add a copy of it to the global_array
   }θ             # After the map: only leave the last value
                  # (and output the result implicitly)
\$\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.