Is this prime?(isthisprime.com)
isthisprime.com
Is this prime?
http://isthisprime.com/game/
125 comments
Ah, you beat me to the minute (game comes with a function is_prime):
var yes = document.getElementById('yes'),
no = document.getElementById('no'),
n = document.getElementById('n'),
start = document.getElementById('start');
function tick() {
console.log('tick');
if (is_prime(n.innerHTML) === 'prime') {
yes.click();
} else {
no.click();
}
window.setTimeout(tick, 500);
}
start.click();
tick();Or, do away with the whole "checking" nonsense:
game.check = function (answer) {
this.streak += 1;
this.next_n();
}
setInterval(function() {
document.querySelector("#yes").click();
}, 0);
document.querySelector("#start").click();
Why only add 1? Why add anything at all?
game.check = function() {
this.streak = Number.MAX_VALUE;
this.next_n();
};
document.querySelector("#start").click();
document.querySelector("#yes").click();24607 (with the cheat), 621 (without) :D
Fun evening challenge :P
function isPrime(n){
if ((n<=1) || (!n % 2)) {
return false;
}
for (var k = 3; k < Math.round(Math.sqrt(n) + 0.5); k = k+2) {
if (n % k == 0) {
return false;
}
}
return true;
}
var nSpan = $("span#n")
var yesButton = $("button#yes");
var noButton = $("button#no");
var body = $("body");
function solve(){
if (isPrime(parseInt(nSpan.innerHTML)) {
yesButton.click();
} else {
noButton.click();
}
if (body.className != "end") {
setTimeout(solve,0);
}
}
solve();Decreasing the loop's upper bound to Math.sqrt(value) and only testing odd values after 2 are really simple ways to improve performance.
Beyond that it'd be nice to build a list of previously determined primes to reduce your number of checks, but I guess at that point it might just be better to implement classic primality tests...
Beyond that it'd be nice to build a list of previously determined primes to reduce your number of checks, but I guess at that point it might just be better to implement classic primality tests...
It's faster to check that the value isn't less than the loop counter squared than to perform a square root.
If you go that way, it may be even faster (depending on you CPU, of course) to use a recursion for computing the squares:
(Quick check: if you use a binary search to find sqrt(n), you need 2log(n) iterations, each of which requires a division by two (for integers, that is a bit shift) and one addition. A linear search takes sqrt(n) iterations, each with three additions. For whatever ratio of speed of operations you pick, the former will be faster for sufficiently large n)
(n+1)^2 = n^2 + 2n + 1
def squares:
n = 1
nSquared = 1
delta = 1
while nSquared <= n:
n += 1
yield n
delta += 2
nSquared += delta
(Quick check: if you use a binary search to find sqrt(n), you need 2log(n) iterations, each of which requires a division by two (for integers, that is a bit shift) and one addition. A linear search takes sqrt(n) iterations, each with three additions. For whatever ratio of speed of operations you pick, the former will be faster for sufficiently large n)
You would normally use something like newton-raphson to compute a square root, which still isn't O(1) but converges fairly quickly. I would be very skeptical that n muls/adds would be faster than an sqrt, at very least for x86-64 since it is implemented as an instruction.
My mental model of a CPU is a 6502 or, at best, a 68000 without FPU :-)
When asked about modern day performance, I would just say “I do not know”. Thing is that those muls, on modern CPUs, might be pipelined in parallel with the adds, so that, time wise, you would get them for free.
But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit.
If you really want to know for x_64, http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf is insane.
And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’)
When asked about modern day performance, I would just say “I do not know”. Thing is that those muls, on modern CPUs, might be pipelined in parallel with the adds, so that, time wise, you would get them for free.
But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit.
If you really want to know for x_64, http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf is insane.
And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’)
Incidentally, even if you are using Newton's method to do square roots, it helps significantly to start with a guess of the right size. If your initial guess is way too large, each step will cut it down by about a factor of 1/2; if it's way too small, it's equivalent (for finding sqrt(N)) to choosing N/guess. Thus, if you're taking the square root of 2^64, and you start with 1, your subsequent guesses will be roughly 2^63, 2^62, 2^61, 2^60, ..., taking a total of 36 steps to reach the right integer; whereas if you started with 2^33, it takes (by my computation) only 5 steps to get to the right integer.
The effect is more significant with larger numbers:
The effect is more significant with larger numbers:
arc> (newton-steps (round (* 3/2 (expt 2 1000))) 1)
508
arc> (newton-steps (round (* 3/2 (expt 2 1000))) (expt 2 500))
8My mental model of a CPU unfortunately tends toward x86.
> But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit.
On the CPU side, the branch predictor might make the sqrt free by pipelining it, but that starts to make the analysis a bit harder. Strange things can happen when you introduce branch prediction. The performance would also depend on ALU/FPU contention, hyperthreads, etc...
> If you really want to know for x_64, http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf is insane.
I've only just started reading Agner Fog's documentation (which is awesome), but it definitely seems like the place the find low level information of the ilk when it's needed. If you read through the instruction table though, you probably noticed there are fsqrt and (v)sqrt(p)(s/d). For most purposes, x87 is actually deprecated and SSE2, the latter, is preferred for scalar floating point. I would guess the Mill devs might have some insightful comments.
> And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’)
I'm not sure that's quite right. Counting leading zeros is normally very fast if you have the instruction, but those two functions diverge pretty quick. For a constant cost, my guess is that the accuracy lost wouldn't be performance gained. The other point is that accuracy is fairly important if you're testing for primality.
> But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit.
On the CPU side, the branch predictor might make the sqrt free by pipelining it, but that starts to make the analysis a bit harder. Strange things can happen when you introduce branch prediction. The performance would also depend on ALU/FPU contention, hyperthreads, etc...
> If you really want to know for x_64, http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf is insane.
I've only just started reading Agner Fog's documentation (which is awesome), but it definitely seems like the place the find low level information of the ilk when it's needed. If you read through the instruction table though, you probably noticed there are fsqrt and (v)sqrt(p)(s/d). For most purposes, x87 is actually deprecated and SSE2, the latter, is preferred for scalar floating point. I would guess the Mill devs might have some insightful comments.
> And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’)
I'm not sure that's quite right. Counting leading zeros is normally very fast if you have the instruction, but those two functions diverge pretty quick. For a constant cost, my guess is that the accuracy lost wouldn't be performance gained. The other point is that accuracy is fairly important if you're testing for primality.
It's an FPU instruction with some setup and teardown instructions associated.
I usually bow to Agner Fog on this:
"On Core2 65nm, FSQRT takes 9 to 69 cc's (with almost equal reciprocal throughput), depending on the value and precision bits. For comparison, FDIV takes 9 to 38 cc's (with almost equal reciprocal throughput), FMUL takes 5 (recipthroughput = 2) and FADD takes 3 (recipthroughput = 1). SSE performance is about equal, but looks faster because it can't do 80bit math. SSE has a super fast approximate reciprocal and approximate reciprocal sqrt though.
On Core2 45nm, division and square root got faster; FSQRT takes 6 to 20 cc's, FDIV takes 6 to 21 cc's, FADD and FMUL haven't changed. Once again SSE performance is about the same."
I usually bow to Agner Fog on this:
"On Core2 65nm, FSQRT takes 9 to 69 cc's (with almost equal reciprocal throughput), depending on the value and precision bits. For comparison, FDIV takes 9 to 38 cc's (with almost equal reciprocal throughput), FMUL takes 5 (recipthroughput = 2) and FADD takes 3 (recipthroughput = 1). SSE performance is about equal, but looks faster because it can't do 80bit math. SSE has a super fast approximate reciprocal and approximate reciprocal sqrt though.
On Core2 45nm, division and square root got faster; FSQRT takes 6 to 20 cc's, FDIV takes 6 to 21 cc's, FADD and FMUL haven't changed. Once again SSE performance is about the same."
x87 is largely deprecated. Try inspecting the code emitted for floating point by all the major compilers.
You are correct. It looks like SSE sqrt matches or beats fsqrt too.
SSE performance is better than x87, for a number of reasons. Latency and throughput are generally better, but SSE also supports SIMD which allows more than one op per instruction. SSE also has more registers (x87 only has 8 80bit compared to at least 16 128bit). If I'm not mistaken, the number of available execution units with SSE is also larger, which means more opportunities for instruction level parallelism.
These are why modern compilers don't emit x87 for floating point.
These are why modern compilers don't emit x87 for floating point.
No it isn't. You only calculate the square root once, vs calculating the square at each iteration.
Calculating a square is ~1. A square root it ~N. Much harder to do. Its a common optimization in graphics code to compare squares for this reason.
She's right about squaring on each iteration, though. And granted, a square root is much more expensive, though done only once. Which method is faster would depend on the number of iterations.
The latency for sqrtss on broadwell is 11 cycles with a throughput of 4, where mul is a latency of 3 and throughput of 1. So, using some concrete numbers, sqrt is more expensive, but not polynomially or even an order of magnitude.
Right with modern floating point implementations its not the old guess-and-iterate method any more. SQRT is probably now on the order of an inverse?
I honestly haven't looked into it in that much detail, but if I had to guess... probably. I'm not sure what the implementation used in hardware currently is, but at very least it's constant bounded,
Conversions are still somewhat expensive, but I do know compared to polynomial time or a large enough constant, it can be a better choice for an optimization. For example, computing log10 of an integer.
Conversions are still somewhat expensive, but I do know compared to polynomial time or a large enough constant, it can be a better choice for an optimization. For example, computing log10 of an integer.
Since you're claiming that square root is "~N", the N here must be the number of digits. The number of multiplications required for the "optimization" you're proposing is exponential in this N.
Dynamic programming (testing divisibility by the primes already found) would greatly improve the algorithm. And of course sieving is absurdly fast compared to checking primality individually.
If you don't want the browser to freeze ...
var target = document.getElementById('n');
function detect() {
n = parseInt(target.firstChild.nodeValue);
if (typeof n === 'number' && is_prime(n) === 'prime') {
console.log('>> YES,' + n + ' is prime, clicking "yes" ...');
document.getElementById('yes').click();
} else {
console.log('>> NO,' + n + ' is not prime, clicking "no" ...');
document.getElementById('no').click();
}
}
var observer = new MutationObserver(function (mutations) {
mutations.forEach(function (mutation) {
window.setTimeout(detect, 500);
});
});
observer.observe(target, {
attributes: true,
childList: true,
characterData: true
});Or just:
setInterval(function() {game.check(is_prime(game.current_n) === 'prime')}, 0);Now the game is, Who can write most efficient primality check algorithm!
window.is_prime = function () { return "prime"; }[deleted]
At least write your own prime checking algorithm!
He initially did. Then decided to reuse the one already provided. The goal of cheating in this manner, after all, would be to match exactly the implementation the original programmer used. Even if it was buggy.
Am I the only one who thought this was an online tool to check if a product was Prime-eligable on Amazon?
I thought the same thing lol
That's a pretty good idea! lol
Nope. I thought same thing.
Yes.
Nice game. Something weird can happen in the brain when we have to choose a binary answer under pressure. Maybe the fact that we are answering positively for prime (which is not the default) adds to that. For me it helped to rename 'yes' to 'prime' and 'no' to 'divisible'.
Same here. What happened to me is, instead of asking myself "Is this a prime number?" I
kept starting to ask myself "Can this number be expressed as a multiplication of two other numbers?" for which the answers are obviously reversed.
Finding divisors is often hard when your number is large. It turns out the condition that a number n can be expressed as a multiple of two other numbers is equivalent to there being a number z less than n except for 1 and n-1 so that (z^2 mod n) == 1.
This condition is the basis of the Miller-Rabin primality test. Sadly its a bit hard for humans to implement this algorithm for mentally proving primality.
This condition is the basis of the Miller-Rabin primality test. Sadly its a bit hard for humans to implement this algorithm for mentally proving primality.
Yes, I found the UX aspect here interesting as it twisted my brain a bit too. A current example of this is the Brexit referendum, where the question was initially posed as a Yes or No, but required revision to a "Remain" or "Leave", which is much easier for casual observers to grok and lets people get behind their favourite actual position instead of embracing an arbitrary Boolean value (as happened with the Scottish referendum's Yes and No camps).
Also, Prime itself is a tricky term for a Yes-No question as it's really a negative concept - the absence of something. So asking if X is prime is requiring double-negative logic in the same way as an app setting like "Disable X feature [On / Off]".
Also, Prime itself is a tricky term for a Yes-No question as it's really a negative concept - the absence of something. So asking if X is prime is requiring double-negative logic in the same way as an app setting like "Disable X feature [On / Off]".
"1 is non-prime by definition."
dammit!
dammit!
It's mainly due to the Fundamental Theorem of Arithmetic (aka unique prime factorization) - https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme...
However this was not settled surprisingly late.
I have seen tables of prime counts produced in the 1950s and 1960s that specified whether they counted 1 as a prime, and some did count it.
I have seen tables of prime counts produced in the 1950s and 1960s that specified whether they counted 1 as a prime, and some did count it.
"The history of the primality of one: a selection of sources" (https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.h..., via https://primes.utm.edu/):
"The way mathematicians have viewed the number one (unity, the monad) has changed throughout the years. Most of the early Greeks did not view one as a number, but rather as the origin, or generator, of number. Around the time of Simon Stevin (1548-1620), one (and zero) were first widely viewed as numbers. This created a period of confusion about whether or not the number one was prime. In this dynamic survey, we collect a cornucopia of sources which deal directly with the "question what is the smallest prime?" The goal is to create a source book for studying the history of the definition of prime, especially as applied to the number one."
"The way mathematicians have viewed the number one (unity, the monad) has changed throughout the years. Most of the early Greeks did not view one as a number, but rather as the origin, or generator, of number. Around the time of Simon Stevin (1548-1620), one (and zero) were first widely viewed as numbers. This created a period of confusion about whether or not the number one was prime. In this dynamic survey, we collect a cornucopia of sources which deal directly with the "question what is the smallest prime?" The goal is to create a source book for studying the history of the definition of prime, especially as applied to the number one."
Still the case for the natural numbers (with 0 instead of 1). Though perhaps more obvious why you would choose one or the other there.
Going through school I'd be told 1 was/not prime differently by different teachers. Always seemed pretty arbitrary to me; like 'They' ought just to decide!
What we seem to be hearing here is that They had, just another classic case of this information taking 50 years to filter down the education system.. (I wonder how many planets they teach there as being in our solar system?)
Going through school I'd be told 1 was/not prime differently by different teachers. Always seemed pretty arbitrary to me; like 'They' ought just to decide!
What we seem to be hearing here is that They had, just another classic case of this information taking 50 years to filter down the education system.. (I wonder how many planets they teach there as being in our solar system?)
>(I wonder how many planets they teach there as being in our solar system?)
Your comment got me to look up the number of objects considered planets over the years, this has ranged from 5-23. Data since 1543 is available here: https://dx.doi.org/10.1038%2Fscientificamerican0107-34
For fun I did a linear regression of year vs # planets and found that the while the slope was 1.8 planets/century, this was not significantly different from zero. The evidence appears to be consistent with a constant number of planets.
Your comment got me to look up the number of objects considered planets over the years, this has ranged from 5-23. Data since 1543 is available here: https://dx.doi.org/10.1038%2Fscientificamerican0107-34
For fun I did a linear regression of year vs # planets and found that the while the slope was 1.8 planets/century, this was not significantly different from zero. The evidence appears to be consistent with a constant number of planets.
I froze when I saw 1, and ended up going the same way you did. That one feels cheap. :P
Yeah, that ended my run at 22 correct answers. Pretty annoying. I knew it was non-prime by definition, but I had no idea whether this quiz was aware of that, so I just made a quick gut decision.
I always get tripped up on multiples of 13. I wonder why that is.
There is no easy way to tell multiples of 13. 91 is particularly hard because it's a multiple of 7 and 13.
Obviously 5 * 13 is too easy. There's a test for division by 3, so 9 * 13 is too easy.
So basically you should only miss 91.
Obviously 5 * 13 is too easy. There's a test for division by 3, so 9 * 13 is too easy.
So basically you should only miss 91.
143 and 169 come to mind as well. Got 65 as highest score btw, was always a good calculator.
I've heard 91 called the "smallest non-obvious composite". Assume that testing for divisiblity by 2, 3, 5, and 11 is easy - for 2 and 5 you just look at the last digit, for 3 you take the sum of the digits, and with two-digit numbers a number is divisible by 11 if and only if both its digits are the same. Also assume that you can recognize squares. Then 91 = 7*13 is the first number that you won't recognize as composite using these test.
There is a rule for divisibility by 7 - take the last digit, double it, and subtract from the rest of the numbers. If that is divisible by 7, the original number is too. For example, 91 gives 9 - 2 * 1 = 7, so it is divisible by 7
Neat trick! Just used it to find out that this post id is divisible by 7.
Well, I feel better for going out on 91 now after only 5 numbers.
For me it's 17, 17*3= 51 which at a first quick glance looks like a prime, up until you add the digits and it's clear of course.
That's one where experience playing darts really helps. :-)
Where I'm from, 17 and 51 are two freeways that run kinda parallel to each other, so that was an easy one for me.
At school we did exercises to memorize from 1x1 up to 12x12, so even now I can remember all of them (and powers of two, of course :-))
Got 21
Funny fact, the number 100, in any base (>2 obviously) is not prime (updated)
In base 10, the number can only be prime if it ends in 1, 3, 7, 9 (where 10-1 = 9 and 10 - 3 = 7) - condition necessary but not sufficient of course
If all digits sum to a multiple of 3 it is divisible by 3, of course (because 10^X mod 3 is 1 for any integer X)
For 7 you want 3x the 2nd digit (21 - 2x3 + 1 = 7, divisible by 7) and 2x the 3rd digit (so 119 - 2x1 + 3x1 + 9 = 14)
Funny fact, the number 100, in any base (>2 obviously) is not prime (updated)
In base 10, the number can only be prime if it ends in 1, 3, 7, 9 (where 10-1 = 9 and 10 - 3 = 7) - condition necessary but not sufficient of course
If all digits sum to a multiple of 3 it is divisible by 3, of course (because 10^X mod 3 is 1 for any integer X)
For 7 you want 3x the 2nd digit (21 - 2x3 + 1 = 7, divisible by 7) and 2x the 3rd digit (so 119 - 2x1 + 3x1 + 9 = 14)
Au contraire, there are infinitely many bases in which "10" is prime.
However, "100" is an example of a digit string which is not prime in any base. Another is "1001" (it's always divisible by "11").
However, "100" is an example of a digit string which is not prime in any base. Another is "1001" (it's always divisible by "11").
More specifically "10" is a prime in all prime bases.
Oh you're right, I'm felling stupid now
Larger Lemma: every number ending in '0' (besides '10') is not prime in any base. (The primeness of '10' obviously depends on the primeness of the base.)
100 in base 2 is composite.
I'd strongly prefer a UX of "Prime" "Composite" buttons, not "yes" "no". And exclude 1; it's special (not-prime for good reasons, but also not composite; Prime vs. Non-Prime isn't as good a test. Plus, treatment of one is largely for definitional reasons and isn't intuitive to non-mathematicians.
Fun game, though!
Fun game, though!
You'd have to exclude 1 if you were to do "prime" vs "composite" since 1 is neither of those.
The following theorem, originally imparted to me by an algebra professor in the UCLA math department (grad school), may be helpful to you when testing yourself:
Theorem. All numbers < 100 that look prime, are prime EXCEPT 91.
(My addendum)
Where "look prime" means, is not a multiple of 2, 3, 5, 11, nor a perfect square. All these numbers have quick tests for divisibility.
Note that 91 = 7 * 13.
Theorem. All numbers < 100 that look prime, are prime EXCEPT 91.
(My addendum)
Where "look prime" means, is not a multiple of 2, 3, 5, 11, nor a perfect square. All these numbers have quick tests for divisibility.
Note that 91 = 7 * 13.
That's awesome. Came here to say that 91 keeps killing my gut-instincts!
There is a nice rule I heard once: "Below 100 (119 really), any number that looks like a prime is a prime. Except 49 and 91".
The remaining composite numbers are all trivially divisible by 2 or 5, or their digit sum is divisible by 3.
The remaining composite numbers are all trivially divisible by 2 or 5, or their digit sum is divisible by 3.
or by 11.
The not 49 and 91 rule combined with the rule that "a prime above 3 is always exactly 1 off being a multiple of 6" will get you flying through this test.
Or the Grothendieck prime, 57
https://en.wikipedia.org/wiki/57_(number)
https://en.wikipedia.org/wiki/57_(number)
Holy shit Grothendieck died in 2014, I NEVER MOURNED HIM. How did this happen?
I don't think 49 "looks like a prime", because it's clearly 7^2. But I hadn't realized that the other perfect squares are obvious non-primes for other reasons, ie. because of 2s, 3s, and 5s. Neat!
Interesting how after a few games, I just became terrible at this. I started out getting 13-16 right before screwing up, but after a while, I was messing up after two on numbers like 21 and 63. I think this game broke me.
After a few goes my best score is 2. Considering I just wrote a program yesterday to calculate primes this is pretty embarrassing.
I got 22 on my first try. The most helpful trick is to note that if the digits add up to a multiple of 3 it cannot be prime (because it is divisible be 3) with the exception of 3 itself.
Nice game. Reminds me of Infinite Certainty:
http://www.spaceandgames.com/?p=27
(now, granted there's a catch: question like 'is 89 prime' is harder than 'is 5 prime'; so it makes sense to have very high confidence of the latter (99.99% sounds reasonable) while much lower of the former)
p.s. Game over
117 = 32×13
You correctly sorted 20 numbers. Feel I did pretty well.
(now, granted there's a catch: question like 'is 89 prime' is harder than 'is 5 prime'; so it makes sense to have very high confidence of the latter (99.99% sounds reasonable) while much lower of the former)
p.s. Game over
117 = 32×13
You correctly sorted 20 numbers. Feel I did pretty well.
I got to 31 before I got tripped up on the exact same number. It looks prime!
Trick: add up digits, if they are divisible by 3 so is the number. In this case 117 yields 1+1+7 = 9, and sure enough so is 117. (117 / 3 == 39).
https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility...
https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility...
Yeah, I had been doing that with other numbers, but somehow didn't trigger for that one. Must have been the timing pressure.
Works on pretty much any browser:
var element=document.getElementById("n");element.addEventListener("DOMSubtreeModified",function(){function a(a){setTimeout(function(){var b=document.createEvent("Events");b.initEvent("click",!0,!1),document.getElementById(a).dispatchEvent(b)},1)}var b=parseInt(element.innerText);a("prime"===is_prime(b)?"yes":"no")});Any number whose digits sum up to a multiple of 3 (3,6,9) when summed until 1 digit remains; is a multiple of 3. Could this be something useful as a quick check for qualifying numbers?
I don't have any Assembly knowledge, but I presume that it wouldn't be efficient implementing this, because of having to cast to string, then back from string for each digit. Then the while loop to sum each digit.
Running the check only for odd numbers could also be an improvement.
I don't have any Assembly knowledge, but I presume that it wouldn't be efficient implementing this, because of having to cast to string, then back from string for each digit. Then the while loop to sum each digit.
Running the check only for odd numbers could also be an improvement.
You can check if a number is prime by going to the URL
http://isthisprime.com/nnnnn...
where nnnn is a number (like http://isthisprime.com/5867868) (note it does take some time with BIG numbers)
http://isthisprime.com/nnnnn...
where nnnn is a number (like http://isthisprime.com/5867868) (note it does take some time with BIG numbers)
There's a similar game on iOS — Infinite Primes.
https://itunes.apple.com/us/app/infinite-primes/id1063881848...
https://itunes.apple.com/us/app/infinite-primes/id1063881848...
If we're playing Stargate Atlantis rules then these numbers should be 3, 4, or 5 digits long.
Simple but effective - I like that it provides an explanation when you get one wrong.
I've been asking myself lately: What is the first prime number after googolplex?
If you have an advice or know the answer, please do tell :)
(This question appears to be very hard and it seems like nobody has the answer yet)
If you have an advice or know the answer, please do tell :)
(This question appears to be very hard and it seems like nobody has the answer yet)
Largest known primes are Mersenne primes with the biggest found (by distributed search) having 20 odd million digits:
http://www.mersenne.org/primes/?press=M74207281
It seems testing and searching googolplex-sized numbers would be far beyond wildly impractical.
http://www.mersenne.org/primes/?press=M74207281
It seems testing and searching googolplex-sized numbers would be far beyond wildly impractical.
Well, it is what it is (the first prime number after a googolplex). What would you prefer as a description of it? A listing of its digits? That would take rather a long time to read out. I can start you off, though. Its first few digits are 100000....
(It's easy enough to write a program that will eventually, slowly, find and stream to the display its digits or any other basic information about it you are interested in, of course. It's just infeasibly slow to use such a thing at the moment.)
The current largest "known" prime, for some sense of what it is to indicate a specific number and know it to be prime, has about 20 million digits (and a very specific convenient form). The prime you are looking for will have about a googol digits instead. So, we're far off, at the moment, from being able to figure out the sort of information about it you're presumably interested in.
(It's easy enough to write a program that will eventually, slowly, find and stream to the display its digits or any other basic information about it you are interested in, of course. It's just infeasibly slow to use such a thing at the moment.)
The current largest "known" prime, for some sense of what it is to indicate a specific number and know it to be prime, has about 20 million digits (and a very specific convenient form). The prime you are looking for will have about a googol digits instead. So, we're far off, at the moment, from being able to figure out the sort of information about it you're presumably interested in.
Well, we could represent it by googolplex + x. I believe x cannot be 1 for it to be prime due to number theoretical reasonings that I forgot in the meantime.
So, we're far off, at the moment, from being able to figure out the sort of information about it you're presumably interested in.
I'm not "presumably interested". I'm genuinely interested and curious about it. I'm just hesitant to invest a lot of time in it because of the unlikelihood of success.
So, we're far off, at the moment, from being able to figure out the sort of information about it you're presumably interested in.
I'm not "presumably interested". I'm genuinely interested and curious about it. I'm just hesitant to invest a lot of time in it because of the unlikelihood of success.
Just to clarify, when I said "the sort of information about it you're presumably interested in", I wasn't at all doubting your genuine interest and curiosity, but rather, whether I was correct in my assumptions as to the sort of information about the relevant number that said interest and curiosity would be directed towards.
Mostly, it's just a hedging phrase that I felt the need to write which carries no great meaning. (And, in some sense, this whole post is similar...)
Mostly, it's just a hedging phrase that I felt the need to write which carries no great meaning. (And, in some sense, this whole post is similar...)
[deleted]
Imagine primality testing was O(p) where p is the number of bits in the number you want to test. It is, in fact, way slower but let's give ourselves a huge advantage. Testing any googolplex-sized number would still be impossible. This seems to answer your question fairly simply and conclusively.
I agree with you, there is no way we could compute it with our computers. But there is still number theory with which you can analyze incomprehensibly large numbers and make statements about them. Maybe you could say that the next 10 numbers after googolplex are not prime. That would already be a first step towards an answer. You can't just categorically say it's impossible to find out. It is just that our understanding of mathematics is far from being able to answer this question. Anyway, it's more of a playful question I'm asking just for fun. Whether or not we find an answer is not of importance to me.
It's a perfectly fun and good question, I just don't think the answer is that hard. Short of a truly titanic mathematical breakthrough, it's not possible to find out. Beside this being one of the oldest, most worked class of problems in mathematics, the people doing these large and systematic searches are not ignorant of number theory:
https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_...
https://en.wikipedia.org/wiki/Repunit#Repunit_primes
While you can easily tell some numbers around googolplex are not prime (googolplex + 1 and googolplex + 2 are obviously not) this doesn't tell you anything useful about where the next prime might be. Testing a single such gigantic number for primality is infeasible and there aren't exactly a lot of prime numbers out there - on average, one every couple of googols as you can see from:
https://en.wikipedia.org/wiki/Prime_number_theorem
Even if you could test them very quickly, you'd be looking for quite a while.
https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_...
https://en.wikipedia.org/wiki/Repunit#Repunit_primes
While you can easily tell some numbers around googolplex are not prime (googolplex + 1 and googolplex + 2 are obviously not) this doesn't tell you anything useful about where the next prime might be. Testing a single such gigantic number for primality is infeasible and there aren't exactly a lot of prime numbers out there - on average, one every couple of googols as you can see from:
https://en.wikipedia.org/wiki/Prime_number_theorem
Even if you could test them very quickly, you'd be looking for quite a while.
The theoretical reasoning is not very complex, it's just an algebraic factorization, see:
https://en.wikipedia.org/wiki/Cunningham_project#Other_facto...
https://en.wikipedia.org/wiki/Cunningham_project#Other_facto...
You're probably not going to do this with googolplex sized numbers, though.
I did mine the hard way. No java script here.
https://www.youtube.com/watch?v=3ITOhyVemCU
https://www.youtube.com/watch?v=3ITOhyVemCU
This is extremely relevant: http://www.spaceandgames.com/?p=27
First go: I got 23 correct, one wrong. Fun game!
Game needs a control panel where you can customize it.
I'd like to be able to declare that 51 is prime for the purposes of play.
I'd like to be able to declare that 51 is prime for the purposes of play.
I'd love to see the statistics on which numbers get guessed right/wrong.
Fun game - it would be great to have an achievement if your score is a prime number too
Got 41. The ones over 100 took me quite a bit longer than the sub 100 numbers.
My top score so far is 35.
i memorized all the prime numbers up to 100 for the GRE
Got 15 right. Also get caught up on multiples of 13
29 right...yep
Nice game. 530 correct, first try
I'm not sure which of us is sillier – you, for lying about this, or me, for spending my time calling you out.
Or, hopefully, it was just a typo of 53. In which case I'd be impressed, since I haven't topped 25.
Or, hopefully, it was just a typo of 53. In which case I'd be impressed, since I haven't topped 25.
Dang, HN is so harsh. Yea just a joke; I couldn't get past 5. Fun game though.
There is a 60 sec timeout.
Save you all some time: http://primecoin.io/
EDIT: replaced my isPrime with the one already in the game.
EDIT 2: There appears to be some sort of increasing delay (pretty sure it's not just `is_prime` being slow) starting around 500 points. Maybe the game itself trying to compute primes?