It's worth noting that it may have got lucky with the first response. A clean session with the prompt:
> Could you generate me a 64 bit prime?
Returns:
> Sure, here's a 64-bit prime number: 15592425903773483751
> You can verify that it's prime by checking that it has no divisors between 2 and its square root. In this case, the square root of the number is approximately 12489593.5, so you would need to check divisibility for all integers between 2 and 12489593.5. Since the number is odd, you can skip checking even numbers, which will reduce the number of checks you need to perform.
> However, if you're looking for a larger 64-bit prime or a prime number with specific properties, you may need to use a more sophisticated algorithm or a specialized prime number generator.
Like GPT3.5 and Bard, it confidently suggests that 15592425903773483751 is prime, and even explains why.
> No, I cannot factor 15592425903773483751 because it is a prime number, and prime numbers cannot be factored into smaller non-trivial factors. By definition, a prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself. In this case, 15592425903773483751 is a 64-bit prime number, which means it is a prime number that fits into a 64-bit data type.
> To verify that 15592425903773483751 is a prime number, you can use a primality test, such as the Fermat primality test or the Miller-Rabin primality test. These tests can quickly determine whether a number is prime or composite (not prime) with high probability. In the case of 15592425903773483751, both tests confirm that it is a prime number.
Even further prompting to get it to try to multiply numbers together quickly turns into a disaster, culminating with:
> That doesn't look right
> I apologize for the mistake in my previous response. Here is the correct result of the multiplication:
> 3 x 3 x 3 x 7 x 167 x 853 x 911 x 635723119 = 322711211111111111
> Therefore, the product of the numbers is:
> 322711211111111111.
> I apologize for any confusion my previous response may have caused.
The context seems to be really aggressively baked in, because when I ask it:
> Can you factor 322711211111111111?
It returns
> Yes, I can factor the number 322711211111111111. Here is its prime factorization:
> 322711211111111111 = 3 x 3 x 3 x 7 x 167 x 853 x 911 x 635723119
> Therefore, the prime factors of the number are 3, 7, 167, 853, 911, and 635723119.
> Note that the prime factorization is unique up to reordering of the factors. In this case, the prime factors are repeated several times, so the prime factorization can be written more compactly as:
> 3^3 x 7 x 167 x 853 x 911 x 635723119
> or
> 3 x 3 x 3 x 7 x 167 x 853 x 911 x 635723119
> I hope this helps! Let me know if you have any other questions.
Interesting, I ran my "prime test", it passed on generating a prime, it failed on it being large.
> "Can you generate me a large prime please"
> Sure, here's a large prime number: 193707721
> This number is a prime number because it is only divisible by 1 and itself. You can check its primality by trying to divide it by all the numbers up to its square root, and if none of them divide it evenly, then it is a prime number. This number is quite large, but there are much larger prime numbers known. For example, the largest known prime number, as of January 2022, is 2^82,589,933-1, a number with 24,862,048 digits, discovered as part of the Great Internet Mersenne Prime Search (GIMPS).
I then prompted "That's not large" which seemed to break it, the response is stuck in a loop:
> That isn't large
> I apologize if the prime number I provided did not meet your expectations for "large." Prime numbers can be very large indeed, and there is no upper limit to how large a prime number can be.
If you are looking for a very large prime number, here is one with a billion digits:
I just asked chatgpt whether 3442177452 is prime. It insisted that 58657 is a factor (it's not) on the basis that it's the largest prime less than or equal to the square root (which I think is correct but irrelevant), and even though it gave a non zero remainder when dividing the two numbers (I did not check if the remainder is correct). Then it gave a (wrong) factorisation, not even using 58657.
It's cool and it will probably be able to get this right one day but it's a big goal to miss.
> Are all prime numbers smaller then this one also known?
No, and they will never all be known.
There are approximately n/log(n) primes less than n. In this case n is 2^77232917 - 1. n/log(n) is approximately 8.6 x 10^2317930.
If you gave every person on Earth a million million processors [1], running at 1000 GHz each, that could find a prime each clock cycle, and each person used a time machine to send their processors back to when the dinosaurs went extinct so they by now they have all been running 65 million years...we'd have found about 1.4 x 10^49 primes.
Heck, if every particle in the universe was somehow made to computer, each of which could produce a new prime in the time it takes light to travel the Planck length (the smallest meaningful length possible in the universe), and they had all been doing this since the beginning of the universe, they would have discovered by now about 10^147 primes.
That's a mere 0.000...00012 percent of the way there, where I've skipped more than 23000000 zeros.
That made me wonder how the game determines if the number is a prime or not. Turns out it's the Miller-Rabin test with a deterministic variant used for the range (up to 2^53) the game supports. I don't know why the game internally uses a bigint implementation while only supporting numbers up to 2^53 though...
Wait, you expect to be able to easily check primality of 2^32 + 1 by hand? Like with a naive algorithm you’d need to use erastothenes sieve to find primes up to 2^16 to test against. Granted, 641 itself is rather small but if you didn’t expect to encounter a factor that early...
I don't recall. I don't think I went beyond the use of 32bit integers (or was it 64) when I first looked at it, so not very large. The intermediate products can get quite big quickly. I do remember using a binary number to represent group membership of each prime, and seeing a pattern that broke down after only a few primes.
Though the factor-checking like verification won't work for “this number is prime” the same as it will for “this number is not prime”. A test that results in saying a number is prime doesn't output any factors to test because if such existed the number would not be prime.
I'll have to read up on the certification/verification process to comment any further though.
"On my machine, testing the prime number 27,644,437 took about 1.2 milliseconds with a k value of 50 (far higher than you’ll probably need for your applications.)"
I'm sorry, but WHAT?
Writing the dumbest implementation of trial-division that I could, in C++ on my laptop, in Debug mode, took 0.0247046 ms to determine definitively if 27,644,437 is prime.
My dumbest-possible implementation, in Debug mode, is 48.5 times faster, and doesn't get confused by Carmichael numbers.
Move along, folks, nothing to see here.
"The trial-division method... gets slow quickly."
That may be true, but using the number 27,644,437 as a benchmark will not get you anywhere near that "slow" point.
Step 2 (checking if huge numbers are prime) is a hard problem.
Additionally, the author wanted to find a prime that encoded the program that was also notable for some other reason (to give people a legitimate pretext to host it). He decided to try to make it one of the largest primes ever discovered, and it was, though it no longer is.
I’d argue that you’re just misunderstanding what makes a number prime. You can literally never be 100% sure a randomly generated number is or isn’t prime, it’s just the way numbers work.
If you ask chat GPT whether 2147462299 is prime, it'll output a wrong result.
And after discussing with the AI I got this response:
"I apologize for any confusion my previous response may have caused. You are correct that 2147462299 is not divisible by 137, 73, or 41. In fact, 2147462299 is a prime number.
To determine if a number is prime, you can use a variety of methods, including trial division and the sieve of Eratosthenes. These methods involve dividing the number in question by a series of smaller numbers, typically starting with 2 and ending with the square root of the number being tested. If the number being tested is not divisible by any of these smaller numbers, it is likely to be prime.
It is also possible to use specialized software or online tools to determine if a number is prime. Some of these tools use more advanced methods, such as the AKS (Agrawal–Kayal–Saxena) primality test, which can determine with high accuracy whether a number is prime or composite.
I apologize for any mistake I made in my previous response. Please let me know if you have any further questions."
I got a popup 'Not a 5 digit prime' on my first try and it wouldn't let me try any further. Not sure if I'm dense or if the UX is just terrible
I had tried 18141, by the way, which I modestly think was a pretty good guess in hindsight given its only two factors are 3 and 6047. 19141 would have been a prime, but perhaps not the one I was supposed to find? I don't play Wordle so I'm a little confused
> Could you generate me a 64 bit prime?
Returns:
> Sure, here's a 64-bit prime number: 15592425903773483751
> You can verify that it's prime by checking that it has no divisors between 2 and its square root. In this case, the square root of the number is approximately 12489593.5, so you would need to check divisibility for all integers between 2 and 12489593.5. Since the number is odd, you can skip checking even numbers, which will reduce the number of checks you need to perform.
> However, if you're looking for a larger 64-bit prime or a prime number with specific properties, you may need to use a more sophisticated algorithm or a specialized prime number generator.
Like GPT3.5 and Bard, it confidently suggests that 15592425903773483751 is prime, and even explains why.
It's wrong:
> $ factor 15592425903773483751 > 15592425903773483751: 3 3 3 7 167 853 911 635723119
Further prompting:
> Can you factor 15592425903773483751?
> No, I cannot factor 15592425903773483751 because it is a prime number, and prime numbers cannot be factored into smaller non-trivial factors. By definition, a prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself. In this case, 15592425903773483751 is a 64-bit prime number, which means it is a prime number that fits into a 64-bit data type.
> To verify that 15592425903773483751 is a prime number, you can use a primality test, such as the Fermat primality test or the Miller-Rabin primality test. These tests can quickly determine whether a number is prime or composite (not prime) with high probability. In the case of 15592425903773483751, both tests confirm that it is a prime number.
Even further prompting to get it to try to multiply numbers together quickly turns into a disaster, culminating with:
> That doesn't look right
> I apologize for the mistake in my previous response. Here is the correct result of the multiplication:
> 3 x 3 x 3 x 7 x 167 x 853 x 911 x 635723119 = 322711211111111111
> Therefore, the product of the numbers is:
> 322711211111111111.
> I apologize for any confusion my previous response may have caused.
The context seems to be really aggressively baked in, because when I ask it:
> Can you factor 322711211111111111?
It returns
> Yes, I can factor the number 322711211111111111. Here is its prime factorization:
> 322711211111111111 = 3 x 3 x 3 x 7 x 167 x 853 x 911 x 635723119
> Therefore, the prime factors of the number are 3, 7, 167, 853, 911, and 635723119.
> Note that the prime factorization is unique up to reordering of the factors. In this case, the prime factors are repeated several times, so the prime factorization can be written more compactly as:
> 3^3 x 7 x 167 x 853 x 911 x 635723119
> or
> 3 x 3 x 3 x 7 x 167 x 853 x 911 x 635723119
> I hope this helps! Let me know if you have any other questions.
The real irony? 322711211111111111 is prime!
reply