mersenneforum.org How to test your cell phone warranty
 Register FAQ Search Today's Posts Mark Forums Read

2011-08-11, 17:23   #34
axn

Jun 2003

22×3×409 Posts

Quote:
 Originally Posted by science_man_88 flaw: Code: (13:13)>binary(128) %15 = [1, 0, 0, 0, 0, 0, 0, 0] (13:18)>[1,0,0]+[0,0,0] %16 = [1, 0, 0] (13:18)>128%7 %17 = 2 (13:19)>2^3-1 %18 = 7 also I don't see how you get the last equation. according to you to do 128 mod (7=2^3-1) I take 100 + 000 = 100 and solve it as 4 but 128 = (2*49) + (4*7) +2 so the correct result is 2.
you should group the bits in 3, starting from the right and working to the left. so the right way is [0,1,0] + [0,0,0] + [0,0,0].

PS:- for LL testing, there will only be two groups of bits -- can you say why?
PPS:- can you relate this to divisibility rule for 9? can you generalize it from this?

2011-08-11, 18:03   #35
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by axn you should group the bits in 3, starting from the right and working to the left. so the right way is [0,1,0] + [0,0,0] + [0,0,0]. PS:- for LL testing, there will only be two groups of bits -- can you say why? PPS:- can you relate this to divisibility rule for 9? can you generalize it from this?
AXN it's not what they said they said add the lower and higher n bits only.

re:PS:yes because x never gets above p^2 which will have at most 2n bits ?
re:PPS:no to both.

Last fiddled with by science_man_88 on 2011-08-11 at 18:05 Reason: PS was originally no

2011-08-11, 22:52   #36
ckdo

Dec 2007
Cleves, Germany

53010 Posts

Quote:
 Originally Posted by science_man_88 re:PPS:no to both.
Yes to both. Minor hint: 9 = 10^1 - 1

2011-08-12, 00:07   #37
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by ckdo Yes to both. Minor hint: 9 = 10^1 - 1
so in other words the mersennes follow the same test for all repunits 99=10^2-1 and can be tested with a similar test even though it's clearly a multiple of 9

2011-08-12, 01:48   #38
ckdo

Dec 2007
Cleves, Germany

2×5×53 Posts

Quote:
 Originally Posted by science_man_88 also I don't see how you get the last equation. according to you to do 128 mod (7=2^3-1) I take 100 + 000 = 100 and solve it as 4 but 128 = (2*49) + (4*7) +2 so the correct result is 2.
Getting back to the 128 % 7 example:

12810 % 710 = 2008 % 78 = 28 + 08 + 08 = 28 = 210.

Or, if you prefer binary (leading zeroes and spaces added for clarity):

12810 % 710 = 010 000 0002 % 1112 = 0102 + 0002 + 0002 = 0102 = 210.

2011-08-12, 07:44   #39
LaurV
Romulan Interpreter

Jun 2011
Thailand

33·347 Posts

Quote:
 Originally Posted by science_man_88 flaw: also I don't see how you get the last equation. according to you to do 128 mod (7=2^3-1) I take 100 + 000 = 100 and solve it as 4 but 128 = (2*49) + (4*7) +2 so the correct result is 2.
You can write any number x as x=2n*a+b, by separating it in two parts, first n bits (from the right to the middle, somewhere) and the rest of the bits (from the middle to the left - first - most significant bit). This equation you can write like

x=2n*a-a+a+b

Then you group like:

x=(2n-1)*a+a+b

When you do mod m, with m=2^n-1, the paranthesis is gone and what you get left is y=a+b, where b are last n LSBits of x, and a is the rest of the MSBits.

Of course, if the result is bigger then m, you repeat the procedure until you get something smaller or equal to m (that fits on n bits). Please remark the "or equal" part. Because you always add positive numbers from which at least one is not null, you will never get 0. You will always get a number between 1 and m, inclusive, that is on binary (n bits) between 0...001 and 1...111, so in the case you got 1...111 then the modulus is 0. In the other cases, you got the right result.

Now if you do LL tests, as I said in the first post, you always square numbers smaller then m, so you will never get more then 2m bits, that means you have to do the procedure only once.

Examples (don't care where the numbers come from, either LL test, other calculus, my belly, etc):

55%31: 110111%11111=
(group 5 bits from the right)
1 10111 % 11111 =
1+10111 % 11111 = 11000
Decimal: 55%31=1+23=24 (mod 31) - the right result

165%15= 1010 0101 % 1111 = 1010+0101 = 1111 so 15 divides 165

961%31= 1111000001%31 = 11110 00001 %31 = 11111 - that is 0, so 31 divides 961

etc.

for your example, what you wrote down is 100 000 that is not 128, but 32 in decimal. Of course, 32 mod 7 makes 4.

Last fiddled with by LaurV on 2011-08-12 at 07:46

2011-08-12, 08:07   #40
LaurV
Romulan Interpreter

Jun 2011
Thailand

33·347 Posts

Quote:
 Originally Posted by science_man_88 so in other words the mersennes follow the same test for all repunits 99=10^2-1 and can be tested with a similar test even though it's clearly a multiple of 9
I don't understand this part. GIMPS does not take any modulo operations in LL tests. P95 uses floating point FFT to square the numbers, which in return (in George's words) "it performs the modulo step for free". (see Math page on mersenne.org)

 2012-08-18, 15:15 #41 Damian     May 2005 Argentina 2·3·31 Posts How to test your ANDROID cell phone warranty Good? news! I migrated the old .jar code to android .apk Now you can "test your android warranty" by downloading the lucas lehmer test from the market !! I'm currently testing $2^{86243} - 1$ on a SGS2, will post statistics when it finishes. (Warning: use at your own risk, I didn't optimize the code and it is barely tested)
2012-08-18, 17:36   #42
Damian

May 2005
Argentina

2·3·31 Posts
It finished!

Quote:
 Originally Posted by henryzz 1802 seconds/30 minutes to test 2^23209-1(M26) on one core of a Samsung Galaxy S II. Anyone ever tested higher?
Yes now:

$2^{86243} - 1$ is prime!!
Lasted: 9809679 miliseconds
(That is 2hs 43min 30sec, on my Samsung Salaxy S II)
Biggest prime number ever verified on a cell phone?
Anyone brave enough to surpass that record?

For comparison, I also tested $2^{23209} - 1$:
$2^{23209} - 1$ is prime !!
Lasted: 196668 miliseconds
(That is 3 min 17 sec, MUCH faster than the half an hour it lasted on your converted .apk version)

I didn't optimize it, so I'm not sure why it is so much faster now. How do you know it only uses one core? It seems logical, but still I'm not sure.

 2012-08-19, 14:35 #43 nucleon     Mar 2003 Melbourne 5×103 Posts ok, found the app on google play. Tested M23209 on my HTC velocity 4G (1.5 GHz dual core) 197170ms -- Craig
 2012-08-19, 20:01 #44 Damian     May 2005 Argentina 2×3×31 Posts tested m23209 on motorola xt610 lasted 717510ms on chinese apad lasted 1264250ms

 Similar Threads Thread Thread Starter Forum Replies Last Post Spherical Cow Astronomy 59 2019-01-21 22:47 wblipp Lounge 0 2014-09-09 18:42 Flatlander Puzzles 35 2013-10-31 10:34 tha Hardware 1 2006-09-07 16:24 JuanTutors Lounge 5 2004-08-18 08:53

All times are UTC. The time now is 19:43.

Wed Apr 14 19:43:44 UTC 2021 up 6 days, 14:24, 0 users, load averages: 2.70, 2.53, 2.30