Mancala game and factorization of big numbers

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Mancala game and factorization of big numbers

Postby Goahead52 » Sat Jul 04, 2015 12:50 pm UTC

Hi,

Everybody knows the Mancala game.
You can see here or Google it if you do not know the game :

https://en.wikipedia.org/wiki/Mancala

Here is the idea of building an efficient algorithm of factorization (particularly big semi-prime numbers).
In Mancala game you have pits in circular form.
You empty one pit and you sow seeds one by one clockwise.
I added another rule : you pick from each pit one seed and you sow it on one pit.
Hence each time you have 2 choices
- either you empty one pit and you remove it
- either you pick one seed from the other pit and you sow them all on the same pit

By searching the tree you will reach a situation where the gcd of n=pq (p and q odd primes) is > 1

You start by creating int(sqrt(n)) pits.
For example :
n=91
int(sqrt(91))=9
91=9^2+10
then you will with 8 pits containing 9 seeds and one containing 9+10=19
Your algorithm will work like this :
-either you pick one seed on each of the 8 containing 9 or you empty the pit with 19 one by one on the other pits
- when finished you will have to compute the gcd of n with the UNIQUE values on the pits
and so on

There are some problems to fix that is why I posted this problem.
I will ask you to think carefully on the limits of this algorithm when n grows.
Thank you very much.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Mancala game and factorization of big numbers

Postby Goahead52 » Sat Jul 04, 2015 1:13 pm UTC

I forget to say that each time you perform one of the 2 actions you have to have 2 kinds of pits :
- pits containing the same number of seeds
- and one pit containing the remaining seeds

example :

9 pits : 9-9-9-9-9-9-9-9-19 is the starting position

First choice you remove the pit containing 19 seeds

8 pits : 11-11-11-11-11-11-11-14

gcd(91,14)-7
gcd(91,11)=1


Done you stop 91 divisible by 7

Second choice :

9 pits after move :
8-8-8-8-8-8-8-8-27

gcd(91,27)=1
gcd(91,8)=1

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Mancala game and factorization of big numbers

Postby Goahead52 » Sat Jul 04, 2015 3:53 pm UTC

Problems to fix :
- what is the upper bound of the tree size : 2^k given the size of n ?
- is there a way to find the factors by converging quickly to the solution (some leafs of the tree maybe will not need a further search (?))
- is the computational complexity reasonable or no? If no then there is no need to continue
= how to optimize the algorithm even if it is not practical (theoretical goal)?

Thank you for any comment.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Mancala game and factorization of big numbers

Postby mfb » Sun Jul 05, 2015 9:47 am UTC

Having of the order of sqrt(n) pits is not efficient, it is completely impractical. Typical factorization problems involve factors that exceed the total number of atoms in the whole universe.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Mancala game and factorization of big numbers

Postby Goahead52 » Sun Jul 05, 2015 2:18 pm UTC

mfb wrote:Having of the order of sqrt(n) pits is not efficient, it is completely impractical. Typical factorization problems involve factors that exceed the total number of atoms in the whole universe.

Thank you for your comment.
In regard to my algorithm at each step we have a state not S(k*a,b) where k is the number of pits containing the same number of seeds and the number of seeds on the remaining pit with b>a. The total number of pits = k+1.
We move from S(k*a,b) to S((k-1)*c,d) in the case of removing one pit.
We move from S(k*a,b) to S(k*c,d) in the case of non removing one pit.
So the only efficient way is to start from int(sqrt(n)) as number of pits. Why? because either you remove one pit either you do not remove.
What is hidden in this algorithm is that there any many solutions possible even if the size of the tree is large.
To have an idea about the solutions it is interesting to test numbers of 10 digits for example to see the graph tree and the node solutions.
For any n threre is only one size of three (solution found or not).
2 choices for each state until you reach 2 pits remaining.
The tree will be around 2^((int(sqrt(n))-1). It is large in fact but reaching a solution is very quick in my point of view.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Mancala game and factorization of big numbers

Postby >-) » Sun Jul 05, 2015 2:23 pm UTC

Dixon's factorization algorithm factorizes in O(exp(2*sqrt(2)*log(n)*log(log(n)))) compared to at least O(sqrt(2n)) = O(2n/2) = O(exp(n*log(2)/2)) for this.
Äsymptotically, 2*sqrt(2)*log(n)*log(log(n)) < n*log(2)/2
Last edited by >-) on Sun Jul 05, 2015 4:43 pm UTC, edited 1 time in total.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Mancala game and factorization of big numbers

Postby Goahead52 » Sun Jul 05, 2015 4:33 pm UTC

Not easy to implement anyway.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Mancala game and factorization of big numbers

Postby Goahead52 » Mon Jul 06, 2015 12:36 pm UTC

Can we prove that by using this algorithm if we do not find solution then it implies that n is prime?


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests