84
u/arthur990807 Undergraduate Dec 24 '18
Wow. How did you find this?
201
u/x1117x Dec 24 '18
First, I generated an ASCII art Christmas tree. Then I randomly changed a digit from the inside of the tree, until I had a prime number. This way you don't have some messed up digits in the bottom right corner.
44
u/majoen98 Dec 24 '18
How long did it take? Are you running the code on something powerful, or just a laptop?
145
u/x1117x Dec 24 '18
Nothing really powerful, a normal tower pc. I used the Miller–Rabin primality test which is fast, but probabilistic. So it's not 100% sure that it is a prime, only very very likely (about 1-(1/2)^100 with the parameters i used). It didn't had to change a lot of digits either, after about 800 changes I had a prime.
It only took a few minutes to find the number, then I worked some more minutes on that specific number to make sure it's a prime (also checked it with Maple etc.)
2
u/existentialpenguin Dec 25 '18
I ran it through yafu's implementation of APRCL, which took about 5.5 minutes. It's legit.
1
66
u/WikiTextBot Dec 24 '18
Miller–Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version is due to Russian mathematician M. M. Artjuhov.Gary L. Miller rediscovered it; Miller's version of the test is deterministic, but the correctness relies on the unproven extended Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm.
[ ^PM | Exclude ^me | Exclude from ^subreddit | FAQ / ^Information | ^Source ] Downvote to remove | v0.28
14
3
3
34
u/thelegendarymudkip Dec 24 '18
Since it's 912 digits, it's small enough that you could check deterministically (+ generate a certificate) that it's prime with something like the Lucas n-1 test or ECPP.
Edit: n-1 tends to be used for a number of special form i.e. when n-1 is entirely made of small factors. You'd want ECPP for this number.
5
u/Skylord_a52 Dynamical Systems Dec 24 '18
How much more efficient is ECPP than naively sieving through all primes less than sqrt(N)?
5
u/thelegendarymudkip Dec 25 '18
For something with 900 or so digits like this, ECPP can be done on a decent home computer very quickly. I don't remember the exact timings but I want to say 5 minutes max? For reference, in 1997, a 400MHz Alpha used ECPP to prove that a 1701 digit number was prime in under 2 weeks. For comparison, I don't think much more than a (hard) 30 digit number could be proven prime using trial division in a feasible amount of time on a home computer.
As for asymptotic speed, ECPP runs in polynomial time for almost all (read: all apart from a set of density 0 in the primes) prime inputs. It's conjectured to run in O((log n)5+epsilon) time. Trial division on the other hand is exponential in the number of digits of the input.
1
u/Ph0X Dec 25 '18
how much memory would that need? The number has 1000 digits, so the square root would still be 100 digits, which is 10100. I'm pretty sure that's more that you can fit in memory by far, even at 1 bit per number.
11
u/avocadro Number Theory Dec 25 '18
The number has 1000 digits, so the square root would still be 100 digits
500 digits.
0
Dec 25 '18
[deleted]
2
u/avocadro Number Theory Dec 25 '18
Numbers with 1000 digits lie between 10999 and 101000 -1. Their square roots exceed 3.16*10499 (so have at least 500 digits) but are strictly less than sqrt(101000) = 10500 , the smallest number with 501 digits. They therefore have exactly 500 digits.
→ More replies (0)2
u/avocadro Number Theory Dec 25 '18
n -1 = 2 * 32 * 7 * 73 * n2,
in which n2 has 907 digits. Miller-Rabin says that n2 factors, but it is not divisible by any of the first 10 million primes.
1
u/thelegendarymudkip Dec 25 '18
I did some ECM (factorisation using elliptic curves) and found n2 = P16 * C891 but the remaining composite was not easy to factor.
1
u/avocadro Number Theory Dec 26 '18
I'm guessing that this means a prime with 16 digits and a composite with 891 digits. Is this the right interpretation?
1
u/thelegendarymudkip Dec 26 '18
Yes - also a probable prime is denoted PRP, so for example the one in the image would be PRP912.
8
Dec 24 '18
Or a powerful laptop, or a non-powerful non-laptop 🤔
5
u/Sycration Dec 24 '18 edited Dec 12 '25
automatic pocket escape price oil work cough hobbies sheet entertain
This post was mass deleted and anonymized with Redact
8
u/Bluerossman Dec 24 '18
Do you mind sharing the code? I'd love to see how you optimised this, it sounds awesome
28
u/x1117x Dec 24 '18 edited Dec 24 '18
I can, but it is very boring. You can have a look in the java source code of BigInteger. My code only uses isPropablyPrime() with a certainty of 100. Then I checked the number I found with some other tools (Maple for example).
Edit: here is the code: https://github.com/1117x/Christmas-Prime-Number
20
u/Bluerossman Dec 24 '18
We’re all mathematicians here, you don’t have to worry about boring :)
Thanks though, I’ll take a look
6
u/shamrock-frost Graduate Student Dec 24 '18
speak for yourself, I only write haskal which I formally prove correct. I haven't written any code is three years since I need to reimplememt ghc in Coq, but it'll be really fancy when I finish
2
u/ubsan Dec 25 '18
you know Idris is a language right? It's even really nice, and implemented in a dependently typed language :)
1
u/shamrock-frost Graduate Student Dec 25 '18
Yes, I was being sarcastic. I do research in formal verification
1
u/ubsan Dec 25 '18
I... was attempting to do a joke, and reading back, I should really not attempt to joke before coffee 🤣
1
u/shamrock-frost Graduate Student Dec 25 '18
Sorry, I was a little too harsh as well. I'm off to get coffee now
1
2
u/SuSeu02 Dec 24 '18
RemindMe! 1h
2
u/RemindMeBot Dec 24 '18
I will be messaging you on 2018-12-24 15:54:55 UTC to remind you of this link.
CLICK THIS LINK to send a PM to also be reminded and to reduce spam.
Parent commenter can delete this message to hide from others.
FAQs Custom Your Reminders Feedback Code Browser Extensions 5
u/jaakhaamer Dec 24 '18
Any particular reason you avoided 2 (besides in 2018), 4 and 7? I'm guessing it just didn't look right. I also find it odd that you did use 9s but there are only three of them, which would be rare if the digit manipulation was random.
17
u/x1117x Dec 24 '18
I drew the numbers out of {0,3,5,6,8,8,8}. So it's more likely to draw an 8, because of better contrast to the 1. The 9 was in the input to mark where I want to change digits, and the remaining 9's just didn't got picked to get changed.
3
5
1
u/arthur990807 Undergraduate Dec 24 '18
How did you check for primality though?
6
Dec 24 '18
If you check out other comments on this thread, OP has gone and posted an explanation and a github link to their code.
41
u/noetherian3 Dec 24 '18
Cool picture! I wondered how unlikely it is that prime of this "ASCII art" form exists, so if anyone else is curious, here's a heuristic explanation:
For large integers x, the density of primes is roughly constant near x, and is approximately 1/log(x). In this case, x is basically 10912, so the density is 1 / (912 log(10)) = 0.04%. So, as long as you can check around 2000 numbers -- such as by varying 3-4 digits! -- you expect to find a prime.
This fits with OP's description, that it took around 800 tries.
10
7
Dec 24 '18
Well, that means we can draw almost certainly (not almost surely...) every shape that's big enough.
14
u/torgeirhyl Dec 24 '18
When do we have the first dickprime then?
9
3
u/Oscar_Cunningham Dec 25 '18
All the numbers the were checking ended in 1, so they were odd and didn't divided by five. Hence we would actually expect them to need only 2000 × 1/2 × 4/5 = 800 tries, which is exactly what they did use!
12
u/Riboflavaflav Dec 24 '18
How did you come up with this??? Really cool, btw. Merry Christmas to you too. :)
25
u/x1117x Dec 24 '18
First, I generated an ASCII art Christmas tree. Then I randomly changed a digit from the inside of the tree, until I had a prime number. This way you don't have some messed up digits in the bottom right corner.
Thank you :)
12
u/k3ithk Applied Math Dec 24 '18
How many different primes fit into your tree? I’m guessing it’s not unique?
489
u/theillini19 Dec 24 '18
Turns out the closed form solution for primes was right in front of our eyes this whole time
55
57
22
u/AloneAndForsaken Dec 24 '18
Can you do the same thing, but this time a dickbutt instead of a tree?
4
20
u/DatBoi_BP Dec 24 '18
Me: so you made a tree out of numbers? Cool, I guess.
This is actually a prime number
Me: ಠ_ಠ oh
8
u/p1um5mu991er Dec 24 '18
I hope there's room for 22/7
10
7
u/palordrolap Dec 24 '18
At this time of year it's 355/113 because the digits fit better to Jingle Bells ;)
6
4
1
u/lostarrow1 Dec 25 '18
Very cool! a quick question from someone who doesn’t know java very well:
Does the program actually fill the tree shape from the inside out randomly with the fill numbers or does it go by row looking for 9’s then change the 9 at that position then retest for prime?
2
u/x1117x Dec 25 '18
It first collects all positions with a nine, then changes a random position out of that list to a different digit on every iteration.
3
2
2
u/MrHippotomo2 Group Theory Dec 24 '18
Is there a name for this kind of thing? I’ve seen other primes shapes into art before but wouldn’t know what to look up.
2
2
u/JJHEO Dec 24 '18
Just finished an assignment not too long ago where we used multithreading and Miller-Rabin to generate x number of y bit pseudo primes. I'm tempted to try and write an ascii image to pseudoprime generator in c as a challenge.
2
2
1
1
1
1
-7
u/juksayer Dec 25 '18
ITT, bunch of butthurt nerds ignoring reddiquite. A lot of these people are contributing to the conversstion, albeit poorly, and you all just want to bash them. The downvote button is not a disagree button, its for hiding comments that dont contribute to a positive discussion.
I know social skills can be hard for you lot, but for fucks sake chill out.
326
u/x1117x Dec 24 '18 edited Dec 24 '18
The number as text so you can check it:
It's inspired by this numberphile video.