[seqfan] Re: A066411
franktaw at netscape.net
franktaw at netscape.net
Sun Jan 29 04:23:50 CET 2012
I was going to suggest that. There's still a combinatorial explosion,
so I'm guessing we'll only get a few more terms, but it's worth having
that.
Another (minor) improvement: you could use binomial(n,k)-1 instead of
binomial(n,k). You get slightly smaller sums, but more importantly the
first stage becomes trivial. Of course, for n = 2^m-1, you want to use
(binomial(n,k)-1)/2 instead.
Another, perhaps incompatible idea: let p be the greatest prime divisor
of n. Process first the binomial coefficients that are not divisible by
p: i.e., binomial(n,k*p). Then you can look at the range of values
already seen only modulo p. Or similarly for p the largest prime less
than or equal to n; after the first n-p+1 steps, the remaining
coefficients are all divisible by p.
Franklin T. Adams-Watters
-----Original Message-----
From: Graeme McRae <g_m at mcraefamily.com>
A066411(17)=1471123
The way to speed things up is to do some pruning of the recursion tree.
If I'm
on a branch that can't reach any new leaves, I cut it off. (Can't reach
new
leaves means of the branch I'm sitting on, all the leaves from the
smallest to
the largest permutation have already been seen).
There would be no additional advantage by taking advantage of the
powers of two
that arise from the repeated combinations because the second visit to
an
identical branch would be quickly pruned away.
Regarding the fact that 2^n is a peak, this is a consequence of the
fact that
the combinations of 2^n-1 are odd, so only even-numbered sums can be
reached.
Oh, and by the way, I hereby verify the elements 0 through 16 of
A066411 that
have been reported on the database and in this thread.
--Graeme McRae,
Palmdale, CA
On Jan 28, 2012, at 8:44 AM, "Heinz, Alois"
<alois.heinz at hs-heilbronn.de> wrote:
>
> a(16) = 683311.
>
> a(16)/a(15) = 4.32.
>
> This is compatible with the pattern so far (peaks at n=2^k):
>
> . . .
>
> Am 27.01.2012 19:13, schrieb Ron Hardin:
>> I get 1 1 3 5 23 61 143 215 995 2481 5785 12907 29279 64963 144289
158049
which
>> agrees with the series.
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list