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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

K (ngn/k), ⁴³ 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.

Answer 4

K (ngn/k), ⁵⁹ 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

Answer 5

05AB1E, 16 14 13 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 Ï.

Answer 6

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.

Answer 7

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

Answer 8

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!

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

Vyxal, 118 bits^v2, 14.75 bytes

W£λ¥nġΠṅ;+)T⁺⌐Ḟ

Try it Online!

Answer 15

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!

Answer 16

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.