A094913 extension

[petsie at dordos.net]

Hi seqfans,

I do not know, why it works, but it seems to...

I start with an empty list and at each step I try to insert a zero or an one at each possible position. Then I pick the first list with maximal number of sublists and start over.
Say, we have had {0,0,1,1,0} as one of the lists with max. nr. of sublists. Then my candidates for the next test are:

With[{lastbest = {0, 0, 1, 1, 0}},
  Union[Flatten[
    Outer[Insert[lastbest, #2, #1] & , 
     Range[1 + Length[lastbest]],
     {0, 1},
    1], 1]]]

{{0, 0, 0, 1, 1, 0}, {0, 0, 1, 0, 1, 0}, {0, 0, 1, 1, 0, 0}, 
  {0, 0, 1, 1, 0, 1}, {0, 0, 1, 1, 1, 0}, {0, 1, 0, 1, 1, 0}, 
  {1, 0, 0, 1, 1, 0}}

see http://freenet-homepage.de/Peter_Berlin/Mathe/heuristicA094913.nb for the Mathematica notebook with the complete (simple) algorithm. There's a screenshot too (same URL but with .png instead of .nb).

If this works correctly, the first 100 values of A094913 are calculated in ~30s :-)

Peter



hv at crypt.org wrote:
:Using this approach, I calculate a(7) = 13005235 with the code below
:(which takes 860 minutes on my computer - for comparison, a(6) takes
:just under 12s).
:
:Given my track record so far on this, I would welcome confirmation. :)
:
:Further optimisations are possible [...]

After trying a variety of them, and then converting the whole thing
into PARI code (and then finding that under PARI the recursive version
was after all faster than the stack-based version), the timings are now:

? print(A118085(6));
49513
time = 1,711 ms.
? print(A118085(7));
13005235
time = 2h, 19mn, 38,180 ms.

The only significant improvement I can think of for this approach is if
there is a way to calculate directly any of a) |{ f : f | n, f < cutoff }|,
b) |{ f : f | n, f == n/f == -q (mod p - q) }|, or c) the intersection of
those two sets.

:As a rough feeling, I would expect calculation of a(8) with this approach
:to take between 10^6 and 10^9 times as long as a(7), but I don't know
:right now how to get a firmer estimate than my hunch.

Based on these timings and the dominant factor, I'd expect a(8) to take

Hugo

<<END
A118085(n) = {
};

A118085_r(p, q, prev, len) = {
}   
END




I've reported the problem.
Neil




In case I'm travelling (or asleep, though that rarely happens)
the email address for reporting troubles is


and you would say something like

The machine running Neil Sloane's On-Line Encyclopedia 
of Integer Sequences web site seems to have crashed


Neil