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. (Formerly M2335)

1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 43, 45, 46, 55, 57, 58, 63, 64, 67, 79, 81, 82, 85, 87, 91, 93, 94, 111, 115, 117, 118, 121, 127, 129, 130, 135, 136, 139, 159, 163, 165, 166, 171, 172, 175, 183, 187, 189, 190, 193, 202, 223, 231, 235, 237

Offset

1,2

Comments

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

a(n+1) = A007448(a(n)), which also gives the record values of A007448 and their positions. - Reinhard Zumkeller, Jul 14 2010

Named after the American mathematician David Anthony Klarner (1940-1999) and the German-British mathematician Richard Rado (1906-1989). - Amiram Eldar, Jun 24 2021

References

Michael L. Fredman and Donald E. Knuth, Recurrence relations based on minimization, Abstract 71T-B234, Notices Amer. Math. Soc., Vol. 18 (1971), p. 960.

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 78.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence)

Niklaus Wirth, Systematisches Programmieren, 1975, exercise 15.12.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Benoit Cloitre, Graph of initial terms.

David A. Klarner and Richard Rado, Linear combinations of sets of consecutive integers, The American Mathematical Monthly, Vol. 80, No. 9 (1973), pp. 985-989.

Jeffrey C. Lagarias, Erdős, Klarner and the 3x+ 1 Problem, Amer. Math. Monthly, Vol. 123, No. 8 (2016), pp. 753-776.

Remco Niemeijer, Wirth Problem 15.12, Bonsai Code.

Formula

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

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

Example

a(10) = 21 = 2*(3*(2*1+1)+1)+1: A132139(A132140(10)) = A132139(43) = 21;
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.

Mathematica

Union[ Flatten[ NestList[{2# + 1, 3# + 1} &, 1, 6]]] (* Robert G. Wilson v, May 11 2005 *)

Prog

(Haskell)
import Data.Set
a002977 n = a002977_list !! (n-1)
a002977_list = f $ singleton 1 where
   f :: Set Integer -> [Integer]
   f s = m : (f $ insert (3*m+1) $ insert (2*m+1) s') where
        (m, s') = deleteFindMin s
-- Reinhard Zumkeller, Feb 10 2011
(Haskell) See Niemeijer link.
import Data.List.Ordered (union)
a002977_list = 1 : union
   (map ((+1) . (*2)) a002977_list) (map ((+1) . (*3)) a002977_list)
-- Reinhard Zumkeller, Nov 12 2014
(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

Crossrefs

Cf. A007448, A058361, A076291, A077477.

See A276786 for multi-set version.

Sequence in context: A005098 A185661 A276786 * A024799 A240531 A212013

Adjacent sequences: A002974 A002975 A002976 * A002978 A002979 A002980

Keyword

easy,nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Ray Chandler, Sep 06 2003

Status

approved