1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Neat little thing (prime numbers finder)

  1. Jun 1, 2014 #1
    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).
     
  2. jcsd
  3. Jun 1, 2014 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

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

    with the numerator ##p## a prime. Or does it only work for subsequent fractions? Or what is it exactly?
     
  4. Jun 1, 2014 #3
    It does produce a lot of prime numbers, but it does not always produce a prime.

    Javascript:
    Code (Text):

    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.
     
    Last edited: Jun 1, 2014
  5. Jun 1, 2014 #4

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    1, 4, 9: 49 is non-prime (7x7)
     
  6. Jun 2, 2014 #5
    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?
     
  7. Jun 2, 2014 #6

    Borek

    User Avatar

    Staff: Mentor

    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.
     
  8. Jun 2, 2014 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I ran the following code on Scheme:

    Code (Text):

    #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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Neat little thing (prime numbers finder)
  1. Neat Number Trick (Replies: 3)

  2. Prime numbers (Replies: 12)

  3. Prime numbers (Replies: 8)

Loading...