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

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

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000

Index entries for sequences computed from exponents in factorization of n

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

Cf. A001221, A001222, A005171.

Sequence in context: A105469 A257857 A339871 * A308427 A252736 A351416

Adjacent sequences: A276803 A276804 A276805 * A276807 A276808 A276809

Keyword

nonn

Author

Yuriy Sibirmovsky, Sep 17 2016

Status

approved