does a number that contains all primes less than it exist?Do there exist any dormant primes?Currently, what is the largest publicly known prime number such that all prime numbers less than it are known?Difference between two (not consecutive) primesProof that there exists a larger prime than prime number P, which is the largest of a finite set of primes?A very basic (I think) question about proofs and infinitely many primes.Can it be proven/disproven that there are highly composite numbers that prime-factorize into larger primes such as $9999991$?Given a number N, how many numbers less than N can be written as a product of less than k prime factors?Sums of consecutive primesIs it true for any $n=2p$ where $p$ is prime, that the number of twin primes less than $n$ approaches the number of prime pairs?Can it be shown that Double Goldbug Numbers cannot exist?
Confusion about multiple information Sets
I played my first (rapid) tournament recently and I wanted to calculate my ELO
Do we or do we not observe (measure) superpositions all the time?
How should I behave to assure my friends that I am not after their money?
Symbol for "not absolutely continuous" in Latex
Does anycast addressing add additional latency in any way?
How to determine what is the correct level of detail when modelling?
Are there any vegetarian astronauts?
How come I was asked by a CBP officer why I was in the US when leaving?
Does ultrasonic bath cleaning damage laboratory volumetric glassware calibration?
MH370 blackbox - is it still possible to retrieve data from it?
How likely is sample A and sample B is from distribution C?
Set vertical spacing between two particular items
What speedlites can work with the Canon EOS 4000D's non-standard hotshoe?
Analog is Obtuse!
The use of "I" and "we" used in the same sentence and other questions
Is there a short way to check uniqueness of values without using 'if' and multiple 'and's?
Do 3D printers really reach 50 micron (0.050mm) accuracy?
Why is a blank required between "[[" and "-e xxx" in ksh?
How to convert object fill in to fine lines?
What does 2>&1 | tee mean?
Can I travel from Germany to England alone as an unaccompanied minor?
Difference between 'demás' and 'otros'?
Why does this fireplace work?
does a number that contains all primes less than it exist?
Do there exist any dormant primes?Currently, what is the largest publicly known prime number such that all prime numbers less than it are known?Difference between two (not consecutive) primesProof that there exists a larger prime than prime number P, which is the largest of a finite set of primes?A very basic (I think) question about proofs and infinitely many primes.Can it be proven/disproven that there are highly composite numbers that prime-factorize into larger primes such as $9999991$?Given a number N, how many numbers less than N can be written as a product of less than k prime factors?Sums of consecutive primesIs it true for any $n=2p$ where $p$ is prime, that the number of twin primes less than $n$ approaches the number of prime pairs?Can it be shown that Double Goldbug Numbers cannot exist?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
I want a number that has a prime factorization that contains all prime numbers less than that number (besides $2$), anyone with an answer please show a proof.
I have made a little progress, if this number exists, then it is one less than a prime number.
proof:
make a list of all the primes less than $n$ $P_1,space P_2,space P_3,cdots$
$n+1$ is not a factor of any of these primes so it ether is a prime or has a prime that our list missed and since the list contains all primes less than $n$, $n+1$ must be prime.
and more evidence that suggests this exists is the proof that any arbitrary prime gap exists. if $n!+1$ is prime then the prime gap between $n!+1$ and the next prime is at least $n-1$ because:
$n!+2$ is a multiple of $2$ and
$n!+3$ is a multiple of $3$ and so-on until
$n!+n$ which is a multiple of $n$
any more help would be appreciated
prime-numbers prime-factorization prime-gaps
$endgroup$
|
show 2 more comments
$begingroup$
I want a number that has a prime factorization that contains all prime numbers less than that number (besides $2$), anyone with an answer please show a proof.
I have made a little progress, if this number exists, then it is one less than a prime number.
proof:
make a list of all the primes less than $n$ $P_1,space P_2,space P_3,cdots$
$n+1$ is not a factor of any of these primes so it ether is a prime or has a prime that our list missed and since the list contains all primes less than $n$, $n+1$ must be prime.
and more evidence that suggests this exists is the proof that any arbitrary prime gap exists. if $n!+1$ is prime then the prime gap between $n!+1$ and the next prime is at least $n-1$ because:
$n!+2$ is a multiple of $2$ and
$n!+3$ is a multiple of $3$ and so-on until
$n!+n$ which is a multiple of $n$
any more help would be appreciated
prime-numbers prime-factorization prime-gaps
$endgroup$
5
$begingroup$
Bertrand's postulate?
$endgroup$
– Lord Shark the Unknown
8 hours ago
$begingroup$
@LordSharktheUnknown if I understand Bertrand's postulate, no. he has a way of finding prime gaps (sort-of) I'm just wondering if a number can contain all prime numbers less that its self
$endgroup$
– spydragon
8 hours ago
$begingroup$
Prime gaps of arbitrary length appear. Small prime gaps persist indefinitely with gaps at most $246$ appearing infinitely often (en.wikipedia.org/wiki/Polymath_Project) - the conjecture is that $246$ can be reduced to $2$, and that "prime pairs" occur infinitely often. Primes are too dense for your idea to work. Exploring them is mathematically rich territory - proving new things about primes is almost always standing on the shoulders of giants.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
You need to understand the question you are asking. Bertrand's postulate shows that there is a prime which is not "included" (because there is a prime between $n$ and $2n$ which is, therefore, not a factor of $2n$, and the product you are creating is of the from $2n$)
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
@MarkBennet I know, but as it hasn't been proven you and I cannot know for certain and even though primes are not always 1,000,000 numbers apart there could still be a number that works
$endgroup$
– spydragon
8 hours ago
|
show 2 more comments
$begingroup$
I want a number that has a prime factorization that contains all prime numbers less than that number (besides $2$), anyone with an answer please show a proof.
I have made a little progress, if this number exists, then it is one less than a prime number.
proof:
make a list of all the primes less than $n$ $P_1,space P_2,space P_3,cdots$
$n+1$ is not a factor of any of these primes so it ether is a prime or has a prime that our list missed and since the list contains all primes less than $n$, $n+1$ must be prime.
and more evidence that suggests this exists is the proof that any arbitrary prime gap exists. if $n!+1$ is prime then the prime gap between $n!+1$ and the next prime is at least $n-1$ because:
$n!+2$ is a multiple of $2$ and
$n!+3$ is a multiple of $3$ and so-on until
$n!+n$ which is a multiple of $n$
any more help would be appreciated
prime-numbers prime-factorization prime-gaps
$endgroup$
I want a number that has a prime factorization that contains all prime numbers less than that number (besides $2$), anyone with an answer please show a proof.
I have made a little progress, if this number exists, then it is one less than a prime number.
proof:
make a list of all the primes less than $n$ $P_1,space P_2,space P_3,cdots$
$n+1$ is not a factor of any of these primes so it ether is a prime or has a prime that our list missed and since the list contains all primes less than $n$, $n+1$ must be prime.
and more evidence that suggests this exists is the proof that any arbitrary prime gap exists. if $n!+1$ is prime then the prime gap between $n!+1$ and the next prime is at least $n-1$ because:
$n!+2$ is a multiple of $2$ and
$n!+3$ is a multiple of $3$ and so-on until
$n!+n$ which is a multiple of $n$
any more help would be appreciated
prime-numbers prime-factorization prime-gaps
prime-numbers prime-factorization prime-gaps
asked 8 hours ago
spydragonspydragon
4310 bronze badges
4310 bronze badges
5
$begingroup$
Bertrand's postulate?
$endgroup$
– Lord Shark the Unknown
8 hours ago
$begingroup$
@LordSharktheUnknown if I understand Bertrand's postulate, no. he has a way of finding prime gaps (sort-of) I'm just wondering if a number can contain all prime numbers less that its self
$endgroup$
– spydragon
8 hours ago
$begingroup$
Prime gaps of arbitrary length appear. Small prime gaps persist indefinitely with gaps at most $246$ appearing infinitely often (en.wikipedia.org/wiki/Polymath_Project) - the conjecture is that $246$ can be reduced to $2$, and that "prime pairs" occur infinitely often. Primes are too dense for your idea to work. Exploring them is mathematically rich territory - proving new things about primes is almost always standing on the shoulders of giants.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
You need to understand the question you are asking. Bertrand's postulate shows that there is a prime which is not "included" (because there is a prime between $n$ and $2n$ which is, therefore, not a factor of $2n$, and the product you are creating is of the from $2n$)
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
@MarkBennet I know, but as it hasn't been proven you and I cannot know for certain and even though primes are not always 1,000,000 numbers apart there could still be a number that works
$endgroup$
– spydragon
8 hours ago
|
show 2 more comments
5
$begingroup$
Bertrand's postulate?
$endgroup$
– Lord Shark the Unknown
8 hours ago
$begingroup$
@LordSharktheUnknown if I understand Bertrand's postulate, no. he has a way of finding prime gaps (sort-of) I'm just wondering if a number can contain all prime numbers less that its self
$endgroup$
– spydragon
8 hours ago
$begingroup$
Prime gaps of arbitrary length appear. Small prime gaps persist indefinitely with gaps at most $246$ appearing infinitely often (en.wikipedia.org/wiki/Polymath_Project) - the conjecture is that $246$ can be reduced to $2$, and that "prime pairs" occur infinitely often. Primes are too dense for your idea to work. Exploring them is mathematically rich territory - proving new things about primes is almost always standing on the shoulders of giants.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
You need to understand the question you are asking. Bertrand's postulate shows that there is a prime which is not "included" (because there is a prime between $n$ and $2n$ which is, therefore, not a factor of $2n$, and the product you are creating is of the from $2n$)
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
@MarkBennet I know, but as it hasn't been proven you and I cannot know for certain and even though primes are not always 1,000,000 numbers apart there could still be a number that works
$endgroup$
– spydragon
8 hours ago
5
5
$begingroup$
Bertrand's postulate?
$endgroup$
– Lord Shark the Unknown
8 hours ago
$begingroup$
Bertrand's postulate?
$endgroup$
– Lord Shark the Unknown
8 hours ago
$begingroup$
@LordSharktheUnknown if I understand Bertrand's postulate, no. he has a way of finding prime gaps (sort-of) I'm just wondering if a number can contain all prime numbers less that its self
$endgroup$
– spydragon
8 hours ago
$begingroup$
@LordSharktheUnknown if I understand Bertrand's postulate, no. he has a way of finding prime gaps (sort-of) I'm just wondering if a number can contain all prime numbers less that its self
$endgroup$
– spydragon
8 hours ago
$begingroup$
Prime gaps of arbitrary length appear. Small prime gaps persist indefinitely with gaps at most $246$ appearing infinitely often (en.wikipedia.org/wiki/Polymath_Project) - the conjecture is that $246$ can be reduced to $2$, and that "prime pairs" occur infinitely often. Primes are too dense for your idea to work. Exploring them is mathematically rich territory - proving new things about primes is almost always standing on the shoulders of giants.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
Prime gaps of arbitrary length appear. Small prime gaps persist indefinitely with gaps at most $246$ appearing infinitely often (en.wikipedia.org/wiki/Polymath_Project) - the conjecture is that $246$ can be reduced to $2$, and that "prime pairs" occur infinitely often. Primes are too dense for your idea to work. Exploring them is mathematically rich territory - proving new things about primes is almost always standing on the shoulders of giants.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
You need to understand the question you are asking. Bertrand's postulate shows that there is a prime which is not "included" (because there is a prime between $n$ and $2n$ which is, therefore, not a factor of $2n$, and the product you are creating is of the from $2n$)
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
You need to understand the question you are asking. Bertrand's postulate shows that there is a prime which is not "included" (because there is a prime between $n$ and $2n$ which is, therefore, not a factor of $2n$, and the product you are creating is of the from $2n$)
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
@MarkBennet I know, but as it hasn't been proven you and I cannot know for certain and even though primes are not always 1,000,000 numbers apart there could still be a number that works
$endgroup$
– spydragon
8 hours ago
$begingroup$
@MarkBennet I know, but as it hasn't been proven you and I cannot know for certain and even though primes are not always 1,000,000 numbers apart there could still be a number that works
$endgroup$
– spydragon
8 hours ago
|
show 2 more comments
5 Answers
5
active
oldest
votes
$begingroup$
This is impossible. For every $n>1$, we have gcd$(n,n-1)=1$. Since there is a prime dividing $n-1$, the result follows.
Edit : I should have assumed $n>2$ since I need a prime divisor of $n-1$.
$endgroup$
$begingroup$
Well, $n=2$ actually works ...
$endgroup$
– Henning Makholm
8 hours ago
$begingroup$
@HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$.
$endgroup$
– Levent
8 hours ago
$begingroup$
what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime?
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$).
$endgroup$
– Levent
8 hours ago
$begingroup$
@spydragon you want $n$ to contain every prime factor less than or equal to $n$ - it doesn't have to be prime. But the factors of $n-1$ don't divide $n$. If $n-1$ has a non-trivial prime factor, $n$ cannot contain it, Please think about this - try out some examples. $n=2$ is the only solution.
$endgroup$
– Mark Bennet
8 hours ago
|
show 7 more comments
$begingroup$
To make Lord Shark's comment explicit:
Let $n$ be composite and let $p$ be its largest prime factor. Then certainly $nge 2p$. By Bertrand's postulate, there exists a prime $q$ between $p$ and $2p$, hence there exist primes below $n$ that do not divide $n$.
$endgroup$
$begingroup$
unless that prime $q$ is in between $n$ and $2p$
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$.
$endgroup$
– Ethan Bolker
3 hours ago
add a comment |
$begingroup$
$n=2cdotnover 2$ at most for the factoring to work out. But, by that very logic, applying it with Bertrand's Postulate $$exists cinmathbbP,nover 2leq cleq nimplies cmid n land 2nmid n$$ contradicting the possibility of an n with the property of divisibility by 2 working. which then says n doesn't include all primes less than it.
$endgroup$
add a comment |
$begingroup$
Look at it from the other side, the "half-primorials" (see http://oeis.org/A070826) of which the first composite one is 15, which as you know is $3 times 5$.
But it's not divisible by 7, 11 or 13. Multiply those in and you get 15015. But that's not divisible by 17, 19, 23, 29, ..., 14983 or 15013. Multiply those in... actually, don't, you might tie up your computer for too long.
$endgroup$
add a comment |
$begingroup$
A small dilation on the answer of Levent: Let us imagine there is such a number and there are $n$ primes smaller than that number. Then the smallest number that contains all of those primes is the product of all of those primes, which is called a primorial and is denoted $p_n#$.
Your question in effect asks, "Is it ever the case that $p_n+1>p_n#$?"
We can start by considering the number $p_n#+1$. Since every one of the first $n$ primes divides $p_n#$, and none of them divide $1$, we conclude none of them can divide $p_n#+1$. So that number must either be a prime or have prime factors. If it has prime factors, they must be other than any of the first $p_n$, and those factors must be smaller than $p_n#$, and larger than $p_n$ itself. In this case, the prime next larger than $p_n$ would have to be smaller than $p_n#$ and the answer to your question would be "No". So that forces us to consider that $p_n#+1$ is in fact a prime, and postulate that it is the prime next larger than $p_n$, i.e. $p_n+1$. If it were ever the case that $p_n+1=p_n#+1$, that would be the only possible way to answer your question in the positive.
Here is how Levent's answer sinks that ship. We must now consider the number $p_n#-1$. As in the case of $p_n#+1$, each $p_n$ divides $p_n#$ but none of them divide $1$, so $p_n#-1$ must either be a prime or have prime factors, in either instance smaller than $p_n#$. That being the case, $p_n#+1$ cannot be the prime next larger than $p_n$.
Levent's answer stands on its own in answering your question in the negative. However, the excursion taken here shows that Levent's answer also undercuts the only reasonable candidate for the kind of number you postulate.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3271974%2fdoes-a-number-that-contains-all-primes-less-than-it-exist%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is impossible. For every $n>1$, we have gcd$(n,n-1)=1$. Since there is a prime dividing $n-1$, the result follows.
Edit : I should have assumed $n>2$ since I need a prime divisor of $n-1$.
$endgroup$
$begingroup$
Well, $n=2$ actually works ...
$endgroup$
– Henning Makholm
8 hours ago
$begingroup$
@HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$.
$endgroup$
– Levent
8 hours ago
$begingroup$
what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime?
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$).
$endgroup$
– Levent
8 hours ago
$begingroup$
@spydragon you want $n$ to contain every prime factor less than or equal to $n$ - it doesn't have to be prime. But the factors of $n-1$ don't divide $n$. If $n-1$ has a non-trivial prime factor, $n$ cannot contain it, Please think about this - try out some examples. $n=2$ is the only solution.
$endgroup$
– Mark Bennet
8 hours ago
|
show 7 more comments
$begingroup$
This is impossible. For every $n>1$, we have gcd$(n,n-1)=1$. Since there is a prime dividing $n-1$, the result follows.
Edit : I should have assumed $n>2$ since I need a prime divisor of $n-1$.
$endgroup$
$begingroup$
Well, $n=2$ actually works ...
$endgroup$
– Henning Makholm
8 hours ago
$begingroup$
@HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$.
$endgroup$
– Levent
8 hours ago
$begingroup$
what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime?
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$).
$endgroup$
– Levent
8 hours ago
$begingroup$
@spydragon you want $n$ to contain every prime factor less than or equal to $n$ - it doesn't have to be prime. But the factors of $n-1$ don't divide $n$. If $n-1$ has a non-trivial prime factor, $n$ cannot contain it, Please think about this - try out some examples. $n=2$ is the only solution.
$endgroup$
– Mark Bennet
8 hours ago
|
show 7 more comments
$begingroup$
This is impossible. For every $n>1$, we have gcd$(n,n-1)=1$. Since there is a prime dividing $n-1$, the result follows.
Edit : I should have assumed $n>2$ since I need a prime divisor of $n-1$.
$endgroup$
This is impossible. For every $n>1$, we have gcd$(n,n-1)=1$. Since there is a prime dividing $n-1$, the result follows.
Edit : I should have assumed $n>2$ since I need a prime divisor of $n-1$.
edited 8 hours ago
answered 8 hours ago
LeventLevent
2,9539 silver badges26 bronze badges
2,9539 silver badges26 bronze badges
$begingroup$
Well, $n=2$ actually works ...
$endgroup$
– Henning Makholm
8 hours ago
$begingroup$
@HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$.
$endgroup$
– Levent
8 hours ago
$begingroup$
what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime?
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$).
$endgroup$
– Levent
8 hours ago
$begingroup$
@spydragon you want $n$ to contain every prime factor less than or equal to $n$ - it doesn't have to be prime. But the factors of $n-1$ don't divide $n$. If $n-1$ has a non-trivial prime factor, $n$ cannot contain it, Please think about this - try out some examples. $n=2$ is the only solution.
$endgroup$
– Mark Bennet
8 hours ago
|
show 7 more comments
$begingroup$
Well, $n=2$ actually works ...
$endgroup$
– Henning Makholm
8 hours ago
$begingroup$
@HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$.
$endgroup$
– Levent
8 hours ago
$begingroup$
what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime?
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$).
$endgroup$
– Levent
8 hours ago
$begingroup$
@spydragon you want $n$ to contain every prime factor less than or equal to $n$ - it doesn't have to be prime. But the factors of $n-1$ don't divide $n$. If $n-1$ has a non-trivial prime factor, $n$ cannot contain it, Please think about this - try out some examples. $n=2$ is the only solution.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
Well, $n=2$ actually works ...
$endgroup$
– Henning Makholm
8 hours ago
$begingroup$
Well, $n=2$ actually works ...
$endgroup$
– Henning Makholm
8 hours ago
$begingroup$
@HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$.
$endgroup$
– Levent
8 hours ago
$begingroup$
@HenningMakholm you are correct, in $n=2$ case, $n-1$ is not divisible by any prime. I should have assumed that $n>2$.
$endgroup$
– Levent
8 hours ago
$begingroup$
what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime?
$endgroup$
– spydragon
8 hours ago
$begingroup$
what if $n-1$ and $n+1$ are twin primes, I never said $n$ had to be prime?
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$).
$endgroup$
– Levent
8 hours ago
$begingroup$
@spydragon I did not assume that $n$ is a prime. Let $n>2$ be any integer. Then gcd$(n,n-1)=1$ (why?). Now $n-1>1$ so there exists a prime divisor $p$ of $n-1$ (it can be $n-1$ itself). Then $p<n$ and $p$ does not divide $n$ (since $p$ divides $n-1$ and gcd$(n,n-1)=1$).
$endgroup$
– Levent
8 hours ago
$begingroup$
@spydragon you want $n$ to contain every prime factor less than or equal to $n$ - it doesn't have to be prime. But the factors of $n-1$ don't divide $n$. If $n-1$ has a non-trivial prime factor, $n$ cannot contain it, Please think about this - try out some examples. $n=2$ is the only solution.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
@spydragon you want $n$ to contain every prime factor less than or equal to $n$ - it doesn't have to be prime. But the factors of $n-1$ don't divide $n$. If $n-1$ has a non-trivial prime factor, $n$ cannot contain it, Please think about this - try out some examples. $n=2$ is the only solution.
$endgroup$
– Mark Bennet
8 hours ago
|
show 7 more comments
$begingroup$
To make Lord Shark's comment explicit:
Let $n$ be composite and let $p$ be its largest prime factor. Then certainly $nge 2p$. By Bertrand's postulate, there exists a prime $q$ between $p$ and $2p$, hence there exist primes below $n$ that do not divide $n$.
$endgroup$
$begingroup$
unless that prime $q$ is in between $n$ and $2p$
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$.
$endgroup$
– Ethan Bolker
3 hours ago
add a comment |
$begingroup$
To make Lord Shark's comment explicit:
Let $n$ be composite and let $p$ be its largest prime factor. Then certainly $nge 2p$. By Bertrand's postulate, there exists a prime $q$ between $p$ and $2p$, hence there exist primes below $n$ that do not divide $n$.
$endgroup$
$begingroup$
unless that prime $q$ is in between $n$ and $2p$
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$.
$endgroup$
– Ethan Bolker
3 hours ago
add a comment |
$begingroup$
To make Lord Shark's comment explicit:
Let $n$ be composite and let $p$ be its largest prime factor. Then certainly $nge 2p$. By Bertrand's postulate, there exists a prime $q$ between $p$ and $2p$, hence there exist primes below $n$ that do not divide $n$.
$endgroup$
To make Lord Shark's comment explicit:
Let $n$ be composite and let $p$ be its largest prime factor. Then certainly $nge 2p$. By Bertrand's postulate, there exists a prime $q$ between $p$ and $2p$, hence there exist primes below $n$ that do not divide $n$.
answered 8 hours ago
community wiki
Hagen von Eitzen
$begingroup$
unless that prime $q$ is in between $n$ and $2p$
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$.
$endgroup$
– Ethan Bolker
3 hours ago
add a comment |
$begingroup$
unless that prime $q$ is in between $n$ and $2p$
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$.
$endgroup$
– Ethan Bolker
3 hours ago
$begingroup$
unless that prime $q$ is in between $n$ and $2p$
$endgroup$
– spydragon
8 hours ago
$begingroup$
unless that prime $q$ is in between $n$ and $2p$
$endgroup$
– spydragon
8 hours ago
$begingroup$
@spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$.
$endgroup$
– Ethan Bolker
3 hours ago
$begingroup$
@spydragon $p$ was chosen as the largest prime divisor of $n$ so any larger prime - e.g. the $q$ that comes from Bertrand, or any other prime larger than $p$, does not divide $n$.
$endgroup$
– Ethan Bolker
3 hours ago
add a comment |
$begingroup$
$n=2cdotnover 2$ at most for the factoring to work out. But, by that very logic, applying it with Bertrand's Postulate $$exists cinmathbbP,nover 2leq cleq nimplies cmid n land 2nmid n$$ contradicting the possibility of an n with the property of divisibility by 2 working. which then says n doesn't include all primes less than it.
$endgroup$
add a comment |
$begingroup$
$n=2cdotnover 2$ at most for the factoring to work out. But, by that very logic, applying it with Bertrand's Postulate $$exists cinmathbbP,nover 2leq cleq nimplies cmid n land 2nmid n$$ contradicting the possibility of an n with the property of divisibility by 2 working. which then says n doesn't include all primes less than it.
$endgroup$
add a comment |
$begingroup$
$n=2cdotnover 2$ at most for the factoring to work out. But, by that very logic, applying it with Bertrand's Postulate $$exists cinmathbbP,nover 2leq cleq nimplies cmid n land 2nmid n$$ contradicting the possibility of an n with the property of divisibility by 2 working. which then says n doesn't include all primes less than it.
$endgroup$
$n=2cdotnover 2$ at most for the factoring to work out. But, by that very logic, applying it with Bertrand's Postulate $$exists cinmathbbP,nover 2leq cleq nimplies cmid n land 2nmid n$$ contradicting the possibility of an n with the property of divisibility by 2 working. which then says n doesn't include all primes less than it.
edited 3 hours ago
mlchristians
17110 bronze badges
17110 bronze badges
answered 7 hours ago
Roddy MacPheeRoddy MacPhee
1,7432 gold badges2 silver badges24 bronze badges
1,7432 gold badges2 silver badges24 bronze badges
add a comment |
add a comment |
$begingroup$
Look at it from the other side, the "half-primorials" (see http://oeis.org/A070826) of which the first composite one is 15, which as you know is $3 times 5$.
But it's not divisible by 7, 11 or 13. Multiply those in and you get 15015. But that's not divisible by 17, 19, 23, 29, ..., 14983 or 15013. Multiply those in... actually, don't, you might tie up your computer for too long.
$endgroup$
add a comment |
$begingroup$
Look at it from the other side, the "half-primorials" (see http://oeis.org/A070826) of which the first composite one is 15, which as you know is $3 times 5$.
But it's not divisible by 7, 11 or 13. Multiply those in and you get 15015. But that's not divisible by 17, 19, 23, 29, ..., 14983 or 15013. Multiply those in... actually, don't, you might tie up your computer for too long.
$endgroup$
add a comment |
$begingroup$
Look at it from the other side, the "half-primorials" (see http://oeis.org/A070826) of which the first composite one is 15, which as you know is $3 times 5$.
But it's not divisible by 7, 11 or 13. Multiply those in and you get 15015. But that's not divisible by 17, 19, 23, 29, ..., 14983 or 15013. Multiply those in... actually, don't, you might tie up your computer for too long.
$endgroup$
Look at it from the other side, the "half-primorials" (see http://oeis.org/A070826) of which the first composite one is 15, which as you know is $3 times 5$.
But it's not divisible by 7, 11 or 13. Multiply those in and you get 15015. But that's not divisible by 17, 19, 23, 29, ..., 14983 or 15013. Multiply those in... actually, don't, you might tie up your computer for too long.
answered 3 hours ago
Robert SoupeRobert Soupe
12k2 gold badges21 silver badges53 bronze badges
12k2 gold badges21 silver badges53 bronze badges
add a comment |
add a comment |
$begingroup$
A small dilation on the answer of Levent: Let us imagine there is such a number and there are $n$ primes smaller than that number. Then the smallest number that contains all of those primes is the product of all of those primes, which is called a primorial and is denoted $p_n#$.
Your question in effect asks, "Is it ever the case that $p_n+1>p_n#$?"
We can start by considering the number $p_n#+1$. Since every one of the first $n$ primes divides $p_n#$, and none of them divide $1$, we conclude none of them can divide $p_n#+1$. So that number must either be a prime or have prime factors. If it has prime factors, they must be other than any of the first $p_n$, and those factors must be smaller than $p_n#$, and larger than $p_n$ itself. In this case, the prime next larger than $p_n$ would have to be smaller than $p_n#$ and the answer to your question would be "No". So that forces us to consider that $p_n#+1$ is in fact a prime, and postulate that it is the prime next larger than $p_n$, i.e. $p_n+1$. If it were ever the case that $p_n+1=p_n#+1$, that would be the only possible way to answer your question in the positive.
Here is how Levent's answer sinks that ship. We must now consider the number $p_n#-1$. As in the case of $p_n#+1$, each $p_n$ divides $p_n#$ but none of them divide $1$, so $p_n#-1$ must either be a prime or have prime factors, in either instance smaller than $p_n#$. That being the case, $p_n#+1$ cannot be the prime next larger than $p_n$.
Levent's answer stands on its own in answering your question in the negative. However, the excursion taken here shows that Levent's answer also undercuts the only reasonable candidate for the kind of number you postulate.
$endgroup$
add a comment |
$begingroup$
A small dilation on the answer of Levent: Let us imagine there is such a number and there are $n$ primes smaller than that number. Then the smallest number that contains all of those primes is the product of all of those primes, which is called a primorial and is denoted $p_n#$.
Your question in effect asks, "Is it ever the case that $p_n+1>p_n#$?"
We can start by considering the number $p_n#+1$. Since every one of the first $n$ primes divides $p_n#$, and none of them divide $1$, we conclude none of them can divide $p_n#+1$. So that number must either be a prime or have prime factors. If it has prime factors, they must be other than any of the first $p_n$, and those factors must be smaller than $p_n#$, and larger than $p_n$ itself. In this case, the prime next larger than $p_n$ would have to be smaller than $p_n#$ and the answer to your question would be "No". So that forces us to consider that $p_n#+1$ is in fact a prime, and postulate that it is the prime next larger than $p_n$, i.e. $p_n+1$. If it were ever the case that $p_n+1=p_n#+1$, that would be the only possible way to answer your question in the positive.
Here is how Levent's answer sinks that ship. We must now consider the number $p_n#-1$. As in the case of $p_n#+1$, each $p_n$ divides $p_n#$ but none of them divide $1$, so $p_n#-1$ must either be a prime or have prime factors, in either instance smaller than $p_n#$. That being the case, $p_n#+1$ cannot be the prime next larger than $p_n$.
Levent's answer stands on its own in answering your question in the negative. However, the excursion taken here shows that Levent's answer also undercuts the only reasonable candidate for the kind of number you postulate.
$endgroup$
add a comment |
$begingroup$
A small dilation on the answer of Levent: Let us imagine there is such a number and there are $n$ primes smaller than that number. Then the smallest number that contains all of those primes is the product of all of those primes, which is called a primorial and is denoted $p_n#$.
Your question in effect asks, "Is it ever the case that $p_n+1>p_n#$?"
We can start by considering the number $p_n#+1$. Since every one of the first $n$ primes divides $p_n#$, and none of them divide $1$, we conclude none of them can divide $p_n#+1$. So that number must either be a prime or have prime factors. If it has prime factors, they must be other than any of the first $p_n$, and those factors must be smaller than $p_n#$, and larger than $p_n$ itself. In this case, the prime next larger than $p_n$ would have to be smaller than $p_n#$ and the answer to your question would be "No". So that forces us to consider that $p_n#+1$ is in fact a prime, and postulate that it is the prime next larger than $p_n$, i.e. $p_n+1$. If it were ever the case that $p_n+1=p_n#+1$, that would be the only possible way to answer your question in the positive.
Here is how Levent's answer sinks that ship. We must now consider the number $p_n#-1$. As in the case of $p_n#+1$, each $p_n$ divides $p_n#$ but none of them divide $1$, so $p_n#-1$ must either be a prime or have prime factors, in either instance smaller than $p_n#$. That being the case, $p_n#+1$ cannot be the prime next larger than $p_n$.
Levent's answer stands on its own in answering your question in the negative. However, the excursion taken here shows that Levent's answer also undercuts the only reasonable candidate for the kind of number you postulate.
$endgroup$
A small dilation on the answer of Levent: Let us imagine there is such a number and there are $n$ primes smaller than that number. Then the smallest number that contains all of those primes is the product of all of those primes, which is called a primorial and is denoted $p_n#$.
Your question in effect asks, "Is it ever the case that $p_n+1>p_n#$?"
We can start by considering the number $p_n#+1$. Since every one of the first $n$ primes divides $p_n#$, and none of them divide $1$, we conclude none of them can divide $p_n#+1$. So that number must either be a prime or have prime factors. If it has prime factors, they must be other than any of the first $p_n$, and those factors must be smaller than $p_n#$, and larger than $p_n$ itself. In this case, the prime next larger than $p_n$ would have to be smaller than $p_n#$ and the answer to your question would be "No". So that forces us to consider that $p_n#+1$ is in fact a prime, and postulate that it is the prime next larger than $p_n$, i.e. $p_n+1$. If it were ever the case that $p_n+1=p_n#+1$, that would be the only possible way to answer your question in the positive.
Here is how Levent's answer sinks that ship. We must now consider the number $p_n#-1$. As in the case of $p_n#+1$, each $p_n$ divides $p_n#$ but none of them divide $1$, so $p_n#-1$ must either be a prime or have prime factors, in either instance smaller than $p_n#$. That being the case, $p_n#+1$ cannot be the prime next larger than $p_n$.
Levent's answer stands on its own in answering your question in the negative. However, the excursion taken here shows that Levent's answer also undercuts the only reasonable candidate for the kind of number you postulate.
answered 1 hour ago
Keith BackmanKeith Backman
1,7721 gold badge9 silver badges13 bronze badges
1,7721 gold badge9 silver badges13 bronze badges
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3271974%2fdoes-a-number-that-contains-all-primes-less-than-it-exist%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
5
$begingroup$
Bertrand's postulate?
$endgroup$
– Lord Shark the Unknown
8 hours ago
$begingroup$
@LordSharktheUnknown if I understand Bertrand's postulate, no. he has a way of finding prime gaps (sort-of) I'm just wondering if a number can contain all prime numbers less that its self
$endgroup$
– spydragon
8 hours ago
$begingroup$
Prime gaps of arbitrary length appear. Small prime gaps persist indefinitely with gaps at most $246$ appearing infinitely often (en.wikipedia.org/wiki/Polymath_Project) - the conjecture is that $246$ can be reduced to $2$, and that "prime pairs" occur infinitely often. Primes are too dense for your idea to work. Exploring them is mathematically rich territory - proving new things about primes is almost always standing on the shoulders of giants.
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
You need to understand the question you are asking. Bertrand's postulate shows that there is a prime which is not "included" (because there is a prime between $n$ and $2n$ which is, therefore, not a factor of $2n$, and the product you are creating is of the from $2n$)
$endgroup$
– Mark Bennet
8 hours ago
$begingroup$
@MarkBennet I know, but as it hasn't been proven you and I cannot know for certain and even though primes are not always 1,000,000 numbers apart there could still be a number that works
$endgroup$
– spydragon
8 hours ago