[seqfan] Re: A new and surprisingly hard elementary number theory question

[Robert Gerbicz]

2017-05-04 4:54 GMT+02:00 Neil Sloane <njasloane at gmail.com>:

> Sequence is A284597:
> a(n) is the least number that begins a run of exactly n consecutive
> numbers with a nondecreasing number of divisors.
>
> It begins
> 46, 5, 43, 1, 1613, 241, 17011, 12853, 234613, 376741, 78312721,
> 125938261, 4019167441, 16586155153, 35237422882, 1296230533473
>
> Only 16 terms are known. Submitted by Fred Schneider in March, and
> corrected by Bill McEachen and Giovanni Resta, Apr 26 2017
>
> The words "begins" and "exactly" in the definition are crucial. The
> initial values of tau (number of divisors function, A000005) can be
> partitioned into non-decreasing runs as follows:
> {1, 2, 2, 3}, {2, 4}, {2, 4}, {3, 4}, {2, 6}, {2, 4, 4, 5}, {2, 6},
> {2, 6}, {4, 4}, {2, 8}, {3, 4, 4, 6}, {2, 8}, {2, 6}, {4, 4, 4, 9},
> {2, 4, 4, 8}, {2, 8}, {2, 6, 6}, {4}, {2, 10},...
> From this we can see that a(1) = 46 (the first singleton), a(2)=5 (the
> first pair), a(3)=43, a(4)=1, ... - Bill McEachen and Giovanni Resta,
> Apr 26 2017.
>
> Nice problem!
> Neil
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
Hi!

Found new terms:
a(17)=42301168491121;
a(18)=61118966262061;
and a(n)>3.37*10^14 for n>18. My sieve reached even 1.4e9 n/sec., but at
the high range it has slowed down to 1.1e9 n/sec. on my 8 threaded core-i7
6700.

The main (standard) trick here is to sieve only up to n^(1/3), with that if
the factored part is r, then numdiv(n)=k*numdiv(r) where k=1,2,3 or 4
[because the unfactored part is n/r=c={1,p,p^2,p*q}, where p,q>n^(1/3)
prime], and even using this partial information it is possible to decide if
numdiv(n)<=numdiv(n+1)..<=numdiv(n+L-1) is true or not in most of the
cases. Actually there is so few hits that it is faster to store only
numdiv(r) and omit r. For hits: resieve say [n-32,n+32] and do only at most
one squaretest+primality test per n value, to decide k=1 (case 1=n/r), k=2
(case p=n/r is prime), k=3 (case p^2=n/r), and k=4 if we are not in the
previous cases (the advantage here is that we don't need to factorize n/r).