A071912 a(0) = 0, a(1) = 1; to get a(n+1) for n >= 1, let m = a(n) and consider in turn the numbers k = m-1, m-2, ..., 2, 1, m+1, m+2, m+3, ... until reach a k such that gcd(m,k) = 1 and m/k is different from all a(i)/a(i+1) for i = 0, ..., n-1.

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 4, 1, 5, 4, 5, 3, 5, 2, 5, 1, 6, 5, 6, 1, 7, 6, 7, 5, 7, 4, 7, 3, 7, 2, 7, 1, 8, 7, 8, 5, 8, 3, 8, 1, 9, 8, 9, 7, 9, 5, 9, 4, 9, 2, 9, 1, 10, 9, 10, 7, 10, 3, 10, 1, 11, 10, 11, 9, 11, 8, 11, 7, 11, 6, 11, 5, 11, 4, 11, 3, 11, 2, 11, 1, 12, 11, 12, 7, 12

Offset: 0

Author

N. J. A. Sloane, Jun 13 2002

Keywords

• nonn
• easy
• nice
• look

Comments

A version of a greedy construction of an integer-valued function a such that a(n)/a(n+1) runs through all nonnegative rationals exactly once.

After initial 0, odd-indexed terms are integers in order with m repeated phi(m) times; even-indexed terms are the corresponding numbers <= m and relatively prime to m, in descending order. - Franklin T. Adams-Watters, Dec 06 2006

Examples

			After [0 1 1 2 1 3 2] we have seen the fractions 0/1, 1/1, 1/2, 2/1, 1/3, 3/2; we consider k = 1, 3, 4, 5, ...; the first of these that gives a new ratio is k=3, giving 2/3, so the next term is 3.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• N. J. A. Sloane, FORTRAN program

Crossrefs

Cf. A002487.

Bisections: A038567 and essentially A020653.

Cf. A038566.

Programs

Haskell

Following Franklin T. Adams-Watters's comment.
import Data.List (transpose)
a071912 n = a071912_list !! n
a071912_list = 0 : concatMap f [1..] where
   f x = concat $ transpose [take (length tots) $ repeat x, reverse tots]
         where tots = a038566_row x
-- Reinhard Zumkeller, Dec 16 2013

Mathematica

a[0] = 0; a[1] = a[2] = 1; a[n_] := a[n] = Module[{m = a[n-1], ff = Table[ a[i]/a[i+1], {i, 0, n-2}], ok}, ok := GCD[m, k] == 1 && FreeQ[ff, m/k]; For[k = m-1, k >= 1, k--, If[ok, Return[k]]]; For[k = m+1, True, k++, If[ok, Return[k]]]]; Table[a[n], {n, 0, 89}] (* Jean-François Alcover, Oct 28 2017 *)