Leave it to the computers - will you?

[storflyt32]

Can you make a guess about a number being prime just by looking at it?

Of course. First of all the number in question needs to be an odd one.

But perhaps not ending in 5 (psst, psst).

Take 2^99-1 for example. It writes out as
633825300114114700748351602687 (2^99-1) and it is not a prime.

Why so?

Try factorize it. You should end up with this number being expressed as 7*23*73*89*199*153649*599479*33057806959.

Should I say something about the factors I got here as well? Make up your own guess.

*** 299556989487*2^1290000-1 (doublechecker) ***

[Batalov]

N = 2^99-1 = X^3-1 (where X=2³³), so X-1 divides it, therefore N is composite.

If someone gave it to you as a decimal N = 633825300114114700748351602687, you could start trial factoring N, N-1 and N+1, and for this particular N, you would have soon found the N+1 = 2^99 = X^3 and establish that it is a composite as shown in the first paragraph.

For 299556989487*2^1290000-1, you simply enter it in the search field at http://primes.utm.edu/primes/search.php and get done with it.

Now, if you are good at guessing, tell us if

N = 89583649921898335546755162597196822062641633175520937530927940881007232352672380501178121583193640839934761013141127170003983125296971622250705020459425891356097027290154854540776876849478569350005562962280855907807148606558950080660092349081097329269014016433631576429222225764264647166787691734028687967269380993741637775905438234504898499851513172201808861942346759871595885006730035499922992220350739500963053465964588797220469241693331794092977369464477733100086937643344942406652051880099885426531750203760438887366916698997512400954654287647236080888144460921500901

is composite or prime. Your turn.

[storflyt32]

C:\Users\Me\DOCUME~1>pfgw32 --
Enter expression followed by carriage return:
89583649921898335546755162597196822062641633175520937530927940881007232352672380
50117812158319364083993476101314112717000398312529697162225070502045942589135609
70272901548545407768768494785693500055629622808559078071486065589500806600923490
81097329269014016433631576429222225764264647166787691734028687967269380993741637
77590543823450489849985151317220180886194234675987159588500673003549992299222035
07395009630534659645887972204692416933317940929773694644777331000869376433449424
06652051880099885426531750203760438887366916698997512400954654287647236080888144
460921500901

PFGW Version 3.4.9.32BIT.20110630.Win_Dev [GWNUM 26.6]
PRP: 8958364992189833....8144460921500901 1/1899 mro=0.015625 sum=10463171.08/0.
PRP: 8958364992189833....8144460921500901 1899/1899 mro=0.015625 sum=10463171.08
89583649921898335546755162597196822062641633175520937530927940881007232352672380
50117812158319364083993476101314112717000398312529697162225070502045942589135609
70272901548545407768768494785693500055629622808559078071486065589500806600923490
81097329269014016433631576429222225764264647166787691734028687967269380993741637
77590543823450489849985151317220180886194234675987159588500673003549992299222035
07395009630534659645887972204692416933317940929773694644777331000869376433449424
06652051880099885426531750203760438887366916698997512400954654287647236080888144
460921500901 is composite: RES64: [8A78C88F760440DE] (0.2343s+0.1494s)

C:\Users\Me\DOCUME~1>

Apparently this number is composite.

But the strange thing is that there have been quite many Mersenne prime numbers being found.

But the same may not be true for the Genefer numbers, despite being slightly smaller, N being 1048576 or 4194304. The value being used for b may increase their sizes, though.

What is the reason for it being so?

Another interesting question: Apparently 5795*2^5795+1 is a prime number.

What is the decimal representation for this number? It should have 1749 digits.

And not forgetting this weird number either.

393050634124102232869567034555427371542904833

It's a Cullen number, 141*2^141+1 (141=3*47, by the way).

And it possibly may run a little faster using a DOS command prompt Window:

C:\Users\Me\DOCUME~1>pfgw32 --
Enter expression followed by carriage return:
90825*2^90825+1
PFGW Version 3.4.9.32BIT.20110630.Win_Dev [GWNUM 26.6]
90825*2^90825+1 is 3-PRP! (9.8721s+0.0047s)

Another Cullen prime there.

[LaurV]

Originally Posted by storflyt32

Can you make a guess about

something? (anything)

Originally Posted by storflyt32

Of course.

You may not be right, but to make a guess, you can.

[Mr. P-1]

Originally Posted by storflyt32

C:\Users\Me\DOCUME~1>pfgw32

I thought the point of the exercise was the determine the status of the number "just by looking at it" i.e., without recourse to computation. This is what Batalov did with your two challenge numbers.

[m_f_h]

Originally Posted by storflyt32

Can you make a guess about a number being prime just by looking at it?

Take 2^99-1 for example. It writes out as
633825300114114700748351602687 (2^99-1) and it is not a prime.

Why so?

I think anyone who comes to this forum with at least half-way serious intentions has already seen the well known factorization of 2^ab - 1 which is also valid for any other x^ab - 1 and based on the even more general X^b - 1 = (X - 1)(X^(b-1) -+ ... - X + 1).

[storflyt32]

I was wondering about this. Perhaps someone bother answering me.

I have just installed Windows to a new partition on a new disc today. Not all my data are currently available to me because of this.

Anyway, I was able to download a version of the pfgw software which apparently is a quite recent version. I am getting quite decent run times when testing this out in a Windows DOS prompt.

Prime numbers are divided into different types. PPS LLR / PPS LLR Extended, Sophie Germain are two or three of the short types. Woodall, Prime Sierpinski and Genefer are three of the long types of prime numbers.

You are supposed to believe that there is no given or defined rule for the value of k being tested vs. or against N. A PPS LLR number like 1019*2^1790495+1 is known to be not a prime number because it is consisting of or having two or more factors in it.

Same goes for a PPS LLR Extended number like 2437*2^1090800+1 which also is known to be not a prime number.

In this case you are adding 1 at the end in order to make it an odd number for the computer to process.

For a Sophie Germain number like 508226744727*2^1290000-1 you instead subtract 1 at the end and in the same way get an odd number to compute.

This number also known to be not a prime number as well.

Common for all of these numbers are that the factors these numbers are supposed to be having are not known. The algorithm which is being used (LLR) is not supposed to or being capable at finding out whether a given number of such a size is having any factors - only whether or not the number in question is a prime number or not may be found this way.

The question really is as follows: When are the factors of a given number "converging" and you are getting only "one" - meaning that the number in question is a prime?

Following are three sample outputs from a DOS command prompt using pfgw32 in Windows 7 Ultimate, 32 bits:

C:\Users\Me\DOCUME~1\PFGW_W~1.3_2>pfgw32 --
Enter expression followed by carriage return:
1019*2^1790495+1
PFGW Version 3.7.3.32BIT.20130210.Win_Dev [GWNUM 27.8]
1019*2^1790495+1 is composite: RES64: [18BF21B1C3287056] (2462.6789s+0.0005s)


C:\Users\Me\DOCUME~1\PFGW_W~1.3_2>pfgw32 --
Enter expression followed by carriage return:
2437*2^1090800+1
PFGW Version 3.7.3.32BIT.20130210.Win_Dev [GWNUM 27.8]
2437*2^1090800+1 is composite: RES64: [4374FA2883FA3F0D] (1040.3614s+0.0004s)


C:\Users\Me\DOCUME~1\PFGW_W~1.3_2>pfgw32 --
Enter expression followed by carriage return:
508226744727*2^1290000-1
PFGW Version 3.7.3.32BIT.20130210.Win_Dev [GWNUM 27.8]
508226744727*2^1290000-1 is composite: RES64: [EC5DB56429811921] (1830.5552s+0.0006s)

The first of the tasks above is PPS LLR, the second one is PPS LLR Extended. The third task is a Sophie Germain number.

As you may be able to see, the Sophie Germain task took a little longer to compute. Except for its name, the PPS LLR Extended tasks typically are having shorter run time lengths than the similar or corresponding PPS LLR.

[storflyt32]

Is it possible to factorize 2^441-1 ?

Apparently this number is not a prime number.

In return I may give you this one.

C:\Users\Me\DOCUME~1\PFGW_W~1.3_2>pfgw32 --
Enter expression followed by carriage return:
2^859433-1
PFGW Version 3.7.3.32BIT.20130210.Win_Dev [GWNUM 27.8]
2^859433-1 is 3-PRP! (1319.0470s+0.0004s)

Download this software and find prime numbers on your own.

Have fun!

[bsquared]

Originally Posted by storflyt32

Is it possible to factorize 2^441-1 ?

Yes... it took my computer less than 10 seconds to do.

[EdH]

Originally Posted by bsquared

Yes... it took my computer less than 10 seconds to do.

Darn! It took mine 46 seconds...

[xilman]

Originally Posted by EdH

Darn! It took mine 46 seconds...

It took mine 1/90 of a second elapsed and 1/1000 second cpu time.

[pcl@anubis cunningham]$ time grep '^441' 2-.txt
441	126127.309583.5828257.4487533753346305838985313.	P34

real	0m0.011s
user	0m0.000s
sys	0m0.001s
[pcl@anubis cunningham]$

Surely that's how anyone would factor something that small and that well known these days? Perhaps you may not have the luxury of a local file but it wouldn't take either factordb or Google much longer.


P.S. Don't spoil the fun by giving the missing factors. Let the OP learn something by finding them and, more importantly, why I omitted them.