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

%I #13 Jan 17 2023 10:01:03

%S 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 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 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 Number of factorizations of n into factors not divisible by p^p for any prime p (terms of A048103).

%H Antti Karttunen, <a href="/A359778/b359778.txt">Table of n, a(n) for n = 1..65537</a>

%F a(n) <= A001055(n).

%F For all n >= 0, a(A276086(n)) = A317836(n).

%e 108 has in total 16 = A001055(108) factorizations:

%e Factors Are there any factors that are divisible by p^p,

%e where p is any prime?

%e -------------------------------------------------------------------

%e [3, 3, 3, 2, 2] No

%e [4, 3, 3, 3] Yes (4, divisible by 2^2)

%e [6, 3, 3, 2] No

%e [6, 6, 3] No

%e [9, 3, 2, 2] No

%e [9, 4, 3] Yes (4)

%e [9, 6, 2] No

%e [12, 3, 3] Yes (12, divisible by 2^2)

%e [12, 9] Yes (12)

%e [18, 3, 2] No

%e [18, 6] No

%e [27, 2, 2] Yes (27, divisible by 3^3)

%e [27, 4] Yes (both 27 and 4)

%e [36, 3] Yes (36)

%e [54, 2] Yes (54, divisible by 3^3)

%e [108] Yes (108 = 2^2 * 3^3)

%e Thus only seven of the factorizations satisfy the criterion, and a(108) = 7.

%o (PARI)

%o A359550(n) = { my(f = factor(n)); prod(k=1, #f~, (f[k, 1]>f[k, 2])); };

%o 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 Cf. A001055, A048103, A276086, A317836, A359550, A359779 (Dirichlet inverse).

%Y Cf. also A358236.

%K nonn

%O 1,6

%A _Antti Karttunen_, Jan 16 2023