[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 

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>


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 
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 
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 

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 
>> 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