Monday, March 7, 2011

The lure of xy-1

We can easily calculate for any number n which is the smallest y, so that that n divides xy-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     1
         000000      0
        100011       1
       100011        1
      100011         1

1110101=117 and 35*117=4095 which is 212-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. alt : It seems your browser does not support SVG. Consider using Google Chrome or another SVG enabled browser, I don'know why this fails in IE.... 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