A199337 Number of highly composite numbers not divisible by n.

0, 1, 3, 3, 8, 3, 14, 9, 12, 8, 26, 4, 37, 14, 8, 18, 53, 12, 67, 8, 14, 26, 86, 9, 54, 37, 40, 14, 107, 8, 122, 51, 26, 53, 14, 12, 145, 67, 37, 11, 163, 14, 180, 26, 13, 86, 202, 18, 107, 54, 53, 37, 222, 40, 26, 15, 67, 107, 252, 8, 275, 122, 16, 79, 37

Offset: 1

Author

J. Lowell, Nov 05 2011

Keywords

• nonn

Comments

The sequence is well defined since for any n there is m such that n | A002182(k) for all k >= m. This follows from eq.(54) in Ramanujan (1915): [log_p P] <= e_p <= 2*[log_p P'], where for any N = A002182(k), P = gpf(N) is the greatest prime factor, e_p = valuation(N, p) is the exponent of any p in the prime factorization, P' = nextprime(P+1) and [.] = floor: The right inequality gives N <= Product_{prime p} p^(2*[log_p P']) = A003418(P')^2, so P -> oo as N -> oo. Then the left inequality implies e_p -> oo for any p, as N -> oo. - M. F. Hasler, Jan 03 2020

Sequences A329570 and A329571 give the gpf P as above and L = A003418(P) such that all A002182(k) >= L^2 are divisible by n. - M. F. Hasler, Jan 07 2020

Examples

			a(6) = 3 because among highly composite numbers, only 1, 2, and 4 are not divisible by 6.
To illustrate the comment, we prove that n = 12 = A002182(5), respectively n = 60 = A002182(9), divide all A002182(k) >= n (whence a(12) = 5 - 1 = 4, a(30) = 9 - 1 = 8): From eq.(54) we have e_2 >= 2 and e_3 >= 1 when [log_2 P] >= 2, [log_3 P] >= 1, which is the case for P >= 5. To get gpf(N) >= 5, use the other side of the inequality, e_p <= 2*[log_p P'] with P = 3, P' = 5: This gives e_2 <= 4; e_3, e_5 <= 2; e_p = 0 for p > 5. Thus all N = a(n) > 2^4*3^2*5^2 = 3600 must have gpf(N) > 3, i.e., gpf(N) >= 5. This implies e_2 >= 2 and e_3 >= 1 and also e_5 >= 1, so we have 12 | N and 60 | N for all N = A002182(k) > 3600. The terms between 12 (resp. 60) and 3600 are also multiples of 12 (resp. 60), which completes the proof. - _M. F. Hasler_, Jan 03 2020
		

Links

• David A. Corneth, Table of n, a(n) for n = 1..600 (using b-file of A002182)
• S. Ramanujan, Highly composite numbers, Proceedings of the London Mathematical Society ser. 2, vol. XIV, no. 1 (1915): 347-409. (DOI: 10.1112/plms/s2_14.1.347, a variant of better quality with an additional footnote is available at this alternative link)

Crossrefs

Cf. A002182, A106037.

Cf. A329570, A329571 (bounds from the Ramanujan formula).

Programs

Mathematica

(* let t be terms of b002182 *) Table[Length[Select[t, Mod[#, n] > 0 &]], {n, 100}] (* T. D. Noe, Mar 18 2012 *)

Extensions

Extended by T. D. Noe, Mar 18 2012