A277130 Number of planar branching factorizations of n.

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

Daniel Mondot, Table of n, a(n) for n = 1..9999

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 */

Crossrefs

Cf. A277120.

Cf. A000108, A001055, A074206, A118376, A281113, A319122, A319123.

Cf. A277130, A281118, A281119, A292504, A292505, A295279, A295281, A319136, A319137, A319138.

Sequence in context: A145969 A357985 A140352 * A082588 A006241 A336105

Adjacent sequences: A277127 A277128 A277129 * A277131 A277132 A277133

Keyword

nonn

Author

Michel Marcus, Oct 01 2016

Extensions

Terms a(65) and beyond from Daniel Mondot, May 19 2017

Status

approved