A336041 Number of refactorable divisors of n.

1, 2, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 1, 3, 1, 4, 1, 2, 1, 2, 1, 5, 1, 2, 2, 2, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 4, 1, 2, 1, 2, 2, 2, 1, 5, 1, 2, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 2, 2, 3, 1, 2, 1, 2, 1, 2, 1, 9, 1, 2, 1, 2, 1, 2, 1, 5, 2, 2, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2

Offset: 1

Author

Wesley Ivan Hurt, Jul 07 2020

Keywords

• nonn
• easy

Comments

Inverse Möbius transform of A336040. - Antti Karttunen, Nov 24 2021

Examples

			a(6) = 2; The divisors of 6 are {1,2,3,6}. Only two of these divisors are refactorable since d(1) = 1|1 and d(2) = 2|2, but d(3) = 2 does not divide 3 and d(6) = 4 does not divide 6.
a(7) = 1; The divisors of 7 are {1,7} and d(1) = 1|1, but d(7) = 2 does not divide 7, so a(7) = 1.
a(8) = 3; The divisors of 8 are {1,2,4,8}. 1, 2 and 8 are refactorable since d(1) = 1|1, d(2) = 2|2 and d(8) = 4|8 but d(4) = 3 does not divide 4, so a(8) = 3.
a(9) = 2; The divisors of 9 are {1,3,9}. 1 and 9 are refactorable since d(1) = 1|1 and d(9) = 3|9 but d(3) = 2 does not divide 3. Thus, a(9) = 2.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537
• Eric Weisstein's World of Mathematics, Refactorable Number

Crossrefs

Cf. A000005 (tau), A033950 (refactorable numbers), A336040 (refactorable characteristic), A349658 (number of nonrefactorable divisors).

Cf. also A335182, A335665.

Programs

Maple

A336041 := proc(n)
    local a ;
    a := 0 ;
    for d in numtheory[divisors](n) do
        if type(d/numtheory[tau](d),integer) then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:
seq(A336041(n),n=1..30) ; # R. J. Mathar, Nov 24 2020

Mathematica

a[n_] := DivisorSum[n, 1 &, Divisible[#, DivisorSigma[0, #]] &]; Array[a, 100] (* Amiram Eldar, Jul 08 2020 *)

PARI

a(n) = sumdiv(n, d, d%numdiv(d) == 0); \\ Michel Marcus, Jul 07 2020

Formula

a(n) = Sum_{d|n} c(d), where c(n) is the refactorable characteristic of n (A336040).

a(n) = Sum_{d|n} (1 - ceiling(d/tau(d)) + floor(d/tau(d))), where tau(n) is the number of divisors of n (A000005).

a(n) = A000005(n) - A349658(n). - Antti Karttunen, Nov 24 2021

a(p) = 1 for odd primes p. - Wesley Ivan Hurt, Nov 28 2021