mersenneforum.org Primes and composites
 Register FAQ Search Today's Posts Mark Forums Read

 2005-06-28, 16:06 #1 mfgoode Bronze Medalist     Jan 2004 Mumbai,India 22·33·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
 2005-06-28, 16:45 #2 tom11784     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, ...
 2005-06-28, 18:16 #3 trilliwig     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.
2005-06-28, 23:29   #4
trilliwig

Oct 2004
tropical Massachusetts

6910 Posts

Quote:
 Originally Posted by trilliwig 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.
Actually, more accurately, it's equivalent to stating that n2 = 1 (mod 8) if n is not divisible by 2, and that n = +/- 1 (mod 3) (and therefore n2 = 1 mod 3) if n is not divisible by 3.

 2005-06-30, 23:37 #5 Orgasmic Troll 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?
2005-07-01, 00:52   #6
drew

Jun 2005

2×191 Posts

Quote:
 Originally Posted by TravisT 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?
Yes. Only test odd numbers.

Drew

2005-07-02, 08:25   #7
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

205210 Posts

Quote:
 Originally Posted by drew Yes. Only test odd numbers. Drew
Of these one can also eliminate those odd numbers ending in 5.
Mally

 2005-07-02, 16:57 #8 Ken_g6     Jan 2005 Caught in a sieve 2×197 Posts I believe what you're heading toward is known as "wheel factorization".
2005-07-03, 16:37   #9
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts
Primes and composites

:
Quote:
 Originally Posted by Ken_g6 I believe what you're heading toward is known as "wheel factorization".
Thanks Ken g 6 for the website. Very valuable information indeed. I was not aware of this
Mally

2005-07-03, 17:14   #10
R.D. Silverman

Nov 2003

1C4016 Posts

Quote:
 Originally Posted by mfgoode : Thanks Ken g 6 for the website. Very valuable information indeed. I was not aware of this Mally

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

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
And I listened when experts told me what books to read.

 2005-07-03, 17:45 #11 mfgoode Bronze Medalist     Jan 2004 Mumbai,India 205210 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Zeta-Flux Factoring 3 2020-03-09 08:55 CuriousKit PrimeNet 7 2015-10-15 19:25 gd_barnes Conjectures 'R Us 57 2011-09-12 12:31 ixfd64 PrimeNet 4 2011-02-21 11:51 Thomas11 Riesel Prime Search 32 2008-11-20 21:04

All times are UTC. The time now is 08:14.

Thu Oct 29 08:14:08 UTC 2020 up 49 days, 5:25, 1 user, load averages: 1.44, 1.47, 1.47

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.