6 ms·

What Is an “Almost Prime” Number?

59 points by chablent 8y ago

LarryMade2 8y ago
I don't know what to apply it with yet, but as a programmer I can see this will be useful information.
- kijin 8y ago
  A lot of public key cryptography involves computing a very large number that is a product of two prime numbers.
- dentemple 8y ago
  Welcome to a new generation of whiteboard interview problems
alangpierce 8y ago
Similar amusing math terms are "almost everywhere" and "almost surely"/"almost never". For example, if you pick a random real number between 0 and 1, it will almost never be exactly 0.5. It's possible that you'll get 0.5, but the probability of getting it is exactly 0. https://en.wikipedia.org/wiki/Almost_everywhere https://en.wikipedia.org/wiki/Almost_everywhere https://en.wikipedia.org/wiki/Almost_surely https://en.wikipedia.org/wiki/Almost_surely
- perl4ever 8y ago
  I think the proper interpretation of that is that you can't "pick a random real number between 0 and 1". After all, you would have to choose an infinite number of digits.
  - mcphage 8y ago
    Well, you can do that if you have the Axiom of choice.
    - perl4ever 8y ago
      My brain is fuzzy tonight, and I'm not good at math, but something about the distinction between countable and noncountable infinities makes me question the axiom of choice. I can't precisely state the issue, but something seems off and inconsistent.
      - yantrams 8y ago
        A recent twitter thread that could be helpful - https://twitter.com/johncarlosbaez/status/1056200189130600449 https://twitter.com/johncarlosbaez/status/105620018913060044... And this from the same thread :) https://pbs.twimg.com/media/DqhjmPdU4AAb979.jpg https://pbs.twimg.com/media/DqhjmPdU4AAb979.jpg
  - AaronFriel 8y ago
    You absolutely can "pick a random real number between 0 and 1", at least for the sake of mathematical argument. But for an interval [a, b] a random real number will be x s.t. a <= x <= b is zero. That's because the set {x} has measure 0. An even more fun fact is that the probability that the randomly chosen number is rational is also zero, by the same argument. However, once one starts to try to describe a distribution over the reals, e.g.: "let X be a real number chosen from a uniform probability distribution over [0, 1]", then you run into serious problems. That example begs the question because there is no uniform probability distribution over that set.
    - thaumasiotes 8y ago
      There definitely is a uniform probability distribution over the interval [0,1]. It is given by the probability density function f(x) = 1. There's no uniform probability distribution over the reals, or over the integers, but defining one over a closed real interval is trivially easy. That's what "pick a random real number between 0 and 1" means.
      - AaronFriel 8y ago
        I don't believe there is a uniform probability distribution over any interval of the reals. Suppose such a distribution existed over [0, 1]. Then as we have shown before, the probability of choosing 0 <= x <= 1 is zero. The second axiom of probability states the probability of one of the numbers being chosen must be is one. The third axiom requires countable additivity. We can easily see that for our distribution, we cannot satisfy both at the same time. If we strive for the sum of probabilities to equal 1, then we end up with the sum(P(x)) = 1, but P(x) is everywhere zero. The countable additivity never enters into this, but for any uncountable set of events a uniform distribution is impossible.
        thaumasiotes 8y ago
        > I don't believe there is a uniform probability distribution over any interval of the reals. Then I'll observe that you probably shouldn't be trying to comment on this topic. I didn't just assert that there is one, I pointed out to you what it was. The probability density function f(x) = 1, defined over the interval [0,1], is uniform (all values are equal, being 1) and covers an area of 1. That's all a uniform distribution is. It satisfies the axiom which I assume you're referring to as the "second axiom of probability" in that the definite integral of the pdf over the entire interval is 1. It satisfies the requirement you're confused about in that the probability of choosing a number that falls into either of two disjoint subintervals is equal to the sum of the probabilities of (1) choosing a number falling into the first subinterval; + (2) choosing a number falling into the second subinterval. > Suppose such a distribution existed over [0, 1]. Then as we have shown before, the probability of choosing 0 <= x <= 1 is zero. For fixed x, the probability of choosing x from a uniform distribution over the reals is 0. That is a special case of the probability that a value chosen from a uniform distribution over the reals will lie within an interval. The probability of drawing a value from within the interval [a,b], for any distribution, is the definite integral of the distribution's pdf from a to b. As you can see, when a = b, this value is 0, but when a ≠ b, it isn't. The probability of choosing an x such that 0 <= x <= 1 from a uniform distribution over [0,1] is 1, not 0.
- yantrams 8y ago
  Remember coming across this concept while reading about Measure theory. There are also concepts like "almost well-ordered" and "almost complete" in graph theory if my memory serves right.
  - anyfoo 8y ago
    Something applying to “almost all” elements in a (preferably infinite) set: Applies to all elements, with the exception of a finite number of elements. For example, almost all prime numbers are odd.
    - yantrams 8y ago
      Exactly! I can't remember where but I distinctly remember some theory quantifying this as almost-1, almost-2,... as a function of the number of finite (or countably infinite maybe) exceptions.
    - jhanschoo 8y ago
      A warning: in general mathematical usage, this is not the definition of "almost all"; the notion of "almost all" is with respect to some notion of measure on a set. In the set of real numbers, for example, with the usual Lebesgue measure on it, if all but a /countable/ number of elements has a property X, then almost all the reals has that property X. (Note that uncountable sets in R exists that have zero measure; i.e. uncountable sets that "almost no" points in R lie in that uncountable subset of R)
      - anyfoo 8y ago
        Ah. "With the exception of finitely many" [1] was the definition given to me in University. The generalization makes sense, however. [1] I don't think I'm doing a good job translating the original German definition I was given, which sounds much better: "Mit Ausnahme endlich vieler".
        jhanschoo 8y ago
        Ah, in English "all but finitely many" is indeed very commonly used, and rarely is "almost all" defined to have that sense.
skh 8y ago
In case anyone reads the article and wonders why 1 is not a prime number I'll give a brief answer. A prime number has to have the property that not every number is a multiple of it. In the language of abstract algebra this means that the ideal generated by that number is proper (not the entire set of numbers one is considering). Another reason for discounting 1 as a prime number is that considering 1 to be a prime destroys the uniqueness of prime factorization. For instance, 24 is uniquely, up to order of powers of prime factors: 2^3 times 3 If we allow 1 to be prime then I can write 24 as 1^17 times 2^3 times 3 or I can write it as 1^2 times 2^3 times 3 We lose the property that representations of numbers as products of powers of primes is unique. Thus we have a good reason to discount 1 as being prime and there aren't any good reasons to count it as a prime. The definition given in elementary school is not the correct one. It's a working definition that works well and is correct for all positive integers except 1. In my experience people remember the definition of: "only divisible by itself and 1". Then they ask, "Why isn't 1 considered prime then?" It's because the definition given isn't correct.
- doomrobo 8y ago
  I like the following definition: p is a prime in a ring R iff the ideal generated by p is a prime ideal of R. Equivalently, p is prime iff p | ab implies p | a or p | b. The only issue with this definition is that you're forced to admit that 0 is prime in integral domains.
  - tacomonstrous 8y ago
    It's the same issue though, since you have to specify that prime ideals cannot be the whole ring to avoid 1 being prime.
  - vram22 8y ago
    >p is a prime in a ring R That reminds of the topic of groups, rings and fields that I had in either last year of high school or an early year of college (Math.). I thought that was a really cool topic. Not too hard (for the stuff we covered), and still some cool results/theorems in it. Also, they underlie a lot of other areas of mathematics. https://en.wikipedia.org/wiki/Group_(mathematics) https://en.wikipedia.org/wiki/Group_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Field_(mathematics) https://en.wikipedia.org/wiki/Field_(mathematics)
no_gravity 8y ago
It might be interesting to calculate the 'primeness' of complex numbers and then render the values as shades of grey on the complex plane. Some years I did something similar for the 'divisibility' of prime numbers and the result was pretty interesting: http://www.gibney.de/does_anybody_know_this_fractal http://www.gibney.de/does_anybody_know_this_fractal The most common interpretation of a 'complex prime' is the gaussian prime. When rendered on the complex plane looks like this: https://commons.wikimedia.org/wiki/File:Gauss-primes-768x768.png https://commons.wikimedia.org/wiki/File:Gauss-primes-768x768... Looks rather random. Maybe going from 'is prime or not' to 'primeness' would reveal some more insight.
mangecoeur 8y ago
Sub-prime :P
d--b 8y ago
I find it terrible naming. “Almost-x” is good but “2-almost-x” really sounds bad. “2-factor number” ? “2nd-order-prime”? Twime, Thrime? Even “2-quasi-prime” sounds better.
deleted 8y ago
[deleted]
deleted 8y ago
[deleted]

59 points by chablent 8y ago

LarryMade2 8y ago

I don't know what to apply it with yet, but as a programmer I can see this will be useful information.

kijin 8y ago
A lot of public key cryptography involves computing a very large number that is a product of two prime numbers.
dentemple 8y ago
Welcome to a new generation of whiteboard interview problems

alangpierce 8y ago

Similar amusing math terms are "almost everywhere" and "almost surely"/"almost never". For example, if you pick a random real number between 0 and 1, it will almost never be exactly 0.5. It's possible that you'll get 0.5, but the probability of getting it is exactly 0. https://en.wikipedia.org/wiki/Almost_everywhere https://en.wikipedia.org/wiki/Almost_everywhere https://en.wikipedia.org/wiki/Almost_surely https://en.wikipedia.org/wiki/Almost_surely

perl4ever 8y ago
I think the proper interpretation of that is that you can't "pick a random real number between 0 and 1". After all, you would have to choose an infinite number of digits.
- mcphage 8y ago
  Well, you can do that if you have the Axiom of choice.
  - perl4ever 8y ago
    My brain is fuzzy tonight, and I'm not good at math, but something about the distinction between countable and noncountable infinities makes me question the axiom of choice. I can't precisely state the issue, but something seems off and inconsistent.
    - yantrams 8y ago
      A recent twitter thread that could be helpful - https://twitter.com/johncarlosbaez/status/1056200189130600449 https://twitter.com/johncarlosbaez/status/105620018913060044... And this from the same thread :) https://pbs.twimg.com/media/DqhjmPdU4AAb979.jpg https://pbs.twimg.com/media/DqhjmPdU4AAb979.jpg
- AaronFriel 8y ago
  You absolutely can "pick a random real number between 0 and 1", at least for the sake of mathematical argument. But for an interval [a, b] a random real number will be x s.t. a <= x <= b is zero. That's because the set {x} has measure 0. An even more fun fact is that the probability that the randomly chosen number is rational is also zero, by the same argument. However, once one starts to try to describe a distribution over the reals, e.g.: "let X be a real number chosen from a uniform probability distribution over [0, 1]", then you run into serious problems. That example begs the question because there is no uniform probability distribution over that set.
  - thaumasiotes 8y ago
    There definitely is a uniform probability distribution over the interval [0,1]. It is given by the probability density function f(x) = 1. There's no uniform probability distribution over the reals, or over the integers, but defining one over a closed real interval is trivially easy. That's what "pick a random real number between 0 and 1" means.
    - AaronFriel 8y ago
      I don't believe there is a uniform probability distribution over any interval of the reals. Suppose such a distribution existed over [0, 1]. Then as we have shown before, the probability of choosing 0 <= x <= 1 is zero. The second axiom of probability states the probability of one of the numbers being chosen must be is one. The third axiom requires countable additivity. We can easily see that for our distribution, we cannot satisfy both at the same time. If we strive for the sum of probabilities to equal 1, then we end up with the sum(P(x)) = 1, but P(x) is everywhere zero. The countable additivity never enters into this, but for any uncountable set of events a uniform distribution is impossible.
      - thaumasiotes 8y ago
        > I don't believe there is a uniform probability distribution over any interval of the reals. Then I'll observe that you probably shouldn't be trying to comment on this topic. I didn't just assert that there is one, I pointed out to you what it was. The probability density function f(x) = 1, defined over the interval [0,1], is uniform (all values are equal, being 1) and covers an area of 1. That's all a uniform distribution is. It satisfies the axiom which I assume you're referring to as the "second axiom of probability" in that the definite integral of the pdf over the entire interval is 1. It satisfies the requirement you're confused about in that the probability of choosing a number that falls into either of two disjoint subintervals is equal to the sum of the probabilities of (1) choosing a number falling into the first subinterval; + (2) choosing a number falling into the second subinterval. > Suppose such a distribution existed over [0, 1]. Then as we have shown before, the probability of choosing 0 <= x <= 1 is zero. For fixed x, the probability of choosing x from a uniform distribution over the reals is 0. That is a special case of the probability that a value chosen from a uniform distribution over the reals will lie within an interval. The probability of drawing a value from within the interval [a,b], for any distribution, is the definite integral of the distribution's pdf from a to b. As you can see, when a = b, this value is 0, but when a ≠ b, it isn't. The probability of choosing an x such that 0 <= x <= 1 from a uniform distribution over [0,1] is 1, not 0.
yantrams 8y ago
Remember coming across this concept while reading about Measure theory. There are also concepts like "almost well-ordered" and "almost complete" in graph theory if my memory serves right.
- anyfoo 8y ago
  Something applying to “almost all” elements in a (preferably infinite) set: Applies to all elements, with the exception of a finite number of elements. For example, almost all prime numbers are odd.
  - yantrams 8y ago
    Exactly! I can't remember where but I distinctly remember some theory quantifying this as almost-1, almost-2,... as a function of the number of finite (or countably infinite maybe) exceptions.
  - jhanschoo 8y ago
    A warning: in general mathematical usage, this is not the definition of "almost all"; the notion of "almost all" is with respect to some notion of measure on a set. In the set of real numbers, for example, with the usual Lebesgue measure on it, if all but a /countable/ number of elements has a property X, then almost all the reals has that property X. (Note that uncountable sets in R exists that have zero measure; i.e. uncountable sets that "almost no" points in R lie in that uncountable subset of R)
    - anyfoo 8y ago
      Ah. "With the exception of finitely many" [1] was the definition given to me in University. The generalization makes sense, however. [1] I don't think I'm doing a good job translating the original German definition I was given, which sounds much better: "Mit Ausnahme endlich vieler".
      - jhanschoo 8y ago
        Ah, in English "all but finitely many" is indeed very commonly used, and rarely is "almost all" defined to have that sense.

skh 8y ago

In case anyone reads the article and wonders why 1 is not a prime number I'll give a brief answer. A prime number has to have the property that not every number is a multiple of it. In the language of abstract algebra this means that the ideal generated by that number is proper (not the entire set of numbers one is considering). Another reason for discounting 1 as a prime number is that considering 1 to be a prime destroys the uniqueness of prime factorization. For instance, 24 is uniquely, up to order of powers of prime factors: 2^3 times 3 If we allow 1 to be prime then I can write 24 as 1^17 times 2^3 times 3 or I can write it as 1^2 times 2^3 times 3 We lose the property that representations of numbers as products of powers of primes is unique. Thus we have a good reason to discount 1 as being prime and there aren't any good reasons to count it as a prime. The definition given in elementary school is not the correct one. It's a working definition that works well and is correct for all positive integers except 1. In my experience people remember the definition of: "only divisible by itself and 1". Then they ask, "Why isn't 1 considered prime then?" It's because the definition given isn't correct.

doomrobo 8y ago
I like the following definition: p is a prime in a ring R iff the ideal generated by p is a prime ideal of R. Equivalently, p is prime iff p | ab implies p | a or p | b. The only issue with this definition is that you're forced to admit that 0 is prime in integral domains.
- tacomonstrous 8y ago
  It's the same issue though, since you have to specify that prime ideals cannot be the whole ring to avoid 1 being prime.
- vram22 8y ago
  >p is a prime in a ring R That reminds of the topic of groups, rings and fields that I had in either last year of high school or an early year of college (Math.). I thought that was a really cool topic. Not too hard (for the stuff we covered), and still some cool results/theorems in it. Also, they underlie a lot of other areas of mathematics. https://en.wikipedia.org/wiki/Group_(mathematics) https://en.wikipedia.org/wiki/Group_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Field_(mathematics) https://en.wikipedia.org/wiki/Field_(mathematics)

no_gravity 8y ago

It might be interesting to calculate the 'primeness' of complex numbers and then render the values as shades of grey on the complex plane. Some years I did something similar for the 'divisibility' of prime numbers and the result was pretty interesting: http://www.gibney.de/does_anybody_know_this_fractal http://www.gibney.de/does_anybody_know_this_fractal The most common interpretation of a 'complex prime' is the gaussian prime. When rendered on the complex plane looks like this: https://commons.wikimedia.org/wiki/File:Gauss-primes-768x768.png https://commons.wikimedia.org/wiki/File:Gauss-primes-768x768... Looks rather random. Maybe going from 'is prime or not' to 'primeness' would reveal some more insight.

mangecoeur 8y ago

Sub-prime :P

d--b 8y ago

I find it terrible naming. “Almost-x” is good but “2-almost-x” really sounds bad. “2-factor number” ? “2nd-order-prime”? Twime, Thrime? Even “2-quasi-prime” sounds better.

deleted 8y ago

[deleted]

deleted 8y ago

[deleted]