The original post is probably prime. A prime factor can be up to the square root of a number. For this 1800 digit number, the square root is 900 digits. How can anyone know for sure that the number Elon posted is in fact prime?
For this post "potentially prime" means contains no prime factors smaller than 1 million. That is the limit of my patience. (About 6 minutes with my quickly cobbled together C++ program, compiled with -O3.)
If the 7 is shifted one character to the right, the prime factors are 29, 83, ...
If the 7 is shifted one character to the left, the prime factors are 1399, ...
If the 7 is shifted one character up, the prime factors are 231529, ...
If the 7 is shifted one character down, the prime factors are 12277, 47981 ...
If the 7 is changed to 1, the prime factors are 7, 11, 13, 2591, 24373 ...
If the 7 is changed to 2 it is potentially prime.
If the 7 is changed to 3, the prime factors are 3, 19, ...
If the 7 is changed to 4, the prime factors are 653, ...
If the 7 is changed to 5 it is potentially prime.
If the 7 is changed to 6, the prime factors are 3, ...
If the 7 is changed to 8, the prime factors are 7, 21701 ...
If the 7 is changed to 9, the prime factors are 3, 439 ...
TL;DR It's likely that the 7 needs to be where it is and it needs to be a 7.
It's hard to post code here but I think this works.
Nice to see someone using C++ to do stuff like this!
BTW, while looking into checking for Primes, I came across this concept of Primality Cetificate, which is apparently how you prove that a number is prime. Not sure if its possible to implement this or how hard it would be.
The Java BigInteger class has a method .isProbablePrime(int certainty) which claims to return true if a given number is likely prime up to the requested level of certainty.
I tested Elon's prime up to a certainty of 10,240, and it returned true.
This means that there is less than one chance in 10^3000 that the number is composite.
From the JavaDoc:
Returns true if this BigInteger is probably prime, false if it's definitely composite. If certainty is ≤ 0, true is returned.
Params:
certainty – a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - (1/2) ^ certainty). The execution time of this method is proportional to the value of this parameter.
Returns: true if this BigInteger is probably prime, false if it's definitely composite.
Here's the Java code (String taken from above C++ code. Thanks!)
package misc.primes;
import java.math.*;
public class XPrime { static final String xPrimeString = "111111111111111111111111111111111111111111111111111111111111" + //line 01 "111111111111111111111111111111111111111111111111111111111111" + //line 02 "111111111111111111111111111111111111111111111111111111111111" + //line 03 "111111111111111111111111111111111111111111111111111111111111" + //line 04 "111111111111111111111111111111111111111111111111111111111111" + //line 05 "111111111111111111111111111111111111111111111111111111111111" + //line 06 "111111111111188888888888111111111111111111888811111111111111" + //line 07 "111111111111118888888888881111111111111188888111111111111111" + //line 08 "111111111111111888811118888111111111118888811111111111111111" + //line 09 "111111111111111118888111888811111111188881111111111111117111" + //line 10 // originally ends 7111 "111111111111111111888811188888111118888811111111111111111111" + //line 11 "111111111111111111188888111888811888881111111111111111111111" + //line 12 "111111111111111111111888811188888888111111111111111111111111" + //line 13 "111111111111111111111188881118888811111111111111111111111111" + //line 14 "111111111111111111111118888811188881111111111111111111111111" + //line 15 "111111111111111111111111188881118888811111111111111111111111" + //line 16 "111111111111111111111111188888811188881111111111111111111111" + //line 17 "111111111111111111111118888888881118888111111111111111111111" + //line 18 "111111111111111111111888881118888111888881111111111111111111" + //line 19 "111111111111111111118888111111888881118888111111111111111111" + //line 20 "111111111111111111888881111111118888111888811111111111111111" + //line 21 "111111111111111188888111111111111888811118888111111111111111" + //line 22 "111111111111118888811111111111111188888888888811111111111111" + //line 23 "111111111111188881111111111111111111888888888881111111111111" + //line 24 "111111111111111111111111111111111111111111111111111111111111" + //line 25 "111111111111111111111111111111111111111111111111111111111111" + //line 26 "111111111111111111111111111111111111111111111111111111111111" + //line 27 "111111111111111111111111111111111111111111111111111111111111" + //line 28 "111111111111111111111111111111111111111111111111111111111111" + //line 29 "111111111111111111111111111111111111111111111111111111111111";
}
Thanks.
To be sure, we need to check all primes up to ~10^900. The number of factors to check is given by the prime counting function π(n), a lower bound of which can be estimated by calculating n/ln(n), where ln(x) is the natural log.
Doing this, you see the number of primes that need to be checked is on the order of 10^895. This is literally impossible in the age of the universe even with several supercomputers doing trillions of multiplies per second. So we are left with 2 options:
Elon lied and he has no idea if that number is prime or not. He just found a number that couldn't be easily detected.
Elon has access to an extremely advanced quantum computer that can run Shor's algorithm on a number that large.
I love that you did this. I was thinking of doing same, but I haven’t written code in years and don’t have an environment set up.
Elon: My super computer can beat up your super computer."
Can someone please direct me to the original Elon (graphical) post? I am having a tough time finding it......
https://twitter.com/elonmusk/status/1739490396009300015
Many Thanks! I really appreciate it! 👍
I had already done this in Python yesterday. It is a prime number.
I was also scratching my head on this, how can he generate that prime number while embedding an X logo as well as a "17" in a 60x30 matrix of numbers. I tried to generate an 1800 digit prime number, all I got was the first prime number containing 1800 digits that started with a "1", ending with "1953" and all "0"s in between, using below python script (as suggested by AI):
import sympy
prime_number = sympy.nextprime(10**1799)
print(f"A prime number with 1800 digits:\n{prime_number}")
It would require a lot of computing power to get what Elon obtained (he probably used Grok for this).