cp's OEIS Frontend

A277120 Number of branching factorizations of n.

%I A277120 #95 Aug 06 2024 09:36:34
%S A277120 0,1,1,2,1,3,1,5,2,3,1,11,1,3,3,15,1,11,1,11,3,3,1,45,2,3,5,11,1,19,1,
%T A277120 51,3,3,3,62,1,3,3,45,1,19,1,11,11,3,1,195,2,11,3,11,1,45,3,45,3,3,1,
%U A277120 113,1,3,11,188,3,19,1,11,3,19,1,345,1,3,11,11,3
%N A277120 Number of branching factorizations of n.
%C A277120 Per the formula, a(n) = 1 at prime n. As the sequence extends, additional values become more frequent than 1. These values can be characterized, for example, a(n) = 19 is seen at n corresponding to A007304, a(n) = 3 is seen at n corresponding to A006881, a(n) = 113 is seen at n corresponding to A085987. - _Bill McEachen_, Dec 28 2023
%C A277120 From _Antti Karttunen_, Jan 02 2024: (Start)
%C A277120 The value of a(n) depends only on the prime signature of n. In other words, for all i, j >= 1, it holds that A101296(i) = A101296(j) => a(i) = a(j). Moreover, it seems that the converse proposition also holds, that for all i, j >= 1, a(i) = a(j) => A101296(i) = A101296(j), i.e., for each distinct prime signature there exists a distinct value of a(n). This has been empirically checked up to the first 21001 prime signatures in A025487 (see A366884), and can be proved if one can show that the latter sequence (equally: A366377) is injective. If this conjecture holds, it would imply an unlimited number of statements like those given in the previous comment (see the formula section of A101296).
%C A277120 Questions: Are there any terms of the form 10k+4 or 10k+6? What is the asymptotic density of terms of the form 10k+5 (those ending with digit "5")? Compare to the data shown in A366884.
%C A277120 For squarefree n > 1, a(n) is never even, and apparently, never a multiple of five. See comments in A052886.
%C A277120 (End)
%H A277120 Daniel Mondot, <a href="/A277120/b277120.txt">Table of n, a(n) for n = 1..9999</a>
%H A277120 H.-K. Hwang, <a href="https://web.archive.org/web/20220220210857/http://algo.stat.sinica.edu.tw/hk/files/2005_07/pdf/Theoremes_limites_pour_les_structures_combinatories.pdf">Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques</a>, PhD thesis, in Ecole Polytechnique, 1994. See page 198.
%H A277120 A. Knopfmacher, M. E. Mays, <a href="https://citeseerx.ist.psu.edu/pdf/d7ed31ad7c11cad37442838d6614f658af539ef5">A survey of factorization counting functions</a>, International Journal of Number Theory, 1(4):563-581,(2005). See page 14.
%H A277120 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A277120 a(1) = 0; for n > 1, a(n) = 1 + Sum_{d|n, 1 < d < n} a(d)*a(n/d). - _Antti Karttunen_, Nov 02 2016, after _Daniel Mondot_'s C program, simplified Dec 30 2023.
%F A277120 For all n >= 1, a(prime^n) = A007317(n), and a(product of n distinct primes) = A052886(n). - _Antti Karttunen_, Dec 31 2023
%e A277120 In this scheme, the following factorizations of 12 are counted as distinct: 12, 2 x 6, 2 x (2 x 3), 2 x (3 x 2), 3 x 4, 3 x (2 x 2), 4 x 3, (2 x 2) x 3, 6 x 2, (2 x 3) x 2, (3 x 2) x 2, thus a(12) = 11. - _Antti Karttunen_, Nov 02 2016, based on the illustration given at page 14 of Knopfmacher & Mays paper.
%e A277120 The following factorizations of 30 are counted as distinct: 30, 2 x 15, 15 x 2, 3 x 10, 10 x 3, 5 x 6, 6 x 5, 2 x (3 x 5), 2 x (5 x 3), 3 x (2 x 5), 3 x (5 x 2), 5 x (2 x 3), 5 x (3 x 2), (2 x 3) x 5, (2 x 5) x 3, (3 x 2) x 5, (3 x 5) x 2, (5 x 2) x 3, (5 x 3) x 2, thus a(30) = 19. - _Antti Karttunen_, Jan 02 2024
%t A277120 v[n_] := v[n] = If[n == 1, 0, 1 + Sum[If[d == 1 || d^2 > n, 0, If[d^2 == n, 1, 2]*v[d]*v[n/d]], {d, Divisors[n]}]]; Table[v[n], {n, 1, 100}] (* _Vaclav Kotesovec_, Jan 13 2024, after _Antti Karttunen_ *)
%o A277120 (C)
%o A277120 #include <stdio.h>
%o A277120 #define MAX 10000
%o A277120 /* Number of branching factorizations of n. */
%o A277120 unsigned long n, m, a, b, p, x, nbr[MAX];
%o A277120 int main(void)
%o A277120 {
%o A277120   for (x=n=1; n<MAX; ++n)
%o A277120   { if (x*x == n) ++x;
%o A277120     for (b=0, p=2; p<x; ++p)
%o A277120     {
%o A277120       if ((n%p)==0)
%o A277120       {
%o A277120         m = n/p;
%o A277120         if (m<p) break;
%o A277120         a = nbr[p] * nbr[m];
%o A277120         b += (m==p) ? a : 2*a;
%o A277120       }
%o A277120     }
%o A277120     nbr[n] = b+1;
%o A277120   }
%o A277120   printf("1 0\n");
%o A277120   for (n=2; n<MAX; ++n) printf("%lu %lu\n", n, nbr[n]);
%o A277120   return(0);
%o A277120 } /* _Daniel Mondot_, Oct 01 2016 */
%o A277120 (PARI) A277120(n) = if(1==n, 0, 1+sumdiv(n, d, if((1==d)||(d*d)>n,0,if((d*d)==n,1,2)*A277120(d)*A277120(n/d)))); \\ _Antti Karttunen_, Nov 02 2016, after _Daniel Mondot_'s C-program above.
%o A277120 (PARI) seq(n)={my(v=vector(n)); for(n=2, n, v[n] = 1 + sumdiv(n, d, v[d]*v[n/d])); v} \\ _Andrew Howroyd_, Nov 17 2018
%Y A277120 Cf. A007317, A052886, A074206, A101296, A277130, A366377 [= a(A108951(n))], A366884 [= a(A025487(n))].
%Y A277120 After n=1 differs from A104725 for the next time at n=32, where a(32) = 51, while A104725(32) = 52.
%K A277120 nonn
%O A277120 1,4
%A A277120 _Michel Marcus_, Oct 01 2016
%E A277120 More terms from _Daniel Mondot_, Oct 01 2016