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.

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

Offset: 1

Author

Kevin Ryde, May 10 2020

Keywords

• easy
• nonn

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, 11-13 June 2007. And in SIAM Journal of Computing, volume 30, number 3, 2009, pages 979-1005.
• Index to divisibility sequences

Crossrefs

Cf. A001069, A014221 (indices of new highs), A063511, A211667.

Programs

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<Kevin Ryde, May 18 2020

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