Mixing
Question on Identifying Prime Factors of a Very Large Number
$begingroup$
Let $P$ be the product of all numbers less than $90$. Find the largest integer $N$ so that for each
$n∈$ {$2,3,4,...,N$}, the number $P+n$ has a prime factor less than 90.
Upon first thinking about this question, my plan of action was to find the first prime number that is larger than $P$ since that would guarantee that by that number, $P+n$ would not have a prime factor less than $90$.
So maybe the answer is one subtracted from that certain prime number.
However, obviously, $P$ is much too large a number to brute force this problem using that strategy nor to guess and check the answer.
So I'm stuck. When analyzing the prime factorization, where the answer might lie, I'm at a lost on how to deal with the added $+n$ to the product.
What actual steps am I supposed to take when answering this question?
prime-numbers
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
$endgroup$
add a comment |
$begingroup$
Let $P$ be the product of all numbers less than $90$. Find the largest integer $N$ so that for each
$n∈$ {$2,3,4,...,N$}, the number $P+n$ has a prime factor less than 90.
Upon first thinking about this question, my plan of action was to find the first prime number that is larger than $P$ since that would guarantee that by that number, $P+n$ would not have a prime factor less than $90$.
So maybe the answer is one subtracted from that certain prime number.
However, obviously, $P$ is much too large a number to brute force this problem using that strategy nor to guess and check the answer.
So I'm stuck. When analyzing the prime factorization, where the answer might lie, I'm at a lost on how to deal with the added $+n$ to the product.
What actual steps am I supposed to take when answering this question?
prime-numbers
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
$endgroup$
$begingroup$
So, $P=89!$, right?
$endgroup$
– lhf
Feb 3 at 10:35
add a comment |
$begingroup$
Let $P$ be the product of all numbers less than $90$. Find the largest integer $N$ so that for each
$n∈$ {$2,3,4,...,N$}, the number $P+n$ has a prime factor less than 90.
Upon first thinking about this question, my plan of action was to find the first prime number that is larger than $P$ since that would guarantee that by that number, $P+n$ would not have a prime factor less than $90$.
So maybe the answer is one subtracted from that certain prime number.
However, obviously, $P$ is much too large a number to brute force this problem using that strategy nor to guess and check the answer.
So I'm stuck. When analyzing the prime factorization, where the answer might lie, I'm at a lost on how to deal with the added $+n$ to the product.
What actual steps am I supposed to take when answering this question?
prime-numbers
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
$endgroup$
Let $P$ be the product of all numbers less than $90$. Find the largest integer $N$ so that for each
$n∈$ {$2,3,4,...,N$}, the number $P+n$ has a prime factor less than 90.
Upon first thinking about this question, my plan of action was to find the first prime number that is larger than $P$ since that would guarantee that by that number, $P+n$ would not have a prime factor less than $90$.
So maybe the answer is one subtracted from that certain prime number.
However, obviously, $P$ is much too large a number to brute force this problem using that strategy nor to guess and check the answer.
So I'm stuck. When analyzing the prime factorization, where the answer might lie, I'm at a lost on how to deal with the added $+n$ to the product.
What actual steps am I supposed to take when answering this question?
prime-numbers
prime-numbers
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
asked Feb 3 at 8:32
SolvingTraineeSolvingTrainee
484
484
$begingroup$
So, $P=89!$, right?
$endgroup$
– lhf
Feb 3 at 10:35
add a comment |
$begingroup$
So, $P=89!$, right?
$endgroup$
– lhf
Feb 3 at 10:35
$begingroup$
So, $P=89!$, right?
$endgroup$
– lhf
Feb 3 at 10:35
$begingroup$
So, $P=89!$, right?
$endgroup$
– lhf
Feb 3 at 10:35
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You are very close, but instead of focussing on $P$, you should focus on the largest prime factor of $P$, which is $89$. I'll answer the question you asked: what steps am I supposed to take?
Try to imagine $P + n$. You can visualise $P$ as
$$ P = 2 cdot 3 cdot ldots cdot 89 $$
and $n$ as
$$ n = p_{1} cdot p_{2} cdot ldots cdot p_{k} $$
where the $p_{i}$ are prime numbers (so this is the prime factorisation of $n$).
Then we have
$$P + n = (2 cdot 3 cdot ldots cdot 89) + (p_{1} cdot p_{2} cdot ldots cdot p_{k})$$
This number can be divided by some prime $p_{i} leq 89$ if and only if $p_{i}$ appears in both $P$ and $n$.
So we need to force $n$ to not have any $p_{i}$ from $1, ldots, 89$.
Of course, if $n leq 89$ then we must have some $p_{i} leq 89$ since any $n$ can be factorised into primes and they all must be $leq n$.
So how can we get at least one $p_{i} > 89$? Well, it must include the first prime $p$ larger than $89$. That is $97$. In fact, $97$ itself should be the smallest such $n$.
Let's now pick a few numbers at random and test our intuition:
$n = 35 = 7 times 5$ contains $5$ which is in $P$ and $n$ and thus $P+n$. No good.
$n = 90 = 2 times 3 times 3 times 5$ contains $2$. No good.
$n = 91 = 7 times 13$. No good.
$n = 97 = ldots$ Aha!
$n = 96, 95, 94, 93, 92$, these all have primes in common with $P$.
This is just to give you some idea about how I approached the problem in my mind, in the hope that it might help you approach similar problems in the future.
There are no 'steps' per se. Problems are very often not routine and don't have a clear and obvious method to follow. It requires turning the problem over in your mind, using some ideas you're familiar with (prime factorisation and algebra, in this case) and approaching from several angles until you find some insight.
As a final note, it is absolutely possible to brute force this using a computer. Here is some badly written sage code to solve this problem:
X = range(2,91)
for x in X:
for k in range(2,int(sqrt(x))+1):
if x % k == 0:
X.remove(x)
break
P = 1
for x in X:
P *= x
n = 2
while any((P+n) % x == 0 for x in X):
n += 1
print n
You can try this code by clicking here. I think this problem is best solved on paper. But sometimes making the computer find the answer and then figuring out why that is the answer is a useful learning experience.
answered Feb 3 at 10:05
ShaiShai
1,217811
$endgroup$
add a comment |
$begingroup$
Hint :
The number $$P+97$$ does not have a prime factor less than $90$ (Try to find out why). On the other hand, $$P+2,cdots,P+96$$ have a prime factor less than $90$ (again try to find out why , hint : the second summand divides the sum). Hence the answer is $96$.
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
$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%2f3098317%2fquestion-on-identifying-prime-factors-of-a-very-large-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You are very close, but instead of focussing on $P$, you should focus on the largest prime factor of $P$, which is $89$. I'll answer the question you asked: what steps am I supposed to take?
Try to imagine $P + n$. You can visualise $P$ as
$$ P = 2 cdot 3 cdot ldots cdot 89 $$
and $n$ as
$$ n = p_{1} cdot p_{2} cdot ldots cdot p_{k} $$
where the $p_{i}$ are prime numbers (so this is the prime factorisation of $n$).
Then we have
$$P + n = (2 cdot 3 cdot ldots cdot 89) + (p_{1} cdot p_{2} cdot ldots cdot p_{k})$$
This number can be divided by some prime $p_{i} leq 89$ if and only if $p_{i}$ appears in both $P$ and $n$.
So we need to force $n$ to not have any $p_{i}$ from $1, ldots, 89$.
Of course, if $n leq 89$ then we must have some $p_{i} leq 89$ since any $n$ can be factorised into primes and they all must be $leq n$.
So how can we get at least one $p_{i} > 89$? Well, it must include the first prime $p$ larger than $89$. That is $97$. In fact, $97$ itself should be the smallest such $n$.
Let's now pick a few numbers at random and test our intuition:
$n = 35 = 7 times 5$ contains $5$ which is in $P$ and $n$ and thus $P+n$. No good.
$n = 90 = 2 times 3 times 3 times 5$ contains $2$. No good.
$n = 91 = 7 times 13$. No good.
$n = 97 = ldots$ Aha!
$n = 96, 95, 94, 93, 92$, these all have primes in common with $P$.
This is just to give you some idea about how I approached the problem in my mind, in the hope that it might help you approach similar problems in the future.
There are no 'steps' per se. Problems are very often not routine and don't have a clear and obvious method to follow. It requires turning the problem over in your mind, using some ideas you're familiar with (prime factorisation and algebra, in this case) and approaching from several angles until you find some insight.
As a final note, it is absolutely possible to brute force this using a computer. Here is some badly written sage code to solve this problem:
X = range(2,91)
for x in X:
for k in range(2,int(sqrt(x))+1):
if x % k == 0:
X.remove(x)
break
P = 1
for x in X:
P *= x
n = 2
while any((P+n) % x == 0 for x in X):
n += 1
print n
You can try this code by clicking here. I think this problem is best solved on paper. But sometimes making the computer find the answer and then figuring out why that is the answer is a useful learning experience.
answered Feb 3 at 10:05
ShaiShai
1,217811
$endgroup$
add a comment |
$begingroup$
You are very close, but instead of focussing on $P$, you should focus on the largest prime factor of $P$, which is $89$. I'll answer the question you asked: what steps am I supposed to take?
Try to imagine $P + n$. You can visualise $P$ as
$$ P = 2 cdot 3 cdot ldots cdot 89 $$
and $n$ as
$$ n = p_{1} cdot p_{2} cdot ldots cdot p_{k} $$
where the $p_{i}$ are prime numbers (so this is the prime factorisation of $n$).
Then we have
$$P + n = (2 cdot 3 cdot ldots cdot 89) + (p_{1} cdot p_{2} cdot ldots cdot p_{k})$$
This number can be divided by some prime $p_{i} leq 89$ if and only if $p_{i}$ appears in both $P$ and $n$.
So we need to force $n$ to not have any $p_{i}$ from $1, ldots, 89$.
Of course, if $n leq 89$ then we must have some $p_{i} leq 89$ since any $n$ can be factorised into primes and they all must be $leq n$.
So how can we get at least one $p_{i} > 89$? Well, it must include the first prime $p$ larger than $89$. That is $97$. In fact, $97$ itself should be the smallest such $n$.
Let's now pick a few numbers at random and test our intuition:
$n = 35 = 7 times 5$ contains $5$ which is in $P$ and $n$ and thus $P+n$. No good.
$n = 90 = 2 times 3 times 3 times 5$ contains $2$. No good.
$n = 91 = 7 times 13$. No good.
$n = 97 = ldots$ Aha!
$n = 96, 95, 94, 93, 92$, these all have primes in common with $P$.
This is just to give you some idea about how I approached the problem in my mind, in the hope that it might help you approach similar problems in the future.
There are no 'steps' per se. Problems are very often not routine and don't have a clear and obvious method to follow. It requires turning the problem over in your mind, using some ideas you're familiar with (prime factorisation and algebra, in this case) and approaching from several angles until you find some insight.
As a final note, it is absolutely possible to brute force this using a computer. Here is some badly written sage code to solve this problem:
X = range(2,91)
for x in X:
for k in range(2,int(sqrt(x))+1):
if x % k == 0:
X.remove(x)
break
P = 1
for x in X:
P *= x
n = 2
while any((P+n) % x == 0 for x in X):
n += 1
print n
You can try this code by clicking here. I think this problem is best solved on paper. But sometimes making the computer find the answer and then figuring out why that is the answer is a useful learning experience.
answered Feb 3 at 10:05
ShaiShai
1,217811
$endgroup$
add a comment |
$begingroup$
You are very close, but instead of focussing on $P$, you should focus on the largest prime factor of $P$, which is $89$. I'll answer the question you asked: what steps am I supposed to take?
Try to imagine $P + n$. You can visualise $P$ as
$$ P = 2 cdot 3 cdot ldots cdot 89 $$
and $n$ as
$$ n = p_{1} cdot p_{2} cdot ldots cdot p_{k} $$
where the $p_{i}$ are prime numbers (so this is the prime factorisation of $n$).
Then we have
$$P + n = (2 cdot 3 cdot ldots cdot 89) + (p_{1} cdot p_{2} cdot ldots cdot p_{k})$$
This number can be divided by some prime $p_{i} leq 89$ if and only if $p_{i}$ appears in both $P$ and $n$.
So we need to force $n$ to not have any $p_{i}$ from $1, ldots, 89$.
Of course, if $n leq 89$ then we must have some $p_{i} leq 89$ since any $n$ can be factorised into primes and they all must be $leq n$.
So how can we get at least one $p_{i} > 89$? Well, it must include the first prime $p$ larger than $89$. That is $97$. In fact, $97$ itself should be the smallest such $n$.
Let's now pick a few numbers at random and test our intuition:
$n = 35 = 7 times 5$ contains $5$ which is in $P$ and $n$ and thus $P+n$. No good.
$n = 90 = 2 times 3 times 3 times 5$ contains $2$. No good.
$n = 91 = 7 times 13$. No good.
$n = 97 = ldots$ Aha!
$n = 96, 95, 94, 93, 92$, these all have primes in common with $P$.
This is just to give you some idea about how I approached the problem in my mind, in the hope that it might help you approach similar problems in the future.
There are no 'steps' per se. Problems are very often not routine and don't have a clear and obvious method to follow. It requires turning the problem over in your mind, using some ideas you're familiar with (prime factorisation and algebra, in this case) and approaching from several angles until you find some insight.
As a final note, it is absolutely possible to brute force this using a computer. Here is some badly written sage code to solve this problem:
X = range(2,91)
for x in X:
for k in range(2,int(sqrt(x))+1):
if x % k == 0:
X.remove(x)
break
P = 1
for x in X:
P *= x
n = 2
while any((P+n) % x == 0 for x in X):
n += 1
print n
You can try this code by clicking here. I think this problem is best solved on paper. But sometimes making the computer find the answer and then figuring out why that is the answer is a useful learning experience.
answered Feb 3 at 10:05
ShaiShai
1,217811
$endgroup$
You are very close, but instead of focussing on $P$, you should focus on the largest prime factor of $P$, which is $89$. I'll answer the question you asked: what steps am I supposed to take?
Try to imagine $P + n$. You can visualise $P$ as
$$ P = 2 cdot 3 cdot ldots cdot 89 $$
and $n$ as
$$ n = p_{1} cdot p_{2} cdot ldots cdot p_{k} $$
where the $p_{i}$ are prime numbers (so this is the prime factorisation of $n$).
Then we have
$$P + n = (2 cdot 3 cdot ldots cdot 89) + (p_{1} cdot p_{2} cdot ldots cdot p_{k})$$
This number can be divided by some prime $p_{i} leq 89$ if and only if $p_{i}$ appears in both $P$ and $n$.
So we need to force $n$ to not have any $p_{i}$ from $1, ldots, 89$.
Of course, if $n leq 89$ then we must have some $p_{i} leq 89$ since any $n$ can be factorised into primes and they all must be $leq n$.
So how can we get at least one $p_{i} > 89$? Well, it must include the first prime $p$ larger than $89$. That is $97$. In fact, $97$ itself should be the smallest such $n$.
Let's now pick a few numbers at random and test our intuition:
$n = 35 = 7 times 5$ contains $5$ which is in $P$ and $n$ and thus $P+n$. No good.
$n = 90 = 2 times 3 times 3 times 5$ contains $2$. No good.
$n = 91 = 7 times 13$. No good.
$n = 97 = ldots$ Aha!
$n = 96, 95, 94, 93, 92$, these all have primes in common with $P$.
This is just to give you some idea about how I approached the problem in my mind, in the hope that it might help you approach similar problems in the future.
There are no 'steps' per se. Problems are very often not routine and don't have a clear and obvious method to follow. It requires turning the problem over in your mind, using some ideas you're familiar with (prime factorisation and algebra, in this case) and approaching from several angles until you find some insight.
As a final note, it is absolutely possible to brute force this using a computer. Here is some badly written sage code to solve this problem:
X = range(2,91)
for x in X:
for k in range(2,int(sqrt(x))+1):
if x % k == 0:
X.remove(x)
break
P = 1
for x in X:
P *= x
n = 2
while any((P+n) % x == 0 for x in X):
n += 1
print n
You can try this code by clicking here. I think this problem is best solved on paper. But sometimes making the computer find the answer and then figuring out why that is the answer is a useful learning experience.
answered Feb 3 at 10:05
ShaiShai
1,217811
answered Feb 3 at 10:05
ShaiShai
1,217811
answered Feb 3 at 10:05
ShaiShai
1,217811
answered Feb 3 at 10:05
ShaiShai
1,217811
1,217811
add a comment |
add a comment |
$begingroup$
Hint :
The number $$P+97$$ does not have a prime factor less than $90$ (Try to find out why). On the other hand, $$P+2,cdots,P+96$$ have a prime factor less than $90$ (again try to find out why , hint : the second summand divides the sum). Hence the answer is $96$.
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
$endgroup$
add a comment |
$begingroup$
Hint :
The number $$P+97$$ does not have a prime factor less than $90$ (Try to find out why). On the other hand, $$P+2,cdots,P+96$$ have a prime factor less than $90$ (again try to find out why , hint : the second summand divides the sum). Hence the answer is $96$.
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
$endgroup$
add a comment |
$begingroup$
Hint :
The number $$P+97$$ does not have a prime factor less than $90$ (Try to find out why). On the other hand, $$P+2,cdots,P+96$$ have a prime factor less than $90$ (again try to find out why , hint : the second summand divides the sum). Hence the answer is $96$.
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
$endgroup$
Hint :
The number $$P+97$$ does not have a prime factor less than $90$ (Try to find out why). On the other hand, $$P+2,cdots,P+96$$ have a prime factor less than $90$ (again try to find out why , hint : the second summand divides the sum). Hence the answer is $96$.
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
answered Feb 3 at 9:12
PeterPeter
49.2k1240138
49.2k1240138
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%2f3098317%2fquestion-on-identifying-prime-factors-of-a-very-large-number%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
$begingroup$
So, $P=89!$, right?
$endgroup$
– lhf
Feb 3 at 10:35