15
\$\begingroup\$

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:

Graph

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 so any output is fine)

This is so shortest answer in bytes wins!

\$\endgroup\$
4
  • 6
    \$\begingroup\$ Please consider adding test cases in your challenges. Also avoid accepting an answer in the first day of the challenge. Finally, please use "sandbox" that you will find in the upper right corner of the site. Welcome to code golf! \$\endgroup\$
    – ZaMoC
    Sep 5 at 17:33
  • 4
    \$\begingroup\$ I'll have to add this to my list of examples where extrapolation badly fails... \$\endgroup\$
    – TLW
    Sep 6 at 6:06
  • 1
    \$\begingroup\$ That's actually four straight lines at the end: \$y=1\$, \$y=n+2\$, \$y=2(n+1)\$, and \$y=2\$. \$\endgroup\$
    – Nitrodon
    Sep 8 at 15:36
  • 1
    \$\begingroup\$ @Nitrodon - thanks. I couldn't see the difference between \$y=1\$ and \$y=2\$ at that zoom. I have edited the question with this information. \$\endgroup\$
    – The Thonnu
    Sep 8 at 15:37

14 Answers 14

7
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ Shouldn't that be '12 UTF8 unicode characters'? \$\endgroup\$
    – P i
    Sep 8 at 13:07
  • \$\begingroup\$ @Pi 05AB1E uses, like some other code-golfing languages you'll see pretty often (like Vyxal, Jelly, Charcoal, MathGolf, etc.) it's own custom codepage for the 256 characters it knows. I usually link them in the bytes portion of my answers, as you can see above. Each of these 256 characters are 1 byte each in this 05AB1E encoding. I'm not sure how to compile/run it with raw bytes in the new 05AB1E version that's built in Elixir, but here is an example of the legacy 05AB1E version, which was built in Python, where the raw bytes are run with --osabie flag. \$\endgroup\$ Sep 8 at 13:32
  • 1
    \$\begingroup\$ I was curious from an information-theory perspective. So each glyph is holding 8 bits of information. Fascinating. Props for patterning your brain with this. \$\endgroup\$
    – P i
    Sep 8 at 16:07
6
\$\begingroup\$

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;}
\$\endgroup\$
8
  • \$\begingroup\$ Since you save the result of h in global variable r, it no longer needs to 'return', so you can remove the a= within h to save 2 bytes. \$\endgroup\$ Sep 5 at 15:26
  • \$\begingroup\$ @KevinCruijssen Huh, I don't understand that. Why does the return value of calling h become right, even though I only put it into a global variable? \$\endgroup\$
    – pxeger
    Sep 5 at 15:31
  • \$\begingroup\$ I was actually trying to figure that out myself after I made my comment just yet and realizing it would still need a return for h(t=c(n-1),n)<2.. 🤔 The result didn't seem to change, hence my comment, but it's indeed a bit confusing. I'm trying to find a difference with or without the a= for a certain n, but there doesn't seem to be one for the values I've checked thus far. Although I'm not sure why.. \$\endgroup\$ Sep 5 at 15:34
  • 1
    \$\begingroup\$ @KevinCruijssen Well, they generate identical assembly: godbolt.org/z/EaMK6KEWd \$\endgroup\$
    – pxeger
    Sep 5 at 15:38
  • 3
    \$\begingroup\$ Oh sorry.. If you mean why an external (global) variable is good for the eax trick Idk for sure, i think it's just the last assignment the cpu perform but I know for sure it works consistently in gcc \$\endgroup\$
    – AZTECCO
    Sep 5 at 19:26
4
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ 56: N+X:-N>1,N-1+B,C=gcd(B,N),(C<2,X is B+N+1;X is B/C);X=1. \$\endgroup\$
    – Steffan
    Sep 5 at 19:34
  • \$\begingroup\$ @Steffan Yo how is that not hitting stack limit, I tried N-1+B and it was always hitting stack limit for some reason. \$\endgroup\$
    – Aiden Chow
    Sep 5 at 19:35
  • \$\begingroup\$ That's because you're checking directly if N=1 or N=0 with the top checks and not evaluating N-1. I'm using N>1 which evaluates it. \$\endgroup\$
    – Steffan
    Sep 5 at 19:37
3
\$\begingroup\$

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);}}
\$\endgroup\$
9
  • \$\begingroup\$ You can remove most of the int bits from the declarations, as C variables default to type int if none is specified. \$\endgroup\$
    – pxeger
    Sep 5 at 14:30
  • \$\begingroup\$ From the definitions, the variables, or the arguments? \$\endgroup\$ Sep 5 at 14:31
  • \$\begingroup\$ From all of them. \$\endgroup\$
    – pxeger
    Sep 5 at 14:32
  • \$\begingroup\$ You also don't need to submit a full program, so you can remove the main() function entirely and take I/O using the arguments and return value of c \$\endgroup\$
    – pxeger
    Sep 5 at 14:33
  • \$\begingroup\$ I've done that in a few other answers, but because of the first line and the other definitions, I'm not so sure it's feasible to do that. Could you edit it yourself and show? \$\endgroup\$ Sep 5 at 14:36
3
\$\begingroup\$

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

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

\$\endgroup\$
1
  • \$\begingroup\$ If[#<2,1,If[(s=GCD[#,d=#0[#-1]])<2,d+#+1,d/s]]& \$\endgroup\$
    – alephalpha
    Sep 6 at 8:22
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ I guess this would be Python 3.8 or more (because of :=)? \$\endgroup\$ Sep 5 at 14:30
  • 2
    \$\begingroup\$ @py3programmer Yes, I use the latest version of Python as much as possible. \$\endgroup\$
    – pxeger
    Sep 5 at 14:31
1
\$\begingroup\$

Python 3, 115 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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can put l=1 inside the function definition: def f(n,l=1); if g==1:l+=i+1\n else:l//=g can be l=g==1and l-~i or l//g; g=gcd(l,i) can be placed inline as (g:=gcd(l,i)) in Python 3.8+; and the loop can be inline then as well: 99 bytes I'm also pretty sure it can be a recursive lambda to get rid of the spaces and newlines, but haven't looked too closely. \$\endgroup\$ Sep 5 at 14:29
  • \$\begingroup\$ Ungolfed Sage plot: sagecell.sagemath.org/… \$\endgroup\$
    – PM 2Ring
    Sep 6 at 12:45
  • \$\begingroup\$ It would be smaller to just import math and then use math.gcd later, since you only use it once. It's only 1 byte, but every byte counts \$\endgroup\$ Sep 6 at 21:12
  • \$\begingroup\$ is it shorter to implement gcd manually? something like while i:i,g=g,i%g \$\endgroup\$
    – qwr
    Sep 7 at 6:37
1
\$\begingroup\$

Vyxal, 15 bytes

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

Try it Online!

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

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!

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

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!

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

Raku, 46 bytes

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

Try it online!

This is an expression for the infinite sequence.

\$\endgroup\$
1
  • \$\begingroup\$ 42 bytes, though it relies on not messing with $/ while the sequence is being generated (though you can still save one regardless with $!<2) \$\endgroup\$
    – Jo King
    Sep 13 at 1:57
0
\$\begingroup\$

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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