## Re: Bill Krys' sieve: Q&A&Q&A

Expand Messages
• HI BILL AND OTHER LIST MEMBERS! ... WE CAN USE ERATOSTHEN S SIEVE FOR *ANY* FRAGMENT IF WE HAVE A LIST OF PRIMES NOT LESS THAN SQRT(N), WHERE N IS THE LARGEST
Message 1 of 1 , Dec 30, 2000
HI BILL AND OTHER LIST MEMBERS!

> Andrey,
>
>
> --- Andrey Kulsha <Andrey_601@...> wrote:
> > Hello Bill!
> >
> > > Audrey,
> >
> > Well, I'm not offended :-)
> >
> > > the sieve as it stands cannot avoid division,
> > unless i
> > > figure out something else.
> >
> > I think it will be Eratosthen's sieve :-)
>
> IT WON'T BE THAT KIND OF SIEVE BECAUSE THAT SIEVE MUST
> START AT ONE AND CONTINUOUSLY REFERENCE ONE, BUT MINE
> CAN START ANYWHERE.

WE CAN USE ERATOSTHEN'S SIEVE FOR *ANY* FRAGMENT IF WE HAVE
A LIST OF PRIMES NOT LESS THAN SQRT(N), WHERE N IS THE
LARGEST NUMBER IN FRAGMENT! IT'S OBVIOUS!

> ALSO I PLAN ON HAVING AN ALGORITHM
> THAT DOESN'T REQUIRE DIVISIONS TO SIMPLIFY THE
> SIEVING. AFTER THAT I PLAN TO HAVE A REVERSE ALGORITHM
> TO FIND THE PRIMES DIRECTLY.

ALL YOU CAN FIND - JUST A KNOWN SIEVE FOR NUMBERS OF KIND
6N+-1 (YOUR STRANDS 7 AND 5):

IF N IS NOT A NUMBER OF KIND 6KM+-(K+M), THEN 6N+1 IS PRIME;
IF N IS NOT A NUMBER OF KIND 6KM+-(K-M), THEN 6N-1 IS PRIME.

SO WE CAN SIEVE ALL COMPOSITES OF SUCH TYPE BY SORTING OUT K
AND M (K>=M>0).

> >
> > > So the sieve can be started anywhere on the
> > fragment,
> > > but I thought the square of a prime would be as
> > good a
> > > place as any.
> > >
> > > Some definitions:
> > >
> > > N# = a number to be factored
> > > R# = the rank of a number to be factored
> > > F# = the factor of a composite
> > > ArmA = the left half of the fragment
> > > ArmB = the right half of a fragment
> >
> > Well, if M is a center of the fragment, then
> > R=|N-M|.
>
> YES, THAT'S RIGHT.
> >
> > > For example, on the frag 2^6 to 2^7, we start at
> > 121
> > > on Arm B. Its factors are F11 and F11. its rank is
> > > R25. look for all ranks that occupies a gcd=1
> > position
> >
> > All N of a kind 6k+-1, and only them, occupies a
> > gcd=1
> > position. Hence, theirs (and only theirs) ranks have
> > this
> > form too.
>
> TRUE.
> >
> > > on arm A and which, when added to R25, will be
> > > divisible by F11.
> >
> > Let this rank will be Rx, and number of this rank
> > will be
> > Nx=M-Rx.
> > M+R25 is divisible by 11. R25+Rx must be divisible
> > by R11.
>
> IT MUST BE DIVISIBLE BY F11, NOT R11.

WELL, IT WAS A MISPRINT, BUT F11=R11=11, SO IT'S TRUE.

>
> > Hence, (M+R25)-(R25+Rx)=Nx will be too.
>
> RIGHT.
> >
> > > That rank is R19 and the number is N77.
> >
> > All that you are doing there, - a trial sieving the
> > numbers
> > 6k+-1 divisible by 11 from the ArmA. There are
> > around M/33
> > such numbers, so if you take M, for example, 3*2^50,
> > you
> > will have more than 10^14 such numbers!
>
> RIGHT. I BOO-BOO'ED HERE. I WILL ENDEAVOR TO HAVE THE
> SIEVE SIEVE FOR COMPOSITES DIRECTLY WITHOUT SIEVING
> FOR RANKS, AND EVENTUALLY, AS I'VE MENTIONED ABOVE, NO
> SIEVING. BUT EVEN AS IT STANDS, WE DON'T NEED TO
> REFERENCE "1" ALL THE TIME AND CAN SIEVE ANY FRAGMENT
> NEEDED, UNLIKE ERATOSTHENE'S SIEVE.

ERATOSTHEN'S SIEVE.

> >
> > > N77/F11=F7, so
> > > now look for a rank on arm B where gcd=1 which,
> > when
> > > added to R19 is divisible by F7 or F11.
> >
> > And now you have sieved:
> >
> > a) all the numbers 6k+-1 divisible by 11 from the
> > ArmB (and
> > now you have sieved them from both fragments);
> >
> > b) all the numbers 6k+-1 divisible by 7 from the
> > ArmB (at
> > the next step you will sieve such numbers from
> > another
> > fragment too).
> >
> > > There are none for F11 so stop this thread. But
> > there
> > > is one for F7. N119 at R23: (N119/F7=F17). So look
> > for
> > > a number on arm A that occupies gcd=1, whose rank
> > when
> > > added to R23 is divisible by F17 or F7.
> > >
> > > There are 2 new numbers: N85 at R11,
> > (R23+R11)/F17=2
> > > and N91 at R5 (R23+R5/F7=4). N91 has no number or
> > rank
> > > that fits the criteria on arm B, so stop this
> > >
> > > N85/F17=5, so continue as above. There are 2
> > numbers
> > > on arm B derived from N85: N115 and N125 at ranks
> > R19
> > > and R29 respectively.
> > >
> > > There are no ranks on arm B that when added to R29
> > = a
> > > number divisible by 25, so stop this thread. The
> > other
> > > number, 115 when divided by 5=23. Look for a
> > number on
> > > arm B at gcd=1 whose rank when added to 19 is
> > > divisible by 5. 65 and 95 fulfil this criteria at
> > > ranks 31 and 1 respectively. 95's rank (rank=1)
> > has no
> > > number whose rank will fit the criteria, so stop
> > this
> > > thread. Continue with 65. There should be no
> > > composites left at gcd's=1.
> >
> > Well, now you have sieved all the numbers 6k+-1
> > divisible by
> > 11,7 and 5 from both fragments. Hence, all left
> > numbers
> > 6k+-1 must be prime.
> >
> > But Eratosthen's sieve is much faster, because:
> >
> > a) generating a list of primes less or equal to
> > sqrt(N) is
> > much faster than irregular receiving them when
> > dividing
> > ranks (lots of them appears for large N, about
> > 3*2^50);
>
> TRUE, BUT EVEN IF I SIEVE IN AN ERATOSTHENIAN WAY, I
> CAN SIEVE WITHOUT REFERENCING "1" AND THEREFORE CAN
> SIEVE OTHER FRAGMENTS.

SEE ABOVE...

> >
> > b) we can work with any fragments, not with two
> > given;
>
> NO, YOU MUST ALWAYS START AT 1 AND SIEVE UP TO THE
> DESIRED POINT.

SEE ABOVE... :-)

> >
> > c) there are no squares or any another powers of
> > primes in
> > Eratosthen's sieve.
>
> THE SQUARES OR POWERS IS JUST A STARTING POINT BECAUSE
> THEY ARE EASY TO FIND.
> >
> > > I am working on finding a pattern to the factors
> > > without relying on division. Some interesting
> > teasers
> > > appear, but I need more numbers to look at.
> >
> > I've just showed you a method.
> >
>
> ARE YOU REFERRING TO ERATOSTHENE'S? BECAUSE I DON'T
> SEE ANY OTHER METHOD YOU'VE SHOWN.

YOU'VE GUESSED!

>
> > > Could you
> > > generate, in an excel-readable file, fragments
> > that
> > > include the gcd's and the greatest factor (not the
> > > gcd), for those numbers that are at gcd=1, but are
> > > composite.
> >
> > There will be 1/3 of all composites, namely of form
> > 6k+-1,
> > i.e. non-divisible by 2 or 3.
>
> BUT ANDREY, THE COMPOSITES NOT DIVISIBLE BY 2 OR 3
> ALSO SHOW A SYMMETRY. I REALLY THINK THIS IS YOUR AND
> OTHER CRITICS' MAIN AREA OF CONFUSION. I AM TRYING TO
> FIND A PATTERN FOR THIS SYMMETRY WITHOUT SIEVING FOR
> THEM AND THERE ARE PATTERNS, I JUST NEED TO SEE MORE
> NUMBERS.

WELL, I THINK YOU WILL NOT FIND ANY SYMMETRY WHEN YOU SEE
MORE NUMBERS. IF YOU REALLY WANT, I CAN DO SOME CALCULATINGS
FOR YOU (I LIKE TO WRITE PROGRAMS), JUST PARTICULARLY SHOW
ME WHAT YOU NEED.

> >
> > > I've included the excel files for reference.
> >
> > I'm surprized that you missed that your "symmetry"
> > exists
> > only for divisibility by 2 and 3. All of exceptions
> > from
> > your symmetry are divisible by prime greater than 3,
> > and you
> > are "restoring" this symmetry by trial sieving of
> > these
> > numbers.
>
> KIND OF RIGHT. THE FACT THAT THERE IS SYMMETRY OF
> THESE OTHER COMPOSITES IS A PATTERN WORTHY OF
> INVESTIGATION, NOT DEBUNKING BEFORE IT'S UNDERSTOOD
> WHAT YOU'RE DEBUNKING.
>

THAT YOU WILL SEE THAT IS WAS NOT WORTHY.

> > > Reimann
> >
> > Well, I'm not offended on "Audrey", but please don't
> > distort
> > a surname of great scientist!
>
> WHAT DOES THIS MEAN? I COULD GO ON AND ON ABOUT
> UNQUESTIONED AUTHORITY IS DANGEROUS, ETC, ETC. I'M NOT
> CLAIMING TO BE IN HIS LEAGUE OR ATTEMPTING TO BELITTLE
> HIM OR HIS LEGACY.

WELL, JACK TOLD YOU WHAT'S THE MATTER. I WROTE YOU THE SAME
YET EARLIER...

> >
> > > will wait.
> >
> > I think he never will wait. :-)
> >
> I DON'T KNOW WHAT THIS MEANS. BUT ALL I UNDERSTAND
> ABOUT REIMANN IS THAT THERE IS A LINE WHICH ON EITHER
> SIDE HAS AN EQUAL NUMBER OF PRIMES. IF THIS
> UNDERSTANDING IS WRONG THEN I'M SORRY. HOWEVER, IF
> EACH FRAGMENT CAN BE SHOWN TO HAVE AN EQUAL NUMBER OF
> PRIMES AND POWERS OF PRIMES (PERHAPS ONLY SQUARES OF
> PRIMES), THAT GOES A LONG WAY TO PROVING PRIMES ALONE
> ARE BALANCED IF YOU SHOW POWERS OF PRIMES ARE
> BALANCED.

SEE http:\\www.utm.edu\research\primes\notes\rh.html

>
>

:-)

I THINK IT'S NOT ATTACK, BUT AN INTERESTING DISPUTE.

SOME WEEKS AGO I'VE ALSO FOUND SOME CONJECTURES, ABOUT
MU-FUNCTION. I'VE REALLY BOTHERED TO DAVID BROADHURST WITH
THEM!

BUT YOU HAVE NOT BOTHERED TO ME, I LIKE TO HELP PEOPLE TO
GET RID OF WASTE WORK.

> BILL

WBW, ANDREY

P.S. "WBW" means "With Best Wishes"
Your message has been successfully submitted and would be delivered to recipients shortly.