mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2005-06-28, 16:06   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Question 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
mfgoode is offline   Reply With Quote
Old 2005-06-28, 16:45   #2
tom11784
 
tom11784's Avatar
 
Aug 2003
Upstate NY, USA

2×163 Posts
Default

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, ...
tom11784 is offline   Reply With Quote
Old 2005-06-28, 18:16   #3
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3×23 Posts
Default

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.
trilliwig is offline   Reply With Quote
Old 2005-06-28, 23:29   #4
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

6910 Posts
Default

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.
trilliwig is offline   Reply With Quote
Old 2005-06-30, 23:37   #5
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

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?
Orgasmic Troll is offline   Reply With Quote
Old 2005-07-01, 00:52   #6
drew
 
drew's Avatar
 
Jun 2005

2×191 Posts
Default

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
drew is offline   Reply With Quote
Old 2005-07-02, 08:25   #7
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

205210 Posts
Cool

Quote:
Originally Posted by drew
Yes. Only test odd numbers.

Drew
Of these one can also eliminate those odd numbers ending in 5.
Mally
mfgoode is offline   Reply With Quote
Old 2005-07-02, 16:57   #8
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

2×197 Posts
Default

I believe what you're heading toward is known as "wheel factorization".
Ken_g6 is offline   Reply With Quote
Old 2005-07-03, 16:37   #9
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Default 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
mfgoode is offline   Reply With Quote
Old 2005-07-03, 17:14   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Thumbs down

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
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.
R.D. Silverman is offline   Reply With Quote
Old 2005-07-03, 17:45   #11
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

205210 Posts
Thumbs up 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
mfgoode is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Wieferich related composites Zeta-Flux Factoring 3 2020-03-09 08:55
Factorising Mersenne composites CuriousKit PrimeNet 7 2015-10-15 19:25
PRPs that are composites gd_barnes Conjectures 'R Us 57 2011-09-12 12:31
What's the point of factoring known composites? ixfd64 PrimeNet 4 2011-02-21 11:51
false composites with LLR 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.