The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A123535 Recurrence from values at floor of a third and two-thirds. 1
 1, 4, 8, 16, 17, 26, 32, 33, 43, 58, 59, 61, 73, 74, 90, 101, 102, 105, 124, 125, 127, 145, 146, 158, 170, 171, 175, 210, 211, 213, 217, 218, 237, 241, 242, 255, 280, 281, 283, 289, 290, 326, 344, 345, 348, 364, 365, 367, 388, 389, 394, 399, 400, 414, 459, 460 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS Roughly analogous to maximal number of comparisons for sorting n elements by binary insertion (A001855). LINKS Paolo Xausa, Table of n, a(n) for n = 0..10000 Wikipedia, Akra-Bazzi method. As of 10 Nov 2006, this article correctly gives the asymptotic, but incorrectly refers to merge-sort rather than binary insertion sort. FORMULA a(0) = 1, for n>0: a(n) = a(floor(n/3)) + a(floor(2n/3)) + n + 1. EXAMPLE a(0) = 1 by definition. a(1) = a(floor(1/3)) + a(floor(2/3)) + 1 + 1 = a(0) + a(0) + 2 = 4. a(2) = a(floor(2/3)) + a(floor(4/3)) + 2 + 1 = a(0) + a(1) + 3 = 8. a(3) = a(floor(3/3)) + a(floor(6/3)) + 3 + 1 = a(1) + a(2) + 4 = 16. a(4) = a(floor(4/3)) + a(floor(8/3)) + 4 + 1 = a(1) + a(2) + 5 = 17. a(5) = a(floor(5/3)) + a(floor(10/3)) + 5 + 1 = a(1) + a(3) + 6 = 26. a(6) = a(floor(6/3)) + a(floor(12/3)) + 6 + 1 = a(2) + a(4) + 7 = 32. MAPLE A123535 := proc(n) options remember ; if n = 0 then RETURN(1) ; else RETURN(A123535(floor(n/3))+A123535(floor(2*n/3))+n+1) ; fi ; end: for n from 0 to 100 do printf("%d, ", A123535(n)) ; od : # R. J. Mathar, Jan 13 2007 MATHEMATICA a[0] = 1; a[n_] := a[n] = a[Floor[n/3]] + a[Floor[2*n/3]] + n + 1; Array[a, 100, 0] (* Paolo Xausa, Jun 27 2024 *) CROSSREFS Cf. A000040, A001768, A001855, A029837, A003071, A000337, A030190, A030308, A061168. Sequence in context: A242349 A309521 A072603 * A312765 A065192 A161994 Adjacent sequences: A123532 A123533 A123534 * A123536 A123537 A123538 KEYWORD easy,nonn AUTHOR Jonathan Vos Post, Nov 11 2006 EXTENSIONS Corrected and extended by R. J. Mathar, Jan 13 2007 a(0)=1 prepended by Paolo Xausa, Jun 27 2024 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 19 14:33 EDT 2024. Contains 374405 sequences. (Running on oeis4.)