[seqfan] Re: A066411
Graeme McRae
g_m at mcraefamily.com
Sun Jan 29 07:51:50 CET 2012
Very interesting! Especially the idea of using (C(15,k)-1)/2. I handled it a different way that eats a few cycles for every calculation. As for the first stage becoming trivial, I either don't understand what you mean or I don't think my program is structured in a way to take advantage of that help (or both). I keep the array of combinations fixed, and in descending order, and permute the array of 0..n using a recursive subroutine. For your second idea, it may be worth writing a special-purpose program to compute A066411(23).
--Graeme McRae,
Palmdale, CA
On Jan 28, 2012, at 7:23 PM, franktaw at netscape.net wrote:
> 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/
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list