Neat little thing (prime numbers finder)

[shadowboy13]

So i was messing around with egyptian fractions and i eventually decided to try adding them together and then reducing the one single fraction that formed into its lowest terms.

Anyway i set them up with having 1 in the numerator ALWAYS (or else it won't work) and proceeded to add them up.

Surprisingly enough after adding them up and reducing them to their lowest terms i would always get 2 interesting things, the LCM of the various numbers in the denominator and a prime number in the numerator.

Note: This has only worked when i had 3 different fractions (again with 1 as the numerator), when i had 2 or 4 this method failed.

Anyways try it out, maybe someone with more expertise may know something (i'm just a kid

(Try out say 1/2 + 1/3 +1/4 and and see for yourself).

 

[micromass]

Sorry but could you be more specific, what exactly is it that you claim?

Is it that if you add three Egyptian fractions then you get the result? Any three? Like

\frac{1}{m}+\frac{1}{n} + \frac{1}{k} = \frac{p}{\text{LCM}(m,n,k)}

with the numerator $p$ a prime. Or does it only work for subsequent fractions? Or what is it exactly?

 

[Nick O]

It does produce a lot of prime numbers, but it does not always produce a prime.

Javascript:

var i, j, k, num, den, red;

var gcd = function(a,b) {
    return b ? gcd(b,a%b) : a;
};

for(i = 1; i < 8; i++) {
    for(j = i+1; j < 9; j++) {
        for(k = j + 1; k < 10; k++) {
            num = i*j + i*k + j*k;
            den = i*j*k;
            red = num/gcd(num,den);
            console.log(i + ', ' + j + ', ' + k + ': ' + red);
        }
    }
}

Results:

(denominator 1, denominator 2, denominator 3, reduced numerator)

1, 2, 3: 11
1, 2, 4: 7
1, 2, 5: 17
1, 2, 6: 5
1, 2, 7: 23
1, 2, 8: 13
1, 2, 9: 29
1, 3, 4: 19
1, 3, 5: 23
1, 3, 6: 3
1, 3, 7: 31
1, 3, 8: 35
1, 3, 9: 13
1, 4, 5: 29
1, 4, 6: 17
1, 4, 7: 39
1, 4, 8: 11
1, 4, 9: 49 /* Bolded after Matterwave pointed this one out */
1, 5, 6: 41
1, 5, 7: 47
1, 5, 8: 53
1, 5, 9: 59
1, 6, 7: 55
1, 6, 8: 31
1, 6, 9: 23
1, 7, 8: 71
1, 7, 9: 79
1, 8, 9: 89
2, 3, 4: 13
2, 3, 5: 31
2, 3, 6: 1
2, 3, 7: 41
2, 3, 8: 23
2, 3, 9: 17

... and so on. Bolded results are nonprime results that immediately appear to me. Others are probably nonprime but I feel too lazy right now to check them.

The prevalence of primes is interesting. My gut tells me that it probably decreases considerably as the denominators get larger, though.

 

[Matterwave]

1, 4, 9: 49 is non-prime (7x7)

 

[shadowboy13]

I just posted this because it is interesting given the percentage of primes vs non primes that you can get.

Maybe there's something to this?

 

[Borek]

Isn't it that the numerator is guaranteed to be not divisible by any prime factors of m, n, k,? That would typically remove small primes leaving only a product of larger ones, for small integers it can give an impression that numerator is often a prime number.

 

[micromass]

I ran the following code on Scheme:

#lang racket
(require math)

(define (fraction n)
  (define Counter 0)
  (define NotPrimeCounter 0)
  (define mx 0)
  (define (iter a b c)
    (set! Counter (+ Counter 1))
    (define x (* (lcm a b c) (+ (/ 1 a) (/ 1 b) (/ 1 c))))
    (cond [(> x mx) (set! mx x)])
    (cond [(not (prime? x)) 
          ; (fprintf (current-output-port) "~a ~a ~a ~a \n" a b c x)
           (set! NotPrimeCounter (+ NotPrimeCounter 1))])
    (cond [(> c 1) (iter a b (- c 1))]
          [(> b 1) (iter a (- b 1) (- b 1))]
          [(> a 1) (iter (- a 1) (- a 1) (- a 1))]))
  (iter n n n)
  (fprintf (current-output-port) "~a ~a ~a" Counter NotPrimeCounter mx))

(fraction 400)

This calculates all the numerators of $\frac{1}{a} +\frac{1}{b} + \frac{1}{c}$ for $1\leq a,b,c\leq 400$.

The result was that we obtained $10,746,800$ number. Of these, we had $7,637,688$ not prime. So less than $30\%$ of the numbers are nonprime. The largest number we obtained by was $476,803$.

To compare, let us choose at random $10,746,800$ numbers between $1$ and $476,803$, and let us contain how many primes to expect.

The number of primes between $1$ and $476,800$ is by the prime number theorem http://en.wikipedia.org/wiki/Prime_number_theorem about $\frac{476803}{\text{log}(476803)}$ (logarithm always basis $e$). This is about $36,000$. So if we select a random number below $476,803$, then the probability of this number being prime is $\frac{36000}{476803} \sim 0.07$.

Now, if we select $10,746,800$ numbers at random between $1$ and $476,803$, then we would expect about $7\%$ primes. So we expect to have about $750,000$ primes. We have now obtained over $2,500,000$ primes, which is about $25\%$. So we do have a lot of primes compared to my back-of-the-envelope calculation. This could be because my calculation selected numbers at random between $1$ and $476,803$. But in my program, it is clear that not all of these numbers are as likely. Or it could be that it does yield disproportionally many primes.