Share good ideas and conversation.   Login, Join Us, or Take a Tour!
comment by wasoxygen
wasoxygen  ·  257 days ago  ·  link  ·    ·  parent  ·  post: The Strong Law of Small Numbers

am_Unition  ·  257 days ago  ·  link  ·  

Yes, I think my statement needs to be amended to say: known set of functions, mappings, transformations etc. that generates ALL prime numbers.

Edit: Actually I wasn't sure there exists even a single algorithm capable of producing only prime numbers as n -> infinity, even if the results for n below a "really large" were a subset of all primes. But Rowland (from wasoxygen's wiki article above) apparently managed to do exactly that.

Can you imagine being a reviewer for this article? It would be incredibly punishing to go through every problem and substitute increasing n until you saw whether or not it continued to meet the criteria after leaving the "small n" domain. In fact, a reviewer wouldn't do that, they'd write code to do it for them, even in 1988.

bfv  ·  257 days ago  ·  link  ·  

Generating all primes is just as easy as testing for primes:

    import math

def is_prime(n):

for m in range(2,int(math.sqrt(n))+1):

if n%m == 0:

return False

return True

def primes():

n = 2

while True:

if is_prime(n):

yield n

n += 1

for p in primes():

print p

it's just that we don't have useful ways to generate primes.

wasoxygen  ·  256 days ago  ·  link  ·  

And in 2019, I just entered the phrase "is 4294967297 prime" into a search engine. That level of effort might explain why I only got two out of three of the examples above correct (no better than chance!) before looking at the solutions.

But #1 stumped Fermat too! I didn't know that this problem sparked Euler's interest in number theory, according to "How Euler Did It" (4-page PDF). It was one of the many problems left over from the famous Fermat-Descartes correspondence.

    Fermat and Descartes did not like each other very much. In fact, some people describe their relationship as a “feud,” but it seems that Descartes resented Fermat more than Fermat disliked Descartes. They probably never met.

I figured Euler must have scribbled out a lot of long division problems to crack the Fermat number conjecture. But apparently he found a shortcut.


    Euler’s mentor in St. Petersburg, Christian Goldbach, alerted Euler to the conjecture in 1729. Euler responded almost immediately that he could make no progress on the problem, but by 1732, close to a hundred years after Fermat had originally made the conjecture, Euler had a solution: Fermat was wrong. In Euler’s first paper on number theory [E26] Euler announced that 641 divides 4,294,967,297.... What Euler did not tell us in E26 was how he thought to try to divide 4,294,967,297 by 641. He hadn’t simply been dividing by prime numbers until he got to 641. He had a much better way, but he waited about fifteen years, until E134, to reveal that secret.