%I #18 May 18 2019 16:58:14
%S 0,0,0,1,0,1,0,3,1,1,0,4,0,1,1,7,0,4,0,4,1,1,0,10,1,1,3,4,0,5,0,13,1,
%T 1,1,13,0,1,1,10,0,5,0,4,4,1,0,22,1,4,1,4,0,10,1,10,1,1,0,16,0,1,4,24,
%U 1,5,0,4,1,5,0,30,0,1,4,4,1,5,0,22,7,1,0,16,1,1,1,10,0,16,1,4,1,1,1,42,0
%N Number of product signs needed to write all the factorizations of n with all factors > 1.
%H Antti Karttunen, <a href="/A076277/b076277.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = A066637(n) - A001055(n) for n > 1. - _Henry Bottomley_, Oct 10 2002
%e 12 = 3*4 = 2*6 = 2*2*3, 4 product signs are needed, so a(12) = 4.
%e 24 = 12*2 = 6*2*2 = 4*3*2 = 3*2*2*2 = 8*3 = 6*4 with 10 multiplies so a(24) = 10.
%t g[1, r_] := g[1, r]={1, 0}; g[n_, r_] := g[n, r]=Module[{ds, i, val}, ds=Select[Divisors[n], 1<#<=r&]; val={0, 0}+Sum[g[n/ds[[i]], ds[[i]]], {i, 1, Length[ds]}]; val+{0, val[[1]]}]; a[1]=0; a[n_] := g[n, n][[2]]-g[n, n][[1]]; a/@Range[97] (* g[n, r] = {c, f}, where c is the number of factorizations of n with factors <= r and f is the total number of factors in them. - _Dean Hickerson_, Oct 10 2002 *)
%o (PARI)
%o A076277(n) = a(n,0);
%o a(n, k=0) = if(k<=0, a(n, 2)[2], if(n<=1||k>n, [0, 0], [1, 0]+sumdiv(n, d, if(d>=max(2, k)&&d<=n/d, a(n/d, d)*[1, 1; 0, 1], [0, 0])))); \\ From the original author. | and & replaced with || and && to conform with modern PARI-systems. - _Antti Karttunen_, May 25 2017
%Y Cf. A001055, A066637.
%K nonn
%O 1,8
%A Remco van Sabben (pvsabben(AT)stwillibrord.nl), Oct 04 2002
%E More terms from _Robert G. Wilson v_ and _Michael Somos_, Oct 08 2002
|