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

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  ·  7 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.

[SPOILER]

    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.