|
|
A130665
|
|
a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().
|
|
28
|
|
|
1, 4, 7, 16, 19, 28, 37, 64, 67, 76, 85, 112, 121, 148, 175, 256, 259, 268, 277, 304, 313, 340, 367, 448, 457, 484, 511, 592, 619, 700, 781, 1024, 1027, 1036, 1045, 1072, 1081, 1108, 1135, 1216, 1225, 1252, 1279, 1360, 1387, 1468, 1549, 1792, 1801, 1828, 1855
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The formula of Mar 26 2010 is equivalent to the left-shifted vector of matrix powers (lim_{k->infinity} M^k), of the production matrix M:
1, 0, 0, 0, 0, 0, ...
4, 0, 0, 0, 0, 0, ...
3, 1, 0, 0, 0, 0, ...
0, 4, 0, 0, 0, 0, ...
0, 3, 1, 0, 0, 0, ...
0, 0, 4, 0, 0, 0, ...
0, 0, 3, 1, 0, 0, ...
...
The sequence divided by its aerated variant is (1, 4, 3, 0, 0, 0, ...). (End)
|
|
LINKS
|
D. E. Knuth, Problem 11320 Amer. Math. Monthly, Vol. 114 No. 9 (Nov 2007) p. 835.
|
|
FORMULA
|
With a different offset: a(1) = 1; a(n) = max { 3*a(k)+a(n-k) | 1 <= k <= n/2 }, for n>1.
a(2n+1) = 4*a(n) and a(2n) = 3*a(n-1) + a(n).
Let r(x) = (1 + 4x + 3x^2), then (1 + 4x + 7x^2 + 16x^3 + ...) =
|
|
MAPLE
|
u:=3; a[1]:=1; M:=30; for n from 1 to M do a[2*n] := (u+1)*a[n]; a[2*n+1] := u*a[n] + a[n+1]; od; t1:=[seq( a[n], n=1..2*M )]; # Gives sequence with a different offset
|
|
MATHEMATICA
|
f[n_] := Sum[3^Count[ IntegerDigits[k, 2], 1], {k, 0, n}]; Array[f, 51, 0] (* Robert G. Wilson v, Jun 28 2010 *)
|
|
PROG
|
(Haskell)
a130665 = sum . map (3 ^) . (`take` a000120_list) . (+ 1)
(Python)
def a(n): # formula version, n=10^10000 takes ~1 second
if n == 0:
return 1
msb = 1 << (n.bit_length() - 1)
(Python)
def a(n): # optimized, n=10^50000 takes ~1 second
n += 1
total = 0
power3 = 1
while n:
log = n.bit_length() - 1
total += power3 << (2*log)
n -= 1 << log
power3 *= 3
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|