10
\$\begingroup\$

Definition

  • Two integers are coprime if they share no positive common divisors other than 1.
  • a(1) = 1
  • a(2) = 2
  • a(n) is the smallest positive integer which is coprime to the a(n-1) and a(n-2) and has not yet appeared, for integer n >= 3.

Task

  • Given positive integer n, output/print a(n).

Example

  • a(11) = 6 because 6 is coprime with the last two predecessors (namely, 11 and 13) and 6 has not appeared before.

Notes

  • Note that the sequence is not ascending, meaning that an element can be smaller than its predecessor.

Specs

  • You must use 1-indexed.

Testcases

n      a(n)
1      1
2      2
3      3
4      5
5      4
6      7
7      9
8      8
9      11
10     13
11     6
12     17
13     19
14     10
15     21
16     23
17     16
18     15
19     29
20     14
100    139
1000   1355
10000  13387
100000 133361

Scoring

  • Since coprime means that the two numbers share only one divisor (1), and 1 is a small number, your code should be as small as possible in terms of byte-count.

References

\$\endgroup\$
  • 4
    \$\begingroup\$ Those "reasons" for short code... \$\endgroup\$ – Luis Mendo Aug 14 '16 at 15:56
  • 1
    \$\begingroup\$ I wonder why this was downvoted. Surely not because of the horrible rationale? \$\endgroup\$ – Conor O'Brien Aug 14 '16 at 16:06
  • \$\begingroup\$ @Conor Not me. Actually I upvoted. I hope people will see both the rationale and my comment as jokes \$\endgroup\$ – Luis Mendo Aug 14 '16 at 20:44
  • 3
    \$\begingroup\$ The problem with these "funny" justifications for code golf is that I need to read a bad joke spanning four lines just to find out that this is standard code golf. It's simply obscuring the challenge's rules for no good reason. \$\endgroup\$ – Martin Ender Aug 14 '16 at 21:39
  • 1
    \$\begingroup\$ @ConorO'Brien Not all browsers always show the title (and then there's the mobile app), and we generally describe the scoring in the post in addition to using the tag, because the tag alone doesn't mean anything to people who are new to the site. Even though I am familiar with our challenge type tags, I never read them to figure out how a challenge is scored but try to find that in the challenge body. The tag is for categorisation, searchability and challenge-type specific information in the tag wiki. \$\endgroup\$ – Martin Ender Aug 14 '16 at 22:10
5
\$\begingroup\$

Python 3.5, 160 141 126 124 121 109 bytes

This is a simple implementation of the sequence's definition. Golfing suggestions welcome.

Edit: -17 bytes thanks to Leaky Nun. -9 bytes thanks to Peter Taylor. -6 bytes thanks to Sp3000 and switching to Python 3.5.

import math;f=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+math.gcd(c,r[0]*r[1])<2and f(n-1,[c]+r)or f(n,r,c+1)

Ungolfing:

import math
def f(n, r=[2,1], c=3):
    if n<2:
        return r[1]
    elif (c in r) + math.gcd(c,r[0]*r[1]) < 2:
        return f(n-1, [c]+r)
    else:
        return f(n, r, c+1)
\$\endgroup\$
  • \$\begingroup\$ For Python 3.5+, import math then g=math.gcd should be shorter than defining your own g. For before 3.5, you can do from fractions import* for gcd. \$\endgroup\$ – Sp3000 Aug 14 '16 at 14:36
  • \$\begingroup\$ If you initialise c=3 inside the loop you only need to do it once. By my count you save 3 chars. \$\endgroup\$ – Peter Taylor Aug 14 '16 at 16:44
  • \$\begingroup\$ There's also a 2-char saving from building the array the other way round: you have to use r=[c]+r rather than +=, but three negative indices become positive. And then there's a further 2-char saving from rewriting as a lambda, although that's a pretty drastic change: from fractions import*;F=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+gcd(r[0]*r[1],c)<2and F(n-1,[c]+r)or F(n,r,c+1) and no need for a print because it's no longer a full program. \$\endgroup\$ – Peter Taylor Aug 14 '16 at 17:14
2
\$\begingroup\$

MATL, 28 27 bytes

2:i:"`@ym1MTF_)Zdqa+}@h]]G)

The code is slow, but gives the correct result.

Try it online! Or verify the first ten cases.

A small modification of the code produces a plot of the sequence:

2:i:"`@ym1MTF_)Zdqa+}@h]]G:)XG

See it as ASCII art, or with graphical output in the offline compiler:

enter image description here

enter image description here

Explanation

2:         % Push [1 2] to initiallize the sequence
i:         % Input n. Push [1 2 ... n]
"          % For loop: repeat n times
  `        %   Do while loop
    @      %     Push iteration index, starting at 1. This is the candidate number
           %     to extend the sequence
    y      %     Duplicate vector containing the sequence so far
    m      %     Is member? Gives true if the candidate is in the sequence
    1M     %     Push candidate and vector again
    TF_)   %     Get last two elements of the vector
    Zd     %     GCD between the candidate and those two elements. Produces a
           %     two-element vector
    qa     %     True if any of the two results exceeds 1, meaning
           %     the candidate is not coprime with the latest two sequence values
    +      %     Add. This corresponds to logical "or" of the two conditions, namely
           %     whether the candidate is member of the sequence so far, and
           %     whether it is not coprime with the latest two. In either case
           %     the do...while must continue with a next iteration, to try a new
           %     candidate. Else the loop is exited, and the current candidate
           %     is the new value of the sequence
  }        %   Finally (execute when the loop is exited)
    @h     %     Push current candidate and concatenate to the sequence vector
  ]        %   End do...while
]          % End for
G)         % Get n-th value of the sequence. Implicitly display
\$\endgroup\$
1
\$\begingroup\$

C, 185 bytes

G(a,b){return a%b?G(b,a%b):b;}
i,j,k;f(n){int a[n+2];for(i=0;i++<n;){a[i]=i<3?i:0;for(j=2;!a[i];++j){for(k=i;--k;){if(a[k]==j)++j,k=i;}a[G(a[i-1],j)*G(a[i-2],j)<2?i:0]=j;}}return a[n];}
\$\endgroup\$
1
\$\begingroup\$

Actually, 38 37 35 33 31 30 bytes

This is a simple implementation of the function definition. Golfing suggestions welcome. Try it online!

Edit: -3 bytes thanks to Leaky Nun.

2R#╗,;`1";2±╜tπg@╜í+Y"£╓╖`nD╜E

Ungolfing:

2R#╗    Push [1,2] and store it in register 0
,;      Take input and duplicate
`1      Start function, push 1
  "       Start string
  ;       Duplicate i
  2±╜t    Push (list in register 0)[-2:]
  πg      gcd(i, product of list[-2:])
  @╜í     Rotate the gcd and bring up i, check for i in list (0-based, -1 if not found)
  +Y      Add the gcd and the index, negate (1 if coprime and not found in list, else 0)
  "£      End string, turn into a function
╓       Push first (1) values where f(x) is truthy, starting with f(0)
╖`      Append result to the list in register 0, end function
n       Run function (input) times
D╜E     Return (final list)[n-1]
\$\endgroup\$
  • 1
    \$\begingroup\$ Stack manipulation much \$\endgroup\$ – Leaky Nun Aug 20 '16 at 9:27
0
\$\begingroup\$

Haskell, 81 73 bytes

c l@(m:n:_)=m:c([x|x<-[1..],gcd(m*n)x<2,all(/=x)l]!!0:l)
((0:1:c[2,1])!!)

Usage example: ((0:1:c[2,1])!!) 12-> 17.

Build the list of all a(n), starting with 0 to fix the 1-based index and 1 and followed by c[2,1]. c takes the head of it's argument list l followed by a recursive call with then next number that fits (co-prime, not seen before) added in front of l. Pick the nth element of this list.

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

R, 141 bytes

 f=Vectorize(function(n)ifelse(n>3,{c=3;a=f(n-1);b=f(n-2);d=f(4:n-3);while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)c=c+1;c},n))

ungolfed

f=Vectorize( function(n)     #build a recursive function. Vectorize allows
    if(n>3) {                #the function to be called on vectors.
        c=3                  #Tests size. Builds some frequent variables.
        a=f(n-1)
        b=f(n-2)
        d=f(4:n-3)           #Should really golf this out, but its horribly slow.
        while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)
              c=c+1          #If we are coprime and not already seen. add.
        c
     } else n)               #First three are 1,2,3.
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 97 90 bytes

a@1=1;a@2=2;a@n_:=SelectFirst[Range[2n],GCD[a[n-1]a[n-2],#]<2&&!MemberQ[a/@Range[n-1],#]&]

Based on my conjecture that a(n) < 2n for all n.

To get a faster run, add a@n= after the original := so that the function doesn't need to recalculate previous values.

Saved 7 bytes thanks to Sherlock9 (if gcd(a,b)=1 then gcd(ab,m) = gcd(a,m)*gcd(b,m))

\$\endgroup\$
  • \$\begingroup\$ It is not a conjecture, since it is written in the OEIS page that "ABS(a(n)-n) < n" \$\endgroup\$ – Leaky Nun Aug 20 '16 at 14:27
  • \$\begingroup\$ @LeakyNun Thanks. The OEIS page was down until a few moments ago, and I was worried about a possible counterexample for large n. \$\endgroup\$ – lastresort Aug 20 '16 at 14:29
0
\$\begingroup\$

Pyth, 23 bytes

eu+Gf&-TGq1iT*F>2G1tQ]1

Test suite

A fairly straightforward implementation, but with some nice golfing tricks.

eu+Gf&-TGq1iT*F>2G1tQ]1
 u                 tQ]1    Apply the following function input - 1 times,
                           where G is the current state (List of values so far)
  +G                       Add to G
    f             1        The first number, counting up from 1
      -TG                  That has not been seen so far
     &                     And where
               >2G         The most recent two numbers
             *F            Multiplied together
           iT              Gcd with the current number being checked
         q1                Equals 1
e                          Output the final element of the list.
\$\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.