login
Except for boundary cases (n <= 3, j = 0, 1, 2^i-1), satisfies a(n) = a(2^i+j) = 2 a(j) + a(j+1), where n = 2^i + j, 0 <= j < 2^i .
6

%I #14 Aug 04 2022 11:00:28

%S 0,1,3,5,8,9,11,17,21,15,11,18,25,29,39,54,53,27,11,18,25,29,39,55,57,

%T 41,40,61,79,97,132,160,129,51,11,18,25,29,39,55,57,41,40,61,79,97,

%U 132,161,133,65,40,61,79,97,133,167,155,122,141,201,255,326,424,448,305,99,11,18

%N Except for boundary cases (n <= 3, j = 0, 1, 2^i-1), satisfies a(n) = a(2^i+j) = 2 a(j) + a(j+1), where n = 2^i + j, 0 <= j < 2^i .

%C The boundary cases are covered by the following formulas:

%C a(n) = 2n-1 if n<=3.

%C a(n) = 1+(3*i+1)*2^(i-2) if j=0.

%C a(n) = 3+ 3*2^(i-1) if j= 1.

%C a(n) = 2*a(j)+a(j+1)-1 if j=2^i-1.

%H David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a> [See A151725, variant]

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%e If written as a triangle:

%e .0,

%e .1,

%e .3, 5,

%e .8, 9, 11, 17,

%e .21, 15, 11, 18, 25, 29, 39, 54,

%e .53, 27, 11, 18, 25, 29, 39, 55, 57, 41, 40, 61, 79, 97, 132, 160,

%e .129, 51, 11, 18, 25, 29, 39, 55, 57, 41, 40, 61, 79, 97, 132, 161, 133, 65, 40, 61, 79, 97, 133, 167, 155, 122, 141, 201, 255, 326, 424, 448,

%e .305, 99, 11, 18, 25, 29, 39, 55, 57, 41, 40, 61, 79, 97, 132, 161, 133, 65, 40, 61, 79, 97, 133, 167, 155, 122, 141, 201, 255, 326, 424, 449, 309, 113, 40, 61, 79, 97, 133, 167, 155, 122, 141, 201, 255, 326, 425, 455, 331, 170, 141, 201, 255, 327, 433, 489, 432, 385, 483, 657, 836, 1076, 1296, 1200,

%e .705, 195, 11, 18, 25, 29, 39, 55, 57, 41, 40, 61, 79, 97, 132, 161, 133, 65, 40, 61, 79, 97, 133, 167, 155, 122, 141, 201, 255, 326, 424, 449, 309, 113, 40, 61, 79, 97, 133, 167, 155, 122, 141, 201, 255, 326, 425, 455, 331, 170, 141, 201, 255, 327, 433, 489, 432, 385, 483, 657, 836, 1076, 1296, 1201, 709, 209, 40, 61, 79, 97, 133, 167, 155, 122, 141, 201, 255, 326, 425, 455, 331, 170, 141, 201, 255, 327, 433, 489, 432, 385, 483, 657, 836, 1076, 1297, 1207, 731, 266, 141, 201, 255, 327, 433, 489, 432, 385, 483, 657, 836, 1077, 1305, 1241, 832, 481, 483, 657, 837, 1087, 1355, 1410, 1249, 1253, 1623, ...

%e then the rows (omitting the first two terms of each row) converge to A151748.

%p A151747 := proc(n) option remember; local i, j;

%p if (n <= 0) then

%p 0;

%p elif (n <= 3) then

%p 2*n-1;

%p else

%p i := floor(log(n)/log(2));

%p j := n - 2^i;

%p if (j = 0) then (3*i+1)*2^(i-2)+1;

%p elif (j = 1) then 3*2^(i-1)+3;

%p elif (j = 2^i-1) then 2*procname(j)+procname(j+1)-1;

%p else 2*procname(j)+procname(j+1);

%p end if;

%p end if;

%p end proc;

%t a[n_] := a[n] = Module[{i, j}, Which[n <= 0, 0, n <= 3, 2n-1, True, i = Floor[Log2[n]]; j = n-2^i; Which[j == 0, (3i+1)*2^(i-2)+1, j == 1, 3*2^(i-1)+3, j == 2^i-1, 2a[j] + a[j+1] - 1,True, 2a[j] + a[j+1]]]];

%t Table[a[n], {n, 0, 67}] (* _Jean-François Alcover_, Aug 04 2022, from Maple code *)

%Y Cf. A151725, A151726, A151735, A151748, A139250, A170879.

%Y The first column gives A170881.

%K nonn,tabf

%O 0,3

%A _David Applegate_, Jun 16 2009