Prime Difference
$begingroup$
Given an integer n, output the smallest prime such that the difference between it and the next prime is at least n.
For example, if n=5
, you would output 23
, since the next prime is 29
, and 29-23>=5
.
More Input/Output Examples
1 -> 2 (3 - 2 >= 1)
2 -> 3 (5 - 3 >= 2)
3 -> 7 (11 - 7 >= 3)
4 -> 7
5 -> 23
6 -> 23
7 -> 89
8 -> 89
This is code-golf, so shortest code wins.
code-golf number
$endgroup$
add a comment |
$begingroup$
Given an integer n, output the smallest prime such that the difference between it and the next prime is at least n.
For example, if n=5
, you would output 23
, since the next prime is 29
, and 29-23>=5
.
More Input/Output Examples
1 -> 2 (3 - 2 >= 1)
2 -> 3 (5 - 3 >= 2)
3 -> 7 (11 - 7 >= 3)
4 -> 7
5 -> 23
6 -> 23
7 -> 89
8 -> 89
This is code-golf, so shortest code wins.
code-golf number
$endgroup$
add a comment |
$begingroup$
Given an integer n, output the smallest prime such that the difference between it and the next prime is at least n.
For example, if n=5
, you would output 23
, since the next prime is 29
, and 29-23>=5
.
More Input/Output Examples
1 -> 2 (3 - 2 >= 1)
2 -> 3 (5 - 3 >= 2)
3 -> 7 (11 - 7 >= 3)
4 -> 7
5 -> 23
6 -> 23
7 -> 89
8 -> 89
This is code-golf, so shortest code wins.
code-golf number
$endgroup$
Given an integer n, output the smallest prime such that the difference between it and the next prime is at least n.
For example, if n=5
, you would output 23
, since the next prime is 29
, and 29-23>=5
.
More Input/Output Examples
1 -> 2 (3 - 2 >= 1)
2 -> 3 (5 - 3 >= 2)
3 -> 7 (11 - 7 >= 3)
4 -> 7
5 -> 23
6 -> 23
7 -> 89
8 -> 89
This is code-golf, so shortest code wins.
code-golf number
code-golf number
edited 3 hours ago
Quintec
asked 3 hours ago
QuintecQuintec
1,5031722
1,5031722
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Husk, 8 bytes
Ψḟo≥⁰≠İp
Try it online!
Inspired by this post in chat
ḟ
, under normal circumstances, finds the first element of a list that satisfies a predicate. However, when combined with the function Ψ
, it finds the first element that satisfies a predicate with respect to its successor in the list.
The predicate is o≥⁰≠
, which asks if the absolute difference of two numbers is at least the input.
The list is İp
, the list of prime numbers
$endgroup$
add a comment |
$begingroup$
Husk, 9 bytes
→←ġo<⁰-İp
Try it online!
This is a really interesting question allowing a range of possible approaches (and Husk is a good fit for it; I learned the language for the challenge).
The TIO link contains a wrapper to run this function on all inputs from 1 to 10.
Explanation
→←ġo<⁰-İp
İp The (infinite) list of primes
ġ Group them, putting adjacent primes in the same group if
- the difference between them
<⁰ is less than the input
o (fix for a parser ambiguity that causes this parse to be chosen)
→ Take the last element of
← the first group
Grouping primes that are too close together means that the first break in the groups will be the first point at which the primes are sufficiently far apart, so we simply just need to find the prime just after the break.
Other potential solutions
Here's an 8-byte solution that, sadly, only works with even numbers as input (and thus isn't valid):
-⁰LU⁰mṗN
N On the infinite list of natural numbers
m replace each element with
ṗ 0 if composite, or a distinct number if prime
U Find the longest prefix with no repeated sublist of length
⁰ equal to the input
-⁰ Subtract the input from
L the length of that prefix
The idea is that when we have two primes that are a distance of (say) 6 apart, there'll be a sequence of five consecutive zeroes in the mṗN
sequence, which contains two identical sublists of length 4 (the first four zeroes and last four zeroes), but such a repetition cannot happen earlier (because as each prime is mapped to a unique number, any length-4 substrings before the first prime gap > 4 will contain a prime number, and the substring will therefore be unique as it's the only substring which contains that number in that position). Then we just have to subtract the trailing zeroes from the length of the prefix to get our answer.
This doesn't work with odd inputs because the sublist of input zeroes only occurs once rather than twice, so the code ends up finding the second point at which it occurs rather than the first.
$endgroup$
add a comment |
$begingroup$
Perl 6, 56 bytes
{first {$^a.$![1]-$a>=$_},.$!}
$!={grep &is-prime,$_..*}
Try it online!
I feel like there's definitely some improvement to be made here, especially in regards to the $![1]
. This is an anonymous code block that can be assigned to a variable, as well as a helper function assigned to $!
.
$endgroup$
add a comment |
$begingroup$
Jelly, 8 bytes
2Æn:+ɗ1#
Try it online!
How it works
2Æn:+ɗ1# Main link. Argument: n
2 Set the return value to 2.
1# Find the first k ≥ 2 such that the link to the left, called with arguments
k and n, returns a truthy value.
ɗ Dyadic chain:
Æn Find the next prime p ≥ k.
+ Yield k + n.
: Perform integer division.
$endgroup$
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.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2fcodegolf.stackexchange.com%2fquestions%2f179017%2fprime-difference%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Husk, 8 bytes
Ψḟo≥⁰≠İp
Try it online!
Inspired by this post in chat
ḟ
, under normal circumstances, finds the first element of a list that satisfies a predicate. However, when combined with the function Ψ
, it finds the first element that satisfies a predicate with respect to its successor in the list.
The predicate is o≥⁰≠
, which asks if the absolute difference of two numbers is at least the input.
The list is İp
, the list of prime numbers
$endgroup$
add a comment |
$begingroup$
Husk, 8 bytes
Ψḟo≥⁰≠İp
Try it online!
Inspired by this post in chat
ḟ
, under normal circumstances, finds the first element of a list that satisfies a predicate. However, when combined with the function Ψ
, it finds the first element that satisfies a predicate with respect to its successor in the list.
The predicate is o≥⁰≠
, which asks if the absolute difference of two numbers is at least the input.
The list is İp
, the list of prime numbers
$endgroup$
add a comment |
$begingroup$
Husk, 8 bytes
Ψḟo≥⁰≠İp
Try it online!
Inspired by this post in chat
ḟ
, under normal circumstances, finds the first element of a list that satisfies a predicate. However, when combined with the function Ψ
, it finds the first element that satisfies a predicate with respect to its successor in the list.
The predicate is o≥⁰≠
, which asks if the absolute difference of two numbers is at least the input.
The list is İp
, the list of prime numbers
$endgroup$
Husk, 8 bytes
Ψḟo≥⁰≠İp
Try it online!
Inspired by this post in chat
ḟ
, under normal circumstances, finds the first element of a list that satisfies a predicate. However, when combined with the function Ψ
, it finds the first element that satisfies a predicate with respect to its successor in the list.
The predicate is o≥⁰≠
, which asks if the absolute difference of two numbers is at least the input.
The list is İp
, the list of prime numbers
answered 2 hours ago
H.PWizH.PWiz
9,95721350
9,95721350
add a comment |
add a comment |
$begingroup$
Husk, 9 bytes
→←ġo<⁰-İp
Try it online!
This is a really interesting question allowing a range of possible approaches (and Husk is a good fit for it; I learned the language for the challenge).
The TIO link contains a wrapper to run this function on all inputs from 1 to 10.
Explanation
→←ġo<⁰-İp
İp The (infinite) list of primes
ġ Group them, putting adjacent primes in the same group if
- the difference between them
<⁰ is less than the input
o (fix for a parser ambiguity that causes this parse to be chosen)
→ Take the last element of
← the first group
Grouping primes that are too close together means that the first break in the groups will be the first point at which the primes are sufficiently far apart, so we simply just need to find the prime just after the break.
Other potential solutions
Here's an 8-byte solution that, sadly, only works with even numbers as input (and thus isn't valid):
-⁰LU⁰mṗN
N On the infinite list of natural numbers
m replace each element with
ṗ 0 if composite, or a distinct number if prime
U Find the longest prefix with no repeated sublist of length
⁰ equal to the input
-⁰ Subtract the input from
L the length of that prefix
The idea is that when we have two primes that are a distance of (say) 6 apart, there'll be a sequence of five consecutive zeroes in the mṗN
sequence, which contains two identical sublists of length 4 (the first four zeroes and last four zeroes), but such a repetition cannot happen earlier (because as each prime is mapped to a unique number, any length-4 substrings before the first prime gap > 4 will contain a prime number, and the substring will therefore be unique as it's the only substring which contains that number in that position). Then we just have to subtract the trailing zeroes from the length of the prefix to get our answer.
This doesn't work with odd inputs because the sublist of input zeroes only occurs once rather than twice, so the code ends up finding the second point at which it occurs rather than the first.
$endgroup$
add a comment |
$begingroup$
Husk, 9 bytes
→←ġo<⁰-İp
Try it online!
This is a really interesting question allowing a range of possible approaches (and Husk is a good fit for it; I learned the language for the challenge).
The TIO link contains a wrapper to run this function on all inputs from 1 to 10.
Explanation
→←ġo<⁰-İp
İp The (infinite) list of primes
ġ Group them, putting adjacent primes in the same group if
- the difference between them
<⁰ is less than the input
o (fix for a parser ambiguity that causes this parse to be chosen)
→ Take the last element of
← the first group
Grouping primes that are too close together means that the first break in the groups will be the first point at which the primes are sufficiently far apart, so we simply just need to find the prime just after the break.
Other potential solutions
Here's an 8-byte solution that, sadly, only works with even numbers as input (and thus isn't valid):
-⁰LU⁰mṗN
N On the infinite list of natural numbers
m replace each element with
ṗ 0 if composite, or a distinct number if prime
U Find the longest prefix with no repeated sublist of length
⁰ equal to the input
-⁰ Subtract the input from
L the length of that prefix
The idea is that when we have two primes that are a distance of (say) 6 apart, there'll be a sequence of five consecutive zeroes in the mṗN
sequence, which contains two identical sublists of length 4 (the first four zeroes and last four zeroes), but such a repetition cannot happen earlier (because as each prime is mapped to a unique number, any length-4 substrings before the first prime gap > 4 will contain a prime number, and the substring will therefore be unique as it's the only substring which contains that number in that position). Then we just have to subtract the trailing zeroes from the length of the prefix to get our answer.
This doesn't work with odd inputs because the sublist of input zeroes only occurs once rather than twice, so the code ends up finding the second point at which it occurs rather than the first.
$endgroup$
add a comment |
$begingroup$
Husk, 9 bytes
→←ġo<⁰-İp
Try it online!
This is a really interesting question allowing a range of possible approaches (and Husk is a good fit for it; I learned the language for the challenge).
The TIO link contains a wrapper to run this function on all inputs from 1 to 10.
Explanation
→←ġo<⁰-İp
İp The (infinite) list of primes
ġ Group them, putting adjacent primes in the same group if
- the difference between them
<⁰ is less than the input
o (fix for a parser ambiguity that causes this parse to be chosen)
→ Take the last element of
← the first group
Grouping primes that are too close together means that the first break in the groups will be the first point at which the primes are sufficiently far apart, so we simply just need to find the prime just after the break.
Other potential solutions
Here's an 8-byte solution that, sadly, only works with even numbers as input (and thus isn't valid):
-⁰LU⁰mṗN
N On the infinite list of natural numbers
m replace each element with
ṗ 0 if composite, or a distinct number if prime
U Find the longest prefix with no repeated sublist of length
⁰ equal to the input
-⁰ Subtract the input from
L the length of that prefix
The idea is that when we have two primes that are a distance of (say) 6 apart, there'll be a sequence of five consecutive zeroes in the mṗN
sequence, which contains two identical sublists of length 4 (the first four zeroes and last four zeroes), but such a repetition cannot happen earlier (because as each prime is mapped to a unique number, any length-4 substrings before the first prime gap > 4 will contain a prime number, and the substring will therefore be unique as it's the only substring which contains that number in that position). Then we just have to subtract the trailing zeroes from the length of the prefix to get our answer.
This doesn't work with odd inputs because the sublist of input zeroes only occurs once rather than twice, so the code ends up finding the second point at which it occurs rather than the first.
$endgroup$
Husk, 9 bytes
→←ġo<⁰-İp
Try it online!
This is a really interesting question allowing a range of possible approaches (and Husk is a good fit for it; I learned the language for the challenge).
The TIO link contains a wrapper to run this function on all inputs from 1 to 10.
Explanation
→←ġo<⁰-İp
İp The (infinite) list of primes
ġ Group them, putting adjacent primes in the same group if
- the difference between them
<⁰ is less than the input
o (fix for a parser ambiguity that causes this parse to be chosen)
→ Take the last element of
← the first group
Grouping primes that are too close together means that the first break in the groups will be the first point at which the primes are sufficiently far apart, so we simply just need to find the prime just after the break.
Other potential solutions
Here's an 8-byte solution that, sadly, only works with even numbers as input (and thus isn't valid):
-⁰LU⁰mṗN
N On the infinite list of natural numbers
m replace each element with
ṗ 0 if composite, or a distinct number if prime
U Find the longest prefix with no repeated sublist of length
⁰ equal to the input
-⁰ Subtract the input from
L the length of that prefix
The idea is that when we have two primes that are a distance of (say) 6 apart, there'll be a sequence of five consecutive zeroes in the mṗN
sequence, which contains two identical sublists of length 4 (the first four zeroes and last four zeroes), but such a repetition cannot happen earlier (because as each prime is mapped to a unique number, any length-4 substrings before the first prime gap > 4 will contain a prime number, and the substring will therefore be unique as it's the only substring which contains that number in that position). Then we just have to subtract the trailing zeroes from the length of the prefix to get our answer.
This doesn't work with odd inputs because the sublist of input zeroes only occurs once rather than twice, so the code ends up finding the second point at which it occurs rather than the first.
edited 2 hours ago
community wiki
2 revs
ais523
add a comment |
add a comment |
$begingroup$
Perl 6, 56 bytes
{first {$^a.$![1]-$a>=$_},.$!}
$!={grep &is-prime,$_..*}
Try it online!
I feel like there's definitely some improvement to be made here, especially in regards to the $![1]
. This is an anonymous code block that can be assigned to a variable, as well as a helper function assigned to $!
.
$endgroup$
add a comment |
$begingroup$
Perl 6, 56 bytes
{first {$^a.$![1]-$a>=$_},.$!}
$!={grep &is-prime,$_..*}
Try it online!
I feel like there's definitely some improvement to be made here, especially in regards to the $![1]
. This is an anonymous code block that can be assigned to a variable, as well as a helper function assigned to $!
.
$endgroup$
add a comment |
$begingroup$
Perl 6, 56 bytes
{first {$^a.$![1]-$a>=$_},.$!}
$!={grep &is-prime,$_..*}
Try it online!
I feel like there's definitely some improvement to be made here, especially in regards to the $![1]
. This is an anonymous code block that can be assigned to a variable, as well as a helper function assigned to $!
.
$endgroup$
Perl 6, 56 bytes
{first {$^a.$![1]-$a>=$_},.$!}
$!={grep &is-prime,$_..*}
Try it online!
I feel like there's definitely some improvement to be made here, especially in regards to the $![1]
. This is an anonymous code block that can be assigned to a variable, as well as a helper function assigned to $!
.
answered 2 hours ago
Jo KingJo King
21.4k248110
21.4k248110
add a comment |
add a comment |
$begingroup$
Jelly, 8 bytes
2Æn:+ɗ1#
Try it online!
How it works
2Æn:+ɗ1# Main link. Argument: n
2 Set the return value to 2.
1# Find the first k ≥ 2 such that the link to the left, called with arguments
k and n, returns a truthy value.
ɗ Dyadic chain:
Æn Find the next prime p ≥ k.
+ Yield k + n.
: Perform integer division.
$endgroup$
add a comment |
$begingroup$
Jelly, 8 bytes
2Æn:+ɗ1#
Try it online!
How it works
2Æn:+ɗ1# Main link. Argument: n
2 Set the return value to 2.
1# Find the first k ≥ 2 such that the link to the left, called with arguments
k and n, returns a truthy value.
ɗ Dyadic chain:
Æn Find the next prime p ≥ k.
+ Yield k + n.
: Perform integer division.
$endgroup$
add a comment |
$begingroup$
Jelly, 8 bytes
2Æn:+ɗ1#
Try it online!
How it works
2Æn:+ɗ1# Main link. Argument: n
2 Set the return value to 2.
1# Find the first k ≥ 2 such that the link to the left, called with arguments
k and n, returns a truthy value.
ɗ Dyadic chain:
Æn Find the next prime p ≥ k.
+ Yield k + n.
: Perform integer division.
$endgroup$
Jelly, 8 bytes
2Æn:+ɗ1#
Try it online!
How it works
2Æn:+ɗ1# Main link. Argument: n
2 Set the return value to 2.
1# Find the first k ≥ 2 such that the link to the left, called with arguments
k and n, returns a truthy value.
ɗ Dyadic chain:
Æn Find the next prime p ≥ k.
+ Yield k + n.
: Perform integer division.
answered 2 hours ago
Dennis♦Dennis
187k32297737
187k32297737
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2fcodegolf.stackexchange.com%2fquestions%2f179017%2fprime-difference%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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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