We can easily calculate for any number n which is the smallest y, so that that n divides x

^{y}-1. This works base any number, but here we start using binary. Use this sample for 35: 35 is 100011 binary. Keep adding multiples of 35 to itself until you have a solid streak ones:```
100011 1
000000 0
-----------+
100011
100011 1
-----------+
10101111
000000 0
-----------+
10101111
100011 1
-----------+
1011011111
100011 1
-----------+
11100111111
100011 1
------------+
111111111111
```

1110101=117 and 35*117=4095 which is 2^{12}-1. I have often been wondering if this could be the basis for an efficient factorization algorithm. In order to gain some more insight in its behavior I plotted y as a function of n. Since in n is prime n divides 2^{n-1}-1 (for theory look at eg. Wikipedia on prime numbers), and therefore often stand out towards the diagonal, I color primes red. This graph raises a lot of questions, and also sheds a lot of light on subjects like Mersenne primes and pseudo primes (composite numnbers n where n divides 2^{n-1}-1). To be continued!
## No comments:

## Post a Comment