The "Fly straight, dammit" sequence

Question

Background

"Fly straight, dammit" (OEIS A133058) is a sequence of integers, which has these rules:

• \$a_0 = a_1 = 1\$

• \$a_n = a_{n-1}+n+1\$ if \$gcd(a_{n-1}, n) = 1\$

• Otherwise, \$a_n = \frac{a_{n-1}}{gcd(a_{n-1}, n)}\$

In pseudocode:

a[0] = a[1] = 1
if gcd(a[n-1], n) == 1 then
    a[n] = a[n-1] + n + 1
else
    a[n] = a[n-1] / gcd(a[n-1], n)

(GCD stands for "Greatest Common Divisor". For example, GCD(8, 12) = 4.)

The graph for this function looks like this:

After n=638, it goes into four straight lines (\$y=1\$ and \$y=2\$ are indistinguishable in this picture, but they are separate lines).

'Whenever I look at this sequence I am reminded of the great "Fly straight, dammit" scene in the movie "Avatar".' - N. J. A. Sloane

Your task

You have to:

• accept an input, n, from the user (it will be a positive integer)
• calculate \$a_n\$ and output (this is sequence so any output is fine)

This is code-golf so shortest answer in bytes wins!

Answer 1

05AB1E, 12 bytes

1‚λDN¿DiNOë÷

Outputs the infinite sequence.

Try it online.

Explanation:

1           # Push 1
 ‚          # Pair the top two values together. Since there is only one value on the
            # stack and there is no input, it implicitly uses the last value that was
            # on the stack, resulting in [1,1]

  λ         # Start a recursive environment,
            # to output the infinite sequence
            # (which is output implicitly afterwards)
1‚          # Start with a(0)=a(1)=1
            # Where every following a(n) is calculated as:
            #  (implicitly push a(n-1) to the stack)
   D        #  Duplicate a(n-1)
    N       #  Push n
     ¿      #  Pop one a(n-1) and n, and calculate their GCD
      D     #  Duplicate this gcd(a(n-1),n)
       i    #  If it's 1:
        N   #   Push n again
         O  #   Sum the three values on the stack: a(n-1)+gcd(a(n-1),n)+n,
            #   where gcd(a(n-1) is always 1 in this case
       ë    #  Else:
        ÷   #   Integer-divide a(n-1) by gcd(a(n-1),n)

Answer 2

C (GCC), 65 bytes

t,r;h(a,b){r=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/r;}

Attempt This Online!

This is based on py3programmer's answer; I'm posting this mostly for their benefit since they say they didn't fully understand the golfing suggestions I gave.

Here's their current version:

h(a,b){if(b){return h(b,a%b);}else{return a;}}c(n){if(n<2){return 1;}if(h(c(n-1),n)<2){return c(n-1)+n+1;}else{return c(n-1)/h(c(n-1),n);}}

The first thing I did was convert the if/else statements into ?/: conditional expressions. You can read x?y:z as "if x then y, otherwise z".

h(a,b){return b?h(b,a%b):a;}c(n){return n<2?1:h(c(n-1),n)<2?c(n-1)+n+1:c(n-1)/h(c(n-1),n);}

GCC has a non-standard extension to C that lets you use x?:z to mean "if x, then x, otherwise z":

h(a,b){return b?h(b,a%b):a;}c(n){return n<2?:h(c(n-1),n)<2?c(n-1)+n+1:c(n-1)/h(c(n-1),n);}

Another quirk of GCC, when used in -O0 optimisation mode (which is the default), is that the CPU register used for the return value of a function is the same as the one used for its first parameter. As a result, we can replace return statements with assignments to the first parameter for both functions:

h(a,b){a=b?h(b,a%b):a;}c(n){n=n<2?:h(c(n-1),n)<2?c(n-1)+n+1:c(n-1)/h(c(n-1),n);}

Then I noticed that the value c(n-1) is reused quite a lot, so I extracted it into a temporary variable:

t;h(a,b){a=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t+n+1:t/h(t,n);}

I declared it as a global variable, because that doesn't require a type in the declaration, but it makes no difference in functionality.

Then I made use of this tip which states that x+y+1 can be shortened to x-~y (because ~y is equivalent to -y - 1)

t;h(a,b){a=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/h(t,n);}

I also noticed that h(t,n) is reused, so I modified h to store its result in a global variable r as well as providing it as a return value. We can then use r instead of calling h again:

t,r;h(a,b){r=a=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/r;}

As pointed out by Kevin Cruijssen in a comment, the a= assignment turns out to be unnecessary. Why, exactly, is beyond me, but it seems GCC just stores the value in the return register by happenstance.

t,r;h(a,b){r=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/r;}

Answer 3

Prolog (SWI), 68 56 bytes

-12 bytes thanks to @Steffan

N+X:-N>1,N-1+B,C=gcd(B,N),(C<2,X is B+N+1;X is B/C);X=1.

Try it online!

Answer 4

JavaScript (ES6),  55  53 bytes

f=(n,a=n,b=q=n>1?f(n-1):-1)=>b?f(n,b,a%b):q/a-~n*!~-a

Try it online!

Commented

f = (                // f is a recursive function taking:
  n,                 //   n = input
  a = n,             //   a = 1st argument of the GCD, initialized to n
  b = q =            //   b = 2nd argument of the GCD, initialized to ...
    n > 1 ? f(n - 1) //       q = f(n - 1) if n > 1
          : -1       //       q = -1 if n ≤ 1 (which will force the GCD
) =>                 //           to be evaluated as -1 as well)
  b ?                // if b is not equal to 0:
    f(n, b, a % b)   //   keep computing the GCD with a recursive call
  :                  // else:
                     //   the GCD is now loaded in a
    q / a -          //   return q / a
    ~n * !~-a        //   add n + 1 if a = 1
                     //   (if q was set to -1, we get -1/-1-~n*0 = 1)

Answer 5

Wolfram Language (Mathematica), 47 bytes

If[#<2,1,If[(s=GCD[#,d=#0[#-1]])<2,d+#+1,d/s]]&

Try it online!

-4 bytes from alephalpha

Answer 6

C (gcc), 234 210 143 139 bytes

Thanks to pxeger for removing a few bytes. Check out his improved answer.

h(a,b){if(b){return h(b,a%b);}else{return a;}}c(n){if(n<2){return 1;}if(h(c(n-1),n)<2){return c(n-1)+n+1;}else{return c(n-1)/h(c(n-1),n);}}

Answer 7

Python, 68 bytes

import math
f=lambda n:n<2or(a:=f(n-1))//(q:=math.gcd(a,n))-~n*(q<2)

Attempt This Online!

Answer 8

Ruby, 59 ... 48 bytes

->n{k=z=1;3.upto(n){|v|z=v.gcd k=z>1?k/z:k+v};k}

Try it online!

Answer 9

Python 3, ¹¹⁵ 109 bytes

from math import*
def f(n):
 l=1
 for i in range(2,n+1):
  g=gcd(l,i)
  if g==1:l+=i+1
  else:l//=g
 print(l)

Try it online!

Ungolfed:

from math import gcd                               # Function for getting gcd of two numbers
def fsd_sequence(n):                               # Define function to get the nth value of the sequence
    prev = 1                                       # The previous value (a[n-1])
    for i in range(2, n + 1):                      # Iterate through numbers from 2 to n+1
        greatest_common_divisor = gcd(prev, i)     # GCD of previous value and i
        if greatest_common_divisor == 1:           # If GCD equals 1,
            prev = prev + i + 1                    # Increment the previous value by i+1
        else:                                      # Otherwise
            prev = prev // greatest_common_divisor # Set the previous value to itself divided by the GCD
    return l                                       # Return the last value

Answer 10

Vyxal, 15 bytes

λ1>[‹x~ġ:ċ[ḭ|++

Try it Online!

Answer 11

PARI/GP, 44 bytes

f(n)=if(n<2,1,2>s=gcd(n,d=f(n-1)),d+n+1,d/s)

Attempt This Online!

Answer 12

Raku, 46 bytes

1,1,{$_/($!=(++$+1)gcd$_)+(++$+2)*($!==1)}...*

Try it online!

This is an expression for the infinite sequence.

Answer 13

Japt, 17 bytes

Outputs the first n terms. I feel like I'm missing a trick here to save a byte or 2.

ÈjY ?XÒY:X/yY}hBì

Try it

ÈjY ?XÒY:X/yY}hBì     :Implicit input of integer U
È                     :Function taking an integer X and an index Y as arguments
 jY                   :  Are X & Y co-prime?
    ?                 :  If so then return
     XÒY              :    X-~Y = X+Y+1
        :             :  Else return
         X/           :    X divided by
           yY         :    GCD of X & Y
             }        :End function
              h       :Repeatedly take the last element of the following array, pass it through the function and push it back to the array until it reaches length U
               B      :  11
                ì     :  To digit array
                      :Implicit output of resulting array

Answer 14

PowerShell Core, 111 bytes

for($i=$r=1;$i-lt"$args"){for($a,$b=++$i,$r;$b){if($a-gt$b){$b,$a=$a,$b}$b%=$a}$r=(($r/$a),($r+$i+1))[!--$a]}$r

Try it online!

Outputs the \$n^{th}\$ term of the sequence

All the terms for 102 bytes