A006558: First group of n consecutive integers with same number of divisors

[hv at crypt.org]

David Wasserman <dwasserm at earthlink.com> wrote:
:Dear fellow seqfans,
:I have submitted a new upper bound: a(9) <= 2197379769820.  This is  
:low enough that someone with enough computing power could check all  
:smaller possibilities and conclusively determine a(9).  In fact, it's  
:only about twice as big as a(8), which was found three years ago, and  
:computers have improved since then.  I hope someone will take on this  
:task.  At the end of this message are some ideas about how to do it.
[...]
:Computing A006558(9): Note that at least one of the 9 numbers must be  
:4 mod 8, so the number of divisors is divisible by 3, and each number  
:is divisible by a square.  2 or 3 of them are divisible by 4, but no  
:other p^2 can divide more than one of them, so at least one of them  
:is divisible by p(i)^2 for some i >= 7.  So here's what I would do if  
:I had a big enough computer: for each prime p from p(7) to sqrt 
:(2197379769820/2), test every multiple of p^2 up to 2197379769820.   
:"Test" means checking consecutive integers both above and below to  
:see how many have the same number of divisors.  Many numbers will be  
:tested more than once, but to eliminate the repetition would probably  
:require more computation than it saves.  The total number of tests in  
:this method is about 18 billion.
:
:Maybe you can think of a more efficient way.

Not radically different, but a number of refinements.

If d(a(9)) = 6, we'd need to find k and k + 4 each of the form 2.p^2,
which clearly isn't possible. Likewise d(a(9)) cannot be odd, so it must
be a multiple of 6 and >= 12. That reduces the upper bound of squares
that need to be considered to sqrt(2197379769820/6), which is p=605167.

Note also that a(9) is necessarily >= a(8), which halves the range that
needs to be considered; I'm not sure whether you've already taken that
into account when counting the 18 billion tests.

Again, if the greatest square prime factor is 17, a(9) must be of the
form 32n-4, so for this case candidates can be verified much faster.

To reduce duplication when checking around candidates of the form
p^2.k, give up as soon as you see a neighbour divisible by prime q^2,
19 <= q < p.

When you have a candidate n, I'm not sure what order is fastest to
check the surrounding numbers, but I guess that d(n+k)=d(n) is rare
enough that the naive approach is fine. It would certainly help at
this point to use a tailored factorisation method that knows the d(n)
required, which will usually allow trial division to abort at n^(1/3)
or earlier. It should probably also make an explicit check when the
remaining factor is required to be a square.

:For consecutive integers with the same prime signature, I also have a  
:new upper bound for the next term: A034173(7) <= 464881210073.  This  
:is a similar problem, and is probably easier.

This has the same constraints on d(a(7)), and the same approach would
require testing p^2 for p in (13 .. 278347).

Hugo