r/Python • u/Gedanke • Jul 03 '19
Using Python to find a prime number that looks like the python logo (or any other image) from far away [OC]
10
u/blerp_2305 Jul 03 '19
How long does it take to render and what sort of primality test do you do?
26
u/Gedanke Jul 03 '19
Rendering time heavily depends on multiple factors here:
Your hardware
whether you are using pypy etc.
you can just be unlucky and hit a very large prime gap
But on my crappy laptop, generating a 5000 digit prime took on average about 20min.
The above python logo took less than 5 :)
4
1
u/o11c Jul 04 '19
you can just be unlucky and hit a very large prime gap
Jumping at random instead of adjacently should fix this.
0
Jul 04 '19
[deleted]
3
u/o11c Jul 04 '19
The average is the same either way. The distribution is what's different, and it becomes extremely unlikely that you'll keep missing your expected case.
Though you can further constrain it to ±1 mod p# for some primorial and simply check a lot fewer numbers to start with.
67
u/erogone775 Jul 03 '19
Never have I seen something so useless and so cool at the same time. Great job!
25
5
u/minepopper Jul 04 '19
719 is part of the picture too ;P
5
3
1
1
1
u/bluzer33 Jul 03 '19
Im completely new to programming and I cannot make it work, every time I paste the image path where it says "Path to image", I get "No such file or directory './prime.png'
1
u/trennersoup Jul 03 '19
Is it in the same directory as the script?
2
u/bluzer33 Jul 03 '19
Yeah, I tried with 'C:/.../image.png' and only using 'image.png' while on the same folder, and it didnt work
5
1
1
1
u/422_no_process Jul 04 '19 edited Jul 04 '19
Impressive. Superb and awesome. I should try this or part of the problem at home. Very interesting problem too.
1
u/hellfiniter Jul 04 '19
I really like projects like this and me myself did plenty of those...but after a while i always ask myself...why did i do that? xD
1
1
1
Jul 31 '19
I'm so used to the logo, that my brain actually fills in the colours. This is so fucking cool.
1
0
Jul 03 '19
[deleted]
5
u/PaleRulerGoingAlone7 Jul 03 '19
Right, and they used python to find that prime number
0
Jul 03 '19
[deleted]
3
u/BACEXXXXXX Jul 03 '19
Except, if I'm not mistaken, that's what OP is saying. It is a single prime number. Although, I haven't checked it to confirm.
0
Jul 03 '19
[deleted]
0
Jul 03 '19
[deleted]
3
u/PaleRulerGoingAlone7 Jul 03 '19
Right, that's the hard part. OP starts with an image, and gets a number. This is almost certainly not prime. From there, individual digits are varied until OP hits a prime. Luckily, the density of primes is large enough that this is usually possible without changing the image too much.
If you look at the numbers in the lower right corner, they're chosen precisely to make the whole number prime, and don't match the pattern around them
271
u/Gedanke Jul 03 '19 edited Jul 03 '19
How it's done:
We proceed in 5 steps:
We resize the image to contain at most a certain amount of pixels.
Run various image processing steps like edge enhancement and smoothing before converting the image into grey-scale (using Pillow)
We then quantise the image into just having 5 to 10 greyness levels.
Now we map each greyness level to a digit, et voila, we have embedded the picture into a number.
It now remains to tweak some of the digits until we find a prime number that still looks like the image.
Note: According to the prime number theorem, the density of prime numbers is asymptotically of order 1/log(n). Hence, if we have a number with m digits, the number of primality tests that we expect to do until we hit a prime number is roughly proportional to m. Since we use the Baillie–PSW primality test, the overall expected computational complexity of our prime searching procedure is O(nlog(n)³).
You can find the code @ Github and experiment yourself.