A007448 Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(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

Author

N. J. A. Sloane

Keywords

• easy
• nonn
• nice

Comments

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

References

• 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).

Links

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

Crossrefs

Cf. A002977.

Programs

Haskell

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

Maple

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

Mathematica

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 *)

Python

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