2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ You can get a slight improvement by using BitLength@n-1 instead of Floor@Log2@N@n $\endgroup$
    – Lukas Lang
    Aug 25 '17 at 7:29
  • $\begingroup$ 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? $\endgroup$
    – ciao
    Aug 25 '17 at 7:31
  • $\begingroup$ @ciao I need to generate the whole sequence from 1 to N. $\endgroup$
    – matrix89
    Aug 25 '17 at 8:12
  • $\begingroup$ @mathe - then see my answer. $\endgroup$
    – ciao
    Aug 25 '17 at 8:13
  • $\begingroup$ @mathe - did answer address issue ? $\endgroup$
    – ciao
    Aug 26 '17 at 2:17
5
$\begingroup$

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}]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.