A151842 a(3n) = n, a(3n+1) = 2n+1, a(3n+2) = n+1.

0, 1, 1, 1, 3, 2, 2, 5, 3, 3, 7, 4, 4, 9, 5, 5, 11, 6, 6, 13, 7, 7, 15, 8, 8, 17, 9, 9, 19, 10, 10, 21, 11, 11, 23, 12, 12, 25, 13, 13, 27, 14, 14, 29, 15, 15, 31, 16, 16, 33, 17, 17, 35, 18, 18, 37, 19, 19, 39, 20, 20, 41, 21, 21, 43, 22, 22, 45, 23, 23, 47

Offset: 0

Author

Shane Geiger (shane.geiger(AT)gmail.com), Jul 14 2009

Keywords

• nonn
• easy

Comments

Take a list of numbers (like 0,1,2,3,4,5,...) and then pair them up like this: (0,1)(1,2),(2,3),(3,4)... Then sum each pair, and insert the sum between the numbers, like this: (0,1,1), (1,3,2), (2,5,3), ... Finally, remove the parentheses: 0,1,1,1,3,2,2,5,3,...

This mirrors the pattern used to make a dragon curve fractal. You take two points, then find one to insert between them. In the next iteration, you take those three points and find two numbers to insert between them. (Rather than summing the two numbers, a different function is used to find a point relative to two other points.)

a(n) is the number of rises in all compositions of n + 2 with parts in {1,2} and adjacent differences in {-1,1}. - John Tyler Rascoe, Apr 29 2025

Examples

			G.f. = x + x^2 + x^3 + 3*x^4 + 2*x^5 + 2*x^6 + 5*x^7 + 3*x^8 + 3*x^9 + ... - _Michael Somos_, Aug 12 2009
		

Links

• Amiram Eldar, Table of n, a(n) for n = 0..10000
• Index entries for linear recurrences with constant coefficients, signature (0,0,2,0,0,-1).

Crossrefs

See A076118 for a version with signs.

Cf. A002264, A003881, A008133.

Programs

Magma

I:=[0,1,1,1,3,2]; [n le 6 select I[n] else 2*Self(n-3)-Self(n-6): n in [1..80]]; // Vincenzo Librandi, Feb 14 2015

Mathematica

CoefficientList[Series[x (1 + x) (1 + x^2) / ((x - 1)^2 (1 + x + x^2)^2), {x, 0, 70}], x] (* Vincenzo Librandi, Feb 14 2015 *)

PARI

{a(n) = kronecker(9, n) + (n\3) * [1, 2, 1][n%3 + 1]} /* Michael Somos, Aug 12 2009 */

Python

def pairup(x): return [x[i:i+2] for i in range(len(x)-1)]
def combine(vals): return sum(vals)
def expand(L,fn): return [(x[0],fn(x),x[1]) for x in pairup(L)]
L = list(range(20))
print(expand(L,combine))

Formula

From R. J. Mathar, Jul 14 2009: (Start)

G.f.: x*(1+x)*(1+x^2)/((x-1)^2*(1+x+x^2)^2).

a(n) = 2*a(n-3) - a(n-6). (End)

From Michael Somos, Aug 12 2009: (Start)

G.f.: x * (1 - x^4) / ((1 - x) * (1 - x^3)^2).

Euler transform of length 4 sequence [ 1, 0, 2, -1]. (End)

-a(n) = a(-1-n). - Michael Somos, Nov 11 2013

From Ridouane Oudra, Nov 23 2024: (Start)

a(n) = 5*n/6 + n^2/2 - n^3/3 + (2*n^2 - n - 3/2)*floor(n/3) - (3*n + 3/2)*floor(n/3)^2.

a(n) = t(n+2)*t(n+3) - t(n)*t(n+1), where t(n) = floor(n/3) = A002264(n).

a(n) = A008133(n+2) - A008133(n). (End)

Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/4 (A003881). - Amiram Eldar, May 10 2025

Extensions

More terms from Vincenzo Librandi, Feb 14 2015