# efficiently method for generating a sequence

The sequence is defined as $a(1)=1,a(n)=a(n-1)+a\left(\left\lfloor \log _2(n)\right\rfloor \right)$

A natural way do this is

ClearAll[a];
a[1] = 1;
a[n_] := a[n] = a[n - 1] + a[Floor@Log2@N@n];
Table[a[i], {i, 1, 2^20}]; // AbsoluteTiming


It's not very quickly enough. I think there is a iteration solution using Nest or Fold,but I can't get it.

• You can get a slight improvement by using BitLength@n-1 instead of Floor@Log2@N@n Aug 25 '17 at 7:29
• Do you need to generate the whole sequence from 1 to some N, or do you want a faster way to generate results for some large distinct arguments?
– ciao
Aug 25 '17 at 7:31
• @ciao I need to generate the whole sequence from 1 to N. Aug 25 '17 at 8:12
• @mathe - then see my answer.
– ciao
Aug 25 '17 at 8:13
– ciao
Aug 26 '17 at 2:17

This will be much much faster:

a3[1]={1};
a3[m_] := Module[{t = 2^Range[Floor[Log2[m]]], a},

a[1] = 1;
a[n_] := a[n] = a[n - 1] + a[Floor[Log2[n]]];

t[[-1]] = m - Tr[Most@t] - 1;
Accumulate@Prepend[Join @@ MapThread[ConstantArray, {a /@ Range[Length@t], t}], 1]];


Using:

a3[X]


will produce the same output as

Table[a[i], {i, 1, X}]