10 ms·
Mathematicians find a new class of digitally delicate primes
- neallindsay 6y agoI love a good math article where "digital" means "base 10".
- bugzz 6y agoIt's a property referencing the digits - thus "digital". The results hold for all bases, not just base 10.
- patrec 6y agoDigit = finger. Most people have 10. It was a pun.
- gibolt 6y agoI have a 2 handed phone number
- drvdevd 6y agoI thought the joke was that digital = binary = 10 :)
- Blikkentrekker 6y agoToes are also digits. Whether the thumb and big toes are fingers is something that depends on definitions, but in the strictest sense they are excluded from fingers and toes, and thus humans generally have 20 digits, eight fingers, and eight toes by this definition.
- lupire 6y agoEvery base is base 10.
- RHSeeger 6y agoI laughed at that a lot more than I should have. After a long day, thank you for that.
- wahern 6y agoThe origin may be this comic: https://web.archive.org/web/20090125051251/http://cowbirdsinlove.com/43 https://web.archive.org/web/20090125051251/http://cowbirdsin...
- p1mrx 6y agoThe origin was probably thousands of years ago; it's a basic property of positional number systems.
- rizpanjwani 6y agonice detail on the alien having 4 digits.
- bckr 6y agoBut every base is not described in the base most commonly written for human reading as "base 10"
- gkop 6y agoSaving other non-math people like me a web search explaining this: https://blogs.scientificamerican.com/roots-of-unity/the-funniest-math-joke/ https://blogs.scientificamerican.com/roots-of-unity/the-funn...
- HoverSausage 6y agoI actually ran into this once not as a joke. I was using some software which had an option that would change the default base it used for all numbers. After typing <command> 16 and fiddling about in hexadecimal I tried switching back to decimal using <command> 10, yet I was still in hex mode. It took me a few more seconds than it should for me to realise what had happened.
- divbzero 6y agoYes, the word for base 10 is “decimal” [1] and digits do not have to be decimal digits. There are also binary digits “bits” [2], ternary digits “trits” [3], and so on. [1]: https://en.wikipedia.org/wiki/Decimal https://en.wikipedia.org/wiki/Decimal [2]: https://en.wikipedia.org/wiki/Bit https://en.wikipedia.org/wiki/Bit [3]: https://en.wikipedia.org/wiki/Ternary_numeral_system https://en.wikipedia.org/wiki/Ternary_numeral_system
- cobbzilla 6y agoHow does it hold in base 2? Wouldn’t changing the least significant digit always make any prime an even number?
- ABeeSea 6y agoPrimes are the same irrespective of base...
- enchiridion 6y agoIs this true for digitally delicate primes as well?
- aardvark179 6y agoDifferent primes will be delicate in different bases (you can trivially demonstrate this by considering a prime n in base n-1) but they exist in all bases.
- deleted 6y ago[deleted]
- DannyB2 6y agoA prime might be 'delicate' in base 10 but not be delicate in base 8. Another prime might NOT be delicate in base 10 but be delicate in base 8.
- ABeeSea 6y agoRight that’s explained in the article. I assumed OP only read the headline and assumed “digital” meant binary rather than an actual digit.
- SubiculumCode 6y agodigits we have, most 10.
- ram_rar 6y agoI am wondering, what kind of implications will it have on encryption. Would it be easier to break down prime factorization if they are composed of digitally delicate primes?
- jerf 6y agoI would expect it to be irrelevant. If being able to factor slightly different numbers was very helpful in factoring a particular number it would already be something we can do; generating known-factorable numbers from a prime is trivial.
- crumpled 6y agoI think the end of the article sums it up. >“The story of mathematical research is that you don’t know beforehand if you can solve a challenging problem or whether it will lead to something important,” Pomerance said. “You can’t decide in advance: Today I’m going to do something valuable. Though it’s great, of course, when things turn out that way.” In other words: 'Maybe someone, someday, will figure out if this matters. It'll be neat if it does'
- kzrdude 6y agoI'm surprised that "digitally delicate primes" are rare, why isn't this the majority of primes? That would be my intuition.
- dnautics 6y agoYou must be able to change any digit into any other digit.
- qsort 6y agoFor a prime to be delicate as per the definition given, all numbers with "levhensthein distance" 1 must be composite. This puts a lot of conditions on what the prime can be, for p = a_0 + a_1 b + a_2 b^2 + ... + a_n b^n, if p is delicate then (p - a_0), (p - a_0 + 1), ..., (p - a_0 + b - 1) must all be composite, and so must be (p - b a_1), ..., (p - b a_1 + b (b-1)), and so forth. This is equivalent to proving that certain slices of some arithmetic successions contain no primes. Not a professional mathematician and I didn't read the paper, but I suspect this is related to prime gaps works by Tao, who is cited in the article.
- breck 6y agoThis is a great explanation, thanks!
- Someone 6y agoNapkin math (possibly with gross errors, and doing stats, so making the math rigid cannot lead to rigorous proof): A prime with N digits has 9N ‘neighbors’. There are about 10^N/ln(10^N) - 10^(N-1)/ln(10^(N-1)) primes with N digits, so the probability of a N-digit number being prime is about 1/ln(10^N), of it not being prime 1-1/ln(10^N). So, the question is about the behavior of (1-1/ln(10^N))^9N as N ⇒ ∞. Google gives me a plot that’s essentially zero, so yes, most primes should be digitally delicate.
- kemiller 6y agoMissed opportunity to call them "digital delicacies".
- aritmo 6y agoNot much they "found" but rather they "declared" a new class.
- thewakalix 6y agoThat's a matter of philosophical disagreement (ferex, Platonism).
- lupire 6y agohttps://news.ycombinator.com/item?id=26667203 https://news.ycombinator.com/item?id=26667203
- thewakalix 6y agoA nonconstructive discovery is still a discovery.
- gweinberg 6y agoWhether math is discovered or invented is always open to debate.
- lupire 6y agoYou might have overlooked the first sentence of the article: > Despite finding no specific examples,
- f154hfds 6y agoWell you all heard the challenge. Who has got idle GPUs sitting around? Let's find the smallest base 10 widely digitally delicate prime! In all seriousness though, it's fascinating that we know this number exists but have no idea what it is. What a treasure hunt..
- mpoteat 6y agoI am unsure whether or not GPUs are good at work involving arbitrary precision numbers. My intuition was that they excelled at doing massively parallel operations for which accuracy is not a high concern. I would probably look into using some sort of large integer sieve if I were trying to search for an example. Thinking about it though, I am even unsure whether it is decidable that N is widely digitally delicate.
- ElderMillennial 6y agoWide integer multiplication works fine on a GPU: Your number is broken up into 32-bit coefficients to 2^32 as a compounding power (sum over a_i * 2^32i) -- and then you can do it as tensor(ish) operations, if you fiddle with carry/mod steps in between to keep the coefficients the right size and partial results properly aligned.
- rurp 6y agoThe fact that the existence of a type of number can be proven despite not finding a single example is very interesting and unintuitive to me as a non-mathematician.
- impendia 6y agoAn example described in the article, and which comes from the same branch of analytic number theory, is Daniel Shiu's result that you can find arbitrarily long strings of primes in "any" arithmetic progression. (By "any" I mean any arithmetic progression a (mod m) where a and m don't share any common prime factor.) So, for example, there is a string of a billion consecutive primes, each of whose decimal expansions ends in a billion ones. In principle you could use the method to find it, possibly the first example would be around 10^(10^10) or so. The gateway to all of this is the quantitative form of Dirichlet's theorem on prime numbers in arithmetic progressions: given coprime a and m, there are infinitely many primes which are a (mod m). (So, in other words, Shiu's result with "just one prime".) In this case, we know asymptotically how many such primes there are, and we can get upper bounds on the error. The proof is highly non-constructive, and uses complex analysis applied to the so-called "L-functions". Using a variety of trickery ("sieve methods", "the circle method", etc.) this can then be leveraged into other interesting results.
- Zenst 6y agoNow if somebody asks for a large prime number safe from bit errors I will know the answer.
- ghayes 6y agoWouldn’t that work best the other way that all transformations lead to other primes? Obviously impossible since changing the last digit to 0 will make any number composite.
- booleandilemma 6y agoWouldn’t it be more interesting to find a prime number where changing any single digit (maybe besides the least significant one) would still be a prime? Call it a sturdy prime.
- deleted 6y ago[deleted]
- qsort 6y agoNo such numbers except a small number of trivial cases exist. In odd bases, n % 2 === (sum of the digits of n), and in even bases, n % (b-1) === (sum of the digits of n).
- kosievdmerwe 6y agoIf we weaken the condition, to allow you to choose the replacement digit there are definitely semi-sturdy primes. For instance, 23 is semi-sturdy as you can replace 2 by 1 or 3 by 9 and both 13 and 29 are prime. The interesting question then becomes: how many?
- qsort 6y agoThis is most likely an open problem. If there existed infinitely many 'semi-sturdy' primes, this would imply that several prime 2-tuples match infinitely many primes, but results in that area are limited AFAIK.
- MaxBarraclough 6y ago> Here, his sweatshirt lists the first 20 digitally delicate primes. Isn't the first digitally delicate prime simply 2? Or are single-digit primes excluded? Or am I missing something terribly fundamental? edit Or is it that, because we can replace 2 by 3 and still get a prime, it doesn't count? Which is to say, replacing any digit in the number by any other digit, must always result in a non-prime?
- paul_f 6y agoYes, you can change the 2 to a 3 and it is still prime. So 2 is not digitally delicate
- MaxBarraclough 6y agoThanks. The article could have been more explicit on this point.
- SkyBelow 6y agoProving there is an infinite number of some subset of primes, for any sort of non trivial subset of primes, seems noteworthy at first. But considering the implications of there being infinite primes, there being a finite limit seems far more noteworthy. Is there any set of finite primes that isn't trivial? I'm considering trivial to be something like all primes less than 100 or all primes divisible by some prime p, which itself is just a much fancier generalization of the claim that 2 is a noteworthy prime for being the only even prime. I think this is the only set of non-trivial primes proven to be finite, and even then it is technically an infinite set of finites sets of primes. https://math.stackexchange.com/questions/2289089/has-any-nontrivial-subset-of-the-integer-primes-been-proven-to-be-finite https://math.stackexchange.com/questions/2289089/has-any-non...
- ReptileMan 6y agoOkay. So they put lots of zeroes in front of the primes. Then they start changing some of the zeroes and prove that it will eventually become composite. This feels like a very distant cousin to Messene prime to me. Could it be used for faster algorithm for finding primes?
- koolba 6y agoAre there digitally delicate twin primes? It would have to be a pair ending in 9 and 1 so that at least one more digit is different between them (though potentially more if it’s ...999).
- Cogito 6y agoThe way I understand this concept of a 'widely digitally delicate prime' is that you can take such a prime, prepend it with any sequence, and receive a prime in return. If that is the case, then finding such a number immediately trivialises the search for the 'largest known prime' - take the largest known prime, tack this number on the back of it, and you now have a new largest prime. I guess you'd get bonus points if somehow it's also Mersenne.
- stochastastic 6y agoI think it’s the other way around — tack this number on the back of anything and the result is composite.
- Cogito 6y agoAh of course and that makes far more sense. Adding this prime to the end of a number guarantees a composite. I wonder if that is a property the belongs to primes, or if there are non-trivial composite examples (any number ending in 2 has this property).
- bodhiandpysics1 6y agoYou can rephrase that conjecture to say... given any sequence of digits not ending in 2 (or 0), is there a prime number that ends in that sequence. That's an interesting conjecture!
- bodhiandphysics 6y agoAcchhh!!! Brain fart!!!
- Cogito 6y agoyes I like that phrasing. Similarly we can say there is a class of primes that have this property, what other classes of numbers also have this property?
- avz 6y ago
- quiescant_dodo 6y agoArticle 404s for me. Here's an archive link: https://web.archive.org/web/20210330142435/https://www.quantamagazine.org/mathematicians-find-a-new-class-of-digitally-delicate-primes-20210330/ https://web.archive.org/web/20210330142435/https://www.quant...
- jhoechtl 6y agoI am still hoping to find a message in the pattern of Ulams spiral, https://en.wikipedia.org/wiki/Ulam_spiral https://en.wikipedia.org/wiki/Ulam_spiral Take the variation seen in https://en.wikipedia.org/wiki/Ulam_spiral#/media/File:Sacks_spiral.svg https://en.wikipedia.org/wiki/Ulam_spiral#/media/File:Sacks_..., isn't there a Fibonacci spiral also contained?
- bjornsing 6y ago> Take a look at the numbers 294,001, 505,447 and 584,141. Notice anything special about them? You may recognize that they’re all prime... Call me stupid, but no, I don’t “recognize” that. :P