A007448 - OEIS

A007448

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

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

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.

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

PROG

(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

(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