A072403 - OEIS

%I #26 Jan 10 2025 01:18:57

%S 1,2,5,4,11,10,1,8,23,22,7,20,19,2,17,16,47,46,5,44,43,14,41,40,13,38,

%T 37,4,35,34,11,32,95,94,31,92,91,10,89,88,29,86,85,28,83,82,1,80,79,

%U 26,77,76,25,74,73,8,71,70,23,68,67,22,65,64,191,190,7

%N Numerator of the Reingold-Tarjan sequence, denominator=A072404.

%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) = a(n)/A072404(n) for n>1, a(1)=1 and A072404(1)=1.

%H Reinhard Zumkeller, <a href="/A072403/b072403.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 a(n) / A072404(n) = 2 - Sum_{k=1..n} 1 / A000244(A029837(k)). - _Reinhard Zumkeller_, Jan 01 2013 [Corrected by _Sean A. Irvine_, Sep 28 2024]

%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, A072404 (denominators).

%K nonn,frac

%O 1,2

%A _Reinhard Zumkeller_, Jun 16 2002