[seqfan] 'Super-Factoring' An Integer, i.e. Matula-Goebel numbers.

[Antti Karttunen]

 > Date: Sat, 6 Dec 03 19:03:43 -0700
 > From: Leroy Quet <qq-quet at mindspring.com>
 > To: seqfan at ext.jussieu.fr
 > Subject: 'Super-Factoring' An Integer
 >
 > I posted here about some sequence a while back where the sequence's
 > closed-form was:
 >
 > c(m) =
 >
 > the number of e()'s where:
 >
 > e(e(e(...e(m)...))) = 0,
 >
 > and e(m) is a nonnegative integer such that:
 > 2^e(m) is the highest power of 2 dividing m.

i.e. e(m) is A007814(m)
and c(m) you have now submitted as A089242,
i.e. #iterates_of_A007814 until a zero is encountered.
(the "A007814-persistence of n", or maybe + 1, depending
on how you count).

 > This sequence had a very interesting palindromic structure which was
 > generated recursively.
 > (I called this sequence's symmetric structure "super-palindromic".)
 >
 >
 > I am wondering now about extending, in a way, the idea somewhat of the
 > above
 > c-sequence.
 >
 > If m =
 >
 > product{p=primes, p|m} p^e(p,m),
 >
 > where e(p,m) is always a positive integer,
 > we can factor e(p,m) still as:
 >
 > e(p,m) = product{q=primes, q|e(p,m)} q^e(q,e(p,m)).
 >
 > And we can do this, in a tree-like manner (I guess), until we get a 1 at
 > the 'leaves' of the tree.
 >
 > A small example:
 >
 > m =
 >
 >
 > 2^(2^(3^1)*3^(2^1*5^(2^1)))*5^(2^(5^(2^1))*7^1)
 >
 > (Oh, forgive me, please,
 > if I messed the parentheses..)

Provided that I understood you correctly, that is, that
your e(p,m) is the exponent of prime p, in the prime-factorization of
integer m, then these are variants of encodings represented in:

http://www.research.att.com/projects/OEIS?Anum=A075166

which of course were inspired by the "Riffs & Rotes" thread initiated
by Jon Awbrey on this list, something like two years ago.
(see how to download the archives at http://www.seqfan.net/
and search for keywords like Riff, Rote, Gobel, Goebel, Göbel, Dana 
Scott, A075166, etc.)
I remember that Jon even gave a link to a paper (in some journal of logics?)
that represented a scheme like yours (without that exponent+1 correction
step that I use in A075166 to make it one-to-one correspondence
with the rooted plane general trees of Catalan family).


On the other hand, if you were recursing ("super-factoring") with prime's
index (i.e. http://www.research.att.com/projects/OEIS?Anum=A049084 )
instead of its exponent, you would get structures isomorphic with unlabeled,
non-oriented, rooted general trees, which are counted by the sequence:

ID Number: A000081 <http://www.research.att.com/projects/OEIS?Anum=A000081> (Formerly M1180 and N0454)
URL:       http://www.research.att.com/projects/OEIS?Anum=A000081
Sequence <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/showtabl.cgi?A=A000081&format=4&height=0&seq=,0,1,1,2,4,9,20,48,115,286,719,1842,4766,12486,32973,87811,235381,634847,1721159,4688676,12826228,35221832,97055181,268282855,743724984,2067174645,5759636510,16083734329,45007066269,126186554308,354426847597>:  0,1,1,2,4,9,20,48,115,286,719,1842,4766,12486,32973,87811,
           235381,634847,1721159,4688676,12826228,35221832,97055181,
           268282855,743724984,2067174645,5759636510,16083734329,
           45007066269,126186554308,354426847597
Name:      Rooted trees with n nodes (or connected functions with a fixed point).


That encoding was probably first discovered by:

D. Matula,A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968),

and then twelve years later, apparently independently by:

F. Göbel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.


See also:


    Deducing properties of trees from their Matula numbers


    Ivan Gutman and Yeong-Nan Yeh


    available on-line at http://www.emis.de/journals/PIMB/067/3.html


Terveisin,

Antti Karttunen

 >
 > But, in any case, if we were to extend (with some modifications) the
 > original c-sequence to involving all the primes (not just 2), we might
 > ask here for:
 >
 > C(m) = number of primes (and 1's) in *total* factorization of m.
 >
 > So, for the m above, whatever that is...,
 > C(m) = 17.
 >
 > (I bet this is not a very fast rising sequence...)
 >
 >
 >   As for this Big-C sequence,...
 >
 > First, we have the two related sequences depending on whether we want to
 > count the one's too or just the primes.
 >
 > Second, C(m) can be generated recursively.
 >
 > C(m) = sum{p|m} (1 + C(e(p,m))),
 >
 > where C(0) = 0 if the 1's are not counted, and is 1 if the one's are
 > counted.
 >
 > (And the sum is over the distinct prime divisors, p, of m.)
 >
 > 3rd, we can generalize the idea so that C(m) = the sum of elements from
 > {a(p)}, a sequence with prime indexes.
 > If we want a(p) to be added every time that the prime p appears in the
 > 'super-factorization' of m, we might generate the C-sequence by the
 > recursion:
 > (the 'super-factorization' includes the factorization of the exponents
 > {and continuing...} as well in the prime-factorization of an integer.)
 >
 > C(1) = what to add each time a 1 appears at the factorization's "leaves"
 > (or = 0 if the 1's are ignored).
 >
 > C(m) = sum{p|m} (a(p) + C(e(p,m))).
 >
 >
 > [So,  also,
 > sum{m=1 to n} C(m) =
 >
 > sum{m=1 to n} sum{p=primes <= n/m} (a(p) + C(e(p,m)+1))]
 >
 >
 >
 >
 > Some examples (figured by hand, so may be wrong):
 >
 > a(p) = 1, C(1) = 1:
 > 1, 2, 2, 3, 2, 4, 2, 3, 3, 4, 2, 5, 2, 4, 4 ,4
 >
 > a(p) = 1, C(1) = 0:
 > 0, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3
 >
 > a(p) = p, C(1) = 0:
 > 0, 2, 3, 4, 5, 5, 7, 5, 5, 7, 11, 7, 13, 9, 8, 6
 >
 > a(p) = ln(p), C(0) = 0:
 >
 > exp(C(m)) -> 1, 2, 3, 4, 5, 6, 7, 6, 6, 10, 11, 12, 13, 14, 15, 8
 >
 > a(p) = C(pi(p)), C(0) = 1:
 > (pi(p) = order of prime p)
 >
 > 1, 2, 3, 4, 4, 7, 5, 5, 5, 8, 6, 8
 >
 >
 > Final questions:
 >
 >
 > How many m's total can be composed from
 > (have a super-factorization consisting of)
 >
 > b(2) 2's , b(3) 3's, b(5) 5's, ...
 > for a given finite sequence of {b(p)}, p = primes?
 >
 > (this seems to be a combinatorial problem mostly.)
 >
 > In each 'branching' of the prime-factorization 'tree', each prime occurs
 > at most once. (But any prime can reoccur at the same level of branching,
 > but only if it has another parent-branch.)
 >
 >
 > And, is there anything remotely symmetric about the structure of C for
 > any particular nontrivial sequence {a(p)}??
 >
 > thanks,
 > Leroy
 > Quet
 >