A191372 The Sierpinski-Stern triangle.

0, 1, 2, 1, 2, 1, 3, 2, 3, 2, 3, 1, 4, 2, 3, 2, 3, 1, 4, 3, 4, 2, 3, 1, 4, 3, 5, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 3, 5, 2, 5, 3, 4, 1, 6, 3, 6, 4, 5, 2, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 4, 6, 2, 5, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3

Offset: 0

Author

Johannes W. Meijer, Jun 05 2011

Keywords

• nonn
• tabf

Comments

The knight sums of the first and second kind Kn1y(n) = Kn2y(n), y >= 1, see A180662 for their definitions, of Sierpinski's triangle A047999 lead to the formula Kn1y(n) = A002487(n+(2*y-1)) - AS2S2S2(n,d) where the AS2S2S2(n,d) is the infinite concatenation of a S2(T, d = y-1) sequence; see for the first ten S2(T, d) and the first four Kn1y(n) the examples.

The A191372 sequence is the concatenation of all S2(T, d) sequences, d >= 0. The lengths of the S2(T, d) sequences are 2^ceiling(log(d)/log(2)) for d >= 1 while the length of S2(T, d=0) is 1.

Both the concatenation of the S2(T, d = 2^p) sequences, p >= 0, and the concatenation of the S2(T, d = 2^p-1) sequences, p >= 0, lead to Stern’s diatomic series A002487(n), n >= 2.

The differences of the sequences (AS2S2S2(T, 2^p-delta) - AS2S2S2(T, 2^(p-1)-delta)), T from 0 to (2^(p-1) -1) and 1 <= delta <= (2^(p-1)-1) (take care that p <= pmax), lead to sequences that are snippets of A002487 and, surprisingly, their reverse; see the examples.

The row sums of the Sierpinski-Stern triangle are given by the terms of A191487.

Links

• Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117 (7), pp. 581-598, 2010.
• Igor Urbiha, Some properties of a function studied by De Rham, Carlitz and Dijkstra and its relation to the (Eisenstein -) Stern's diatomic sequence, Math. Commun. 6, pp. 181-198, 2002.

Crossrefs

Cf. A047999 (Sierpinski), A002487 (Stern).

Programs

Maple

nmax:=2^5; pmax:=log(nmax)/log(2)-1; A047999:=proc(n,k) option remember; A047999(n,k) :=binomial(n,k) mod 2 end: A002487:=proc(n) option remember; if n<=1 then n elif n mod 2=0 then A002487(n/2); else A002487((n-1)/2)+A002487((n+1)/2); fi; end: d:=0: for n from 0 to nmax-d-1 do Kn1(n,d):= add(A047999(n-k+d, k+d),k=0..floor(n/2)): AS2S2S2(n,d):= A002487(n+1+2*d)-Kn1(n,d): od: for p from 1 to pmax do for d from 2^(p-1) to 2^p do for n from 0 to nmax-d-1 do Kn1(n,d):=add(A047999(n-k+d, k+d),k=0..floor(n/2)): AS2S2S2(n,d):= A002487(n+1+2*d)-Kn1(n,d) od: od: od: S2(0,0):=AS2S2S2(0,0): a(0):=S2(0,0): for d from 1 to 2^pmax do for Tx from 0 to 2^ceil(log(d)/log(2))-1 do S2(Tx,d):=AS2S2S2(Tx,d) od: od: Ty:=0: for d from 1 to 2^pmax do for Tx from 0 to 2^ceil(log(d)/log(2))-1 do Ty:=Ty+1: a(Ty):=S2(Tx,d) od: od: S2(0,0); for d from 1 to 2^pmax do seq(S2(Tx,d), Tx=0..2^ceil(log(d)/ log(2))-1) od; seq(a(n),n=0..Ty);

Formula

The first few S2(T, d) rows of the Sierpinski-Stern triangle are:

d=0: [0]

d=1: [1]

d=2: [2, 1]

d=3: [2, 1, 3, 2]

d=4: [3, 2, 3, 1]

d=5: [4, 2, 3, 2, 3, 1, 4, 3]

d=6: [4, 2, 3, 1, 4, 3, 5, 2]

d=7: [3, 1, 4, 3, 5, 2, 5, 3]

d=8: [4, 3, 5, 2, 5, 3, 4, 1]

d=9: [6, 3, 6, 4, 5, 2, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4]

The first four Kn1y(n), y = d+1, sequences:

Kn11(n) = A002487(n+1) - A000004(n)

Kn12(n) = A002487(n+3) - A000012(n)

Kn13(n) = A002487(n+5) - A000034(n+1)

Kn14(n) = A002487(n+7) - A157810(n+1)

Three (AS2S2S2(T, 2^p-delta) - AS2S2S2(T, 2^(p-1)-delta)) sequences for p=6:

delta = 1: [1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4]

delta = 8: [4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1]

delta = 16: [5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 0]