Output the smallest increasing sequence where each term is coprime to preceding 3 terms

This sequence is defined as

• Starts with 1, 2, 3
• The next element of the sequence is the first number greater than the previous three that is co-prime with each of the previous 3 elements in the sequence.
• In other words, if the previous 3 elements are a, b, c, then the next is the first integer n>c such that gcd(a,n)=gcd(b,n)=gcd(c,n)=1.

This sequence on OEIS: OEIS

All elements below 100:

1,2,3,5,7,8,9,11,13,14,15,17,19,22,23,25,27,28,29,31,
33,34,35,37,39,41,43,44,45,47,49,52,53,55,57,58,59,61,
63,64,65,67,69,71,73,74,75,77,79,82,83,85,87,88,89,
91,93,94,95,97,99,


You can either:

• Take a number as input, then output the Nth element in the sequence. Either 0 or 1 based is fine.
• Take a number as input, then output the first N elements in this sequence.
• Take no input, output the sequence infinitely.

Inspired by a discussion in chat

• Note: it’s recommended to post challenges in the sandbox first, but it’s still quite good. Aug 17, 2023 at 18:38
• @TheEmptyStringPhotographer The sequel is in the sandbox but this one is so straightforward I felt it wasn't really necessary to go through the sandbox process Aug 17, 2023 at 18:42
• Does N count the initial 1,2,3 seed? Should f(1) be 1 or 5? I think you’ll get shorter solutions if f(N) returned the first N+3 elements or the N+3rd. Or if you only care about N>3.
– doug
Aug 18, 2023 at 4:59
• @doug You can set the seed to 1,1,1 and get the same behavior you suggest without giving different output than the example Aug 18, 2023 at 5:27
• Okay, I’ll take that to mean you’re not fussy about the low values of N. Being pedantic, the example doesn’t indicate what invocation should generate that output.
– doug
Aug 18, 2023 at 5:32

Python 3, 78 77 bytes

-1 byte thanks to @Bubbler!

Prints the 0-indexed n-th term of the sequence. Who needs gcd anyway?

lambda n:sum((v+(t+b''+v+t)*n)[:n])+1
v=b''*3
t=(b''+v[1:]+v[6:])*3


Try it online!

If we look at the differences between each term in the sequence, they become periodic after the 7th term, repeating every 125th term. The periodic string is:

22112231221122112222112231221122112222112231221122112222112241142112211221122312211221122221122312211221122221122312211221122


The code simply attempts to construct this periodic string, plus the non-periodic bit at the beginning. It helps that the string naturally contains a lot of repetition, making compression relatively short.

By the way, the unprintables in ASCII are 41142, 1122, and 3 in order of appearance.

• t=(b'\x03'+v[1:]+v[6:])*3 is one byte shorter. (literal ascii 3 is not allowed in comments) Aug 18, 2023 at 5:10

Python, 81 79 bytes

from math import*
*a,d=1,
while 1:a+=[d][:gcd(prod(a[-3:]),d)<2!=print(d)];d+=1


Attempt This Online! Prints the sequence indefinitely.

• That's a nifty trick for conditionally appending and printing a value!
– xnor
Aug 18, 2023 at 0:48

K (ngn/k), 43 41 bytes

{{{y+/1<y(|!\)/x,y}[x*y*z]/z}$x-3].1+!3}  Try it online! -2 thanks to ovs. The original version had (|!\|!\)/ for the GCD (because (|!\) alternates between 0,gcd and gcd,0 in the end). ovs suggested y(|!\)/ which iterates exactly y times, which is valid because: • at each iteration, x,y becomes y%x,x, which strictly reduces the minimum of the two until one becomes 0 (except at the first iteration, because x > y at that point); the minimum is reduced at least y-1 times • the above leaves the possibility that the minimum is reduced by 1 y-1 times in a row, but it is impossible: after one reduction, the pair becomes y-1,y, and after one more, 1,y-1, which is a reduction of more than 1 if y >= 4. • Nifty observation – doug Aug 18, 2023 at 6:46 • Instead of doing the double-step for converging, I think y(|!\)/ should be fine – ovs Aug 18, 2023 at 6:51 • same length without recurrence, and technically -2 by printing indefinitely, but that one just feels wrong. – ovs Aug 18, 2023 at 7:06 K (ngn/k), 59 52 bytes {{{~1=(*|(*:)(|!\)/)y,x}[x*y*z](1+)/z+1}$$x-3].1+!3}  Try it online! -7 : peeking at @ovs’s solution suggested obvious golf 05AB1E, 161413 12 bytes λ∞+Dλ3.£P¿Ïн  -1 byte thanks to @ovs. Outputs the infinite sequence. Try it online. Explanation: λ # Start a recursive environment, # to output the infinite sequence # (which is output implicitly at the end) # Implicitly starting with a(0)=1 # Where every following a(n) is calculated as: # (implicitly push a(n-1)) ∞ # Push an infinite positive list: [1,2,3,...] + # Add the a(n-1) to each: [a(n-1)+1,a(n-1)+2,a(n-1)+3,...] D # Duplicate this infinite list λ # Push a list of all items thus far: [a(0),a(1),...,a(n-1)] 3.£ # Pop and only leave (up to†) the last three items: [a(n-3),a(n-2),a(n-1)] P # Take the product of this triplet: a(n-3)*a(n-2)*a(n-1) ¿ # Check the gcd (Greatest Common Divisor) of this product with each value v # in the infinite (duplicated) list: gcd(v,a(n-3)*a(n-2)*a(n-1)) Ï # †† Pop both lists, and only leave the values at the truthy††† positions н # Pop and push the first remaining item of this infinite list  Footnotes: • †: In the first two iterations, λ won't contain three items yet, so will be [1] or [1,"2"] respectively. This won't affect the output though, since it'll calculate $$\2\$$ based on just $$\[a(0)=1]\$$ and calculate $$\3\$$ based on $$\[a(0)=1,a(1)=2]\$$. • ††: The outputs are strings (except for the first implicit item) because of the Ï builtin. Not sure why it does that tbh. (You could add a ï to the footer if you prefer actual integer outputs: Try it online.) • †††: Only 1 is truthy in 05AB1E, so only the items at which gcd(v,a(n-3)*a(n-2)*a(n-1))==1 will be kept with Ï. • If you take the product of the last three items before computing the gcd, you can get rid of the δ – ovs Aug 18, 2023 at 9:49 J, 40 bytes {1&(]],_3&{.>:@]^:(3<1#.+./)^:_{:)&1 2 3  Try it online! 0 indexed, returns the selected element, though it generates all up to that element under the hood. -10 from ovs/emanresu A -5 from Arnauld -3 from dingledooper JavaScript (V8), 64 bytes for(A=B=C=D=j=1;;)A*B*C%j|D%j--||(j||print((A=B,B=C,C=D)),j=++D)  Try it online! • 79 with a trick from ovs's python answer Aug 17, 2023 at 19:21 • 74 Aug 17, 2023 at 23:29 • 64 bytes Aug 18, 2023 at 6:45 R, 83 71 bytes a=3:1 repeat if(all(prod(a[1:3])%%2:a|(T=T+1)%%2:a))show((a=c(T,a))[4])  Attempt This Online! Pyth, 18 bytes #eaYf!-iT>3Y1he|Y0  Try it online! Outputs terms of the sequence indefinitely. Explanation  # implicitly assign Y = [] # # repeat until error |Y0 # short circuiting Y or 0 e # last element of h # plus 1 f # counting up from this number, find the first element which satisfies lambda T >3Y # last three elements of Y iT # map to gcd with T - 1 # remove 1 from this list ! # True if list is empty aY # append to Y e # print the last element of Y  Julia, 84 79 bytes ~n=(i=A=1;while length(A)<n;if max(gcd.(last(A,3),i+=1)...)<2;A=[A;i]end;end;A)  Attempt This Online! Given $$\n\$$, returns $$\[a_1, a_2, \ldots, a_n]\$$. The function last(A,3) works gracefully for vectors with less than 3 values. Substituting A=[A;i] for push!(A,i) saves 3 bytes. Incrementing i inside a function call saves 2 bytes. • -4 bytes thanks to MarcMush: replace i=1;A=[1] with i=A=1 • -1 byte thanks to MarcMush: remove unecessary semicolon • -5 bytes with A=1 and removing a ; ATO Aug 20, 2023 at 19:58 Charcoal, 36 bytes ＦＮ«≔⊕↨υ⁰θＷ¬⬤…²⊕θ∨﹪θλ﹪Π…⮌υ³λ≦⊕θ⊞υθ»Ｉυ  Try it online! Link is to verbose version of code. Outputs the first n numbers. Explanation: ＦＮ«  Repeat n times. ≔⊕↨υ⁰θ  Start with 1 more than the previous number, or 1 if there were no previous numbers. Ｗ¬⬤…²⊕θ∨﹪θλ﹪Π…⮌υ³λ  While a common factor between the candidate number and the product of the last three numbers can be found... ≦⊕θ  ... increment the candidate number. ⊞υθ  Add the next element to the list. »Ｉυ  Output the found elements. Arturo, 69 bytes a:@0..3i:5whileø[drop'a 1print a\0while->1<>gcd@[i∏a]->i:i+1'a++i]  Try it! (Modified to print the first n elements so the playground can actually show the output.) Prints the sequence indefinitely.  a:@0..3 ; assign [0 1 2 3] to a i:5 ; assign 5 to i whileø[ ; start infinite loop drop'a 1 ; delete the first element in a print a\0 ; print the (new) first element in a while->1<> ; while 1 is not equal to... gcd@[i∏a]-> ; ...the gcd of i and the product of a i:i+1 ; increment i (without mutation) 'a++i ; append i to a ] ; end loop  J, 34 bytes (1 2 3,3((]+3<1#.+.)^:_{:)$)^:_~  Attempt This Online! Returns first n terms. Very inefficient because it computes the next term for every 3-window at every iteration. (1 2 3,3((]+3<1#.+.)^:_{:)$$)^:_~
(                            )^:_~  repeat (...) on n until it converges,
also giving n as the fixed left arg
(after 1 iteration, the value is always a
length-n array starting with 1 2 3)
$1 2 3,3( )\] compute the next term for every 3-window, prepend 1 2 3 and make it length n (]+3<1#.+.)^:_{: compute the next term for a window: ( )^:_{: iterate from the 3rd number until convergence: +. gcd with the 3 preceding terms ]+3<1#. if the sum is >3, increment  J, 34 bytes 0{(]}.,](]+3<1#.+.)^:_{:)^:[&1 2 3  Attempt This Online! Returns the nth term, 0-indexed. Maintains the next 3 terms in a loop. 0{(]}.,](]+3<1#.+.)^:_{:)^:[&1 2 3 0{( )^:[&1 2 3 starting from 1 2 3, iterate n times and extract the first number ](]+3<1#.+.)^:_{: compute the next term }., prepend previous two terms ] ignore n in this function  Vyxal, 118 bitsv2, 14.75 bytes W£λ¥nġΠṅ;+)T⁺⌐Ḟ  Try it Online! Haskell, 73 bytes h n|n<4=n h n=head[x|x<-[h$n-1..],all(\d->gcd d x==1)[h$n-1,h$n-2,h$n-3]]  Attempt This Online! Raku, 51 bytes 1,2,3,{first 1==(*Xgcd$^x,$^y,$^z).all,($z..*)}...*  Try it online! This is an expression for the infinite sequence of numbers. • 1, 2, 3, { ... } ... * is a lazy sequence starting with 1, 2, and 3, and with successive elements generated by the brace-delimited anonymous function. The function mentions placeholder variables $^x, $^y, and $^z, so it takes the previous three elements of the sequence as arguments.
• first 1 == (* Xgcd $^x,$^y, $^z).all, ($z .. *) finds the first number in \$z .. *--that is, the numbers starting from the last number in the sequence going up to infinity--such that the gcd of that number with each of the last three elements in the sequence is 1.