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

Improve this question
\$\endgroup\$
11
  • 4
    \$\begingroup\$ Those "reasons" for short code... \$\endgroup\$ Commented Aug 14, 2016 at 15:56
  • 1
    \$\begingroup\$ I wonder why this was downvoted. Surely not because of the horrible rationale? \$\endgroup\$ Commented Aug 14, 2016 at 16:06
  • \$\begingroup\$ @Conor Not me. Actually I upvoted. I hope people will see both the rationale and my comment as jokes \$\endgroup\$ Commented Aug 14, 2016 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\$ Commented Aug 14, 2016 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\$ Commented Aug 14, 2016 at 22:10

8 Answers 8

Reset to default
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)
Improve this answer
\$\endgroup\$
3
  • \$\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\$ Commented Aug 14, 2016 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\$ Commented Aug 14, 2016 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\$ Commented Aug 14, 2016 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
Improve this answer
\$\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];}
Improve this answer
\$\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]
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Stack manipulation much \$\endgroup\$ Commented Aug 20, 2016 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.

Improve this answer
\$\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.
Improve this answer
\$\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))

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ It is not a conjecture, since it is written in the OEIS page that "ABS(a(n)-n) < n" \$\endgroup\$ Commented Aug 20, 2016 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\$ Commented Aug 20, 2016 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.
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.