[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