|
|
A276806
|
|
Height of the shortest binary factorization tree of n.
|
|
1
|
|
|
0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 2, 0, 1, 1, 2, 0, 2, 0, 2, 1, 1, 0, 2, 1, 1, 2, 2, 0, 2, 0, 3, 1, 1, 1, 2, 0, 1, 1, 2, 0, 2, 0, 2, 2, 1, 0, 3, 1, 2, 1, 2, 0, 2, 1, 2, 1, 1, 0, 2, 0, 1, 2, 3, 1, 2, 0, 2, 1, 2, 0, 3, 0, 1, 2, 2, 1, 2, 0, 3, 2, 1, 0, 2, 1, 1, 1, 2, 0, 2, 1, 2, 1, 1, 1, 3, 0, 2, 2, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|