|
%I #18 Jun 17 2019 03:26:09
%S 1,3,9,9,27,27,3,27,81,81,27,81,81,9,81,81,243,243,27,243,243,81,243,
%T 243,81,243,243,27,243,243,81,243,729,729,243,729,729,81,729,729,243,
%U 729,729,243,729,729,9,729,729,243,729,729,243,729,729,81
%N Denominator of the Reingold-Tarjan sequence, numerator=A072403.
%C The Reingold-Tarjan sequence is based on the following function defined on even positive integers and range of the rational numbers:
%C f(2*n) = if n is even then 2*f(n)/3 else (f(n+1)+f(n-1))/3 for n>1, f(2*1)=1.
%C f(2*n) = A072403(n)/a(n) for n>1, A072403(1)=1 and a(1)=1.
%H Reinhard Zumkeller, <a href="/A072404/b072404.txt">Table of n, a(n) for n = 1..10000</a>
%H J.-P. Allouche and J. Shallit, <a href="https://doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197; <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">preprint</a>. See Example 33.
%H E. M. Reingold and R. E. Tarjan, <a href="https://doi.org/10.1137/0210050">On a greedy heuristic for complete matching</a>, SIAM J. Computing 10 (1981), 676-681; <a href="https://www.semanticscholar.org/paper/On-a-Greedy-Heuristic-for-Complete-Matching-Reingold-Tarjan/8a08d2e5de84a8b91299e31562b5147b90ce181e">Semantic Scholar</a>.
%F A072403(n) / a(n) = 1 - Sum_{k=1..n} (1 / A000244(A029837(k)). - _Reinhard Zumkeller_, Jan 01 2013
%o (Haskell)
%o import Data.Ratio ((%), denominator)
%o a072404 n = a072404_list !! (n-1)
%o a072404_list = map denominator $
%o scanl1 (-) $ map ((1 %) . a000244) $ a029837_list
%o -- _Reinhard Zumkeller_, Jan 01 2013
%Y Cf. A000244, A029837, A072403 (numerators).
%K nonn,frac
%O 1,2
%A _Reinhard Zumkeller_, Jun 16 2002
|
