20050628, 16:06  #1 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
Primes and composites
I came across the following formula from a book on pocket calculators by L. Rade and B. Kaufman. It can be shown that the formula f(n)= sqr. root (1+24n) where n is a natural number yields every prime number with the exception of 2 and 3. It also yields many other numbers besides. If a suitable sieve could be found to separate the composites could it in any way help in the search for primes? Mally 
20050628, 16:45  #2 
Aug 2003
Upstate NY, USA
2×163 Posts 
I don't know how helpful it would be since it cannot be used to determine if a number is prime, just if it is composite.
Such a test suggests squaring the number, and if it is not congruent to 1 mod 24 then it is composite. However, that doesn't eliminate composites such as 25, 35, 49, ... 
20050628, 18:16  #3 
Oct 2004
tropical Massachusetts
3×23 Posts 
This is simply another way of stating that all prime numbers other than 2 or 3 must be +/1 mod 4 and +/1 mod 6. So it eliminates precisely those numbers that are multiples of 2 or 3.

20050628, 23:29  #4  
Oct 2004
tropical Massachusetts
69_{10} Posts 
Quote:


20050630, 23:37  #5 
Cranksta Rap Ayatollah
Jul 2003
641 Posts 
f(n) = 2n+1 produces all primes except 2 for all natural numbers n, is there anyway we can use this fact to help sieve for primes?

20050701, 00:52  #6  
Jun 2005
2×191 Posts 
Quote:
Drew 

20050702, 08:25  #7  
Bronze Medalist
Jan 2004
Mumbai,India
2052_{10} Posts 
Quote:
Mally 

20050702, 16:57  #8 
Jan 2005
Caught in a sieve
2×197 Posts 
I believe what you're heading toward is known as "wheel factorization".

20050703, 16:37  #9  
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
Primes and composites
:
Quote:
Mally 

20050703, 17:14  #10  
Nov 2003
1C40_{16} Posts 
Quote:
Perhaps someday you and others may take my advice and actually *study* this subject. Learning about trial division, its variants, and its optimizations are among the first things one encounters in this subject. However, it does require doing some READING. I never understood the penchant that posters in this discussion group have for rhetoric, without having a basic knowledge of the subject they are trying to discuss. When I first became fascinated with this subject, I grabbed every number theory book (and Knuth's TAOCP) and *read*. And read some more..... And I listened when experts told me what books to read. 

20050703, 17:45  #11 
Bronze Medalist
Jan 2004
Mumbai,India
2052_{10} Posts 
Primes and composites
I agree with you 100%. Its only since I joined a year ago that I realised how important Number theory is.
Yes I do have a penchant for words but I always insist that circumlocution is to be avoided at all costs in my posts. I have taken your advice from previous posts on studying a subject thoroughly and getting to the bottom of things, not superficially, or studying for the sake of passing an exam. Well I have passed that stage long ago. Currently I am studying an excellent book, elementary but thorough, viz; 'Number Theory and its history' by Oystein Ore a book that was played down by the Number theorists here for more advanced books like ones by Zucker and Niven and Hardy and Wright, or Tom Apostol. I have ordered 'Solved and unsolved problems in Number theory' by D. Shanks and looking forward to receiving it soon. There is also a similar one by Guy but it was too expensive and in HB. As a starter ORE is excellent for beginners and recommended by Mathworld I have another 4 books on Number theory and hope to master them one by one. It will take me some time to come up to books like those by C. Pomerance but every journey ,even if its a long one, starts off with the first step. Thank you Bob for your interest. Mally 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Wieferich related composites  ZetaFlux  Factoring  3  20200309 08:55 
Factorising Mersenne composites  CuriousKit  PrimeNet  7  20151015 19:25 
PRPs that are composites  gd_barnes  Conjectures 'R Us  57  20110912 12:31 
What's the point of factoring known composites?  ixfd64  PrimeNet  4  20110221 11:51 
false composites with LLR  Thomas11  Riesel Prime Search  32  20081120 21:04 