OFFSET
1,8
COMMENTS
Among all possible binary factorization trees of n we choose a tree with minimal height. The choice may not be unique. a(n) gives the height of the chosen tree.
The positions at which numbers (1,2,3) first appear are respectively (4,8,32). The latter sequence can be described by the formula b(n) = 2^(2^(n-1) + 1).
LINKS
FORMULA
a(n^2) = a(n) + 1.
EXAMPLE
a(12) = 2 since 12 cannot be factored in a binary factorization tree of height less than 2, but it can be factored in a tree of height 2, e.g.,
12
/ \
4 3
/ \
2 2
Similarly, a(16) = 2:
16
/ \
/ \
4 4
/ \ / \
2 2 2 2
and a(40) = 2:
40
/ \
/ \
4 10
/ \ / \
2 2 2 5
and a(84) = 2:
84
/ \
/ \
4 21
/ \ / \
2 2 3 7
PROG
(PARI) a(n)=if(n>1, my(b=bigomega(n), c=(2^logint(b, 2)!=b)); logint(b, 2)+c, 0) \\ David A. Corneth, Oct 01 2016
(PARI) A276806(n) = { my(m=0, h); if((1==n)||isprime(n), 0, fordiv(n, d, if((d>1)&&(d<n), h = 1+max(A276806(d), A276806(n/d)); if(!m || (h < m), m=h)))); m; }; \\ Antti Karttunen, Aug 12 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Yuriy Sibirmovsky, Sep 17 2016
STATUS
approved