

A334789


a(n) = 2^log_2*(n) where log_2*(n) = A001069(n) is the number of log_2(log_2(...log_2(n))) iterations needed to reach < 2.


2



1, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Differs from A063511 for n>=256. For example a(256)=8 whereas A063511(256)=16. The respective exponent sequences are A001069 (for here) and A211667 (for A063511) which likewise differ for n>=256.
2^log*(n) arises in computational complexity measures for Fürer's multiplication algorithm.


LINKS

Kevin Ryde, Table of n, a(n) for n = 1..8192
Martin Fürer, Faster integer multiplication, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 1113 June 2007. And in SIAM Journal of Computing, volume 30, number 3, 2009, pages 9791005.
Index to divisibility sequences


FORMULA

a(n) = 2^A001069(n).
a(n) = 2^lg*(n), where lg*(x) = 0 if x <= 1 and 1 + lg*(log_2(x)) otherwise.  Charles R Greathouse IV, Apr 09 2012


PROG

(PARI) a(n)=my(t); while(n>1, n=log(n+.5)\log(2); t++); 2^t \\ Charles R Greathouse IV, Apr 09 2012
(PARI) a(n) = my(c=0); while(n>1, n=logint(n, 2); c++); 1<<c; \\ Kevin Ryde, May 18 2020


CROSSREFS

Cf. A001069, A014221 (indices of new highs), A063511, A211667.
Sequence in context: A267649 A071805 A063511 * A283207 A164717 A164715
Adjacent sequences: A334786 A334787 A334788 * A334790 A334791 A334792


KEYWORD

easy,nonn


AUTHOR

Kevin Ryde, May 10 2020


STATUS

approved



