cp's OEIS Frontend

A002977 Klarner-Rado sequence: a(1) = 1; subsequent terms are defined by the rule that if m is present so are 2m+1 and 3m+1.

%I A002977 M2335 #68 Jan 13 2022 01:31:14
%S A002977 1,3,4,7,9,10,13,15,19,21,22,27,28,31,39,40,43,45,46,55,57,58,63,64,
%T A002977 67,79,81,82,85,87,91,93,94,111,115,117,118,121,127,129,130,135,136,
%U A002977 139,159,163,165,166,171,172,175,183,187,189,190,193,202,223,231,235,237
%N A002977 Klarner-Rado sequence: a(1) = 1; subsequent terms are defined by the rule that if m is present so are 2m+1 and 3m+1.
%C A002977 Complement of A132142: A132138(a(n)) = 1; for all terms m there exists at least one x such that A132140(x)=m. - _Reinhard Zumkeller_, Aug 20 2007
%C A002977 a(n+1) = A007448(a(n)), which also gives the record values of A007448 and their positions. - _Reinhard Zumkeller_, Jul 14 2010
%C A002977 Named after the American mathematician David Anthony Klarner (1940-1999) and the German-British mathematician Richard Rado (1906-1989). - _Amiram Eldar_, Jun 24 2021
%D A002977 Michael L. Fredman and Donald E. Knuth, Recurrence relations based on minimization, Abstract 71T-B234, Notices Amer. Math. Soc., Vol. 18 (1971), p. 960.
%D A002977 Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 78.
%D A002977 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence)
%D A002977 Niklaus Wirth, Systematisches Programmieren, 1975, exercise 15.12.
%H A002977 Reinhard Zumkeller, <a href="/A002977/b002977.txt">Table of n, a(n) for n = 1..10000</a>
%H A002977 Benoit Cloitre, <a href="/A002977/a002977.jpg">Graph of initial terms</a>.
%H A002977 David A. Klarner and Richard Rado, <a href="https://www.jstor.org/stable/2318772">Linear combinations of sets of consecutive integers</a>, The American Mathematical Monthly, Vol. 80, No. 9 (1973), pp. 985-989.
%H A002977 Jeffrey C. Lagarias, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.123.8.753">Erdős, Klarner and the 3x+ 1 Problem</a>, Amer. Math. Monthly, Vol. 123, No. 8 (2016), pp. 753-776.
%H A002977 Remco Niemeijer, <a href="http://bonsaicode.wordpress.com/2012/12/07/programming-praxis-wirth-problem-15-12">Wirth Problem 15.12</a>, Bonsai Code.
%F A002977 It seems that lim_{n->infinity} log(A002977(n))/log(n) = C = 1.3... and probably A002977(n) is asymptotic to u*n^C with u=1.0... - _Benoit Cloitre_, Nov 06 2002
%F A002977 Limit_{n->infinity} log(A002977(n))/log(n) = C = 1.269220905243564855888589424556..., and lim_{n->infinity} A002977(n)/n^C = u = 1.335... - _Yi Yang_, Jul 23 2011, Aug 21 2017
%e A002977 a(10) = 21 = 2*(3*(2*1+1)+1)+1: A132139(A132140(10)) = A132139(43) = 21;
%e A002977 a(14) = 31 = 3*(3*(2*1+1)+1)+1 = 2*(2*(2*(2*1+1)+1)+1)+1: A132139(A132140(14)) = A132139(52) = 31 and A132139(A132140(16)) = A132139(121) = 31.
%t A002977 Union[ Flatten[ NestList[{2# + 1, 3# + 1} &, 1, 6]]] (* _Robert G. Wilson v_, May 11 2005 *)
%o A002977 (Haskell)
%o A002977 import Data.Set
%o A002977 a002977 n = a002977_list !! (n-1)
%o A002977 a002977_list = f $ singleton 1 where
%o A002977    f :: Set Integer -> [Integer]
%o A002977    f s = m : (f $ insert (3*m+1) $ insert (2*m+1) s') where
%o A002977         (m, s') = deleteFindMin s
%o A002977 -- _Reinhard Zumkeller_, Feb 10 2011
%o A002977 (Haskell) See Niemeijer link.
%o A002977 import Data.List.Ordered (union)
%o A002977 a002977_list = 1 : union
%o A002977    (map ((+1) . (*2)) a002977_list) (map ((+1) . (*3)) a002977_list)
%o A002977 -- _Reinhard Zumkeller_, Nov 12 2014
%o A002977 (PARI) list(lim)=my(u=List(),v=List([1]),t,sz); while(#v, listput(u,v[1]); t=2*v[1]+1; if(t>lim, listpop(v,1); next); listput(v,t); t=3*v[1]+1; listpop(v,1); if(t<=lim, listput(v,t)); if(#v>sz, u=Set(u); v=List(setminus(Set(v),u)); u=List(u); sz=2*#v)); Set(u) \\ _Charles R Greathouse IV_, Aug 21 2017
%Y A002977 Cf. A007448, A058361, A076291, A077477.
%Y A002977 See A276786 for multi-set version.
%K A002977 easy,nonn,nice
%O A002977 1,2
%A A002977 _N. J. A. Sloane_
%E A002977 More terms from _Ray Chandler_, Sep 06 2003