login
A277130
Number of planar branching factorizations of n.
7
0, 1, 1, 2, 1, 3, 1, 6, 2, 3, 1, 14, 1, 3, 3, 24, 1, 14, 1, 14, 3, 3, 1, 78, 2, 3, 6, 14, 1, 25, 1, 112, 3, 3, 3, 110, 1, 3, 3, 78, 1, 25, 1, 14, 14, 3, 1, 464, 2, 14, 3, 14, 1, 78, 3, 78, 3, 3, 1, 206, 1, 3, 14, 568, 3, 25, 1, 14, 3, 25, 1, 850, 1, 3, 14, 14
OFFSET
1,4
COMMENTS
A planar branching factorization of n is either the number n itself or a sequence of at least two planar branching factorizations, one of each factor in an ordered factorization of n. - Gus Wiseman, Sep 11 2018
LINKS
A. Knopfmacher, M. E. Mays, A survey of factorization counting functions, International Journal of Number Theory, 1(4):563-581,(2005). See page 15.
FORMULA
a(prime^n) = A118376(n). a(product of n distinct primes) = A319122(n). - Gus Wiseman, Sep 11 2018
EXAMPLE
From Gus Wiseman, Sep 11 2018: (Start)
The a(12) = 14 planar branching factorizations:
12,
(2*6), (3*4), (4*3), (6*2), (2*2*3), (2*3*2), (3*2*2),
(2*(2*3)), (2*(3*2)), (3*(2*2)), ((2*2)*3), ((2*3)*2), ((3*2)*2).
(End)
MATHEMATICA
ordfacs[n_]:=If[n<=1, {{}}, Join@@Table[(Prepend[#1, d]&)/@ordfacs[n/d], {d, Rest[Divisors[n]]}]]
otfs[n_]:=Prepend[Join@@Table[Tuples[otfs/@f], {f, Select[ordfacs[n], Length[#]>1&]}], n];
Table[Length[otfs[n]], {n, 20}] (* Gus Wiseman, Sep 11 2018 *)
PROG
(C)
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 10000
/* Number of planar branching factorizations of n. */
#define lu unsigned long
lu nbr[MAX]; /* number of branching */
lu a, b, d, e; /* temporary variables */
lu n; lu m, p; // factors of n
lu x; // square root of n
void main(unsigned argc, char *argv[])
{
memset(nbr, 0, MAX*sizeof(lu));
for (b=0, n=1; n<MAX; ++n)
{
d=0;
x=sqrt(n);
for (p=2; p<=x; ++p)
{
if ((n%p)==0)
{
m= n/p;
if (m<p) break;
a = nbr[p] * nbr[m];
b += (m==p) ? a : 2*a;
e = nbr[p] * (nbr[m]-1) + (nbr[p]-1) * nbr[m];
d += (m==p) ? e : 2*e;
}
}
nbr[n]=b+d/2;
printf("%lu %lu\n", n, nbr[n]);
b = 1;
}
} /* Daniel Mondot, May 19 2017 */
KEYWORD
nonn
AUTHOR
Michel Marcus, Oct 01 2016
EXTENSIONS
Terms a(65) and beyond from Daniel Mondot, May 19 2017
STATUS
approved