cp's OEIS Frontend

A359778 Number of factorizations of n into factors not divisible by p^p for any prime p (terms of A048103).

%I A359778 #13 Jan 17 2023 10:01:03
%S A359778 1,1,1,1,1,2,1,1,2,2,1,2,1,2,2,1,1,4,1,2,2,2,1,2,2,2,2,2,1,5,1,1,2,2,
%T A359778 2,5,1,2,2,2,1,5,1,2,4,2,1,2,2,4,2,2,1,5,2,2,2,2,1,6,1,2,4,1,2,5,1,2,
%U A359778 2,5,1,5,1,2,4,2,2,5,1,2,3,2,1,6,2,2,2,2,1,11,2,2,2,2,2,2,1,4,4,5,1,5,1,2,5,2,1,7
%N A359778 Number of factorizations of n into factors not divisible by p^p for any prime p (terms of A048103).
%H A359778 Antti Karttunen, <a href="/A359778/b359778.txt">Table of n, a(n) for n = 1..65537</a>
%F A359778 a(n) <= A001055(n).
%F A359778 For all n >= 0, a(A276086(n)) = A317836(n).
%e A359778 108 has in total 16 = A001055(108) factorizations:
%e A359778   Factors           Are there any factors that are divisible by p^p,
%e A359778                     where p is any prime?
%e A359778   -------------------------------------------------------------------
%e A359778   [3, 3, 3, 2, 2]   No
%e A359778   [4, 3, 3, 3]      Yes (4, divisible by 2^2)
%e A359778   [6, 3, 3, 2]      No
%e A359778   [6, 6, 3]         No
%e A359778   [9, 3, 2, 2]      No
%e A359778   [9, 4, 3]         Yes (4)
%e A359778   [9, 6, 2]         No
%e A359778   [12, 3, 3]        Yes (12, divisible by 2^2)
%e A359778   [12, 9]           Yes (12)
%e A359778   [18, 3, 2]        No
%e A359778   [18, 6]           No
%e A359778   [27, 2, 2]        Yes (27, divisible by 3^3)
%e A359778   [27, 4]           Yes (both 27 and 4)
%e A359778   [36, 3]           Yes (36)
%e A359778   [54, 2]           Yes (54, divisible by 3^3)
%e A359778   [108]             Yes (108 = 2^2 * 3^3)
%e A359778 Thus only seven of the factorizations satisfy the criterion, and a(108) = 7.
%o A359778 (PARI)
%o A359778 A359550(n) = { my(f = factor(n)); prod(k=1, #f~, (f[k, 1]>f[k, 2])); };
%o A359778 A359778(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (d<=m) && A359550(d), s += A359778(n/d, d))); (s));
%Y A359778 Cf. A001055, A048103, A276086, A317836, A359550, A359779 (Dirichlet inverse).
%Y A359778 Cf. also A358236.
%K A359778 nonn
%O A359778 1,6
%A A359778 _Antti Karttunen_, Jan 16 2023