cp's OEIS Frontend

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.

%I A334789 #19 May 28 2020 03:02:43
%S A334789 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,
%T A334789 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,
%U A334789 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
%N 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.
%C A334789 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.
%C A334789 2^log*(n) arises in computational complexity measures for Fürer's multiplication algorithm.
%H A334789 Kevin Ryde, <a href="/A334789/b334789.txt">Table of n, a(n) for n = 1..8192</a>
%H A334789 Martin Fürer, <a href="http://web.archive.org/web/1id_/http://www.cse.psu.edu/~furer/Papers/mult.pdf">Faster integer multiplication</a>, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 11-13 June 2007.  And <a href="http://dx.doi.org/10.1137/070711761">in SIAM Journal of Computing</a>, volume 30, number 3, 2009, pages 979-1005.
%H A334789 <a href="/index/Di#divseq">Index to divisibility sequences</a>
%F A334789 a(n) = 2^A001069(n).
%F A334789 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
%o A334789 (PARI) a(n)=my(t);while(n>1,n=log(n+.5)\log(2);t++);2^t \\ _Charles R Greathouse IV_, Apr 09 2012
%o A334789 (PARI) a(n) = my(c=0); while(n>1, n=logint(n,2);c++); 1<<c; \\ _Kevin Ryde_, May 18 2020
%Y A334789 Cf. A001069, A014221 (indices of new highs), A063511, A211667.
%K A334789 easy,nonn
%O A334789 1,2
%A A334789 _Kevin Ryde_, May 10 2020