A275581 Numbers n such that A010846(n) >= n/2.

1, 2, 3, 4, 6, 8, 10, 12, 18, 30

Offset: 1

Author

Michael De Vlieger, Dec 25 2016

Keywords

• nonn
• easy
• fini
• full

Comments

Let 1 <= r <= n be a number "regular to" n, that is, a product of prime divisors p that also divide n.

This sequence includes numbers n such that there are at least as many regulars r among the range 1 <= m <= n as m that are nonregular to n.

Divisors d are a special case of regular r such that d also divides n in addition to all prime divisors p of d also dividing n.

With the exception of r = 1, all regular numbers r are part of the cototient of n.

For prime n, A010846(n) = A000005(n). Composite n > 4 can have nondivisor r. The only prime numbers in a(n) are {2,3}.

Regular r divides some power of n, but reliably divides n^r. When r is a divisor d of n, r | n.

Because the divisors of n are a subset of the regulars of n, it is interesting to compare A010846(n) with A000005(n) = tau(n):

A010846(n) = n for n = (1,2). Tau(n) = n for n = (1,2).

n/2 < A010846(n) < n for n = (3,4,6,10,12,18,30). n/2 < tau(n) < n for n = (3,4,6).

A010846(n) = n/2 for n = 8. Tau(n) = n/2 for n = (8,12).

Sequence A020490 includes numbers n such that tau(n) >= phi(n). The number 24 is in A020490 but not in a(n). This is because A010846(24) = 11 (cf. A162306(24) = {1,2,3,4,6,8,9,12,16,18,24}).

Numbers n such that tau(n) >= n/2: {1,2,3,4,6,8,12}.

Crossrefs

Cf. A010846, A020490, A051293, A162306.

Programs

Mathematica

Select[Range[10^3], 2 Count[Range@ #, k_ /; PowerMod[#, k, k] == 0] >= # &] (* or *)
Select[Range[10^3], Function[n, 2 Total[MoebiusMu[#] Floor[n/#] &@ Select[Range@ n, CoprimeQ[#, n] &]] >= n]] (* or *)
Select[Range[10^3], Function[n, 2 (1 + Count[Range@ n, m_ /; SubsetQ[FactorInteger[n][[All, 1]], FactorInteger[m][[All, 1]]]]) >= n]]