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

  • #1
Kekkuli
9
2
I announce a playful competition :smile: 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.
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
 
  • Like
Likes DeBangis21
Technology news on Phys.org
  • #2
Bash:
#!/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? :smile:
 
  • Haha
  • Like
Likes phyzguy, Tom.G, DaveE and 2 others
  • #3
I found 18446744073709551557 before I overflowed 64 bits.
 
  • #4
Baluncore said:
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.
 
Last edited:
  • #5
FactChecker said:
... I was looking for the prime factors of 340282366920938461286658806734041124249!
Like all factorials, that must be composite.
 
  • #6
Baluncore said:
Like all factorials, that must be composite.
Sorry. Not a factorial. I should have ended it with a period.
 
  • #7
We must watch these things.
An exclamation needs to be a short and immediate reaction.

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) ?
 
  • #8
Baluncore said:
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?
 
  • Like
Likes Baluncore
  • #9
Baluncore said:
We must watch these things.
An exclamation needs to be a short and immediate reaction.

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) ?
It depends whether ##n## is prime. Otherwise, you could get a factor of 10, say, from 2 times 5.
 
  • Like
Likes Baluncore
  • #10
PeroK said:
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.
 
  • #11
Baluncore said:
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!
 
  • #12
PeroK said:
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 ?
 
  • #13
Baluncore said:
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.
 
  • #14
PeroK said:
Never, except the trivial case of 1
Or zero.
 
  • Like
Likes Baluncore
  • #15
Vanadium 50 said:
Or zero.
##0! =1##
 
  • Wow
Likes pinball1970
  • #16
PeroK said:
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
 
Last edited:
  • #17
PeroK said:
0! =1
Yes, and 0! is exactly as much of a perfect square as 1!, no?
 
  • Like
Likes Baluncore
  • #18
Kekkuli said:
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.
 
  • Like
  • Sad
Likes MatinSAR, Khi Choy Xichdu and Frabjous
  • #19
Vanadium 50 said:
Yes, and 0! is exactly as much of a perfect square as 1!, no?
They are the same perfect square.
 
  • #20
Why yes. Yes they are.
 
  • #21
phinds said:
... and someone is always going to have a bigger and faster computer.
With only one exception, the one with the biggest computer.
 
  • #22
Baluncore said:
With only one exception, the one with the biggest computer.
Until it isn't any more
 
  • Like
Likes Khi Choy Xichdu
  • #23
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
Python:
# 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/
 
  • #25
So wouldn’t 2^18446744073709551557 -1 also be prime?
 
  • #26
BWV said:
So wouldn’t 2^18446744073709551557 -1 also be prime?
Why do you think that?
 
  • #27
pbuk said:
Why do you think that?
Misremembering Mersenne primes, somehow thought 2^prime -1 was also prime
 
  • #28
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. :smile:
 
  • Like
Likes BWV
  • #29
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)

;)
 

Similar threads

  • Programming and Computer Science
2
Replies
36
Views
3K
  • Programming and Computer Science
Replies
34
Views
3K
  • Programming and Computer Science
Replies
7
Views
1K
  • Programming and Computer Science
Replies
13
Views
1K
  • Programming and Computer Science
Replies
16
Views
1K
  • Programming and Computer Science
Replies
1
Views
846
  • Programming and Computer Science
3
Replies
97
Views
7K
  • Programming and Computer Science
Replies
2
Views
2K
Replies
5
Views
998
  • Programming and Computer Science
Replies
10
Views
1K
Back
Top