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$ Commented Aug 25, 2017 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$ Commented Aug 25, 2017 at 7:31
  • $\begingroup$ @ciao I need to generate the whole sequence from 1 to N. $\endgroup$ Commented Aug 25, 2017 at 8:12
  • $\begingroup$ @mathe - then see my answer. $\endgroup$ Commented Aug 25, 2017 at 8:13
  • $\begingroup$ @mathe - did answer address issue ? $\endgroup$ Commented Aug 26, 2017 at 2:17

1 Answer 1

Reset to default
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 and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.