r/Python • • Jul 03 '19

Using Python to find a prime number that looks like the python logo (or any other image) from far away [OC]

Post image
1.7k Upvotes

85 comments sorted by

271

u/Gedanke Jul 03 '19 edited Jul 03 '19

How it's done:

We proceed in 5 steps:

  1. We resize the image to contain at most a certain amount of pixels.

  2. Run various image processing steps like edge enhancement and smoothing before converting the image into grey-scale (using Pillow)

  3. We then quantise the image into just having 5 to 10 greyness levels.

  4. Now we map each greyness level to a digit, et voila, we have embedded the picture into a number.

  5. 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.

30

u/Beheska Jul 03 '19

viola

voila*

"Voila" is French for "there it is". "Viola" is French for "raped".

18

u/Gedanke Jul 03 '19

Oh my! Thank you very much for pointing this out!

4

u/mprenditore Jul 03 '19

"Viola" is also "violet" (color and also the flower) in italian

4

u/[deleted] Jul 03 '19

"Viola" is French for "raped".

Someone's gotta let r/lingling40hrs know. They'd have a field day.

3

u/chmod--777 Jul 03 '19

So if I shove a French person into the back of my van I can say "Voilà, viola"?

6

u/nicocool84 Jul 04 '19

Actually, you should say "voilà, violé".

Viola would be "passé simple", more or less preterit, as in "He raped". ("Il viola.")

Did I mention I'm not a fun guy to hang out with?

1

u/mriguy Jul 04 '19

If the victim were female, wouldn’t that be “voila, violée”, since you are using the past participle, and that should agree with the object?

1

u/nicocool84 Jul 08 '19

Yes, you are right.

2

u/[deleted] Jul 04 '19

It's also the third person singular conjugation for rape in spanish.

As well as a lovely instrument.

5

u/[deleted] Jul 03 '19

Akshally the spelling in English is "Walla", as proven by comment sections on recipe websites.

1

u/jacksodus Jul 04 '19

Isn't that violé(e)?

1

u/Chroneis Jul 04 '19

yep, viola's the passé simple forme (~= preterit)

1

u/Beheska Jul 04 '19

"Viola" is the simple past (~preterit), "violé" is the past participle.

78

u/-_-STRANGER-_- Jul 03 '19

Awesome idea first of all, and then awesome implementation.

2

u/zaqal Jul 03 '19

Absolutely amazing. Great work.

3

u/Kengaro Jul 03 '19

So you basically assume something is a prime, verify, and tweak again until it is a prime?

12

u/Exodus111 Jul 03 '19

You have to with Prime numbers, they are np.

3

u/Kaligule Jul 03 '19

On the other hand we do have quite long lists of known primes. Have you checked if you could just use those instead?

7

u/Anaxamandrous Jul 03 '19

You're not replying to the OP with your question, so odds are the answer is no.

But even if OP did consider it, why make the program larger and less flexible that way? Testing a random number to see if it is likely prime (confidence > 10^100) can be done in a fraction of a second. Testing enough to find a likely prime, even in numbers thousands of digits long, can be done quickly enough not to test the user's patience.

2

u/[deleted] Jul 03 '19

But you can find a large enough gap that it will be time consuming, with a well structured known list the search will be way faster.

14

u/Anaxamandrous Jul 03 '19

These days elliptic curve cryptography is dominant, but 10 or 15 years ago, a great many https websites, including those where you had a secure login or transmitted your credit card information, use RSA to secure the connection.

RSA requires generation of at least 2 unique prime numbers, each hundreds of digits long, for every session. Your phone and / or computer has probably done it thousands of times while you browsed the internet -- even in 2019 though less frequently than in the past -- and you maybe never noticed. Those gaps are a theoretical risk but nothing more. You can search sequentially (all sequential odd numbers) for random numbers, but you do not have to.

Primes tend to occur less frequently the higher their value, true. But the odds of any given number, selected at random, being prime is about equal to 1/log n, n being the value of the number in question. So for numbers with 1000 digits, about 1 in 2302 of them will be prime. If you check 10,000 such numbers at random, you are down to a 1.3% chance of still not having found a prime. If you check 20,000 such numbers at random, you have a .016% chance of still not having found a prime. And by the time you have checked 45,000 such numbers, a task that should still be possible in a fraction of a second, you are down to odds of about 3 in a billion of still not having found a prime.

Even allowing you needed a prime 10,000 digits long, roughly 1 in 23025 of them is prime, and by the time you ran checks on 107,000 randomly selected odd numbers each 10,000 digits long, there would be less than 1% of your not having found a prime one. By making the candidate number have 10 times as many zeroes, you make the tests take longer, and you need about 10 times as many such tests to find a prime. A 10,000 digit prime could indeed take a second or two to find with high probability.

So in short, while there is always a theoretical possibility of searching forever without finding another prime, the reality is that modern processors can shrink that probability into "not going to happen even once in the remaining life of the universe" in less than a second for numbers the size OP's program seems to need.

2

u/worthsies Jul 03 '19

This is a great response. Thanks.

6

u/jjdmol Jul 03 '19

Primes aren't rare enough. For a 1000-pixel image, you need a 1000-digit prime. In that range, primes roughly occur once every ln(10^1000) = ~2303 numbers. That means a full list would very roughly have 10^1000 / 2303 entries. To compare, the number of atoms in the universe is ~10^80.

2

u/Mzsickness Jul 03 '19

You aren't just going to be able carry a list with you in your pocket forever you know?

0

u/Kengaro Jul 03 '19

I know ;)

0

u/[deleted] Jul 03 '19

[deleted]

150

u/Gedanke Jul 03 '19

It's the mathematical "we" :)
I worked on this project on my own

31

u/[deleted] Jul 03 '19

Wait, is it standard for papers to use the royal "we"?

24

u/Gedanke Jul 03 '19

It is not as much a royal "we" as it is either an actual plural or simply including the reader in the process.

I see it used fairly often in all sorts of papers and text books.

20

u/xain1112 Jul 03 '19

Don't forget about the only important reason to use it:

https://en.wikipedia.org/wiki/F._D._C._Willard

11

u/NAG3LT Jul 03 '19

I like to call it academic "we"

5

u/Jonno_FTW hisss Jul 04 '19

Ahh yes, me any my co-authors who never read a word of the paper.

79

u/Beheska Jul 03 '19

The royal "we" is simply using "we" instead of "I". In essays and exposes it basically means "me (the author), you (the reader), and anybody else who wants to try at home".

0

u/[deleted] Jul 03 '19

[deleted]

57

u/HowdySpaceCowboy Jul 03 '19

why we write like this

14

u/[deleted] Jul 03 '19

No Barry, we are the Flash

12

u/wintermute93 Jul 03 '19

It's standard for all of mathematics.

7

u/[deleted] Jul 03 '19

Yes. Typically you have multiple authors. Even if it’s just one you stick to we. Mostly it refers to the authors as a whole, but sometimes it means you and I, the reader. ‘We see that by doing X we arrive at Y’.

1

u/Switters410 Jul 04 '19 edited Mar 25 '26

This post's content no longer exists in its original form. It was anonymized and deleted using Redact, possibly for privacy, security, or data management purposes.

relieved nail consider aspiring flag lip pie voracious squeeze friendly

1

u/trueselfdao Jul 05 '19

Haha yes, I'm royalty. Now would someone point us towards the royal road to number theory?

1

u/mproud Jul 07 '19

You mean the collective “we”.

We are the Borg… resistance is futile.

1

u/[deleted] Jul 04 '19

Royal 'we'

1

u/[deleted] Jul 04 '19

1

u/scobot Jul 04 '19

Well, you didn't think I was driving, writing the algorithm AND talking to you, did you? Man?

0

u/[deleted] Jul 03 '19

[deleted]

9

u/Al2Me6 Jul 03 '19

Point is, the entire string IS a prime, it’s not about individual digits being prime.

4

u/the_blue_bottle Jul 03 '19

The whole number is prime, not the digit

1

u/SirDoctor007 Jul 03 '19

If I understand correctly the image is not composed of prime numbers but merely a single prime number...

2

u/Gedanke Jul 03 '19

That's correct!

6

u/peethon Jul 03 '19

Shit, sorry, I misunderstood. (>ლ)

2

u/Gedanke Jul 03 '19

no worries :)

6

u/peethon Jul 03 '19

No worries - minus 15 karma. LMFAO

¯_(ツ)_/¯

2

u/Sonny0217 Jul 03 '19

re-read the title

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:

  1. Your hardware

  2. whether you are using pypy etc.

  3. 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

u/blerp_2305 Jul 03 '19

I see. Tpp notch idea:) loved it

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

u/[deleted] 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

u/supercoupon Jul 03 '19

719

8

u/jiggs4 Jul 03 '19

It’s the new emergency services number

5

u/minepopper Jul 04 '19

719 is part of the picture too ;P

5

u/Beacon114 Jul 04 '19

/r/outoftheloop Why is that significant?

3

u/Gear5th Jul 04 '19

IDK, July 2019?

2

u/[deleted] Jul 04 '19

So the number is prime.

3

u/aequatio Jul 03 '19

Nerdy. Like it.

1

u/dethb0y Jul 03 '19

That's cunning, i like it!

1

u/Gnabbit Jul 03 '19

Is that an 80 character boundary?

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

u/Reeseallison Jul 03 '19

Possibly try by doing 'C:\\Path\\to\\image\\image.png'

1

u/_z-kani_ Jul 04 '19

Cool thats pretty cool i respect your work.

1

u/[deleted] Jul 04 '19

i just shit my pants. very strong mathematical implementation

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

u/cgw3737 Jul 04 '19

Ridiculous. Awesome.

1

u/BigglyBrick Jul 31 '19

Can confirm it does look like something

1

u/[deleted] Jul 31 '19

I'm so used to the logo, that my brain actually fills in the colours. This is so fucking cool.

1

u/TakeTheWheelMan Jul 03 '19

Man how do get such Gedanken?

0

u/[deleted] Jul 03 '19

[deleted]

5

u/PaleRulerGoingAlone7 Jul 03 '19

Right, and they used python to find that prime number

0

u/[deleted] 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

u/[deleted] Jul 03 '19

[deleted]

0

u/[deleted] 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