A276806 Height of the shortest binary factorization tree of n.

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

Offset: 1

Author

Yuriy Sibirmovsky, Sep 17 2016

Keywords

• nonn

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.

To compute the terms A001222 and A001221 could be used.

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).

Examples

			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
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A001221, A001222, A005171.

Programs

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)&&(dA276806(d),A276806(n/d)); if(!m || (h < m),m=h)))); m; }; \\ Antti Karttunen, Aug 12 2017

Formula

a(n^2) = a(n) + 1.