cp's OEIS Frontend

A276806 Height of the shortest binary factorization tree of n.

%I A276806 #26 Aug 12 2017 12:07:43
%S A276806 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,
%T A276806 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,
%U A276806 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
%N A276806 Height of the shortest binary factorization tree of n.
%C A276806 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.
%C A276806 To compute the terms A001222 and A001221 could be used.
%C A276806 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).
%H A276806 Antti Karttunen, <a href="/A276806/b276806.txt">Table of n, a(n) for n = 1..10000</a>
%H A276806 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A276806 a(n^2) = a(n) + 1.
%e A276806 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.,
%e A276806       12
%e A276806       / \
%e A276806      4   3
%e A276806     / \
%e A276806    2   2
%e A276806 Similarly, a(16) = 2:
%e A276806        16
%e A276806        / \
%e A276806       /   \
%e A276806      4     4
%e A276806     / \   / \
%e A276806    2   2 2   2
%e A276806 and a(40) = 2:
%e A276806        40
%e A276806        / \
%e A276806       /   \
%e A276806      4    10
%e A276806     / \   / \
%e A276806    2   2 2   5
%e A276806 and a(84) = 2:
%e A276806        84
%e A276806        / \
%e A276806       /   \
%e A276806      4    21
%e A276806     / \   / \
%e A276806    2   2 3   7
%o A276806 (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
%o A276806 (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
%Y A276806 Cf. A001221, A001222, A005171.
%K A276806 nonn
%O A276806 1,8
%A A276806 _Yuriy Sibirmovsky_, Sep 17 2016