A123535 - OEIS

%I #17 Jun 27 2024 16:21:28

%S 1,4,8,16,17,26,32,33,43,58,59,61,73,74,90,101,102,105,124,125,127,

%T 145,146,158,170,171,175,210,211,213,217,218,237,241,242,255,280,281,

%U 283,289,290,326,344,345,348,364,365,367,388,389,394,399,400,414,459,460

%N Recurrence from values at floor of a third and two-thirds.

%C Roughly analogous to maximal number of comparisons for sorting n elements by binary insertion (A001855).

%H Paolo Xausa, <a href="/A123535/b123535.txt">Table of n, a(n) for n = 0..10000</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Akra-Bazzi_method">Akra-Bazzi method</a>. As of 10 Nov 2006, this article correctly gives the asymptotic, but incorrectly refers to merge-sort rather than binary insertion sort.

%F a(0) = 1, for n>0: a(n) = a(floor(n/3)) + a(floor(2n/3)) + n + 1.

%e a(0) = 1 by definition.

%e a(1) = a(floor(1/3)) + a(floor(2/3)) + 1 + 1 = a(0) + a(0) + 2 = 4.

%e a(2) = a(floor(2/3)) + a(floor(4/3)) + 2 + 1 = a(0) + a(1) + 3 = 8.

%e a(3) = a(floor(3/3)) + a(floor(6/3)) + 3 + 1 = a(1) + a(2) + 4 = 16.

%e a(4) = a(floor(4/3)) + a(floor(8/3)) + 4 + 1 = a(1) + a(2) + 5 = 17.

%e a(5) = a(floor(5/3)) + a(floor(10/3)) + 5 + 1 = a(1) + a(3) + 6 = 26.

%e a(6) = a(floor(6/3)) + a(floor(12/3)) + 6 + 1 = a(2) + a(4) + 7 = 32.

%p 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

%t a[0] = 1; a[n_] := a[n] = a[Floor[n/3]] + a[Floor[2*n/3]] + n + 1;

%t Array[a, 100, 0] (* _Paolo Xausa_, Jun 27 2024 *)

%Y Cf. A000040, A001768, A001855, A029837, A003071, A000337, A030190, A030308, A061168.

%K easy,nonn

%O 0,2

%A _Jonathan Vos Post_, Nov 11 2006

%E Corrected and extended by _R. J. Mathar_, Jan 13 2007

%E a(0)=1 prepended by _Paolo Xausa_, Jun 27 2024