Mixing
Smallest prime of the form 41033333333…?
What is the smallest prime of the form $410333333333...$ ?
It should have more than $10,000$ digits.
[added from answer posted 2013 May 26 at 20:52 by Peter]
I thought it would be clear, but it seems not to be.
Of course, after $410$, only $3$'s should follow.
Otherwise, it would be very easy to find primes.
I checked the numbers up to about $10,000$ digits,
but of course, I would be glad if someone checks
this, too.
I do not understand the question, WHY this number
is interesting for me. Mersenne primes are not so
much more interesting, but recently a prize of
$100,000$ $was payed for a community finding a
$17$-million-digit mersenne prime. I would have
better ideas what to do with all this money ...
number-theory prime-numbers
edited Nov 21 '18 at 12:32
amWhy
192k28224439
asked May 26 '13 at 19:52
Peter
411
|
show 2 more comments
What is the smallest prime of the form $410333333333...$ ?
It should have more than $10,000$ digits.
[added from answer posted 2013 May 26 at 20:52 by Peter]
I thought it would be clear, but it seems not to be.
Of course, after $410$, only $3$'s should follow.
Otherwise, it would be very easy to find primes.
I checked the numbers up to about $10,000$ digits,
but of course, I would be glad if someone checks
this, too.
I do not understand the question, WHY this number
is interesting for me. Mersenne primes are not so
much more interesting, but recently a prize of
$100,000$ $was payed for a community finding a
$17$-million-digit mersenne prime. I would have
better ideas what to do with all this money ...
number-theory prime-numbers
edited Nov 21 '18 at 12:32
amWhy
192k28224439
asked May 26 '13 at 19:52
Peter
411
8
What evidence do you have that there is a such a prime?
– Thomas Andrews
May 26 '13 at 20:01
4
Do you mean $41033333333cdot 10^k<p<41033333334cdot 10^k$ or $3p=1231cdot 10^k-1$?
– Hagen von Eitzen
May 26 '13 at 20:14
6
Why are you interested? What have you tried?
– draks ...
May 26 '13 at 20:19
3
I assume the number you are interested in is of the form $$41 cdot 10^{n+1} + dfrac{10^n-1}3$$ If so, note that for odd $n$, $11$ divides the number. Hence, $n$ has to be even, for the number to be a prime.
– user17762
May 26 '13 at 20:57
4
Also @user17762, since $37mid41033$, $13mid4103333$ and $13cdot37mid333333$ it follows that $n$ has to be a multiple of $6$, for the number to be prime.
– P..
May 26 '13 at 21:12
|
show 2 more comments
What is the smallest prime of the form $410333333333...$ ?
It should have more than $10,000$ digits.
[added from answer posted 2013 May 26 at 20:52 by Peter]
I thought it would be clear, but it seems not to be.
Of course, after $410$, only $3$'s should follow.
Otherwise, it would be very easy to find primes.
I checked the numbers up to about $10,000$ digits,
but of course, I would be glad if someone checks
this, too.
I do not understand the question, WHY this number
is interesting for me. Mersenne primes are not so
much more interesting, but recently a prize of
$100,000$ $was payed for a community finding a
$17$-million-digit mersenne prime. I would have
better ideas what to do with all this money ...
number-theory prime-numbers
edited Nov 21 '18 at 12:32
amWhy
192k28224439
asked May 26 '13 at 19:52
Peter
411
What is the smallest prime of the form $410333333333...$ ?
It should have more than $10,000$ digits.
[added from answer posted 2013 May 26 at 20:52 by Peter]
I thought it would be clear, but it seems not to be.
Of course, after $410$, only $3$'s should follow.
Otherwise, it would be very easy to find primes.
I checked the numbers up to about $10,000$ digits,
but of course, I would be glad if someone checks
this, too.
I do not understand the question, WHY this number
is interesting for me. Mersenne primes are not so
much more interesting, but recently a prize of
$100,000$ $was payed for a community finding a
$17$-million-digit mersenne prime. I would have
better ideas what to do with all this money ...
number-theory prime-numbers
number-theory prime-numbers
edited Nov 21 '18 at 12:32
amWhy
192k28224439
asked May 26 '13 at 19:52
Peter
411
edited Nov 21 '18 at 12:32
amWhy
192k28224439
asked May 26 '13 at 19:52
Peter
411
edited Nov 21 '18 at 12:32
amWhy
192k28224439
edited Nov 21 '18 at 12:32
amWhy
192k28224439
edited Nov 21 '18 at 12:32
amWhy
192k28224439
192k28224439
asked May 26 '13 at 19:52
Peter
411
asked May 26 '13 at 19:52
Peter
411
asked May 26 '13 at 19:52
Peter
411
411
8
What evidence do you have that there is a such a prime?
– Thomas Andrews
May 26 '13 at 20:01
4
Do you mean $41033333333cdot 10^k<p<41033333334cdot 10^k$ or $3p=1231cdot 10^k-1$?
– Hagen von Eitzen
May 26 '13 at 20:14
6
Why are you interested? What have you tried?
– draks ...
May 26 '13 at 20:19
3
I assume the number you are interested in is of the form $$41 cdot 10^{n+1} + dfrac{10^n-1}3$$ If so, note that for odd $n$, $11$ divides the number. Hence, $n$ has to be even, for the number to be a prime.
– user17762
May 26 '13 at 20:57
4
Also @user17762, since $37mid41033$, $13mid4103333$ and $13cdot37mid333333$ it follows that $n$ has to be a multiple of $6$, for the number to be prime.
– P..
May 26 '13 at 21:12
|
show 2 more comments
8
What evidence do you have that there is a such a prime?
– Thomas Andrews
May 26 '13 at 20:01
4
Do you mean $41033333333cdot 10^k<p<41033333334cdot 10^k$ or $3p=1231cdot 10^k-1$?
– Hagen von Eitzen
May 26 '13 at 20:14
6
Why are you interested? What have you tried?
– draks ...
May 26 '13 at 20:19
3
I assume the number you are interested in is of the form $$41 cdot 10^{n+1} + dfrac{10^n-1}3$$ If so, note that for odd $n$, $11$ divides the number. Hence, $n$ has to be even, for the number to be a prime.
– user17762
May 26 '13 at 20:57
4
Also @user17762, since $37mid41033$, $13mid4103333$ and $13cdot37mid333333$ it follows that $n$ has to be a multiple of $6$, for the number to be prime.
– P..
May 26 '13 at 21:12
8
8
What evidence do you have that there is a such a prime?
– Thomas Andrews
May 26 '13 at 20:01
What evidence do you have that there is a such a prime?
– Thomas Andrews
May 26 '13 at 20:01
4
4
Do you mean $41033333333cdot 10^k<p<41033333334cdot 10^k$ or $3p=1231cdot 10^k-1$?
– Hagen von Eitzen
May 26 '13 at 20:14
Do you mean $41033333333cdot 10^k<p<41033333334cdot 10^k$ or $3p=1231cdot 10^k-1$?
– Hagen von Eitzen
May 26 '13 at 20:14
6
6
Why are you interested? What have you tried?
– draks ...
May 26 '13 at 20:19
Why are you interested? What have you tried?
– draks ...
May 26 '13 at 20:19
3
3
I assume the number you are interested in is of the form $$41 cdot 10^{n+1} + dfrac{10^n-1}3$$ If so, note that for odd $n$, $11$ divides the number. Hence, $n$ has to be even, for the number to be a prime.
– user17762
May 26 '13 at 20:57
I assume the number you are interested in is of the form $$41 cdot 10^{n+1} + dfrac{10^n-1}3$$ If so, note that for odd $n$, $11$ divides the number. Hence, $n$ has to be even, for the number to be a prime.
– user17762
May 26 '13 at 20:57
4
4
Also @user17762, since $37mid41033$, $13mid4103333$ and $13cdot37mid333333$ it follows that $n$ has to be a multiple of $6$, for the number to be prime.
– P..
May 26 '13 at 21:12
Also @user17762, since $37mid41033$, $13mid4103333$ and $13cdot37mid333333$ it follows that $n$ has to be a multiple of $6$, for the number to be prime.
– P..
May 26 '13 at 21:12
|
show 2 more comments
2 Answers
2
active
oldest
votes
I guess $(1231times 10^{6times 6233}-1)/3$, that is with 37,398 threes. (PFGW calls it a probable prime to base 2,3,5,7.)
Let $a(n)=(1231times 10^n-1)/3$. Then if a prime $p$ divides $a(n)$, then
$$
10^n equiv 1231^{-1} pmod{p} \
10^{n+kcdotmathrm{ord}_p10} equiv 1231^{-1} pmod{p} \
p mid a(n+kcdot mathrm{ord}_p10)
$$
where $mathrm{ord}_p10$ is the smallest exponent $i$ for which $10^iequiv 1pmod{p}$.
So for example
$$
11 mid a(2k+1) \
41 mid a(5k) \
35 mid a(3k+2) \
47 mid a(46k+10)
$$
and so forth.
If $n_2$ satisfies one or more of these for a prime $p$ with $k>1$, then there must be a smaller $n_1$ with $k=0$ with $p mid gcd(a(n_2),a(n_1))$. Since GCD can be computed quickly, for $n>10368$ and divisible by 6 I identified candidates where $gcd(a(n),a(i))=1$ for several choices of $i<n$. This eliminated about 95% of cases, I made a list of the rest and tested about 1000 before finding one that reported as a probable prime.
answered May 30 '13 at 4:03
Zander
9,80511548
add a comment |
41033333333323 = 41033333333300 + 23 is prime.
So is 4103333333333333333333000159.
Set $x= 4103333333333333333333...$ ($k$ times a 3). Then $log x approx 6 + 2.3 cdot k$. By the Prime Number Theorem, you'll find a prime of the form $10^nx + r, , r < 10^n$ with high probability (let's say 0.999999) if $10^n > 100 + 30k$ or so. That is, $n ge 3 + log_{10} k$ should be enough.
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
6
Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise.
– Hagen von Eitzen
May 26 '13 at 20:23
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f403184%2fsmallest-prime-of-the-form-41033333333%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
I guess $(1231times 10^{6times 6233}-1)/3$, that is with 37,398 threes. (PFGW calls it a probable prime to base 2,3,5,7.)
Let $a(n)=(1231times 10^n-1)/3$. Then if a prime $p$ divides $a(n)$, then
$$
10^n equiv 1231^{-1} pmod{p} \
10^{n+kcdotmathrm{ord}_p10} equiv 1231^{-1} pmod{p} \
p mid a(n+kcdot mathrm{ord}_p10)
$$
where $mathrm{ord}_p10$ is the smallest exponent $i$ for which $10^iequiv 1pmod{p}$.
So for example
$$
11 mid a(2k+1) \
41 mid a(5k) \
35 mid a(3k+2) \
47 mid a(46k+10)
$$
and so forth.
If $n_2$ satisfies one or more of these for a prime $p$ with $k>1$, then there must be a smaller $n_1$ with $k=0$ with $p mid gcd(a(n_2),a(n_1))$. Since GCD can be computed quickly, for $n>10368$ and divisible by 6 I identified candidates where $gcd(a(n),a(i))=1$ for several choices of $i<n$. This eliminated about 95% of cases, I made a list of the rest and tested about 1000 before finding one that reported as a probable prime.
answered May 30 '13 at 4:03
Zander
9,80511548
add a comment |
I guess $(1231times 10^{6times 6233}-1)/3$, that is with 37,398 threes. (PFGW calls it a probable prime to base 2,3,5,7.)
Let $a(n)=(1231times 10^n-1)/3$. Then if a prime $p$ divides $a(n)$, then
$$
10^n equiv 1231^{-1} pmod{p} \
10^{n+kcdotmathrm{ord}_p10} equiv 1231^{-1} pmod{p} \
p mid a(n+kcdot mathrm{ord}_p10)
$$
where $mathrm{ord}_p10$ is the smallest exponent $i$ for which $10^iequiv 1pmod{p}$.
So for example
$$
11 mid a(2k+1) \
41 mid a(5k) \
35 mid a(3k+2) \
47 mid a(46k+10)
$$
and so forth.
If $n_2$ satisfies one or more of these for a prime $p$ with $k>1$, then there must be a smaller $n_1$ with $k=0$ with $p mid gcd(a(n_2),a(n_1))$. Since GCD can be computed quickly, for $n>10368$ and divisible by 6 I identified candidates where $gcd(a(n),a(i))=1$ for several choices of $i<n$. This eliminated about 95% of cases, I made a list of the rest and tested about 1000 before finding one that reported as a probable prime.
answered May 30 '13 at 4:03
Zander
9,80511548
add a comment |
I guess $(1231times 10^{6times 6233}-1)/3$, that is with 37,398 threes. (PFGW calls it a probable prime to base 2,3,5,7.)
Let $a(n)=(1231times 10^n-1)/3$. Then if a prime $p$ divides $a(n)$, then
$$
10^n equiv 1231^{-1} pmod{p} \
10^{n+kcdotmathrm{ord}_p10} equiv 1231^{-1} pmod{p} \
p mid a(n+kcdot mathrm{ord}_p10)
$$
where $mathrm{ord}_p10$ is the smallest exponent $i$ for which $10^iequiv 1pmod{p}$.
So for example
$$
11 mid a(2k+1) \
41 mid a(5k) \
35 mid a(3k+2) \
47 mid a(46k+10)
$$
and so forth.
If $n_2$ satisfies one or more of these for a prime $p$ with $k>1$, then there must be a smaller $n_1$ with $k=0$ with $p mid gcd(a(n_2),a(n_1))$. Since GCD can be computed quickly, for $n>10368$ and divisible by 6 I identified candidates where $gcd(a(n),a(i))=1$ for several choices of $i<n$. This eliminated about 95% of cases, I made a list of the rest and tested about 1000 before finding one that reported as a probable prime.
answered May 30 '13 at 4:03
Zander
9,80511548
I guess $(1231times 10^{6times 6233}-1)/3$, that is with 37,398 threes. (PFGW calls it a probable prime to base 2,3,5,7.)
Let $a(n)=(1231times 10^n-1)/3$. Then if a prime $p$ divides $a(n)$, then
$$
10^n equiv 1231^{-1} pmod{p} \
10^{n+kcdotmathrm{ord}_p10} equiv 1231^{-1} pmod{p} \
p mid a(n+kcdot mathrm{ord}_p10)
$$
where $mathrm{ord}_p10$ is the smallest exponent $i$ for which $10^iequiv 1pmod{p}$.
So for example
$$
11 mid a(2k+1) \
41 mid a(5k) \
35 mid a(3k+2) \
47 mid a(46k+10)
$$
and so forth.
If $n_2$ satisfies one or more of these for a prime $p$ with $k>1$, then there must be a smaller $n_1$ with $k=0$ with $p mid gcd(a(n_2),a(n_1))$. Since GCD can be computed quickly, for $n>10368$ and divisible by 6 I identified candidates where $gcd(a(n),a(i))=1$ for several choices of $i<n$. This eliminated about 95% of cases, I made a list of the rest and tested about 1000 before finding one that reported as a probable prime.
answered May 30 '13 at 4:03
Zander
9,80511548
answered May 30 '13 at 4:03
Zander
9,80511548
answered May 30 '13 at 4:03
Zander
9,80511548
answered May 30 '13 at 4:03
Zander
9,80511548
9,80511548
add a comment |
add a comment |
41033333333323 = 41033333333300 + 23 is prime.
So is 4103333333333333333333000159.
Set $x= 4103333333333333333333...$ ($k$ times a 3). Then $log x approx 6 + 2.3 cdot k$. By the Prime Number Theorem, you'll find a prime of the form $10^nx + r, , r < 10^n$ with high probability (let's say 0.999999) if $10^n > 100 + 30k$ or so. That is, $n ge 3 + log_{10} k$ should be enough.
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
6
Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise.
– Hagen von Eitzen
May 26 '13 at 20:23
add a comment |
41033333333323 = 41033333333300 + 23 is prime.
So is 4103333333333333333333000159.
Set $x= 4103333333333333333333...$ ($k$ times a 3). Then $log x approx 6 + 2.3 cdot k$. By the Prime Number Theorem, you'll find a prime of the form $10^nx + r, , r < 10^n$ with high probability (let's say 0.999999) if $10^n > 100 + 30k$ or so. That is, $n ge 3 + log_{10} k$ should be enough.
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
6
Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise.
– Hagen von Eitzen
May 26 '13 at 20:23
add a comment |
41033333333323 = 41033333333300 + 23 is prime.
So is 4103333333333333333333000159.
Set $x= 4103333333333333333333...$ ($k$ times a 3). Then $log x approx 6 + 2.3 cdot k$. By the Prime Number Theorem, you'll find a prime of the form $10^nx + r, , r < 10^n$ with high probability (let's say 0.999999) if $10^n > 100 + 30k$ or so. That is, $n ge 3 + log_{10} k$ should be enough.
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
41033333333323 = 41033333333300 + 23 is prime.
So is 4103333333333333333333000159.
Set $x= 4103333333333333333333...$ ($k$ times a 3). Then $log x approx 6 + 2.3 cdot k$. By the Prime Number Theorem, you'll find a prime of the form $10^nx + r, , r < 10^n$ with high probability (let's say 0.999999) if $10^n > 100 + 30k$ or so. That is, $n ge 3 + log_{10} k$ should be enough.
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
edited May 26 '13 at 20:35
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
answered May 26 '13 at 20:20
Hans Engler
10.1k11836
10.1k11836
6
Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise.
– Hagen von Eitzen
May 26 '13 at 20:23
add a comment |
6
Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise.
– Hagen von Eitzen
May 26 '13 at 20:23
6
6
Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise.
– Hagen von Eitzen
May 26 '13 at 20:23
Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise.
– Hagen von Eitzen
May 26 '13 at 20:23
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f403184%2fsmallest-prime-of-the-form-41033333333%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
8
What evidence do you have that there is a such a prime?
– Thomas Andrews
May 26 '13 at 20:01
4
Do you mean $41033333333cdot 10^k<p<41033333334cdot 10^k$ or $3p=1231cdot 10^k-1$?
– Hagen von Eitzen
May 26 '13 at 20:14
6
Why are you interested? What have you tried?
– draks ...
May 26 '13 at 20:19
3
I assume the number you are interested in is of the form $$41 cdot 10^{n+1} + dfrac{10^n-1}3$$ If so, note that for odd $n$, $11$ divides the number. Hence, $n$ has to be even, for the number to be a prime.
– user17762
May 26 '13 at 20:57
4
Also @user17762, since $37mid41033$, $13mid4103333$ and $13cdot37mid333333$ it follows that $n$ has to be a multiple of $6$, for the number to be prime.
– P..
May 26 '13 at 21:12