A130667 a(1) = 1; a(n) = max{ 5*a(k) + a(n-k) | 1 <= k <= n/2 } for n > 1.

1, 6, 11, 36, 41, 66, 91, 216, 221, 246, 271, 396, 421, 546, 671, 1296, 1301, 1326, 1351, 1476, 1501, 1626, 1751, 2376, 2401, 2526, 2651, 3276, 3401, 4026, 4651, 7776, 7781, 7806, 7831, 7956, 7981, 8106, 8231, 8856, 8881, 9006, 9131, 9756, 9881, 10506, 11131

Offset

1,2

Comments

From Gary W. Adamson, Aug 27 2016: (Start)

The formula of Mar 26 2010 is equivalent to the following: Given the production matrix M below, lim_{k->infinity} M^k as a left-shifted vector generates the sequence.

1, 0, 0, 0, 0, ...

6, 0, 0, 0, 0, ...

5, 1, 0, 0, 0, ...

0, 6, 0, 0, 0, ...

0, 5, 1, 0, 0, ...

0, 0, 6, 0, 0, ...

0, 0, 5, 1, 0, ...

...

The sequence divided by its aerated variant is (1, 6, 5, 0, 0, 0, ...). (End)

Links

Alois P. Heinz, Table of n, a(n) for n = 1..16383

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 32-33.

D. E. Knuth, Problem 11320, The American Mathematical Monthly, Vol. 114, No. 9 (Nov., 2007), p. 835.

Formula

a(2*n) = 6*a(n) and a(2*n+1) = 5*a(n) + a(n+1).

Let r(x) = (1 + 6*x + 5*x^2). Then (1 + 6*x + 11*x^2 + 36*x^3 + ...) = r(x) * r(x^2) * r(x^4) * r(x^8) * ... - Gary W. Adamson, Mar 26 2010

a(n) = Sum_{k=0..n} 5^wt(k), where wt = A000120. - Mike Warburton, Mar 14 2019

a(n) = Sum_{k=0..floor(log_2(n))} 5^k*A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

Maple

a:= proc(n) option remember;
      `if`(n=1, 1, `if`(irem(n, 2, 'm')=0, 6*a(m), 5*a(m)+a(n-m)))
    end:
seq(a(n), n=1..70); # Alois P. Heinz, Apr 09 2012

Mathematica

a[1]=1; a[n_] := a[n] = If[EvenQ[n], 6a[n/2], 5a[(n-1)/2]+a[(n+1)/2]]; Array[a, 50] (* Jean-François Alcover, Feb 13 2015 *)

Prog

(Haskell)
import Data.List (transpose)
a130667 n = a130667_list !! (n-1)
a130667_list = 1 : (concat $ transpose
   [zipWith (+) vs a130667_list, zipWith (+) vs $ tail a130667_list])
   where vs = map (* 5) a130667_list
-- Reinhard Zumkeller, Apr 18 2012
(PARI) first(n)=my(v=vector(n), r, t); v[1]=1; for(i=2, n, r=0; for(k=1, i\2, t=5*v[k]+v[i-k]; if(t>r, r=t)); v[i]=r); v \\ Charles R Greathouse IV, Aug 29 2016
(Magma) [&+[5^(2*k - Valuation(Factorial(2*k), 2)): k in [0..n]]: n in [0..50]]; // Vincenzo Librandi, Mar 15 2019

Crossrefs

Cf. A000120, A006046, A116520, A130665, A360189.

Sequence in context: A100093 A219500 A166702 * A259669 A108698 A002570

Adjacent sequences: A130664 A130665 A130666 * A130668 A130669 A130670

Keyword

nonn

Author

N. J. A. Sloane, based on a message from Don Knuth, Jun 23 2007

Status

approved