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

[David Corneth]

I put some sequences that might give ideas for A199337 and A330737.
In particular you might like to see A328520 (GCD of terms in A002182
<https://oeis.org/A002182> that have have n prime factors counted with
multiplicity.). The sequences I put are A328518 through A328524.
They all have status proposed.


On Sat, Jan 4, 2020 at 3:13 AM David Seal <david.j.seal at gwynmop.com> wrote:

> > 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>