New way of choosing numbers?
Martin Round
44,45,46,47,48,49 is the last ticket (assuming a 6/49 lottery).
But what numbers would you choose to get ticket number 7,654,321 ?
There is a new applet at http://www.mround.pwp.blueyonder.co.uk/ that
answers these questions and so gives you a (hopefully) new way of
choosing your numbers. It works for 6/49, 6/53, etc. etc. It even
works for 10/100
Please try it out and let me know what you think.
Martin.
Duncan Smith
"Martin Round" <mro...@writeme.com> wrote in message
news:21c60c4b.02012...@posting.google.com...
> Most people would agree that 1,2,3,4,5,6 is ticket number 1, and that
> 44,45,46,47,48,49 is the last ticket (assuming a 6/49 lottery).
>
> But what numbers would you choose to get ticket number 7,654,321 ?
>
Depends what ordering you use. But if you use a lexicographic ordering you
could always use the code I posted about 2-3 months ago. :-)
>>> lottery1.CombFromIndex(49, 6, 7654321, 1)
[6, 17, 18, 38, 41, 42]
(3 function calls in 0.006 CPU seconds)
or reverse it,
>>> lottery1.IndexFromComb(49, [6,17,18,38,41,42], 1)
mpz(7654321)
(3 function calls in 0.002 CPU seconds)
Code below, but not the most efficient implementation (in order to be
concise), so the reversal takes some time for eg. a 20/200 lottery. (Better
to construct a table of binomial coefficients first rather than
(re-)calculating them on the fly.)
lottery1.py
------------------------------------------------------------
import gmpy
def IndexFromComb(N, comb=[], start=0): # N,k lottery
k=len(comb) #comb as list eg. [1,2,3,4,5,6]
index = gmpy.comb(N, k) - 1 + start #indexing starts at 0 by default
for i in range(k):
index = index - gmpy.comb(N - comb[i], k - i)
return index
def CombFromIndex(N, k, index, start=0):
combsum = gmpy.comb(N, k) - index
if start == 0:
combsum = combsum - 1
comb = []
last_n = 0
for i in range(k):
n = last_n + 1
while gmpy.comb(N - n, k - i) > combsum:
n = n + 1
n = n + last_n
comb.append(n)
combsum = combsum - gmpy.comb(N - n, k - i)
return comb
---------------------------------------------------------
Duncan
Martin Round
(it comes up with the same answers). What language is your code in? Here is
my (very inefficient, but quick enough for the applet) code:
private BigInteger factorial(int n)
{
if (n <= 1)
return (new BigInteger("1"));
else
{
BigInteger bigN = new BigInteger(String.valueOf(n));
return (bigN.multiply(factorial(n - 1)));
}
}
private long polytopic(int r, int n) // return the nth regular r-polytopic
number
{
return ((factorial(r + n - 1).divide(factorial(r).multiply(factorial(n -
1)))).longValue());
}
private long calculateTicket() // returns ticket # for current values of
pick, from and n[]
{
long ticket = 1 + polytopic(pick, 1 + from - pick) - polytopic(pick, 2 +
from - (pick + n[0]));
for (int i = 1; i < pick; i++)
{
ticket += polytopic(i, 1 + from - (n[pick - (i + 1)] + i));
ticket -= polytopic(i, 2 + from - (n[pick - (i)] + i));
}
return ticket;
}
Martin.
"Duncan Smith" <buz...@urubu.freeserve.co.uk> wrote in message
news:a2vs5c$at4$1...@newsg4.svr.pol.co.uk...
Duncan Smith
"Martin Round" <mro...@blueyonder.co.uk.spamfree> wrote in message
news:BmR48.15041$wF1.1...@news1.cableinet.net...
> Looks as though my applet uses the same lexicographic ordering as your
code
> (it comes up with the same answers). What language is your code in?
Python (quite readable isn't it). I've no doubt it would be quicker in C
(but maybe not a lot). It is quicker if you write a class and construct a
table of binomial coefficients when you instantiate a class instance.
Here is
> my (very inefficient, but quick enough for the applet) code:
>
Now to figure out what you've done and why it works (and what I did and why
mine works).
Sean B
>Looks as though my applet uses the same lexicographic ordering as your code
>(it comes up with the same answers). What language is your code in? Here is
>my (very inefficient, but quick enough for the applet) code:
Excellent applet Martin, quick too. I downloaded
the zip. It works standalone in Netscape 4.70 ok.
I converted Duncan's code to GFA Basic,
not yet done the reversal, although its
straight forward enough. Let me know
if you want it reposting.
What language have you used, I presume
its Java or Java Script. I know nothing about
either.
If your method of calculation differs from
Duncan's, I'm sure most rgl regulars would
be very interested in seeing it in a slightly
clearer pseudo code.
A slightly different method using a different
numbering system was posted a few years
ago. This has the advantage of keeping the
same numbers for each set of balls irrespective
of the largest ball value e.g. 39 or 49
'Following algorithm by Don McDonald
'Arranged into ascending order, the lucky numbers were
'3 5 14 22 30 44. The combination sequence number of these
'numbers is :
'2C1 + 4C2 + 13C3 + 21C4 + 29C5 + 43C6 +1 = 6,221,489.
The way the balls change in Don's CSN look
interesting:
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 4 5 8
1 2 3 4 6 8
1 2 3 5 6 8
1 2 4 5 6 8
1 3 4 5 6 8
2 3 4 5 6 8
1 2 3 4 7 8
1 2 3 5 7 8
1 2 4 5 7 8
1 3 4 5 7 8
2 3 4 5 7 8
1 2 3 6 7 8
1 2 4 6 7 8
The 6th balls advances by and then all
possible 1st to 5th balls are filled in, starting
with the lowest possible and then the 6th ball
advances again.
It should not be too hard to write some loops
that would generate Don's CSN.
Cheers,
Sean B
Sharon Balicker
hey Martin
nice one, did you check out www.saliu.com and the ftp download page.
Lots of free stuff including a little routine that will work out the
'combination for a certain sequence number' or the 'sequence number of
a certain combination'
Might be ineresting to you.
thanks
Sharon
Martin Round
"Sean B" <se...@sbacc3.fsnet.co.uk> wrote in message
news:bns85ucltd7h6hj7a...@4ax.com...
> "Martin Round" <mro...@blueyonder.co.uk.spamfree> wrote:
>
> >Looks as though my applet uses the same lexicographic ordering as your
code
> >(it comes up with the same answers). What language is your code in? Here
is
> >my (very inefficient, but quick enough for the applet) code:
>
> Excellent applet Martin, quick too. I downloaded
> the zip. It works standalone in Netscape 4.70 ok.
Thanks. Nice to hear that.
> I converted Duncan's code to GFA Basic,
> not yet done the reversal, although its
> straight forward enough. Let me know
> if you want it reposting.
>
> What language have you used, I presume
> its Java or Java Script. I know nothing about
> either.
It's java (for simple functions or methods like this
java and C or C++ are almost identical).
> If your method of calculation differs from
> Duncan's, I'm sure most rgl regulars would
> be very interested in seeing it in a slightly
> clearer pseudo code.
My method is different to Duncan's, but Duncan's is much the
simpler and better method.
Anyway, here is (I hope) a clearer explanation of how my method
works for the 6/49 case:
If your lottery numbers are (ascending order) n1, n2, n3, n4, n5, n6
define the function P(r, n) = (r + n - 1)! / (r! * (n - 1)!)
the key (or sequence number), k (range 1 to 13,983,816) is given by:
k = P(6, 44) - P(6, 45 - n1)
+ P(5, 45 - n1) - P(5, 46 - n2)
+ P(4, 46 - n2) - P(4, 47 - n3)
+ P(3, 47 - n3) - P(3, 48 - n4)
+ P(2, 48 - n4) - P(2, 49 - n5)
+ P(1, 49 - n5) - P(1, 50 - n6) + 1
Mathematicians may be interested to know that the function P(r, n):
generates the counting numbers 1, 2, 3, 4,... when r = 1
generates the triangular numbers 1, 3, 6, 10,... when r = 2
generates the tetrahedral numbers 1, 4, 10, 20,... when r = 3
generates the pentatope numbers 1, 5, 15, 35,... when r = 4
etc.
Hmmm... interesting. I'll look into that.
>
>
> Cheers,
>
> Sean B
Thanks.
Martin.
Martin Round
>
> "Martin Round" <mro...@blueyonder.co.uk.spamfree> wrote in message
> news:BmR48.15041$wF1.1...@news1.cableinet.net...
> > Looks as though my applet uses the same lexicographic ordering as your
> code
> > (it comes up with the same answers). What language is your code in?
>
> Python (quite readable isn't it). I've no doubt it would be quicker in C
> (but maybe not a lot). It is quicker if you write a class and construct a
> table of binomial coefficients when you instantiate a class instance.
Your code is much simpler and clearer than mine. I looked into Python and
I agree, it's a nice language for this sort of thing.
I converted your code to C++ and found the following:
1. You have a redundant 'last_n' variable in your code that does nothing.
2. The CombFromIndex function can be speeded up by doing a binary chop
search for n where comb(N - n, k - i) <= combsum, instead of sequentially
checking all values of n.
In the java and C++ version where I wrote my own comb() methods, the bulk
of the time is spent calculating factorials, so pregenerating a table of
factorials from 1 to N saves a (relatively) enormous amount of CPU time.
But computers these days are very fast - so do I need to bother? :-)
Martin.
Duncan Smith
"Martin Round" <mro...@blueyonder.co.uk.spamfree> wrote in message
>
> "Duncan Smith" <buz...@urubu.freeserve.co.uk> wrote in message
> news:a318hg$9vr$1...@news8.svr.pol.co.uk...
> >
> > "Martin Round" <mro...@blueyonder.co.uk.spamfree> wrote in message
> > news:BmR48.15041$wF1.1...@news1.cableinet.net...
> > > Looks as though my applet uses the same lexicographic ordering as your
> > code
> > > (it comes up with the same answers). What language is your code in?
> >
> > Python (quite readable isn't it). I've no doubt it would be quicker in
C
> > (but maybe not a lot). It is quicker if you write a class and construct
a
> > table of binomial coefficients when you instantiate a class instance.
>
> Your code is much simpler and clearer than mine. I looked into Python and
> I agree, it's a nice language for this sort of thing.
>
> I converted your code to C++ and found the following:
>
> 1. You have a redundant 'last_n' variable in your code that does nothing.
>
Mmm? I've rewritten the code a few times. It used to do something.:-)
> 2. The CombFromIndex function can be speeded up by doing a binary chop
> search for n where comb(N - n, k - i) <= combsum, instead of
sequentially
> checking all values of n.
>
Yes.
> In the java and C++ version where I wrote my own comb() methods, the bulk
> of the time is spent calculating factorials, so pregenerating a table of
> factorials from 1 to N saves a (relatively) enormous amount of CPU time.
>
> But computers these days are very fast - so do I need to bother? :-)
>
Well, as you know, a relatively enormous amount of CPU time can translate to
an actual enormous amount of CPU time for a big enough problem. OK for
6/49, but for a 20/200 or something silly?
> Martin.
>
>
Duncan Smith
"Martin Round" <mro...@blueyonder.co.uk.spamfree> wrote in message
>
> "Duncan Smith" <buz...@urubu.freeserve.co.uk> wrote in message
> news:a318hg$9vr$1...@news8.svr.pol.co.uk...
> >
> > "Martin Round" <mro...@blueyonder.co.uk.spamfree> wrote in message
> > news:BmR48.15041$wF1.1...@news1.cableinet.net...
[snip]
> In the java and C++ version where I wrote my own comb() methods, the bulk
> of the time is spent calculating factorials, so pregenerating a table of
> factorials from 1 to N saves a (relatively) enormous amount of CPU time.
>
> But computers these days are very fast - so do I need to bother? :-)
>
> Martin.
>
>
Try the code below with some silly numbers and we have our answer.:-) I
can't remember if I posted this earlier. But it's much faster.
my_module.py
-------------------------------------------------------
from Numeric import *
import gmpy
class MyClass:
def __init__(self, n, k):
self.n = n
self.k = k
self.C_table = MyClass.build_C_table(self)
def build_C_table(self):
table = zeros((self.n + 1, self.k + 1), PyObject)
for i in range(self.n + 1):
table[i, 0] = gmpy.mpz(1)
for i in range(1, self.n + 1):
for j in range(1, min([i, self.k]) + 1):
table[i, j] = table[i-1, j-1] + table[i-1, j]
return table
def IndexFromComb(self, comb=[], start=0):
index = self.C_table[self.n, self.k] - 1 + start
for i in range(self.k):
index = index - self.C_table[self.n - comb[i], self.k - i]
return index
def CombFromIndex(self, index, start=0):
combsum = self.C_table[self.n, self.k] - index
if start == 0:
combsum = combsum - 1
comb = []
for i in range(self.k):
n = 1
while self.C_table[self.n - n, self.k - i] > combsum:
n = n + 1
comb.append(n)
combsum = combsum - self.C_table[self.n - n, self.k - i]
return comb
-----------------------------------------------------------------
eg.
>>> import my_module
>>> lot = my_module.MyClass(49,6)
>>> lot.CombFromIndex(10000000)
[9, 19, 32, 34, 35, 46]
>>> lot.IndexFromComb([9, 19, 32, 34, 35, 46])
mpz(10000000)
Sean B
>My method is different to Duncan's, but Duncan's is much the
>simpler and better method.
>
>Anyway, here is (I hope) a clearer explanation of how my method
>works for the 6/49 case:
Thanks, Martin, I'll have a good look
through it.
Sean