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.

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

Author

N. J. A. Sloane

Keywords

• easy
• nonn
• nice

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

Examples

			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.
		

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.

Crossrefs

Cf. A007448, A058361, A076291, A077477.

See A276786 for multi-set version.

Programs

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

Mathematica

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

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

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

Extensions

More terms from Ray Chandler, Sep 06 2003