Author |
Topic: Looking for a better computational technique (Read 480 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
Looking for a better computational technique
« on: Jan 21st, 2010, 5:22pm » |
 Quote  Modify
|
I'm looking for a better computational technique
My question: How to count the size of a large group as quickly as possible?
We could use the Chinese Remainder Theorem
However, there are some limitations to this approach, since it cannot tell us exactly the size of
that large group
I'm interested in finding ways of counting a large group of unknown size. Is there a better technique than the chinese remainder theorem to determine the size of a group?
We could be counting, for example, a very large number N of pennies in jars or other containers ... as shown in this example: Using Grouping to Count Quickly
Or, we could be interested in counting quickly the size of a very large crowd of people.
If the size is 10,000, I figure we could use the 7-11-13 remainder method for larger numbers.
And if the number N is much larger, then we determine the remainder after dividing by each member of a sequence of prime numbers, say 2, 3, 5, 7, 11, 13, 17, 19.
A generalization of this problem would be:
Let N represent the total size of the crowd or group of people.
Let r1 be the remaining number of people when asked to form groups of size p1.
Let r2 be the remaining number of people when asked to form groups of size p2.
If r1 and r2 are relatively prime, the CRT says that the remaining number of people left over when groups of size p1 * p2 are formed is calculated using the following
(r1 * p2 * x1 + r2 * p1 * x2) mod(p1 * p2)
with
x1 = (p2)-1 mod(p2)
and x2 = (p1)-1 (mod(p2)
Which other computational technique would be better than the CRT with this kind of problem?
I mean a better technique that could tell us what N is with certainty [/quote]
|
| « Last Edit: Jan 21st, 2010, 5:23pm by Benny » |
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print