

A063511


a(n) = a(floor(square root(n))) * 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

From Kevin Ryde, May 11 2020: (Start)
The sqrt steps in the definition are equivalent to A211667 but here factors of 2 instead of counting, so a(n) = 2^A211667(n). A211667 is a double logarithm and the effect of power 2^ is to turn the second into a rounding. So a(n) is the bit length of n (see A070939) increased to the next power of 2 if not already a power of 2. Each n = 2^(2^k) is a new high a(n) = 2^(k+1), since such an n is bit length 2^k+1.
In a microcomputer, it's common for machine words to be powerof2 sizes such as 16, 32, 64, 128 bits. a(n) can be thought of as the word size needed to contain integer n. Some algorithms by their nature expect powerof2 sizes, for example Schönhage and Strassen's big integer multiplication.
This sequence differs from A334789 (2^log*(n)) for n>=256. For example a(256)=16 whereas A334789(256)=8. The respective exponent sequences are A211667 (for here) and A001069 (for A334789) which likewise differ for n>=256.
(End)


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, June 1113 2007. And in SIAM Journal of Computing, volume 30, number 3, 2009, pages 9791005. (See size "n" calculation at the start of Algorithm IntegerMultiplication.)
Index to divisibility sequences


FORMULA

a(n) = 2^A211667(n) = 2^ceiling(log_2(log_2(n+1))).  Kevin Ryde, May 11 2020


PROG

(PARI) a(n) = if(n==1, 1, 2<<logint(logint(n, 2), 2)); \\ Kevin Ryde, May 11 2020


CROSSREFS

Cf. A001146 (indices of new highs), A334789.
Sequence in context: A179932 A267649 A071805 * A334789 A283207 A164717
Adjacent sequences: A063508 A063509 A063510 * A063512 A063513 A063514


KEYWORD

easy,nonn


AUTHOR

Reinhard Zumkeller, Jul 30 2001


EXTENSIONS

Formula and code by Charles R Greathouse IV moved to A334789 where they apply.  Kevin Ryde, May 11 2020


STATUS

approved



