15
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Note: it’s recommended to post challenges in the sandbox first, but it’s still quite good. \$\endgroup\$ Aug 17, 2023 at 18:38
  • 4
    \$\begingroup\$ @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 \$\endgroup\$
    – mousetail
    Aug 17, 2023 at 18:42
  • \$\begingroup\$ 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. \$\endgroup\$
    – doug
    Aug 18, 2023 at 4:59
  • 1
    \$\begingroup\$ @doug You can set the seed to 1,1,1 and get the same behavior you suggest without giving different output than the example \$\endgroup\$
    – mousetail
    Aug 18, 2023 at 5:27
  • \$\begingroup\$ 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. \$\endgroup\$
    – doug
    Aug 18, 2023 at 5:32

16 Answers 16

12
\$\begingroup\$

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.

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

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.

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

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.
\$\endgroup\$
3
  • \$\begingroup\$ Nifty observation \$\endgroup\$
    – doug
    Aug 18, 2023 at 6:46
  • 2
    \$\begingroup\$ Instead of doing the double-step for converging, I think y(|!\)/ should be fine \$\endgroup\$
    – ovs
    Aug 18, 2023 at 6:51
  • \$\begingroup\$ same length without recurrence, and technically -2 by printing indefinitely, but that one just feels wrong. \$\endgroup\$
    – ovs
    Aug 18, 2023 at 7:06
5
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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 Ï.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ If you take the product of the last three items before computing the gcd, you can get rid of the δ \$\endgroup\$
    – ovs
    Aug 18, 2023 at 9:49
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ 79 with a trick from ovs's python answer \$\endgroup\$
    – emanresu A
    Aug 17, 2023 at 19:21
  • \$\begingroup\$ 74 \$\endgroup\$
    – Arnauld
    Aug 17, 2023 at 23:29
  • \$\begingroup\$ 64 bytes \$\endgroup\$ Aug 18, 2023 at 6:45
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -5 bytes with A=1 and removing a ; ATO \$\endgroup\$
    – MarcMush
    Aug 20, 2023 at 19:58
2
\$\begingroup\$

Charcoal, 36 bytes

FN«≔⊕↨υ⁰θW¬⬤…²⊕θ∨﹪θλ﹪Π…⮌υ³λ≦⊕θ⊞υθ»Iυ

Try it online! Link is to verbose version of code. Outputs the first n numbers. Explanation:

FN«

Repeat n times.

≔⊕↨υ⁰θ

Start with 1 more than the previous number, or 1 if there were no previous numbers.

W¬⬤…²⊕θ∨﹪θλ﹪Π…⮌υ³λ

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.

»Iυ

Output the found elements.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 118 bitsv2, 14.75 bytes

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

Try it Online!

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

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!

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

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.