[seqfan] Re: A351913: numerator(1/d - 1/n) [was: Re: Upper bound for A091895 and A091896]

hv at crypt.org hv at crypt.org
Mon Apr 18 04:25:21 CEST 2022


Earlier I wrote:
::"M. F. Hasler" <oeis at hasler.fr> wrote:
:::> On Tue, Apr 5, 2022 at 10:51 AM Michel Marcus wrote:
:::>
:::>> A bit different, did you see A351913 <http://oeis.org/A351913> ?
:::>> Any idea when can we say that Unknown can be set to -1 ?
:::>
:::>
:::This is an interesting question, I'd like to make it more explicit to
:::encourage people on this list who might be able to establish some relevant
:::results.
:::The problem is to show that there is no  n  such that numerator( 1/d(n) -
:::1/n ) = 102,
:::for example (first Unknown), where d(n) is the number of divisors of n.
:::Using  d(p^e) = e+1  one can search solutions of the form  n = 2^k m  where
:::m is odd.
:::To get an even numerator  x, one must have
:::(k+1) d(m) = 2^k (1+2E)  for some integer E >= 0, which then leads to
:::m = 1+2E + 2^k g x,  where g = gcd( m(1+2E), m-1-2E ).
:::
:::Maybe one can scan the space of solutions by increasing values of k and E,
:::(k+1 must divide 2^k (2E+1), i.e., k = t*2^K - 1 with  t | 2E+1 ;
:::K=0,1,2,...)
:::for each of which one can make the list of possible prime signatures of m,
:::(cf. oeis.org/A353248) and show that there is no solution  m  for any of
:::these.
:::But there are still some missing pieces to be filled in here, be it just
:::for x=102...
::
::I think it may be easier to do numerically - what's the largest n
::such that (n - d) / d^2 <= 102? A quick check suggests it is probably
::43243200 = 2^6 3^3 5^2 7 11 13, and there is no solution up to that
::value.
:
:Let f(n) = (n - d(n)) / d^2(n), then since x=43243200 is in A002182, I
:_think_ it is enough to show that f(px) > 102 for p prime, px in A002182:
:that should be enough to guarantee that f(A002182(n)) > 102 for all
:A002182(n) > x, and therefore that f(n) > 102 for n > x.

I've been trying to make this more rigorous, with limited success.

Let f(n) = n / d^2(n), since that is a little easier to reason with.
We can reject all n: f(n) > v = 103 > 102 + 1/d(n).

Let A = { n in A002182, n >= 12 }. I think it is clear that 12 divides
all elements of A, so for a in A we have f(ka) > f(a) for all k > 1.

Assume a_m in A is the greatest element with f(a) <= v. Then for all
n >= a_{m+1}: f(n) > v. This follows easily by separately considering
d(n) less than, equal to, or greater than d(a_{m+1}). So at worst we
need to check numerators for all n < a_{m+1} (or for a tighter bound
n <= max(a_i v / f(a_i), 0 <= i <= m)).

The tricky bit is knowing you've found a_m, since while a in A grows
much faster than d(a), f(a) is not uniformly increasing. I suspect
that if a_i is the first element with f(a_i) > v, it would be possible
to prove at least a_m < 2a_{i-1} to put an algorithmic bound on it,
but I don't see how to do that (and observation suggests a much tighter
bound should be possible in practice).

Hugo



More information about the SeqFan mailing list