mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-05-05, 23:51   #23
Graph2022
 
May 2022

32 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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 # ?
Graph2022 is offline   Reply With Quote
Old 2022-05-06, 02:33   #24
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

5×13×53 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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)?
sweety439 is offline   Reply With Quote
Old 2022-05-06, 05:30   #25
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

101508 Posts
Default

Quote:
Originally Posted by Graph2022 View Post
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.

Last fiddled with by paulunderwood on 2022-05-06 at 05:34
paulunderwood is online now   Reply With Quote
Old 2022-05-06, 06:48   #26
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

5×13×53 Posts
Default

Quote:
Originally Posted by Graph2022 View Post
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

Last fiddled with by sweety439 on 2022-05-06 at 06:53
sweety439 is offline   Reply With Quote
Old 2022-05-06, 08:20   #27
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

3×73 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
kruoli is offline   Reply With Quote
Old 2022-05-06, 12:03   #28
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

26×7×13 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2022-05-06, 12:45   #29
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

5×13×53 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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, ...)

Last fiddled with by sweety439 on 2022-05-06 at 12:49
sweety439 is offline   Reply With Quote
Old 2022-05-06, 13:40   #30
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

26×7×13 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Quote:
Originally Posted by Dr Sardonicus View Post
Algebraic factorization can also prove compositeness.
<snip>
Well, my article has many examples of algebraic factorization
<snip>
Since you stated just a few posts back that
Quote:
Originally Posted by sweety439 View Post
Only trial division can be used
I would say the fact stands proven, that you don't pay much attention to your own work.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Presentation Thecmaster GPU to 72 6 2019-03-22 07:21
mersenne prime number application? Tamay82 Information & Answers 3 2018-09-08 16:34
Torture and Benchmarking test of Prome95.Doubts in implementation paramveer Information & Answers 32 2012-01-15 06:05
anyone seen this presentation? ixfd64 Factoring 9 2010-09-21 19:39
my first research paper presentation ixfd64 Lounge 2 2004-11-05 23:42

All times are UTC. The time now is 23:36.


Fri Jun 24 23:36:40 UTC 2022 up 71 days, 21:37, 0 users, load averages: 1.51, 1.82, 2.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔