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

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, 37, 41, 18, 43, 47, 20, 33, 49, 26, 45, 53, 28, 39, 55, 32, 51, 59, 38, 61, 63, 34, 65, 57, 44, 67, 69, 40, 71, 73, 24, 77, 79, 30, 83, 89, 36, 85, 91, 46, 75, 97, 52, 81

Offset: 1

Author

Reinhard Zumkeller, Jun 13 2003

Keywords

• nonn
• look

Comments

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

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

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, ...

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)Reinhard Zumkeller, Dec 16 2007

For a(n) mod 3 see A249603. - N. J. A. Sloane, Nov 03 2014

A249694(n) = GCD(a(n),a(n+3)). - Reinhard Zumkeller, Nov 04 2014

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..100000
• John P. Linderman, Table of n, a(n) for n = 1..764179 (about 10MB)
• Rémy Sigrist, Scatterplot of the first 2500 terms
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

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.

Indices of primes: A249602, and of prime powers: A249575.

Running counts of missing numbers: A249686, A250099, A250100; A249777, A249856, A249857.

Where a(3n)>a(3n+1): A249689.

See also A353706, A353709, A353710.

Programs

Haskell

import Data.List (delete)
a084937 n = a084937_list !! (n-1)
a084937_list = 1 : 2 : f 2 1 [3..] where
   f x y zs = g zs where
      g (u:us) | gcd y u > 1 || gcd x u > 1 = g us
               | otherwise = u : f u x (delete u zs)
-- Reinhard Zumkeller, Jan 28 2012

Maple

N:= 1000: # to get a(n) until the first entry > N
a[1]:= 1: a[2]:= 2:
R:= {$3..N}:
for n from 3 while R <> {} do
  success:= false;
  for r in R do
    if igcd(r,a[n-1]) = 1 and igcd(r,a[n-2])=1 then
       a[n]:= r;
       R:= R minus {r};
       success:= true;
       break
    fi
  od:
  if not success then break fi;
od:
seq(a[i], i = 1 .. n-1); # Robert Israel, Dec 12 2014

Mathematica

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
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 *)

PARI

taken(k,t=v[k])=for(i=3,k-1, if(v[i]==t, return(1))); 0
step(k,g)=while(gcd(k,g)>1, k++); k
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

Python

from math import gcd
A084937_list, l1, l2, s, b = [1,2], 2, 1, 3, set()
for _ in range(10**3):
    i = s
    while True:
        if not i in b and gcd(i,l1) == 1 and gcd(i,l2) == 1:
            A084937_list.append(i)
            l2, l1 = l1, i
            b.add(i)
            while s in b:
                b.remove(s)
                s += 1
            break
        i += 1 # Chai Wah Wu, Dec 09 2014

Extensions

Entry revised by N. J. A. Sloane, Nov 04 2014