Are Legendre symbols proven to be defective?

[cheesehead]

Originally Posted by jasong

My friend has told me(approximate quote),"A lot of the stuff that people accept as fact is not true,

Yup.

A common reason is simple, nondelusional ignorance.

Another common reason is imperfect memory or the imperfections of our human languages.

Example: In a recent post elsewhere in mersenneforum.org I objected to someone's use of "decimate" to mean removing one-tenth of (whatever), because I sincerely thought then that I recalled that "decimate" meant removing nine-tenths of (whatever), or dividing (whatever) by ten.

Once I actually consulted a dictionary, I discovered that I had been mistaken for several years.

I'm pretty sure I correctly knew what "decimate" meant at some time in the past. Perhaps I became confused because of one of the other meanings of "decimate". Webster's Third New International has "2 a : to take a tenth from". But later in the entry is "3 : to destroy a considerable part of : reduce to the point of almost complete extermination" -- a meaning more in line with the idea of removing 90% rather than just 10%, to me at least.

so-and-so(note: I'm not telling who or what was mentioned, but it isn't George :) ) intentionally stacked the deck so that they would find the first 10-million digit prime.

Then there are accidental misunderstandings.

Some prime searches, in order to try to be first to find a 10-million-digit prime, have proceeded nonsequentially, or at least non-exhaustively, through candidates, skipping certain ranges in order to work up to the 10-million-digit region more quickly than if they had worked on every possible sub-10-million-digit candidate first.

There's nothing immoral, unethical, or illegal about that tactic, to me (and many other folks), as long as they carefully document which ranges have been covered and which haven't (which is more a matter of professionalism than ethics or morality).

But I can imagine that some people might have a different opinion as to the morality or ethicality of skipping ranges. Perhaps your friend is one of those, or perhaps has read/heard only a biased description of that tactic given by someone else in that category or else by someone who, for some reason, wants to portray that tactic as "stacking the deck".

(The latter would be more of a deliberately-induced misunderstanding.)

Because of this, a lot of primes on the top-5000 list are actually composite.

As has already been pointed out, a simple way to prove that claim would be to produce some examples of top-5000 listings that are actually composite.

Asking your friend to do that, or asking your friend to ask whoever he got his information from to do that, might clarify the matter.

Perhaps your friend does not understand the distinction between probabilistic primality tests and deterministic ones.

From the way he said it(as I said, it's an approximate quote), it sounds like people have discovered what he discovered in the past(further than you would believe) and it is being suppressed.

Sounds sort of like an urban legend. See "Urban Legends Reference Pages" at http://www.snopes.com/, not for this particular claim, but to see similar patterns in other claims, mathematical or not.

I don't think my friend is a liar, but there are only two possibilities left, delusional and genius.

No, you've overlooked additional mundane possibilities such as I've just outlined. (OTOH, you know your friend better than I do!)

[jasong]

Originally Posted by Jay

If you're attempting to triple check the factors I found, you may want to use the correct factors. I said

2^3355584+1: 769*274177*961934081

Okay, scratch the statement I made before this post. All I can say is, WTF?

I attempted division by 789 and got a whole number result. If that isn't a factor, that what the hell happened?

[Jay]

Dividing by a non-factor will result in a non-zero remainder. Dividing by 789 will give you a remainder of 656. Which proves that 789 is not a factor (divisor) of 2^3355584+1. However dividing by 769 does give a remainder of zero, which proves that it is a factor (divisor).

[PaulJobling]

Originally Posted by paulunderwood

It is a bug only if you not specify "include even k":

Base = 2
Include even k's ? (y) : n
n = 3355583
kmin = 2
kmax = 2
Type : k.b^n+1
The output file newout already exists - continue? (y) : y
Are you ready to start sieving ? (y) : y
CPU capabilities: CMOV: Supported. SSE2: Supported.
Using bitmap : allocating 0.0Kb of RAM...
...succeeded
0 candidates
Sieving numbers with 1010132 decimal digits
Initialising sieve...
Done.
02:26:06 Starting sieve (reduced screen output while p < 1 billion)
Stopping...o 33554467 (33.5 million)
02:26:10 Saving results to newout...
02:26:10 ...done.
Output file 'newout' generated, contains 0 k's

Paul ought to iron this out

I have emailed him

An interesting bug! I'll take a look - at least it will mean that the very latest version will get out there.

[R.D. Silverman]

Originally Posted by jasong

You didn't quote what I said, and I have a bad memory, so I'll have to come back to this later if it starts looking important.

You have failed to answer my question: What do YOU mean by "effective".

Originally Posted by jasong

My friend claimed

Who is this "friend"? When/where did he/she get his math degree?

Originally Posted by jasong

Again, you didn't quote me, but my friend claims that NewPGen spits out the number 2^3355584+1 as having a factor of 2, which is clearly impossible.

And you can't imagine that a piece of compute code might have a bug?
Or that the INPUTS might be wrong??? And once again you quote this
soi-dissant "friend". The peculiarities of a piece of code do not define
the underlying mathematics. Or is this too hard for you to understand.

Originally Posted by jasong

I suggest you consult a life coach on personal etiquette. This has gone beyond sniping in your case, and I'm not simply talking about our encounters.

Others have made the some comments that I have. I notice that you do
not comment on *their* ettiquette. Or is your blaming the *messenger*
a way of avoiding the technical issues? It would seem so.

Jason, I hold you in such utter contempt that it would be hard to find
the proper words to describe it.

[davieddy]

Originally Posted by R.D. Silverman

Jason, I hold you in such utter contempt that it would be hard to find
the proper words to describe it.

Come on folks its my 58th birthday today.
I would hesitate to compare Jason's mathematical
prowess with Mally's (what is 0/0?) but surely even
our late lamented Mumbai resident would have blushed at this "comment".

David

[PaulJobling]

"My friend claimed that Legendre symbols weren't a proven method of determining whether a number was a likely candidate to sieved by a p-value."

They certainly are. I believe what jasong is talking about is the practise - used for fixed k sieves - of not bothering to check to see if a prime p divides any members of the set if it does not pass a number-theoretical test based on the legedre symbol. This is really useful for things like Seventeen or Bust where there are several different k's; it means that you can not bother doing any work at all with some values of p, or you can reduce the amount of work that you have to do.

This is the basics of the technique:

Consider a fixed k sieve, k.2^n+1, with n from n_min to n_max.

We have the next prime, p.

If p divides k.2n+1, then
k.2^n = -1 (mod p), therefore

-k.2^n = 1 (mod p)

For even values of n, this means that -k must be a square mod p.
For odd values of n, this means that -2k must be a square mod p.
So if legendre (-k, p) <>1 and legendre (-2k, p) <> 1, there is no need to test with this value of p.

[mdettweiler]

I think if you check the box for "Verify results" in NewPGen, it will check to see if the factor really divides the candidate, right? And there's a similar option in srsieve, too. Shouldn't that eliminate the bad factors that jasong is worrying about?

[Richard Cameron]

Originally Posted by davieddy

Come on folks its my 58th birthday today.

Happy Birthday.

I note that you are a Piscean whilst I, born just a few days later am an Aries. Correspondingly, our natures will be very different.

Richard.

[jasong]

Originally Posted by R.D. Silverman

Jason, I hold you in such utter contempt that it would be hard to find the proper words to describe it.

The idea that would have any respect for your opinion at all at this point is laughable. I view you the same way you view Hitler, and that is not an understatement. You have a murderous heart and you will probably be close enough to hear his screams when you reach your true home.

The idea that this Forum is referred to as a math forum is a sick joke. The forums at this site that are either fun or productive are fun because math isn't discussed in them, and when it is, the normal suspects generally aren't aware of it, so things tend to stay civil. The various prime projects are fun because the smart-asses that are so smug about the knowledge don't tend to discuss it in those forums, probably because they aren't there to have a good time, but to degrade people. The factoring forum is tolerable, or not, depending on what the subject matter is. If people come here to learn math, of just about any sort, there is a better than even chance that they will be insulted within a few hours of starting their thread.

For those of you who come here to discover prime numbers, I hope you enjoy your stay. I would encourage you to take specifically mathematical questions to other forums, or use Google.

As far as the unanswered questions are concerned, I say to R.D. Silverman and the other people who have insulted me(with the exception of wblipp. If he distances himself from me on this, I am not hurt. Whatever his opinion of me, I would love to crunch his project in the future, since he generally seems to be a fairly kind individual.) FUCK YOU!!! If you wish to know how my trials go with testing (2^3355584+1)/769, you may inquire at Riesel Sieve Forum in a week or two. I fully expect to discover that 769 DOESN'T divide the number. I believe the only numbers that divide 2^3355584+1 are 1 and 2^3355584+1. It will never show up on the Prime Pages because LLR is flawed, not because of theory or programming, but because Intel chips are flawed. It would also appear that AMD is attempting similar tactics to attempt to get their performance crown back, so applications that require a very high amount of precision are going to be very screwed in the future, though DC projects of that sort already are. For those of you who require proof, I have lost all respect for this forum, so don't really care what people believe. This post is what is called closure.

Goodbye, and may your fish dinners contain bones, and may your bowel movements be bloody, hard, and painful.

[wblipp]

Originally Posted by jasong

I believe the only numbers that divide 2^3355584+1 are 1 and 2^3355584+1.

Jason,

I gave you three factors in message #22. 769 is a factor of the second one, so it does divide your number.

Do you see that x+1 always divides x³+1?

Do you see that this means (4+1) divides 4³+1?

And 3221+1 divides 3221³+1?

Set x = 2^64*17477

Do you see that 2^64*17477+1 divides (2^64*17477)³+1?

Do you see that (2^64*17477)³+1 = 2^64*17477*3+1 ?

Do you see that 2^64*17477*3+1 = 2^3355584+1?

This same trick works for ANY exponent that has a odd factor.