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

[Jack Brennen]

I threw together a little C program last night before going to bed to 
work on this sequence, and running single-threaded on my little home 
desktop computer, it runs at an effective rate of processing a little 
over 100,000,000 values of tau per minute.  At this rate, I'm looking at 
about 13,000 minutes, or 220 hours of run-time just to validate the 
correctness of a(16).  It just validated the correctness of a(15) a 
moment ago, but a(16) is a distant target after a(15).

So it might be nice to know two things...  First, is 100,000,000 values 
of tau per CPU-minute a reasonable run rate?  I know that it's much 
faster than something like PARI/GP would be capable of doing, but I know 
there are some master sieve-authors out there who could probably beat 
that by a fair bit.

And also, I'm assuming that a(16) was determined through exhaustive 
search and that no higher gapped values of the sequence -- such as a(18) 
-- were found?  If so, where should one continue the search?  The term 
a(16) is a 41-bit number; I've been running the program overnight and if 
left alone, it will search out through all 48-bit numbers, but that 
would take about 5 years to finish at this rate.

The problem parallelizes easily of course.  You could probably search 
out through all 48-bit numbers in a day if you had 2,000 CPUs the 
equivalent of mine working on the problem.

- Jack


On 05/03/17 19:54, Neil Sloane wrote:
> 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/
>
>
>