A106490 Total number of bases and exponents in Quetian Superfactorization of n, excluding the unity-exponents at the tips of branches.

0, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 3, 2, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 4, 1, 2, 2, 3, 1, 3, 1, 3, 3, 2, 1, 4, 2, 3, 2, 3, 1, 3, 2, 3, 2, 2, 1, 4, 1, 2, 3, 3, 2, 3, 1, 3, 2, 3, 1, 4, 1, 2, 3, 3, 2, 3, 1, 4, 3, 2, 1, 4, 2, 2, 2, 3, 1, 4, 2, 3, 2, 2, 2, 3, 1, 3, 3, 4, 1, 3

Offset: 1

Author

Antti Karttunen, May 09 2005 based on Leroy Quet's message ('Super-Factoring' An Integer) posted to SeqFan-mailing list on Dec 06 2003

Keywords

• nonn

Comments

Quetian Superfactorization proceeds by factoring a natural number to its unique prime-exponent factorization (p1^e1 * p2^e2 * ... pj^ej) and then factoring recursively each of the (nonzero) exponents in similar manner, until unity-exponents are finally encountered.

Examples

			a(64) = 3, as 64 = 2^6 = 2^(2^1*3^1) and there are three non-1 nodes in that superfactorization. Similarly, for 360 = 2^(3^1) * 3^(2^1) * 5^1 we get a(360) = 5. a(65536) = a(2^(2^(2^(2^1)))) = 4.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• A. Karttunen, Scheme-program for computing this sequence.
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A028234, A064372, A067029, A106444, A106491, A106492, A106493.

Cf. A276230 (gives first k such that a(k) = n, i.e., this sequence is a left inverse of A276230).

After n=1 differs from A038548 for the first time at n=24, where A038548(24)=4, while a(24)=3.

Programs

Maple

a:= proc(n) option remember; `if`(n=1, 0,
      add(1+a(i[2]), i=ifactors(n)[2]))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 07 2014

Mathematica

a[n_] := a[n] = If[n == 1, 0, Sum[1 + a[i[[2]]], {i,FactorInteger[n]}]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 11 2015, after Alois P. Heinz *)

PARI

A067029(n) = if(n<2, 0, factor(n)[1,2]);
A028234(n) = my(f = factor(n)); if (#f~, f[1, 1] = 1); factorback(f); /* after Michel Marcus */
a(n) = if(n<2, 0, 1 + a(A067029(n)) + a(A028234(n)));
for(n=1, 150, print1(a(n),", ")) \\ Indranil Ghosh, Mar 23 2017, after formula by Antti Karttunen

Formula

Additive with a(p^e) = 1 + a(e).

a(1) = 0; for n > 1, a(n) = 1 + a(A067029(n)) + a(A028234(n)). - Antti Karttunen, Mar 23 2017

Other identities. For all n >= 1:

a(A276230(n)) = n.

a(n) = A106493(A106444(n)).

a(n) = A106491(n) - A064372(n).