cp's OEIS Frontend

A084937 Smallest number which is coprime to the last two predecessors and has not yet appeared; a(1)=1, a(2)=2.

%I A084937 #105 Jun 28 2025 10:57:07
%S A084937 1,2,3,5,4,7,9,8,11,13,6,17,19,10,21,23,16,15,29,14,25,27,22,31,35,12,
%T A084937 37,41,18,43,47,20,33,49,26,45,53,28,39,55,32,51,59,38,61,63,34,65,57,
%U A084937 44,67,69,40,71,73,24,77,79,30,83,89,36,85,91,46,75,97,52,81
%N A084937 Smallest number which is coprime to the last two predecessors and has not yet appeared; a(1)=1, a(2)=2.
%C A084937 Equivalently, this is the lexicographically earliest sequence of positive numbers satisfying the condition that each term is relatively prime to the next two terms. - _N. J. A. Sloane_, Nov 03 2014
%C A084937 Empirically, the points lie roughly on two lines: if n == 2 mod 3 then a(n) ~= 2n/3, otherwise a(n) ~= 4n/3. See A249680-A249683 for the three trisections, and see also the Sigrist scatterplot. - _N. J. A. Sloane_, Nov 03 2014, Nov 04 2014
%C A084937 All primes and prime powers occur, and the primes occur in their natural order. For any prime p, p occurs before p^2 before p^3, ...
%C A084937 Empirically, this is a permutation of the natural numbers, with inverse A084933: a(A084933(n))=A084933(a(n))=n. It seems that there are no further fixed points after {1,2,3,8,33,39}. Empirically, a(n) mod 2 = A011655(n+1); ABS(a(n)-n) < n; a(3*n+1)>n; a(3*n+2)<n. - _Reinhard Zumkeller_, Dec 16 2007
%C A084937 For a(n) mod 3 see A249603. - _N. J. A. Sloane_, Nov 03 2014
%C A084937 A249694(n) = GCD(a(n),a(n+3)). - _Reinhard Zumkeller_, Nov 04 2014
%H A084937 Reinhard Zumkeller, <a href="/A084937/b084937.txt">Table of n, a(n) for n = 1..100000</a>
%H A084937 John P. Linderman, <a href="/A084937/a084937.txt">Table of n, a(n) for n = 1..764179</a> (about 10MB)
%H A084937 Rémy Sigrist, <a href="/A084937/a084937.png">Scatterplot of the first 2500 terms</a>
%H A084937 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%p A084937 N:= 1000: # to get a(n) until the first entry > N
%p A084937 a[1]:= 1: a[2]:= 2:
%p A084937 R:= {$3..N}:
%p A084937 for n from 3 while R <> {} do
%p A084937   success:= false;
%p A084937   for r in R do
%p A084937     if igcd(r,a[n-1]) = 1 and igcd(r,a[n-2])=1 then
%p A084937        a[n]:= r;
%p A084937        R:= R minus {r};
%p A084937        success:= true;
%p A084937        break
%p A084937     fi
%p A084937   od:
%p A084937   if not success then break fi;
%p A084937 od:
%p A084937 seq(a[i], i = 1 .. n-1); # _Robert Israel_, Dec 12 2014
%t A084937 lst={1,2,3}; unused=Range[4,100]; While[n=Select[unused, CoprimeQ[#, lst[[-1]]] && CoprimeQ[#, lst[[-2]]] &, 1]; n != {}, AppendTo[lst, n[[1]]]; unused=DeleteCases[unused, n[[1]]]]; lst
%t A084937 f[s_] := Block[{k = 1, l = Take[s, -2]}, While[ Union[ GCD[k, l]] != {1} || MemberQ[s, k], k++]; Append[s, k]]; Nest[f, {1, 2}, 67] (* _Robert G. Wilson v_, Jun 26 2011 *)
%o A084937 (Haskell)
%o A084937 import Data.List (delete)
%o A084937 a084937 n = a084937_list !! (n-1)
%o A084937 a084937_list = 1 : 2 : f 2 1 [3..] where
%o A084937    f x y zs = g zs where
%o A084937       g (u:us) | gcd y u > 1 || gcd x u > 1 = g us
%o A084937                | otherwise = u : f u x (delete u zs)
%o A084937 -- _Reinhard Zumkeller_, Jan 28 2012
%o A084937 (Python)
%o A084937 from math import gcd
%o A084937 A084937_list, l1, l2, s, b = [1,2], 2, 1, 3, set()
%o A084937 for _ in range(10**3):
%o A084937     i = s
%o A084937     while True:
%o A084937         if not i in b and gcd(i,l1) == 1 and gcd(i,l2) == 1:
%o A084937             A084937_list.append(i)
%o A084937             l2, l1 = l1, i
%o A084937             b.add(i)
%o A084937             while s in b:
%o A084937                 b.remove(s)
%o A084937                 s += 1
%o A084937             break
%o A084937         i += 1 # _Chai Wah Wu_, Dec 09 2014
%o A084937 (PARI) taken(k,t=v[k])=for(i=3,k-1, if(v[i]==t, return(1))); 0
%o A084937 step(k,g)=while(gcd(k,g)>1, k++); k
%o A084937 first(n)=local(v=vector(n,i,i)); my(nxt=3,t); for(k=3,n, v[k]=step(nxt, t=v[k-1]*v[k-2]); while(taken(k), v[k]=step(v[k]+1,t)); if(v[k]==t, while(taken(k+1,t++),))); v \\ _Charles R Greathouse IV_, Aug 26 2016
%Y A084937 Cf. A084933 (inverse), A103683, A121216, A247665, A090252, A249603 (read mod 3), A249680, A249681, A249682, A249683 (trisections), A249694, A011655, A249684 (numbers that take a record number of steps to appear), A249685.
%Y A084937 Indices of primes: A249602, and of prime powers: A249575.
%Y A084937 Running counts of missing numbers: A249686, A250099, A250100; A249777, A249856, A249857.
%Y A084937 Where a(3n)>a(3n+1): A249689.
%Y A084937 See also A353706, A353709, A353710.
%K A084937 nonn,look
%O A084937 1,2
%A A084937 _Reinhard Zumkeller_, Jun 13 2003
%E A084937 Entry revised by _N. J. A. Sloane_, Nov 04 2014