A007731 a(n) = a(floor(n/2)) + a(floor(n/3)) + a(floor(n/6)), with a(0) = 1.

1, 3, 5, 7, 9, 9, 15, 15, 17, 19, 19, 19, 29, 29, 29, 29, 31, 31, 41, 41, 41, 41, 41, 41, 55, 55, 55, 57, 57, 57, 57, 57, 59, 59, 59, 59, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 103, 103, 103, 103, 103, 103, 117, 117

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Links

• T. D. Noe, Table of n, a(n) for n = 0..10000
• P. Erdős, A. Hildebrand, A. Odlyzko, P. Pudaite and B. Reznick, The asymptotic behavior of a family of sequences, Pacific J. Math., 126 (1987), pp. 227-241.

Crossrefs

Cf. A083662, A088468, A165704, A165706, A061984.

Programs

Haskell

a007731 n = a007731_list !! n
a007731_list = 1 : (zipWith3 (\u v w -> u + v + w)
   (map (a007731 . (`div` 2)) [1..])
   (map (a007731 . (`div` 3)) [1..])
   (map (a007731 . (`div` 6)) [1..]))
-- Reinhard Zumkeller, Jan 11 2014

Maple

A007731 := proc(n) option remember; if n=0 then RETURN(1) else RETURN( A007731(trunc(n/2))+A007731(trunc(n/3))+A007731(trunc(n/6))); fi; end;
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
      add(a(floor(n/i)), i=[2, 3, 6]))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 27 2023

Mathematica

a[n_] := a[n] = a[Floor[n/2]] + a[Floor[n/3]] + a[Floor[n/6]] ; a[0] = 1; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Mar 06 2014 *)

PARI

a(n)=if(n<5, 2*n+1, a(n\2) + a(n\3) + a(n\6)) \\ Charles R Greathouse IV, Feb 08 2017

Formula

From given link, a(n) is asymptotic to c*n where c = 12/log(432) = 1.97744865... - Benoit Cloitre, Dec 18 2002

Extensions

Name clarified by Michel Marcus, Apr 10 2025