login
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.
3

%I #20 Oct 20 2019 01:56:13

%S 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,

%T 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,

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

%N 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.

%C 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.

%C 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

%H Reinhard Zumkeller, <a href="/A071912/b071912.txt">Table of n, a(n) for n = 0..10000</a>

%H N. J. A. Sloane, <a href="/A071912/a071912.txt">FORTRAN program</a>

%e 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.

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

%o (Haskell) Following _Franklin T. Adams-Watters_'s comment.

%o import Data.List (transpose)

%o a071912 n = a071912_list !! n

%o a071912_list = 0 : concatMap f [1..] where

%o f x = concat $ transpose [take (length tots) $ repeat x, reverse tots]

%o where tots = a038566_row x

%o -- _Reinhard Zumkeller_, Dec 16 2013

%Y Cf. A002487.

%Y Bisections: A038567 and essentially A020653.

%Y Cf. A038566.

%K nonn,easy,nice,look

%O 0,4

%A _N. J. A. Sloane_, Jun 13 2002