Leave it to the computers - will you?
 

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) ***

N = 2^99-1 = X^3-1 (where X=2[SUP]33[/SUP]), 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 [url]http://primes.utm.edu/primes/search.php[/url] and get done with it.

Now, if you are good at guessing, tell us if
[CODE]N = 89583649921898335546755162597196822062641633175520937530927940881007232352672380501178121583193640839934761013141127170003983125296971622250705020459425891356097027290154854540776876849478569350005562962280855907807148606558950080660092349081097329269014016433631576429222225764264647166787691734028687967269380993741637775905438234504898499851513172201808861942346759871595885006730035499922992220350739500963053465964588797220469241693331794092977369464477733100086937643344942406652051880099885426531750203760438887366916698997512400954654287647236080888144460921500901[/CODE]
is composite or prime. Your turn.

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.

[QUOTE=storflyt32;334307]Can you make a guess about[/QUOTE]something? (anything)[QUOTE=storflyt32;334307]
Of course.[/QUOTE]
You may not be right, but to make a guess, you can.

[QUOTE=storflyt32;334313]C:\Users\Me\DOCUME~1>pfgw32[/QUOTE]

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

[QUOTE=storflyt32;334307]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?
[/QUOTE]
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).

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.

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!

[QUOTE=storflyt32;334454]Is it possible to factorize 2^441-1 ?
[/QUOTE]

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

[QUOTE=bsquared;334461]Yes... it took my computer less than 10 seconds to do.[/QUOTE]
Darn! It took mine 46 seconds...

[QUOTE=EdH;334487]Darn! It took mine 46 seconds...[/QUOTE]
It took mine 1/90 of a second elapsed and 1/1000 second cpu time.
[code]
[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]$
[/code]

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, [b]why[/b] I omitted them.

[QUOTE=xilman;334499]
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.

[/QUOTE]

It would have taken me longer to look up online than it did to type it into an already open csh.

For the record, I was looking it up in parallel... but yafu beat me to the results.

[QUOTE=bsquared;334519]It would have taken me longer to look up online than it did to type it into an already open csh.[/quote]
csh? :shock:

That's the first time i've actually heard of anyone using it. :smile:

[quote]
For the record, I was looking it up in parallel... but yafu beat me to the results.[/QUOTE]

You of all people certainly know it's good stuff. :smile:

[QUOTE=Dubslow;334526]csh? :shock:

That's the first time i've actually heard of anyone using it. :smile:[/QUOTE]

I remember using it when I was at uni in the early 80s.

Apart from the poor implementation issues(which surely could now be corrected?) it looks quite useful. The syntax doesn't look as criptic as perl at first glance.

Which number could be prime for 2^n+1?
 

If you check out [URL]http://en.wikipedia.org/wiki/Mersenne_prime[/URL], it is known from this list that there are a total of 48 known Mersenne primes on the form 2^n-1.

The largest one being the recent discovery of 2^57,885,161-1 .

But when adding 1 to 2^n, apparently 65537 is still the largest known Fermat prime. The list at [URL]http://en.wikipedia.org/wiki/Fermat_prime[/URL] gives the factors for F0 through F11.

My question is then as follows. If using a LLR algorithm or a Genefer specific equivalent to this, how far or high up has this been tested right now when it comes to the possible primality of numbers when it comes to adding 1 when compared to the similar subtraction of 1?

Meaning - testing out whether 2^n + 1 is a prime (n being a very big number, possibly similar to n=57,885,161 mentioned above).

For 2^n+1 it's easy to prove that only Fermat numbers (with n=2^k for some k) have a chance of being prime. These numbers grow very quickly in size; the first such number that might be prime is n=2^33, and short of trial division (which a lot of people have done) there's just no telling. Look up the Pepin test for a deterministic primality test for Fermat numbers. Definitely do [i]not[/i] try it on F33 though.