Code Golf Asked by Wheat Wizard on November 28, 2020
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)$
$a(5)$
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.
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
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.
After asking this question I submitted this sequence to the OEIS and after a few days it was added.
It pains me to have to invoke a function without a shortcut - can't remember the last time I had to, if ever - but it worked out shorter than any other method I could come up with.
@W{WjY «ZøW ©ÓWaY}a}g
Answered by Shaggy on November 28, 2020
Answered by LegionMammal978 on November 28, 2020
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)
Answered by Kevin Cruijssen on November 28, 2020
ò2 rÈc_aY >1«XøZ «Yk øZk}a+2}[] o
_{† 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.}
Answered by Justin Mariner on November 28, 2020
/oi
1@/2-&whq&[]w].q-H.t*n$K.qG?*h$KW.!kq
/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
Answered by Nitrodon on November 28, 2020
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
Answered by Brian J on November 28, 2020
(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)
Answered by J42161217 on November 28, 2020
f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0
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
Answered by user45941 on November 28, 2020
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP