Prime-generating fractions | Hacker News Reader

Prime-generating fractions

johndcook.com

86 pointslesterbuck8 comments

The way this is constructed is interesting, but it doesn't appear that a real sequence to generate primes is required, just a list of them:

D=0

SUM=0

for n:

  D += num_digits(PRIME[N]) // +1 for a nice single 0 between them

  SUM += PRIME[n]/(10^D)

  print fraction(SUM)

so, you could even skip the math and just append the string representations of the primes.

It seems the really difficult part is finding a good simple fraction to express the string. Perhaps that's the key here. maybe the primes summed in the sequences are a subset that produces a relatively simple fractional representation.

No. If you know some theorems about continued fractions, finding such rational numbers is easy. Just generate best rational approximations until you have one that is close enough.

See for example http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci... or http://www.math.sunysb.edu/~tony/whatsnew/column/irrational-...

This method results in much shorter numerators and denominators than the list of primes it generates. Simplifying this fraction only chops off 2 or so digits on average.

From the title I expected http://en.wikipedia.org/wiki/FRACTRAN (see the list of fractions at the top).

It borrows one problem from Project Euler and seems to scream for another.

Okay. Very interesting. For those who don't understand like me, what is the technical use of this? Where will this be used? Are we somehow going to use this in cryptography?

I don't think it does have a technical use. You certainly couldn't use this technique to generate new primes, since the fractions have been deliberately chosen based on the primes they will generate.

As it stands, it's just a fun mathematical curiosity.

Reply on news.ycombinator.com