[seqfan] Re: Does A330737 fly or will it crash? And is A199337 well-defined?

[David Seal]

> That is, is it guaranteed that for any n and big enough k, prime(n) |
> A002182(i), for all i >= k ?
> 
> And what about A199337?
> That is, it is guaranteed that for any n and big enough k, n |
> A002182(i), for all i >= k ?
> 
> Moreover, I wonder if there is a theorem that
> For any n and big enough k, A002182(n) | A002182(i), for all i >= k ?

Unless I've made a mistake in the argument that follows, the answer is yes to all three of those questions. Clearly the first and third are special cases of the second (for n happening to be a prime and a term of A002182 respectively), so I only need to show that the answer to the second is yes. I should acknowledge that the basic idea behind the following comes from Graeme McRae's link in https://oeis.org/A002183.

Consider the prime factorisation of a highly composite number h, i.e. a term of A002182:

  h = 2^e2 * 3^e3 * 5^e5 * 7^e7 * ...

written in a form in which all primes appear and only a finite number of the exponents are nonzero.

The number of divisors of h is d(h) = (e2+1) * (e3+1) * (e5+1) * (e7+1) * ... We can therefore produce a number with the same number of divisors by exchanging any pair of the exponents. Such an exchange would produce a smaller number with the same number of divisors if the exponent of the larger of the two primes were greater than the exponent of the smaller. That would contradict the fact that h is a highly composite number, so it follows that that order doesn't happen, i.e. that e2 >= e3 >= e5 >= e7 >= ...

We can rule out more pairs of exponents than just the ones that violate that order constraint. For example, for the pair of primes 2 and 3, suppose d2 and d3 are such that 2^d2 > 3^d3. Then if e2 >= d2, define:

  H = h * 3^d3 / 2^d2 = 2^(e2-d2) * 3^(e3+d3) * 5^e5 * 7^e7 * ...

Clearly H < h, so since h is highly composite, H must have fewer divisors than h. The number of divisors of H is (e2-d2+1) * (e3+d3+1) * (e5+1) * (e7+1) * ..., which is ((e2-d2+1)*(e3+d3+1)) / ((e2+1)*(e3+1)) times the number of divisors of h. So we can deduce that (e2-d2+1)*(e3+d3+1) < (e2+1)*(e3+1), which implies that d3*(e2+1) < d2*(e3+d3+1) or equivalently e2 < (d2*e3 + (d2*d3+d2-d3)) / d3. For example, since 2^5 > 3^3, we can apply that formula with d2=5, d3=3 to deduce that e2 < (5e3+17)/3. So we can rule out (e2,e3) = (>5,0), (>7,1), (>8,2), ...

Generalising that formula to an arbitrary pair of primes P and Q, if dP and dQ are numbers with P^dP > Q^dQ, we can deduce that eP < (dP*eQ + (dP*dQ+dP-dQ)) / dQ.

Suppose n = p^e is a prime power. What can we deduce about the prime factorisations of highly composite numbers h that are not divisible by n? Firstly, clearly ep >= e implies that h is divisible by n, so ep < e, and for every other prime q, the last paragraph applied to the case P=q, Q=p, dP = FLOOR(LOGq(p))+1 and dQ=1, which implies that P^dP > q^LOGq(p) = p = Q^dQ, says that eq < dP*(ep+2) - 1. I.e. we have upper bounds on the exponents of every prime in the prime factorisation of h. (Note that this is new only for primes q < p - for primes q > p, LOGq(p) < 1, so we can choose dP = 1 and the limit becomes eq < ep+1, which is of course equivalent to the already-known eq <= ep.)

Now suppose that a prime q > p^e appears in the prime factorisation of h, i.e. eq > 0. Then H = h * p^e / q is smaller than h, and its number of divisors is ((ep+e+1)/(ep+1)) * (eq/(eq+1)) times the number of divisors of h. Since ep < e, (ep+e+1)/(ep+1) >= 2, and since eq > 0, eq/(eq+1) >= 0.5, so the number of divisors of H is at least as big as the number of divisors of h. This is incompatible with h being a highly composite number, so we can conclude that q does not appear in the prime factorisation of h.

So if a highly composite number h is not divisible by n = p^e, we have a finite limit on each of the exponents in the prime factorisation of h, and that limit is 0 for all primes q > n. There are therefore only a finite number of possibilities for such an h, and since there are infinitely many highly composite numbers, all highly composite numbers from some point onwards are divisible by n.

Finally, to deal with general values of n and not just prime powers, suppose that the prime factorisation of n is:

  n = 2^n2 * 3^n3 * 5^n5 * 7^n7 * ...

in which only a finite number of the exponents are nonzero. For each of those finitely many nonzero exponents ep, only a finite number of highly composite numbers will fail to be divisible by p^ep, so only a finite number of highly composite numbers will fail to be divisible by their product, i.e. by n. Again, it follows that all highly composite numbers from some point onwards are divisible by n.

> But in practice, how we can compute both sequences A199337 and A330737
> with some certainty and for how far?

I think the above can clearly be used to find upper limits on the numbers of highly composite numbers not divisible by n with certainty - but I haven't yet thought through how far one can go with it in practice.

David


> On 29 December 2019 at 18:51 Antti Karttunen <antti.karttunen at gmail.com> wrote:
> 
> 
> Cheers,
> 
> prompted by sequence A199337, "Number of highly composite numbers not
> divisible by n":
> https://oeis.org/A199337
> I started wondering how to actually compute that.
> 
> So I created a tentative auxiliary (or "probing") sequence A330737
> whose definition is:
>    a(n) is the position of first index k in A002182 (highly composite
> numbers) from which onward all terms A002182(i), i >= k, are multiples
> of the n-th prime, a(0) = 1 by convention.
> 
> whose draft is here: https://oeis.org/draft/A330737
> 
> Is that sequence well-defined?
> That is, is it guaranteed that for any n and big enough k, prime(n) |
> A002182(i), for all i >= k ?
> 
> And what about A199337?
> That is, it is guaranteed that for any n and big enough k, n |
> A002182(i), for all i >= k ?
> 
> Moreover, I wonder if there is a theorem that
> For any n and big enough k, A002182(n) | A002182(i), for all i >= k ?
> 
> But in practice, how we can compute both sequences A199337 and A330737
> with some certainty and for how far?
> 
> 
> Best regards,
> 
> Antti
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/