A222084 Number of the least divisors of n whose LCM is equal to n.

1, 2, 2, 3, 2, 3, 2, 4, 3, 3, 2, 4, 2, 3, 3, 5, 2, 5, 2, 4, 3, 3, 2, 6, 3, 3, 4, 4, 2, 4, 2, 6, 3, 3, 3, 6, 2, 3, 3, 5, 2, 5, 2, 4, 4, 3, 2, 8, 3, 5, 3, 4, 2, 7, 3, 5, 3, 3, 2, 5, 2, 3, 4, 7, 3, 5, 2, 4, 3, 4, 2, 7, 2, 3, 5, 4, 3, 5, 2, 7, 5, 3, 2, 6, 3, 3, 3

Offset: 1

Author

Paolo P. Lava, Feb 07 2013

Keywords

• nonn

Comments

If we write n as the product of its prime factors, n = p1^a1*p2^a2*p3^a3*...*pr^ar, then tau#(n) gives the number of divisors from 1 to max(p1^a1, p2^a2, p3^a3, ..., pr^ar).

In general tau#(n) <= tau(n).

Also, tau#(n) = tau(n) is A000961, tau#(n) < tau(n) is A024619.

For any prime number p tau(p) = tau#(p) = 2.

tau#(n) = 3 only for semiprimes (A001358).

Examples

			For n=40, the divisors are (1, 2, 4, 5, 8, 10, 20, 40), so tau(40)=8.
lcm(1, 2, 4, 5, 8) = 40, but lcm(1, 2, 4, 5) = 20 < 40, so tau#(40)=5.
		

Links

• Paolo P. Lava, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000005, A000961, A001358, A003418, A005179, A024619, A034444, A077610, A222085.

Programs

Maple

with(numtheory);
A222084:=proc(q)
local a,b,c,j,n; print(1);
for n from 2 to q do a:=ifactors(n)[2]; b:=nops(a); c:=0;
  for j from 1 to b do if a[j][1]^a[j][2]>c then c:=a[j][1]^a[j][2]; fi; od;
  a:=op(sort([op(divisors(n))])); b:=nops(divisors(n));
  for j from 1 to b do if a[j]=c then break; fi; od; print(j); od; end:
A222084(100000);

Mathematica

Table[Count[ Divisors[n] , q_Integer /; q <= Max[Power @@@ FactorInteger[n]]], {n, 87}] (* Wouter Meeussen, Feb 09 2013 *)

PARI

a(n) = {my(d = divisors(n), k = 1); while (lcm(vector(k, j, d[j])) != n, k++); k;} \\ Michel Marcus, Mar 13 2018