Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Andrey Kulsha
    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.

      SEE ABOVE ABOUT SIEVE FOR 6N+-1 AND ABOUT USAGE OF
      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
      > > thread.
      > > >
      > > > 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.
      >

      I CAN HELP YOU WITH INVESTIGATIONS (SEE ABOVE), BUT AFTER
      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

      >
      > PLEASE ATTACK WHEN YOU ARE READY.
      >

      :-)

      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.