A002977 -id:A002977 - cp's OEIS frontend

A007448 Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2a(floor(n/2)), 3a(floor(n/3)) ).

1, 3, 3, 4, 7, 7, 7, 9, 9, 10, 13, 13, 13, 15, 15, 19, 19, 19, 19, 21, 21, 22, 27, 27, 27, 27, 27, 28, 31, 31, 31, 39, 39, 39, 39, 39, 39, 39, 39, 40, 43, 43, 43, 45, 45, 46, 55, 55, 55, 55, 55, 55, 55, 55, 55, 57, 57, 58, 63, 63, 63, 63, 63, 64, 67, 67, 67, 79, 79, 79, 79

Offset: 0

N. J. A. Sloane

Record values and where they occur: a(A002977(n-1)) = A002977(n) and a(m) < A002977(n) for m < A002977(n-1). - Reinhard Zumkeller, Jul 13 2010

A003817 and A179526 are subsequences. - Reinhard Zumkeller, Jul 18 2010

R. L. Graham, D. E. Knuth and O. 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).

T. D. Noe, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Knuth Number.

Cf. A002977.

a007448 n = a007448_list !! n
a007448_list = f [0] [0] where
   f (x:xs) (y:ys) = z : f (xs ++ [2*z,2*z]) (ys ++ [3*z,3*z,3*z])
     where z = 1 + min x y
-- Reinhard Zumkeller, Sep 20 2011

a := proc(n) option remember; ifelse(n = 0, 1, 1 + min(2 * a(iquo(n-1, 2)), 3 * a(iquo(n-1,  3)))) end: seq(a(n), n = 0..70);  # Peter Luschny, Jul 16 2025

a[0] = 1; a[n_] := a[n] = 1 + Min[2*a[Floor[(n - 1)/2]], 3*a[Floor[(n - 1)/3]]]; Table[ a[n], {n, 0, 72}] (* Robert G. Wilson v, Jan 29 2005, corrected by Michael De Vlieger, Jul 16 2025 *)

def aupton(nn):
    alst = [1]
    [alst.append(1 + min(2*alst[n//2], 3*alst[n//3])) for n in range(nn)]
    return alst
print(aupton(70)) # Michael S. Branicky, Mar 28 2022

A005658 If n appears so do 2n, 3n+2, 6n+3.

Original entry on oeis.org

1, 2, 4, 5, 8, 9, 10, 14, 15, 16, 17, 18, 20, 26, 27, 28, 29, 30, 32, 33, 34, 36, 40, 44, 47, 50, 51, 52, 53, 54, 56, 57, 58, 60, 62, 63, 64, 66, 68, 72, 80, 83, 86, 87, 88, 89, 92, 93, 94, 98, 99, 100, 101, 102, 104, 105, 106, 108, 110, 111, 112, 114, 116, 120, 122, 123

Offset: 1

N. J. A. Sloane

David Klarner and coauthors studied several sequences of this type. Some of the references here apply generally to this class of sequences.

Guy, R. K., Klarner-Rado Sequences. Section E36 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 237, 1994.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010. See pp. 6, 280.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, Table of n, a(n) for n = 1..15889
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1982
R. K. Guy, Don't try to solve these problems, Amer. Math. Monthly, 90 (1983), 35-41.
Dean G. Hoffman and David A. Klarner, Sets of integers closed under affine operators-the closure of finite sets, Pacific J. Math. 78 (1978), no. 2, 337-344.
Dean G. Hoffman and David A. Klarner, Sets of integers closed under affine operators-the finite basis theorem, Pacific J. Math. 83 (1979), no. 1, 135-144.
David A. Klarner, m-Recognizability of sets closed under certain affine functions, Discrete Appl. Math. 21 (1988), no. 3, 207-214.
David A. Klarner and Karel Post, Some fascinating integer sequences, A collection of contributions in honour of Jack van Lint, Discrete Math. 106/107 (1992), 303-309.
David A. Klarner and R. Rado, Arithmetic properties of certain recursively defined sets, Pacific J. Math. 53 (1974), 445-463.
Eric Weisstein's World of Mathematics, Klarner-Rado Sequence.
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A002977, A185661.

import Data.Set (Set, fromList, insert, deleteFindMin)
a005658 n = a005658_list !! (n-1)
a005658_list = klarner $ fromList [1,2] where
   klarner :: Set Integer -> [Integer]
   klarner s = m : (klarner $
                    insert (2*m) $ insert (3*m+2) $ insert (6*m+3) s')
      where (m,s') = deleteFindMin s
-- Reinhard Zumkeller, Mar 14 2011

ina:= proc(n) evalb(n=1) end:
a:= proc(n) option remember; local k, t;
      if n=1 then 1
    else for k from a(n-1)+1 while not
           (irem(k, 2, 't')=0 and ina(t) or
            irem(k, 3, 't')=2 and ina(t) or
            irem(k, 6, 't')=3 and ina(t) )
         do od: ina(k):= true; k
      fi
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Mar 16 2011

s={1};Do[a=s[[n]];s=Union[s,{2a,3a+2,6a+3}],{n,1000}];s (* Zak Seidov, Mar 15 2011 *)
nxt[n_]:=Flatten[{#,2#,3#+2,6#+3}&/@n]; Take[Union[Nest[nxt,{1},5]],100] (* Harvey P. Dale, Feb 06 2015 *)

is(n)=if(n<3,return(n>0)); my(k=n%6); if(k==3, return(is(n\6))); if(k==1, return(0)); if(k==5, return(is(n\3))); if(k!=2, return(is(n/2))); is(n\3) || is(n/2) \\ Charles R Greathouse IV, Sep 15 2015

More terms from Larry Reeves (larryr(AT)acm.org), Oct 16 2000

A077477 Least positive integers not excluded by the rule that if n is present then 2n+1 and 3n+1 are not allowed.

Original entry on oeis.org

1, 2, 6, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 22, 24, 26, 27, 30, 32, 35, 36, 38, 39, 40, 42, 44, 47, 48, 50, 51, 52, 54, 56, 57, 58, 59, 60, 62, 63, 64, 66, 68, 69, 70, 72, 74, 75, 76, 78, 80, 83, 84, 86, 87, 88, 90, 92, 93, 94, 96

Offset: 1

Paul D. Hanna, Nov 08 2002

What is the limit of a(n)/n?

With 10000 terms, one gets a(n)/n -> 1.63317... - Jean-François Alcover Dec 11 2012

			a(5)=9 since 9 is not equal to 2*a(k)+1 nor 3*a(k)+1 for 1<=k<5; and since 9 is allowed to be present, then 19(=2*9+1) and 28(=3*9+1) are to be excluded.

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

Cf. A002977.

import Data.List (delete)
a077477 n = a077477_list !! (n-1)
a077477_list = f [1..] where
   f (x:xs) = x : f (delete (2*x + 1) $ delete (3*x + 1) xs)
-- Reinhard Zumkeller, Sep 14 2011

s = {1}; Do[u = Union[s, 2s + 1, 3s + 1]; c = Complement[Range[u // Last], u] // First; AppendTo[s, c], {10000}]; s (* Jean-François Alcover, Dec 11 2012 *)

A190811 Increasing sequence generated by these rules: a(1)=1, and if x is in a then 2x+1 and 3x are in a.

Original entry on oeis.org

1, 3, 7, 9, 15, 19, 21, 27, 31, 39, 43, 45, 55, 57, 63, 79, 81, 87, 91, 93, 111, 115, 117, 127, 129, 135, 159, 163, 165, 171, 175, 183, 187, 189, 223, 231, 235, 237, 243, 255, 259, 261, 271, 273, 279, 319, 327, 331, 333, 343, 345, 351, 367, 375, 379, 381, 387, 405, 447, 463, 471, 475, 477, 487, 489, 495, 511, 513, 519, 523, 525, 543

Offset: 1

Clark Kimberling, May 20 2011

nonn

See A190803.

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

Cf. A190803.

import Data.Set (singleton, deleteFindMin, insert)
a190811 n = a190811_list !! (n-1)
a190811_list = f $ singleton 1
   where f s = m : (f $ insert (2*m+1) $ insert (3*m) s')
             where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, Jun 01 2011

h = 2; i = 1; j = 3; k = 0; f = 1; g = 9 ;
a = Union[Flatten[NestList[{h # + i, j # + k} &, f, g]]]  (* A190811 *)
b = (a - 1)/2; c = a/3; r = Range[1, 300];
d = Intersection[b, r] (* A002977 *)
e = Intersection[c, r] (* A190857 *)

A276786 a(1) = 1; subsequent terms are defined by the rule that if m is present so are 2m+1 and 3m+1; repeated terms are included; final list is sorted.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Oct 06 2016

nonn

31 is the first number to appear twice. This is a multi-set version of the Klarner-Rado sequence A002977.

20479 is the first number to appear three times. - Rémy Sigrist, Dec 19 2016

Rémy Sigrist, Table of n, a(n) for n = 1..29993 [Terms up to 500000]
J. C. Lagarias, Erdős, Klarner and the 3x + 1 Problem, Amer. Math. Monthly 123 (No. 8, 2016), 753-776. See S# on page 756.
Rémy Sigrist, C99 program for A276786

Cf. A002977. See A276787 for repeated terms.

KR:=proc(lis) local i,j,t1,t2,t3;
t1:=lis; t2:=nops(lis); t3:=[];
for i from 1 to t2 do j:=t1[i];
t3:=[op(t3),2*j+1,3*j+1]; od: sort(t3); end;
t:=[1]; b:=[1];
for n from 1 to 10 do
t:=KR(t); b:=[op(b),op(t)]; b:=sort(b);
od: b;

A088349 a(n) = (A085249(n) - 1)/6.

Original entry on oeis.org

5, 29, 173, 245, 365, 749, 1037, 1469, 2189, 3413, 3773, 4469, 5117, 6005, 6221, 7661, 8813, 8957, 9005, 11117, 13133, 14837, 18029, 20477, 20981, 22133, 22613, 22781, 26813, 29525, 29693, 30197, 30701, 31349, 31469, 36029, 37325, 40277, 45245

Offset: 1

Ray Chandler, Sep 26 2003

nonn

Amiram Eldar, Table of n, a(n) for n = 1..1000

Cf. A002977, A085249, A088350.

seq[max_] := Module[{s = Flatten[NestWhileList[Flatten[{2*# + 1, 3*# + 1}] &, 1, Min[#1] < max &]], t, u}, t = Union[Select[s, # <= max &]]; u = Select[t, MemberQ[t, (# - 1)/2] && MemberQ[t, (# - 1)/3] &]; (u - 1)/6]; seq[300000] (* Amiram Eldar, May 07 2022 *)

A088350 a(n) = (A088349(n)-5)/24.

Original entry on oeis.org

0, 1, 7, 10, 15, 31, 43, 61, 91, 142, 157, 186, 213, 250, 259, 319, 367, 373, 375, 463, 547, 618, 751, 853, 874, 922, 942, 949, 1117, 1230, 1237, 1258, 1279, 1306, 1311, 1501, 1555, 1678, 1885, 1887, 1914, 1959, 2203, 2238, 2251, 2446, 2554, 2623, 2650

Offset: 1

Ray Chandler, Sep 26 2003

nonn

Amiram Eldar, Table of n, a(n) for n = 1..1000

Cf. A002977, A085249, A088349.

seq[max_] := Module[{s = Flatten[NestWhileList[Flatten[{2*# + 1, 3*# + 1}] &, 1, Min[#1] < max &]], t, u, v}, t = Union[Select[s, # <= max &]]; u = Select[t, MemberQ[t, (# - 1)/2] && MemberQ[t, (# - 1)/3] &]; v = (u - 1)/6; (v - 5)/24]; seq[400000] (* Amiram Eldar, May 07 2022 *)

A185661 Smallest set containing 1 and closed under the operations x->2x+1, x->3x+1, x->6x+1.

Original entry on oeis.org

1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 25, 27, 28, 31, 39, 40, 43, 45, 46, 51, 55, 57, 58, 61, 63, 64, 67, 76, 79, 81, 82, 85, 87, 91, 93, 94, 103, 111, 115, 117, 118, 121, 123, 127, 129, 130, 133, 135, 136, 139, 151, 153, 154, 159, 163, 165, 166, 169, 171, 172, 175, 183, 184, 187, 189, 190, 193, 202

Offset: 1

N. J. A. Sloane, Feb 08 2011

This sequence has density zero.
To illustrate the density: there are 2011 terms up to 10^4, 14878 terms up to 10^5, 117671 terms up to 10^6, 913314 terms up to 10^7, 7176461 terms up to 10^8, 56591334 terms up to 10^9, and 445290307 terms up to 10^10. - Charles R Greathouse IV, Jul 09 2017
There are 3560822110 terms up to 10^11, 27907016447 terms up to 10^12, 223533750957 terms up to 10^13, 1772572144707 terms up to 10^14, ..., roughly 7.952916868743154^m/log(10) terms up to 10^m. - Yi Yang, Aug 29 2017

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010. See pp. 6, 280.

G. C. Greubel, Table of n, a(n) for n = 1..5000
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A002977.

terms = 69; Clear[f]; f[n_] := f[n] = With[{lst = NestList[{2 # + 1, 3 # + 1, 6 # + 1}&, 1, n] // Flatten // Union}, If[Length[lst] <= terms, lst, Take[lst, terms]]]; f[1]; f[n = 2]; While[f[n] != f[n-1], Print["n = ", n]; n++]; A185661 = f[n] (* Jean-François Alcover, May 17 2017 *)

list(lim)=my(v=List([1]),i,t); while(i++<=#v, t=2*v[i]+1; if(t>lim, next); listput(v,t); t+=v[i]; if(t>lim, next); listput(v,t); t+=t-1; if(t>lim, next); listput(v,t)); Set(v) \\ Charles R Greathouse IV, Jul 09 2017

list(lim)=my(v=List([1]),m=Map(),t,i); while(i++<=#v, t=2*v[i]+1; if(t>lim, next); if(!mapisdefined(m,t), mapput(m,t,0); listput(v,t)); t+=v[i]; if(t>lim, next); if(!mapisdefined(m,t), mapput(m,t,0); listput(v,t)); t+=t-1; if(t<=lim && !mapisdefined(m,t), mapput(m,t,0); listput(v,t))); m=0; Set(v) \\ Charles R Greathouse IV, Jul 09 2017

Name clarified by Charles R Greathouse IV, Jul 09 2017

A276787 Repeated numbers in A276786.

Original entry on oeis.org

31, 63, 94, 127, 175, 189, 190, 255, 283, 351, 379, 381, 382, 511, 526, 567, 568, 571, 703, 759, 763, 765, 766, 850, 1023, 1039, 1053, 1054, 1135, 1137, 1138, 1143, 1144, 1147, 1407, 1471, 1519, 1527, 1531, 1533, 1534, 1579, 1701, 1702, 1705, 1714, 2047, 2079, 2107, 2109, 2110, 2191, 2271

Offset: 1

N. J. A. Sloane, Oct 06 2016

nonn

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Cf. A002977, A276786.

A350603 Irregular triangle read by rows: row n lists the elements of the set S_n in increasing order, where S_0 = {0}, and S_n is obtained by applying the operations x -> x+1 and x -> 2*x to S_{n-1}.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 32, 33, 34, 36, 40, 48, 64

Offset: 0

N. J. A. Sloane, Jan 12 2022, following a suggestion from James Propp

Theorem: S_n contains Fibonacci(n+2) elements.
Proof from Adam P. Goucher, Jan 12 2022 (Start)
Let 'D' and 'I' be the 'double' and 'increment' operators, acting on 0 from the right. Then every element of S_n can be written as a length-n word over {D,I}. E.g., S_4 contains
   0: DDDD
   1: DDDI
   2: DDID
   3: DIDI
   4: DIDD
   5: IDDI
   6: IDID
   8: IDDD
We can avoid having two adjacent 'I's (because we can transform it into an equivalent word by prepending a 'D' -- which has no effect -- and then replacing the first 'DII' with 'ID').
Subject to the constraint that there are no two adjacent 'I's, these 'II'-less words all represent distinct integers (because of the uniqueness of binary expansions).
So we're left with the problem of enumerating length-n words over the alphabet {I, D} which do not contain 'II' as a substring. These are easily seen to be the Fibonacci numbers because we can check n=0 and n=1 and verify that the recurrence relation holds since a length-n word is either a length-(n-1) word followed by 'D' or a length-(n-2) word followed by 'DI'. QED (End)
From Rémy Sigrist, Jan 12 2022: (Start)
For any m >= 0, the value m first appears on row A056792(m).
For any n > 0: row n minus row n-1 corresponds to row n of A243571.
(End)

			The first few sets S_n are:
[0],
[0, 1],
[0, 1, 2],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4, 5, 6, 8],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 32, 33, 34, 36, 40, 48, 64],
...

Alois P. Heinz, Rows n = 0..21, flattened

Cf. A000045, A000126, A002977, A056792, A122554, A243571, A350604.

T:= proc(n) option remember; `if`(n=0, 0,
      sort([map(x-> [x+1, 2*x][], {T(n-1)})[]])[])
    end:
seq(T(n), n=0..8);  # Alois P. Heinz, Jan 12 2022

T[n_] := T[n] = If[n==0, {0}, {#+1, 2#}& /@ T[n-1] // Flatten //
      Union];
Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, May 06 2022, after Alois P. Heinz *)

from itertools import chain, islice
def A350603_gen(): # generator of terms
    s = {0}
    while True:
        yield from sorted(s)
        s = set(chain.from_iterable((x+1,2*x) for x in s))
A350603_list = list(islice(A350603_gen(),30)) # Chai Wah Wu, Jan 12 2022

Definition made more precise by Chai Wah Wu, Jan 12 2022

cp's OEIS Frontend

A007448 Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(floor(n/3)) ).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

A005658 If n appears so do 2n, 3n+2, 6n+3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Extensions

A077477 Least positive integers not excluded by the rule that if n is present then 2n+1 and 3n+1 are not allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A190811 Increasing sequence generated by these rules: a(1)=1, and if x is in a then 2x+1 and 3x are in a.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A276786 a(1) = 1; subsequent terms are defined by the rule that if m is present so are 2m+1 and 3m+1; repeated terms are included; final list is sorted.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A088349 a(n) = (A085249(n) - 1)/6.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A088350 a(n) = (A088349(n)-5)/24.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A185661 Smallest set containing 1 and closed under the operations x->2x+1, x->3x+1, x->6x+1.

Views

Author

Keywords

Comments

References

A007448 Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2a(floor(n/2)), 3a(floor(n/3)) ).