Mathematicians Hunting Prime Numbers Discover Infinite New Pattern

Re:Mathematicians Hunting Prime Numbers Discover Infinite Ne... by waltbosz on Saturday June 21, 2025 @01:18AM (#44334725)

Wouldn't it be fun if someone out there already knows a simple way to determine if a number is prime without factoring, but to them it is so obvious that they didn't even consider others may be interested.

[ Parent | on HN ]

Re:Mathematicians Hunting Prime Numbers Discover Infinite Ne... by kevinventullo on Saturday June 21, 2025 @02:51AM (#44335182)

As far as I know, the Lucas-Lehrer test used by GIMPS does not actually factor: https://en.m.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primali...

[ Parent | on HN ]

Re:Mathematicians Hunting Prime Numbers Discover Infinite Ne... by Someone on Saturday June 21, 2025 @03:24AM (#44335439)

That works for very few numbers. From that Wikipedia article: “In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers”

That’s fine for GIMPS, which only searches for Mersenne primes, but doesn’t work in general.

https://en.wikipedia.org/wiki/Primality_test#Fast_determinis... mentions several tests that do not require factorization, though.

[ Parent | on HN ]

Re:Mathematicians Hunting Prime Numbers Discover Infinite Ne... by vasvir on Saturday June 21, 2025 @02:04AM (#44334948)

Well I have a really elegant proof for this but I don't have enough space in the HN reply box to write it out -- but it is trivial, I am sure you will work it out.

   Fermat Reincarnation.

[ Parent | on HN ]

Re:Mathematicians Hunting Prime Numbers Discover Infinite Ne... by CRConrad on Sunday June 22, 2025 @12:35PM (#44348256)

   >   Fermat Reincarnation.

Pascal, I think.

[ Parent | on HN ]

Re:Mathematicians Hunting Prime Numbers Discover Infinite Ne... by throwaway81523 on Saturday June 21, 2025 @04:50AM (#44335857)

Pseudoprime test usually works, and AKS algorithm always works, both are much faster than factoring.

[ Parent | on HN ]

Re:Mathematicians Hunting Prime Numbers Discover Infinite Ne... by adgjlsfhk1 on Saturday June 21, 2025 @01:08PM (#44339069)

Since 2002 this has been known, and it's one of the least intuitive things in modern math. (versions with probability of 1-\epsilon have existed since Miller-Rabin in 1976)

[ Parent | on HN ]