OFFSET
1,2
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}.
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]]
CROSSREFS
KEYWORD
nonn,easy,fini,full
AUTHOR
Michael De Vlieger, Dec 25 2016
STATUS
approved