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

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, 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, 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

Offset: 1

Author

Antti Karttunen, Jan 16 2023

Keywords

• nonn

Examples

			108 has in total 16 = A001055(108) factorizations:
  Factors           Are there any factors that are divisible by p^p,
                    where p is any prime?
  -------------------------------------------------------------------
  [3, 3, 3, 2, 2]   No
  [4, 3, 3, 3]      Yes (4, divisible by 2^2)
  [6, 3, 3, 2]      No
  [6, 6, 3]         No
  [9, 3, 2, 2]      No
  [9, 4, 3]         Yes (4)
  [9, 6, 2]         No
  [12, 3, 3]        Yes (12, divisible by 2^2)
  [12, 9]           Yes (12)
  [18, 3, 2]        No
  [18, 6]           No
  [27, 2, 2]        Yes (27, divisible by 3^3)
  [27, 4]           Yes (both 27 and 4)
  [36, 3]           Yes (36)
  [54, 2]           Yes (54, divisible by 3^3)
  [108]             Yes (108 = 2^2 * 3^3)
Thus only seven of the factorizations satisfy the criterion, and a(108) = 7.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537

Crossrefs

Cf. A001055, A048103, A276086, A317836, A359550, A359779 (Dirichlet inverse).

Cf. also A358236.

Programs

PARI

A359550(n) = { my(f = factor(n)); prod(k=1, #f~, (f[k, 1]>f[k, 2])); };
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));

Formula

a(n) <= A001055(n).

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