Python Who can find the largest prime number with their own programmed code?

[Kekkuli]

I announce a playful competition Who can find the largest prime number with the programmed code? I found the number 2249999999999999981 with the Python code. I first tabulated the truth value of the prime numerosity of numbers smaller than 1.5 billion using Erasthonene's sieve, and then I started to study numbers from 1.5*1.5 billion downwards.
[CODE lang="python" title="Big Prime number"]import math

maxind = 1500000000 # let's calculate prime numbers smaller than 1.5 billion
primesarray = [True] * (maxind + 1)
amount = maxind
number = 0
ind = 0
squareroot = 0.0
candinate = 0
helper = 0def is_prime_number(num):
if num % 2 == 0:
return False
else:
index = 3
itis = True
while index <= math.isqrt(num) and itis:
if primesarray[index]:
if num % index == 0:
itis = False
print(index)
index += 2
return itisamount = maxind
squareroot = math.isqrt(amount)
for ind in range(2, maxind + 1):
primesarray[ind] = True # let's suppose all are primes
primesarray[1] = False
number = 2
ind = number

while ind <= amount:
primesarray[ind] = False # remove 2's multiplies
ind += 2

while number < squareroot:
while primesarray[number] is False and number < squareroot:
number += 1 # let's find next prime number
ind = number + number
while ind < amount: # remove its multiplies
primesarray[ind] = False
ind += number
number += 1

primesarray[2] = True
# Prime numbers smaller than a billion have now been tabulated.
# Let's print a hundred smaller ones as a test.
for ind in range(1, 101):
if primesarray[ind]:
print(ind)

# let's examine candidate number
helper = 1
while helper < 20:
candinate = maxind * maxind - helper
if is_prime_number(candinate):
print(candinate, ' is a prime number.')
else:
print(candinate, ' is not a prime number.')
helper += 2
[/CODE]

 

[jack action]

#!/bin/bash
wget -q -O - 'https://html.duckduckgo.com/html?q=the%20largest%20known%20prime%20number' | sed 's|<[^>]*>||g' | sed 's|\s+| |g' | grep -P 'the largest known prime number is [^a-z]+' | sed -E 's|.+(the largest known prime number is [^a-zA-Z]+).+|\1|'

Result: the largest known prime number is 2^ (82,589,933) - 1.

What do I win?

 

[Baluncore]

I found 18446744073709551557 before I overflowed 64 bits.

 

[FactChecker]

I found 18446744073709551557 before I overflowed 64 bits.

Thanks! That is just what I needed when I was looking for the prime factors of 340282366920938461286658806734041124249! . ;-)
CORRECTION: The '!' was meant to be an exclamation mark, not a factorial.

 

[Baluncore]

... I was looking for the prime factors of 340282366920938461286658806734041124249!

Like all factorials, that must be composite.

 

[FactChecker]

Like all factorials, that must be composite.

Sorry. Not a factorial. I should have ended it with a period.

 

[Baluncore]

We must watch these things.
An exclamation needs to be a short and immediate reaction.

Assuming a number is a square, s = n².
The factor n will occur exactly twice in s.
But how many times will the factor n occur in s! (yes, the actual factorial) ?

 

[Hill]

Assuming a number is a square, s = n2.
The factor n will occur exactly twice in s.
But how many times will the factor n occur in s! (yes, the actual factorial) ?

$n+1$ times?

 

[PeroK]

We must watch these things.
An exclamation needs to be a short and immediate reaction.

Assuming a number is a square, s = n².
The factor n will occur exactly twice in s.
But how many times will the factor n occur in s! (yes, the actual factorial) ?

It depends whether $n$ is prime. Otherwise, you could get a factor of 10, say, from 2 times 5.

 

[Baluncore]

It depends whether n is prime. Otherwise, you could get a factor of 10, say, from 2 times 5.

So the count would increase.
Does it get any easier if you reduce s! to its prime factors ?
If n was prime, there would be n+1 occurrences.
If n was composite, there would be zero occurrences.

 

[PeroK]

If n was prime, there would be n+1 occurrences.
If n was composite, there would be zero occurrences.

If $n$ is composite, it gets complicated!

 

[Baluncore]

If n is composite, it gets complicated!

What is the factorial of complicated ?

Another related mental exercise.
Under what conditions can a factorial also be a perfect square ?

 

[PeroK]

Under what conditions can a factorial also be a perfect square ?

Never, except the trivial case of 1. This is because you would need even powers of every prime factor, but you always have an odd power of the last prime in the factorial.

 

[Vanadium 50]

Never, except the trivial case of 1

Or zero.

 

[PeroK]

Or zero.

$0! =1$

 

[PeroK]

Never, except the trivial case of 1. This is because you would need even powers of every prime factor, but you always have an odd power of the last prime in the factorial.

A full proof based on this observation requires Bertrand's postulate:

https://en.m.wikipedia.org/wiki/Bertrand's_postulate

 

[Vanadium 50]

0! =1

Yes, and 0! is exactly as much of a perfect square as 1!, no?

 

[phinds]

Who can find the largest prime number with the programmed code?

My reaction is, who cares? It's going to depend on how powerful a computer you can run it on, as much as the algorithm (as @Baluncore showed in post #3) and someone is always going to have a bigger and faster computer.

 

[PeroK]

Yes, and 0! is exactly as much of a perfect square as 1!, no?

They are the same perfect square.

 

[Vanadium 50]

Why yes. Yes they are.

 

[Baluncore]

... and someone is always going to have a bigger and faster computer.

With only one exception, the one with the biggest computer.

 

[phinds]

With only one exception, the one with the biggest computer.

Until it isn't any more

 

[willem2]

The best known way to find large primes is the lucas-lehmer test for mersenne primes (primes of the form 2^p-1 where p is a prime).
This is actually quite simple to do

# returns True if  2**p -1 is a mersenne prime, false otherwise
# assumes p is prime

def is_mersenneprime(p): 
    if p==2:
        return True
    mp = 2**p -1
    m = 4
    for _ in range(p-2):
        m = (m*m-2) % mp

    return (m==0)

python has unlimited integers and I believe uses Karatsuba multiplication, so this should run in O(p^3.58)
running this for p<1000 <1 second
running this for p<10000 14 minutes
running this for p<10^8 10^9 years.
you should really install mpz at this point, to use FFT multiplication and O(p^3) time

Of course the GIMPS project has been at this since 1996 with ~10^5 cpu cores, so it's rather hard to get ahead of this.
https://www.mersenne.org/

 

[johsteffens]

Here is my algo (written in 2020): https://github.com/johsteffens/qprimes
It computes primes up to 2^64-1. The largest being 18446744073709551557 (as already mentioned by @Baluncore).

 

[BWV]

So wouldn’t 2^18446744073709551557 -1 also be prime?

 

[pbuk]

So wouldn’t 2^18446744073709551557 -1 also be prime?

Why do you think that?

 

[BWV]

Why do you think that?

Misremembering Mersenne primes, somehow thought 2^prime -1 was also prime

 

[johsteffens]

With Mersenne primes 2^p-1, p is indeed always prime, but the opposite does not necessarily hold true. Large Mersenne primes occur rather sparsely, the biggest tested so far is 2^82589933 - 1. So, some way to go until we know.

 

[BWV]

Still waiting on my code to finish running, but sure its going to be a winner

for i=82,589,933:1,000,000,000
X(i)=[(2^i)-1*isprime(2^i)-1]
end
max(X)

;)