Presentation and doubts with the application and competition of 100000000 prime digits

[Graph2022]

Originally Posted by Prime95

Welcome aboard. Prime95 can do a *probable* prime test on numbers of the for k*b^n+c where k,b,n,c are all "small". There are other programs that may or may not be able to prove those numbers prime depending on the values of k,b,n,c.

There are no programs that can prove an arbitrary 100,000,000 digit number prime.

Hi. It is not possible to check if 100,000,000 digit is prime.
How quick is is to generate the number itself though? let's say 2^470,000,001 generates 100,000,000+ digit # ?

[sweety439]

Originally Posted by Prime95

Welcome aboard. Prime95 can do a *probable* prime test on numbers of the for k*b^n+c where k,b,n,c are all "small". There are other programs that may or may not be able to prove those numbers prime depending on the values of k,b,n,c.

There are no programs that can prove an arbitrary 100,000,000 digit number prime.

Can Prime95 do a PRP test on general case (k*b^n+c)/gcd(k+c,b-1) (see my minimal prime problem)?

[paulunderwood]

Originally Posted by Graph2022

Hi. It is not possible to check if 100,000,000 digit is prime.
How quick is is to generate the number itself though? let's say 2^470,000,001 generates 100,000,000+ digit # ?

2^470000001 in binary is 1 followed by 470,000,001 zeroes. Using 64 bits per limb -- 7,343,751 limbs. How long does it take to allocate and zero (non static) memory of this many words when the speed of RAM is 2133 MT/s is .. erm... pretty fast

If you want to save its decimal representation to file then the bottleneck is there.

If you want to print it out it would depend on font size and the speed of your printer.

[sweety439]

Originally Posted by Graph2022

Hi. It is not possible to check if 100,000,000 digit is prime.

Only trial division can be used (if the number has small prime factors, say < 2^32), e.g. large Fermat numbers and large double Mersenne numbers

However, if such large numbers are in fact primes, then this will not be proven in our lifetime (even if N-1 or/and N+1 can be trivially 100% factored), e.g. if the Fermat number F34 and/or the double Mersenne number MM127 are in fact primes, then they will not be proven prime (or PRP, e.g. 3-PRP) in our lifetime

[kruoli]

Originally Posted by sweety439

Can Prime95 do a PRP test on general case (k*b^n+c)/gcd(k+c,b-1) (see my minimal prime problem)?

Yes, PRP=k,b,n,c,"divisor", where divisor must be calculated manually. Please be aware that the quotation marks must remain in the worktodo entry. Please be also be aware that this is not feasible for very small numbers.

[Dr Sardonicus]

Algebraic factorization can also prove compositeness.

If p and q are prime, 2^(p*q) - 1 has 2^p - 1 and 2^q - 1 as proper factors, regardless of whether these factors are prime. If p > 10^8 and q > 10^8, it might take a while to find factors of 2^(p*q) - 1 by trial division.

Since 470000001 = 3*156666667, I can absolutely guarantee that 2^470000001 - 1 is composite. It has 2^3 - 1 = 7 as a prime factor, and 2^156666667 - 1 as a proper factor. The latter has the prime factor 90287940192103.

[sweety439]

Originally Posted by Dr Sardonicus

Algebraic factorization can also prove compositeness.

If p and q are prime, 2^(p*q) - 1 has 2^p - 1 and 2^q - 1 as proper factors, regardless of whether these factors are prime. If p > 10^8 and q > 10^8, it might take a while to find factors of 2^(p*q) - 1 by trial division.

Since 470000001 = 3*156666667, I can absolutely guarantee that 2^470000001 - 1 is composite. It has 2^3 - 1 = 7 as a prime factor, and 2^156666667 - 1 as a proper factor. The latter has the prime factor 90287940192103.

Well, my article has many examples of algebraic factorization and small prime factors, or the combine of them, to prove that a family contain no primes, some families require the combine of them, e.g. 8DDD...DDD in base 14, BBB...BBB9B in base 12, DDD...DDD5 in base 14, 1999...999 in base 17, 1666...666 in base 19, contain no primes (only count the numbers > base)

See my post for the factorization pattern for some families, to show that these families contain no primes (only count the numbers > base)

Also, when we sieve a given family (xyyy...yyyz in given base b, the family is (a*b^n+c)/gcd(a+c,b-1) for some integers a > 0 and c != 0, with gcd(a,c) = 1 and gcd(b,c) = 1), we delete the n such that (a*b^n+c)/gcd(a+c,b-1) have small prime factors (say < 2^32), as well as a*b^n+c has algebraic factorization (difference of squares, difference of cubes, Aurifeuillian factorization for x^4+4*y^4, ...)

[Dr Sardonicus]

Originally Posted by sweety439

Well, my article has many examples of algebraic factorization
<snip>

Since you stated just a few posts back that

Originally Posted by sweety439

Only trial division can be used

I would say the fact stands proven, that you don't pay much attention to your own work.