|
%I #37 Feb 24 2021 02:48:18
%S 0,1,4,7,10,16,25,31,34,40,49,58,70,91,115,127,130,136,145,154,166,
%T 187,211,226,238,259,286,316,361,427,487,511,514,520,529,538,550,571,
%U 595,610,622,643,670,700,745,811,871,898,910,931
%N Toothpick sequence in the first three quadrants.
%C From _Omar E. Pol_, Oct 01 2011: (Start)
%C On the infinite square grid, consider only the first three quadrants and count only the toothpicks of length 2.
%C At stage 0, we start from a vertical half toothpick at [(0,0),(0,1)]. This half toothpick represents one of the two components of the first toothpick placed in the toothpick structure of A139250, so a(0) = 0.
%C At stage 1, we place an orthogonal toothpick of length 2 centered at the end, so a(1) = 1. Also we place half toothpick at [(0,-1),(1,-1)]. This last half toothpick represents one of the two components of the third toothpick placed in the toothpick structure of A139250.
%C At stage 2, we place three toothpicks, so a(2) = 1+3 = 4.
%C In each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end.
%C The sequence gives the number of toothpicks after n stages. A153004 (the first differences) gives the number of toothpicks added to the structure at n-th stage.
%C Note that this sequence is different from the toothpick "corner" sequence A153006. For more information see A139250. (End)
%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>
%H <a href="/index/To#toothpick">Index entries for sequences related to toothpick sequences</a>
%F a(n) = (A139250(n+1)-3)*3/4 + 1, if n >= 1.
%F From _Omar E. Pol_, Oct 01 2011: (Start)
%F a(n) = A139250(n+1) - A152998(n) + A153000(n-1) - 1, if n >= 1.
%F a(n) = A139250(n+1) - A153000(n-1) - 2, if n >= 1.
%F a(n) = A152998(n) + A153000(n-1), if n >= 1.
%F (End)
%t A139250[n_] := A139250[n] = Module[{m, k}, If[n == 0, Return[0]]; m = 2^(Length[IntegerDigits[n, 2]] - 1); k = (2 m^2 + 1)/3; If[n == m, k, k + 2 A139250[n - m] + A139250[n - m + 1] - 1]];
%t a[n_] := If[n == 0, 0, (3/4)(A139250[n + 1] - 3) + 1];
%t a /@ Range[0, 49] (* _Jean-François Alcover_, Apr 06 2020 *)
%o (Python)
%o def msb(n):
%o t=0
%o while n>>t>0: t+=1
%o return 2**(t - 1)
%o def a139250(n):
%o k=(2*msb(n)**2 + 1)/3
%o return 0 if n==0 else k if n==msb(n) else k + 2*a139250(n - msb(n)) + a139250(n - msb(n) + 1) - 1
%o def a(n): return 0 if n==0 else (a139250(n + 1) - 3)*3/4 + 1
%o [a(n) for n in range(51)] # _Indranil Ghosh_, Jul 01 2017
%Y Cf. A139250, A139251, A152968, A152978, A152998, A153000, A153004.
%K nonn
%O 0,3
%A _Omar E. Pol_, Jan 02 2009
|
