SoylentNews is people
SoylentNews
Submitted via IRC for Bytram
What Is an "Almost Prime" Number?
When I saw a math paper with the phrase "almost prime" in the title, I thought it sounded pretty funny. It reminded me of the joke about how you can't be a little bit pregnant. On further thought, though, it seems like someone whose pregnancy is 6 weeks along and who hasn't yet noticed a missed period is meaningfully less pregnant that someone rounding the bend at 39 weeks who can balance a dinner plate on their belly. Perhaps "almost prime" could make sense too.
A number is prime if its only factors are 1 and itself. By convention, the number 1 is not considered to be prime, so the primes start 2, 3, 5, 7, 11, and so on. Hence, a prime number has one prime factor. A number with two prime factors, like 4 (where the two factors are both 2) or 6 (2×3) is definitely less prime than a prime number, but it kind of seems more prime than 8 or 30, both of which have three prime factors (2×2×2 and 2×3×5, respectively). The notion of almost primes is a way of quantifying how close a number is to being prime.
(Score: 3, Insightful) by pkrasimirov on Monday November 05 2018, @02:37PM (1 child)
Hmm... methinks if this can be used in encryption somehow... like a crypto that can result in few plaintexts but only one of them makes sense (checksum matches).
(Score: 1, Informative) by Anonymous Coward on Monday November 05 2018, @02:54PM
Sure. 2-almost primes (that is, products of two primes) are an essential part of the RSA algorithm.
(Score: 3, Funny) by takyon on Monday November 05 2018, @02:38PM (10 children)
Fake Primes
[SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
(Score: 2) by requerdanos on Monday November 05 2018, @04:50PM (5 children)
Consider that you can substitute the word "not" for the word "almost" anywhere it's grammatically allowable and have a less ambiguous, easier-to-evaluate version that retains the truth of the original statement.
One of the truisms that I am proud to have taught my son is that if you're in doubt about the meaning of a statement containing the word "almost", remember that almost means "not".
(Score: 1, Informative) by Anonymous Coward on Monday November 05 2018, @05:06PM (2 children)
Playing the lottery almost always leads to a loss.
Playing the lottery not always leads to a loss.
Sure, both statements are true. But the first one contains more useful information.
(Score: 2) by requerdanos on Monday November 05 2018, @05:22PM
You probably weren't in doubt, as the author of at least the headline of this story seems to be.
(Score: 2) by kazzie on Monday November 05 2018, @06:26PM
The second statement is better for marketing purposes, though.
(Score: 2) by Pino P on Monday November 05 2018, @05:56PM (1 child)
Is "some composite numbers are more composite than others, and this difference may be useful for some purpose in number theory" more honest?
(Score: 2) by requerdanos on Monday November 05 2018, @06:40PM
In this case, the following statements can be true (let x=26, for example):
"x is not prime"
"x is less composite than other not-prime numbers of similar magnitude in terms of number of factors"
So no, something completely true about a number's being prime or not is not more honest than something completely true about a number's set of available factors. Each statement tells you something completely true about the number.
If you're in doubt, remember that "almost prime" means that a number isn't prime, and so you're talking about its properties as a composite number. If you're not in doubt, then this probably won't help you.
(Score: 2) by DannyB on Monday November 05 2018, @05:55PM (1 child)
Not Fake Primes.
The opposite of primefulness is Highly composite numbers. [wikipedia.org] Or google for Superior Highly Composite Numbers. [wikipedia.org]
(that would be even better than having a full 640 K of memory)
When trying to solve a problem don't ask who suffers from the problem, ask who profits from the problem.
(Score: 2) by Pino P on Monday November 05 2018, @06:10PM
Unless Gates's editor mistakenly cut off the end of "an easy way to factor large prime numbers" out of a large semiprime. In this sense, one would speak of factoring 3 and 5 out of 15.
(Score: 2) by DannyB on Monday November 05 2018, @05:58PM (1 child)
A scale of primeleyness from prime to infinitely composite maybe?
What would be infinitely composite? Infinity factorial? What could be more composite than multiplying together every possible number?
When trying to solve a problem don't ask who suffers from the problem, ask who profits from the problem.
(Score: 2) by bzipitidoo on Wednesday November 07 2018, @04:22AM
> What could be more composite than multiplying together every possible number?
Powers of 2. The smallest n-almost prime number is 2^n.
(Score: 2, Insightful) by Anonymous Coward on Monday November 05 2018, @03:03PM (9 children)
1 isn't a non-prime purely by convention, it's a byproduct of being the multiplicative identity. A prime is essentially any number that only has 2 whole number factors 1 and itself. 1 has factors of the form 1^x, meaning that it fails the definition. And because it fails the definition they had to put a caveat that the paper doesn't apply to 1 so often that they went the extra step of specifying that it's not prime even though it probably shouldn't have been in the first place.
(Score: 2) by DannyB on Monday November 05 2018, @06:01PM (1 child)
1 also has factors of the form x0.
When trying to solve a problem don't ask who suffers from the problem, ask who profits from the problem.
(Score: 2) by vux984 on Monday November 05 2018, @06:41PM
so does every other number. :)
(Score: 2) by wonkey_monkey on Monday November 05 2018, @07:15PM (3 children)
We could avoid all this "except 1" nonsense if we just went with "prime numbers are integers with exactly two divisors."
systemd is Roko's Basilisk
(Score: 2) by wonkey_monkey on Monday November 05 2018, @07:18PM (2 children)
Postive integers, that is.
systemd is Roko's Basilisk
(Score: 0) by Anonymous Coward on Monday November 05 2018, @08:02PM (1 child)
To be clear: "Prime numbers are positive integers with exactly two (i.e., one pair of) positive integer divisors." Here "divisor" is also assumed to be the more restrictive definition of a number which divides into another without remainder, rather than simply a number that divides into another.
Not sure this is a simpler definition of "prime number."
(Score: 2) by wonkey_monkey on Tuesday November 06 2018, @05:41PM
It's simpler because it doesn't need an exception to be specified.
systemd is Roko's Basilisk
(Score: 2) by vux984 on Monday November 05 2018, @07:23PM
You are right but you wrote that really awkwardly.
"A prime is essentially any number that only has 2 whole number factors 1 and itself."
So... 1 has 1 as a factor. Check. 1 has itself as a factor. Check. There are no other factors: Check. So it's prime?
Or did you mean that the "2 whole numbers" had to be 2 different whole numbers? because that could be read as just enumerating the two criteria of its factors. And the use of 'and' in '1 and itself ' as a logical operator does not imply the two operands not be identical. Also you forgot positive, so now -1 is maybe prime too. :p
"1 has factors of the form 1^x, meaning that it fails the definition"
Why? 1^x = 1. Your "essential" definition of prime clearly says 1 is allowed. The fact that you found out how to write 1 a 2nd way doesn't change that.
I mean 17 has factors of the form ((17+x)-x) but that doesn't make 17 not prime, right?
The main reason 1 isn't considered prime is due to the fact that unique prime factorizations* are really useful. If 1 is allowed to be prime, then each positive number > 1 would not have a unique prime factorization; since you could repeat the 1 factor any number of times.
And yes, that does come from the fact that 1 is the multiplicative identity; so we exclude 1.
Although we could have just defined unique prime factorizations to only include prime numbers greater than 1; but since factorization is the most important application of primes, including 1 in the set, and then excluding it everytime you used the set doesn't make a lot of sense.
* Fundamental Theorem of Arithmetic states that each positive number greater than 1 ** has a unique prime factorization.
** See how many other theorems and proofs also have to explicitly exclude 1 from the set of positive numbers! We should have just excluded 1 from the set of positive whole numbers too, right? :) Except it would be really weird if 1 were excluded from positive numbers when dealing with rational and real numbers, and inconsistent to include it in positive reals but not positive integers...
Meanwhile there aren't really any cases where having 1 in the set of primes gives us anything especially useful, and no inconsistencies arise by leaving it out.
(Score: 3, Funny) by theluggage on Monday November 05 2018, @07:42PM (1 child)
...but has it cleared its own orbit?
(Score: 0) by Anonymous Coward on Monday November 05 2018, @08:10PM
Yes. Proof? Graph any function f(x)=b^x where b>0 is not 1. The function will blow up toward infinity one way or another (depending on whether b is less than 1 or greater than 1). For an arbitrary number of factors (e.g., b^x * c^y * d^z *...., where b, c, d, etc. are all different and not 1), the function will blow up as the exponents increase. This simulates any possible composite number with factors other than 1.
Now graph f(x) = 1^x. It's a line. Any other number has limits that are infinitely far away from the line y=1. We must therefore conclude that all the other integers are afraid of 1 and run away from it over time. Hence, the number 1 will definitely clear its "factor orbit" as we go toward infinity, just like any good multiplicative identity.
(Score: 3, Funny) by inertnet on Monday November 05 2018, @03:32PM
"I'm not pregnant, not even a little bit."
"No, but if it were up to me, you're almost pregnant."
(Score: 2, Interesting) by DECbot on Monday November 05 2018, @03:33PM (3 children)
I think a good example of almost prime could be negative prime numbers. By definition they cannot be prime as they are specifically excluded even though their absolute values are prime numbers. Also, I would consider 1 and 0 to be an almost prime numbers as their only factors are either itself (i.e. 1) or infinity and itself (i.e. 0).
cats~$ sudo chown -R us /home/base
(Score: 2) by vux984 on Monday November 05 2018, @07:41PM (2 children)
"I think a good example of almost prime could be negative prime numbers."
Negative numbers get messy due to -1; if you allow negative numbers you pretty much have to make -1 prime. (its only factors are 1 and itself right? :) but if you make -1 prime then all the numbers now have infinite factorizations involving -1
3 = -1 * -1 * -1 * -1 * 3
-3 = -1 * -1 * -1 * 3
An infinite number factorizations is the main reason why 1 got excluded from the set.
"1 and 0"
1 was excluded to do infinite factorizations.Not just of itself (1, 1x1, 1x1x1, 1x1x1x1...), but of all other numbers.
0 has infinite factorizations no matter what you do: (0, 0x1, 0x2, 0x1x1, 0x3, 0x2x3...);
(Score: 0) by Anonymous Coward on Monday November 05 2018, @11:30PM (1 child)
Ring theorists sorted out the generalization of prime numbers to arbitrary commutative rings ages ago.
Primes are by definition non-zero and non-units (units are elements with multiplicative inverses in the ring). For the ring of integers both -1 and 1 have inverses, therefore they are units, therefore they are not primes. Specifically, for a commutative ring R, a non-zero, non-unit element p ∈ R is prime if, whenever p divides ab for some a, b ∈ R, then p divides a or p divides b.
A related concept is an irreducible element. A non-zero, non-unit element is irreducible if it cannot be expressed as the product of two non-units. This definition is most similar to the definition of "prime number" that is often taught in grade school. For the integers, there is no difference between these two definitions: in a unique factorization domain (such as the integers) an element is prime if and only if it is irreducible.
You will note that in either case, were units not specifically excluded they would trivially satisfy both definitions. The only reason to exclude them is convention: because unique factorization is such an important property, it is simpler to exclude units from the definition of prime than to write "non-unit prime" everywhere.
(Score: 2) by vux984 on Tuesday November 06 2018, @10:32PM
Agreed. And thanks for the contribution of the ring theoretic angle!
Heh, pretty much exactly what I said in a different sub-thread :)
"The main reason 1 isn't considered prime is due to the fact that unique prime factorizations* are really useful. If 1 is allowed to be prime, then each positive number > 1 would not have a unique prime factorization; since you could repeat the 1 factor any number of times.
And yes, that does come from the fact that 1 is the multiplicative identity; so we exclude 1.
We could have just defined unique prime factorizations to only include prime numbers greater than 1; but since factorization is the most important application of primes, including 1 in the set, and then excluding it every time you used the set doesn't make a lot of sense.
https://soylentnews.org/comments.pl?sid=28427&cid=758145 [soylentnews.org]
(Score: 2, Interesting) by opinionated_science on Monday November 05 2018, @03:45PM (4 children)
a) 277,232,917 is REALLY REALLY not prime.
b) 277,232,917-1 is prime.
If we could find b) from a), they wouldn't need to hunt for them...
(Score: 5, Funny) by DannyB on Monday November 05 2018, @06:04PM
Primes wouldn't be so hard to find if we were more responsible and did not hunt them almost to extinction.
When trying to solve a problem don't ask who suffers from the problem, ask who profits from the problem.
(Score: 3, Insightful) by vux984 on Monday November 05 2018, @07:28PM (2 children)
Eh?? We do find b) from a)
Primes of the form of 2^n-1 are Mersenne primes; and they are much easier to find than other primes because of that relationship. You obviously know this because you didn't pick that exponent out of a hat; so I'm more confused by your post than anything else.
(Score: 2) by opinionated_science on Monday November 05 2018, @08:40PM (1 child)
the *form* is know. The hunt is "let's test everyone until we find one".
So, no. Not predictive, though there are other useful properties that can be exploited.
To help your google search look up "relative primes".
(Score: 2) by vux984 on Monday November 05 2018, @10:28PM
I was under the impression that large Mersenne primes were easier to find (and test) than other primes. So the form gives you candidates to test, and that there are algorithms that were specifically useful only for testing Mersenne candidates, but were quite a bit more efficient than testing other primes.
For example, the EFF prize for finding a 100 M digit prime number does not require a Mersenne prime; but anyone looking to claim that prize is looking for Mersenne primes because the odds of finding an proving a mersenne prime are a lot higher.
So that would make the form somewhat predictive.
(Score: 0) by Anonymous Coward on Monday November 05 2018, @04:01PM (7 children)
Pregnant is a simple yes/no field. Time elapsed within pregnancy is a separate value entirely. It should be a NULL value if the Pregnant field is set to NO, but I suppose there could be edge cases where that doesn't entirely hold true. Regardless though, they aren't the same thing - so good data hygiene practices should cause you to track them separately rather than overloading the definition of the one field.
Honestly, mathematicians and their sloppy data management. Hrmph.
(Score: 3, Insightful) by Anonymous Coward on Monday November 05 2018, @04:27PM (2 children)
pregnant is not a yes/no field.
you can have sex now, not be pregnant for a few hours, and then be pregnant for the following 9 months.
or you can be pregnant for a few weeks and then not be pregnant again, and never actually realize you were pregnant (apparently this is quite common).
it depends on the definition of "pregnant", plus the probability of sperm to fertilize egg, plus probability of fertilized egg to travel to the proper place, etc.
(Score: 0) by Anonymous Coward on Monday November 05 2018, @05:22PM
Pregnant is a yes/no field. How and when preconditions occurred is not relevant to evaluating the current state of pregnancy. If you're going to argue that when sex was had determines current state of pregnancy, you might as well argue that a near-future miscarriage means that that a person isn't pregnant now.
(Score: 0) by Anonymous Coward on Monday November 05 2018, @10:18PM
Slashdot: where idiots argue over what it means to be pregnant.
(Score: 0) by Anonymous Coward on Monday November 05 2018, @04:56PM (2 children)
You'd think, but then previous yes/no answers are no longer so cut and dry.
Are you a male?
(Score: 1, Funny) by Anonymous Coward on Monday November 05 2018, @07:08PM (1 child)
I'm an Anonymous Coward striving for (and apparently failing to acquire) a +1 Funny. Perhaps data management and mathematics jokes aren't as universally accessible as I'd thought.
(Score: 3, Touché) by c0lo on Monday November 05 2018, @11:32PM
The process of growing up takes quite a long time in males.
I'm happy (for you) to see you haven't stopped on the way.
https://www.youtube.com/watch?v=aoFiw2jMy-0 https://soylentnews.org/~MichaelDavidCrawford
(Score: 2) by Pino P on Monday November 05 2018, @05:59PM
0 people growing inside a fertile woman: Not pregnant
1 person growing inside a fertile woman: Pregnant
2 people growing inside a fertile woman: More pregnant, in this case with twins
(Score: 2) by ikanreed on Monday November 05 2018, @04:44PM (1 child)
When you see kind of basic things from a field of study as a news story.
Prime factoring fits into a lot of abstract algebra, and "near primes" are(obviously) more likely to be coprime to other numbers than prime primes. Coprimality is, as others have noted, an important aspect of encryption, as, after the first 2k prime test, checking corprimality between public and private keys is the next step of validating their "real" primeness.
(Score: 2) by Freeman on Monday November 05 2018, @06:07PM
This is why I'm not a mathematician. I get the need for encryption, but actually understanding the math behind it is a whole other ballgame.
Joshua 1:9 "Be strong and of a good courage; be not afraid, neither be thou dismayed: for the Lord thy God is with thee"
(Score: 0) by Anonymous Coward on Monday November 05 2018, @04:54PM (1 child)
But I remember some not ready for prime actors in the seventies.
(Score: 2) by DannyB on Monday November 05 2018, @06:07PM
When actors are past their prime, they are composite and begin the process of de-compositing.
When trying to solve a problem don't ask who suffers from the problem, ask who profits from the problem.
(Score: 2) by istartedi on Monday November 05 2018, @06:05PM (4 children)
Prime is just a special case of "how many factors do you have?". At the human level we're comfortable dealing with numbers that have a few factors like 42=2*3*7, but when you get up into astronomical numbers there are going to be monsters with 100 factors. In that realm, a number with 2 factors starts to seem "almost prime". Thinking about primes this way might help us develop a better understanding of any patterns that are lurking way out there in the infinity of natural numbers. Does it even make sense for us to just bash our heads about primes? Maybe we'd learn something by looking for patterns in the N-factor space. How many numbers have 42 factors? I guess it's infinity like primes but I don't have the math chops to prove it. Let's commandeer that Bitcoin hardware and find the largest 42-factor number we can...
Appended to the end of comments you post. Max: 120 chars.
(Score: 2) by DannyB on Monday November 05 2018, @06:12PM (3 children)
Like 100 factorial.
When computing a factorial, half the numbers multiplied are even, thus composite. Many are more composite than that.
Imagine an infinite tape with all of the prime numbers printed on it.
Now have 42 such tapes in parallel, like an odomoter in a car. You can scroll any of the 42 positions to anywhere on their respective tape. It seems there are an infinite number of numbers with 42 factors, since the tapes are infinite.
When trying to solve a problem don't ask who suffers from the problem, ask who profits from the problem.
(Score: 2) by DannyB on Monday November 05 2018, @07:19PM (2 children)
I had to submit my post to rush out as coworkers were heading out the door for lunch . . .
. . . but now that I'm back:
infinity ^ 42 power means there are an infinite number of numbers with 42 factors.
When trying to solve a problem don't ask who suffers from the problem, ask who profits from the problem.
(Score: 2) by pipedwho on Tuesday November 06 2018, @01:55AM (1 child)
Simpler to understand: n^42 where n is one of infinite primes. There are also infinite non-repeating prime factors: take 41 primes and multiply them together. If there are infinite primes then for each prime, make it the 42nd factor of the composite number. Therefore infinite primes implies infinite composite numbers with exactly 42 prime factors.
(Score: 2) by istartedi on Tuesday November 06 2018, @05:09AM
While n^42 definitely proves the set of 42-factor numbers is infinite because the set of primes is infinite, this proof feels a bit sterile since it only refers to raising primes to the 42nd power. The original poster who asked me to imagine infinite tapes was actually more appealing, except that it wasn't expressed in math notation. With the infinite tape image in your head, you can imagine any one of the infinite primes being scrolled into position to build any 42-factor number you desire.
Appended to the end of comments you post. Max: 120 chars.
(Score: 2, Funny) by ChrisMaple on Monday November 05 2018, @06:18PM (1 child)
I think it's acceptable to use "her" in this case.
(Score: 0) by Anonymous Coward on Monday November 05 2018, @11:46PM
You know, it is! And yet I know someone who would use 'their' even while pregnant. Mercifully they weren't obnoxious about it. It *was* interesting.
(Score: 3, Funny) by kazzie on Monday November 05 2018, @06:28PM
Means "not yet available on Amazon" .
(Score: 4, Funny) by Dr Spin on Monday November 05 2018, @07:04PM
2 + 2 = 5 (for large values of 2)
Warning: Opening your mouth may invalidate your brain!
(Score: 2) by mrpg on Monday November 05 2018, @07:10PM
If someone is afraid of number 13, are they afraid of 13.1?
This is not offtopic, 13 is prime.