home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / c / 18760 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  1.6 KB
  1. Path: sparky!uunet!spool.mu.edu!sdd.hp.com!decwrl!bu.edu!news.tufts.edu!news.tufts.edu!rdorich
  2. From: rdorich@jade.tufts.edu (Rob)
  3. Newsgroups: comp.lang.c
  4. Subject: finding prime numebrs
  5. Message-ID: <RDORICH.92Dec21191037@jade.tufts.edu>
  6. Date: 22 Dec 92 00:21:59 GMT
  7. Sender: news@news.tufts.edu (USENET News System)
  8. Distribution: wold
  9. Organization: Tufts University - Medford, MA
  10. Lines: 37
  11.  
  12.  
  13.     Since some one else had something to prove in this newsgroup,
  14. I'm going to post this (do we have/need a group gen.nums.proves?).
  15. Ok, so here it goes:
  16.  
  17.     For any prime number, if we represent it in base 3, and then
  18. get the addition of all the digits, I claim that:
  19.  
  20.     1.-    If the sum is even, then it is not a prime.
  21.  
  22.     2.-     If it is odd:
  23.             It is either prime.    
  24.             or a multiple of another lower prime.
  25.  
  26. Ages ago (about 2 years) I made a little Pascal (ugh) program to do
  27. this,  and it basically goes from 1 to n creating and checking if the
  28. current number is prime, if it is, add it to a list.  Basically the
  29. program has the following runtime:
  30.  
  31.         n + num_primes_to(n)
  32.  
  33.         which is a O(n) as n -> oo (infinity).
  34.  
  35.     How do you guys like this? proves? counterexamples? anything
  36. would be most welcome.
  37.  
  38. Rob
  39.  
  40.  
  41.  
  42. --
  43. -------------------------------------------------------------------------------
  44. Roberto Dorich         |           /~~  \ /  ~~/~~ /~~/  /~~  /|  /    /~~
  45.              |    SKI   /--    X    /   /__/  /--  / |/ |   /--
  46. Electrical Engineering     |         /__    / \  /   /\    /__  /     |  /__
  47. rdorich@jade.tufts.edu     |  Tufts University, College of Engineering.
  48. -------------------------------------------------------------------------------
  49.