Poll

2 votes (66.66%)
No votes (0%)
No votes (0%)
No votes (0%)
1 vote (33.33%)
No votes (0%)

3 members have voted

gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 46
  • Posts: 2859
November 8th, 2020 at 2:48:45 PM permalink
delete duplicate.

Edit: Interesting that some of these numbers are Mersenne primes.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4683
November 8th, 2020 at 4:33:42 PM permalink
Quote: gordonm888

Thinking out loud: Does this apply to all integers of the form n= 2m +/- a2k, with a =an integer?


Doubtful, considering 212 + 72x4 = 5,768,897, which is prime
So is 32,687 = 215 - 32x2
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1372
  • Posts: 22846
November 8th, 2020 at 7:05:55 PM permalink
This is indeed interesting! I don't have any good comments offhand, but love how primes have strong correlations like this, but there is still no easy way to check whether a huge number is prime.
It's not whether you win or lose; it's whether or not you had a good bet.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4683
November 8th, 2020 at 7:25:40 PM permalink
Quote: Wizard

This is indeed interesting! I don't have any good comments offhand, but love how primes have strong correlations like this, but there is still no easy way to check whether a huge number is prime.


It depends on what you mean by "easy." Lucas-Lehmer is simple enough, but (a) it only works on Mersenne primes (primes that are one less than a power of 2 - and note that the power to which 2 is raised has to be prime as well, as (2 raised to a nonprime power) minus 1 cannot be prime), and (b) it takes a long time; I think even the fastest computers at the moment need a month to test some numbers.

"The quick version" of Lucas-Lehmer: let N = 2P - 1, where P is a prime. Let S0 = 4, and for all positive integers K, SK = (SK-12 - 2) mod N. N is prime if and only if SP-2 = 0.
Example: let P = 5; N = 31
S1 = (42 - 2) mod 31 = 14
S2 = (142 - 2) mod 31 = 8
S3 = (82 - 2) mod 31 = 0
SP-2 = 0, so 31 is prime
gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 46
  • Posts: 2859
November 8th, 2020 at 11:22:06 PM permalink
Quote: ThatDonGuy

Quote: gordonm888

Thinking out loud: Does this apply to all integers of the form n= 2m +/- a2k, with a =an integer?


Doubtful, considering 212 + 72x4 = 5,768,897, which is prime
So is 32,687 = 215 - 32x2



But (57688972 -1) = 27 * 3 * 7 * 73 * 79 * 163 * 13171. That is 13 prime factors!

And (326872-1) = 25 * 32 * 59 * 227 * 277. That is 10 prime factors.

But clearly since 'a' is these equations is not divisible by 2, we don't get as high an exponent on the 2 in the prime factors expression.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4683
November 9th, 2020 at 6:40:56 AM permalink
Quote: gordonm888

Quote: ThatDonGuy

Quote: gordonm888

Thinking out loud: Does this apply to all integers of the form n= 2m +/- a2k, with a =an integer?


Doubtful, considering 212 + 72x4 = 5,768,897, which is prime
So is 32,687 = 215 - 32x2



But (57688972 -1) = 27 * 3 * 7 * 73 * 79 * 163 * 13171. That is 13 prime factors!

And (326872-1) = 25 * 32 * 59 * 227 * 277. That is 10 prime factors.

But clearly since 'a' is these equations is not divisible by 2, we don't get as high an exponent on the 2 in the prime factors expression.


Oh, you mean (2m +/- a2k)2 - 1, don't you? My bad...
rsactuary
rsactuary 
Joined: Sep 6, 2014
  • Threads: 21
  • Posts: 1807
November 10th, 2020 at 7:11:46 AM permalink
slightly off topic, but for those that like number theory, there is a gentleman on YouTube that does daily math contest type questions. His knowledge is amazing.

Look up Michael Penn. Very informative and reminds me how much of my math knowledge I've lost since graduating 30 years ago.

Here's a problem involving primes.....

https://www.youtube.com/watch?v=G-bzYoKd5ms
gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 46
  • Posts: 2859
November 11th, 2020 at 2:41:35 PM permalink
One of my takeaways from all this is that (n2 -m2) can never be prime because

(n2 -m2) = (n + m) *(n - m).

Therefore, if you were wondering whether 57 was prime or not, you might discover that 57 = (112 -82) and therefore cannot be prime. Indeed, 57 is 3 * 19 which is (11-8) * (11+8). And its obvious that every composite number can be expressed as (n2 -m2) so once you have discovered a suitable n and m you know that (n + m) and (n - m) are factors.

Test for Primes/Factoring Non-Primes (questionable Efficiency.)

Let's say you want to be able test for primeness and determine prime factors for many numbers up to 10,000,000,000; 10E10.

Step 1. Calculate n^2 for all numbers 1 to 10E10 and list the values in ascending order in two look-up tables -one for odd values n^2 and the other for even values of n^2.

Step 2. Given an (odd) number X to be factored, subtract X from all values on the Even n^2 table that are greater than X and less than X^2.

Step. 3 Using a vlookup function or something equivalent, look to see if any of the differences between n^2 and X calculated in step 2 are on the odd table. If they are then you that discovered that X is not prime and you know from the two n^2 values what the two factors are, although those factors are not necessarily prime and may need to be factored further.

Step 4, Repeat Steps 2 and 3 but reverse the roles of the odd N^2 table and Even N^2 table.

Compared to a standard Erasthosthenes sieve where you divide a number X by all primes smaller than sqrt(x) this method has the following advantages:

1. It doesn't require you to know all the primes up to sqrt(X).

2. It substitutes a subtraction operation for the division operation used in the standard sieve technique. My impression is that subtraction of two long numbers is more computationally efficient than division (of two long numbers).

3. If you are undertaking a large number of factorizations the upfront work of calculating all the n^2 values is amortized over many tasks.

Additionally, you could use a hybrid sieve to make this more efficient. Example:

Given an X to test and factorize, first divide X by all prime numbers under 1000 (there are 168 of them). This will quickly identify the great majority of composite numbers under 10E10 as being composite and give you some factors for each successfully identified composite number and is ~0.01 of the maximum number of division operations in the Erastoshenes Sieve method. But by doing this first, it reduces the range of 1 to 10E10 on the precalculated tables of n^2 to instead be from 10E3 to 10E7 - that is a reduction of precalculated values by greater than a factor of 1000. This might make the whole thing more manageable.

Could this help factorize odd numbers that are 10^60 to 10^100? Oh God, probably not. But maybe there is a role.

For example if I am given a number X that has 64 digits -well I don't what the primes are in the range 10^20 to 10^32. But I can start looking at n^2 - X values for n>sqrt(x) and see if any of those n^2 - X differences are a square. I would have to be lucky to find one, but at least its possible.

LOL, I fully expect ThatDonGuy and others to critique this and explain why this is worse than Erastosthenes sieve. But at least give me credit for thinking . . .
Last edited by: gordonm888 on Nov 11, 2020
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4683
November 11th, 2020 at 3:56:55 PM permalink
Quote: gordonm888

LOL, I fully expect ThatDonGuy and others to critique this and explain why this is worse than Erastosthenes sieve. But at least give me credit for thinking . . .


Challenge accepted!

Doesn't your method make the assumption that every nonprime number can be expressed as the difference of two squares?

Try your method with X = 10. What happens?

Also, you need to make sure that if you do find two squares, they aren't consecutive, as otherwise one of your factors will be 1. Note that every positive odd number can be expressed as the difference of two (consecutive) primes.
gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 46
  • Posts: 2859
November 11th, 2020 at 4:05:25 PM permalink
Okay, again let's assume you have an integer X and you want to test to see whether there is a solution to

n2 - m2 = X

as a way to find factors of X.

I believe we can use modular arithmetic to develop selection rules so that we don't need to test all values of n and n2 to see if an m2 solution exists.

Any square of an integer is congruent with (0,1,4,5,6,9)mod10. Thus we know that m2 cannot be congruent with (2,3,7,8)mod 10.

Now lets say that our mystery number X ends with a last digit of 7. We know that there will be no value of n2 that ends in 9, 0, 4 or 5 that can satisfy the equation because that would require a value of m2 that ends in 2,3,7 or 8.

- If n2 cannot end in 9 then n cannot end in 3 or 7.
- If n2 cannot end in 0 then n cannot end in 0.
- If n2 cannot end in 4 then n cannot end in 2 or 8.
- If n2 cannot end in 5 then n cannot end in 5.

So, given that X ends in 7, when searching for a set of (n,m) that satisfy the equation, we need only look at values of n that end in 1,4,6 or 9. We have effectively reduced the possibilities to look at by 60%!

If X ends in 1 then n cannot have a 2, 3, 7 or 8 as its last digit.
If X ends in 3 then n cannot have a 0, 1, 4, 5, 6 or 8 as its last digit.
If X ends in 9 then n cannot have a 1, 4, 6, or 9 as its last digit.

I suspect that if one went into a different number base one might be able to develop additional selection rules that could further eliminate values of n^2 that are possible solutions.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.

  • Jump to: