A strange idea......
 

Hi,

I am new, and I am in no way a mathematician or programmer, that's why I need experts' opinion on this.

I have been studying the prime numbers in general, and I have discovered something about them, what - I think - might make looking for primes easier. Because, as I said, I am no expert, I have no idea if what I am suggesting here is new at all. And, of course it is possible that using this method would be even more difficult, or impossible.

Anyway....

I was playing with prime numbers, and discovered, that if I divide 1 by a prime number, than in many cases the reminders have a unique character. There are exceptions, and there are a few non-prime numbers that have this character, but in general, it might be a good screening process. Of course I wasn't able to test the very high numbers, but I am sure there are members who could do that for me.

I'll make it short.

When I divide the number 1 by a prime number, in most cases the repeating residue will be a number where starting the first and the very middle digits, they always add up to 9.

To explain, here are some examples:

7/11

0.142857 142857

1+8=9 4+5=9 2+7=9

1/11

0.0909090909090909

0+9=9


1/13

0.076923 076923

0+9=9 7+2=9 9+3=9

etc.

Larger numbers:

1/29

0.0344827586206896551724137931 0344827586206896551724137931

When I divide the repeating residue into 2 parts, it is easy to see that here, too it works.

03448275862068 96551724137931

0+9=9 3+6=9 4+5=9 etc.


1/61

0.016393442622950819672131147540983606557377149180327868852459

divided up it works:

016393442622950819672131147540 983606557377149180327868852459

There are exceptions, like 1/49 which works out like this, although it is not a prime, and there are primes that don't have this quality.

But I thought, based on this, there could be a pre-screening of primes.
What I had in mind was, to divide 1 by the number we want to test, and if there is a patterns like this in the repeating residue, the number is probably a prime.

I don't know how difficult it is to divide such huge numbers, but if it can be done, it might be easier, than factoring. And once we have the result of the division, we would have to find the repeating residue (it is not always as long as the number itself), and in the middle of the repeating residue there should be a bunch of 9-s of course, because it would start with a bunch of 0-s.

As I said, I don't know if this is feasible. or it might be already part of the screening process.......

I am just an amateur, trying to be useful.

Eva

To explain a bit more what it looks like, I have posted a few on my website:

http://www.newhorizonscience.com/prime1.gif

http://www.newhorizonscience.com/prime2.gif

http://www.newhorizonscience.com/prime3.gif

http://www.newhorizonscience.com/prime4.gif

Here you can see the residues compared to the ones of the composite numbers.

Re: A strange idea......
 

[quote="epatka"]I am new[/quote]
... so you have a good chance to present fresh insight,

[quote]and I am in no way a mathematician or programmer,[/quote]
... so perhaps you are not so likely to miss seeing something that a mathematician or programmer might overlook.

[quote]that's why I need experts' opinion on this.[/quote]
... but you'll have to do with this cheesellama's opinion, apparently.

[quote]I have no idea if what I am suggesting here is new at all.[/quote]
Sometimes everything old is new again ... and "useful", "inspiring", and "insightful" are often more important than either "old" or "new".

[quote]And, of course it is possible that using this method would be even more difficult, or impossible.[/quote]
That would not stop a [i]real[/i] mathematician-programmer!

Reminds me of a story (in an inverse sort of way):

A (non-math) professor commented that mathematics was of little value. "Why, mathematicians even claim to work with [i]imaginary[/i] numbers! How can anything be more useless than that?"

A math major student in the audience protested, "Hey! Imaginary numbers are just as useful as any other numbers!"

The professor called her to come down to the front next to the blackboard. "Show me", he smugly commanded, "the square root of minus one pieces of chalk", handing her a fresh stick of chalk.

The student frowned. The professor smiled and reached to take back the chalk. The student said, "I'll do it! I'll do it [b]if[/b] you first show me one-half piece of chalk."

The professor's smile changed to a grin as he snapped the chalk in two and handed one of the halves to the student. "There you are. One-half piece of chalk."

As she held up the chalk piece, the student carefully explained, "No, this is [b]one[/b] piece of chalk. You have one piece of chalk in your hand, and I have one piece of chalk in my hand. But I asked you for [b]one-half[/b] piece of chalk, not [b]one[/b] piece."

The professor's grin slowly faded.

The student said, "See? The square root of minus one is just as real as one-half." and turned to resume her seat.

[quote]Anyway....[/quote]

[quote]When I divide the number 1 by a prime number, in most cases the repeating residue will be a number where starting the first and the very middle digits, they always add up to 9.

To explain, here are some examples:

7/11[/quote]
(... 7/11 = 1/7 in base-48, of course ...)

[quote]0.142857 142857

1+8=9 4+5=9 2+7=9[/quote]

Oooooookaaaaaaaaaay ... what we have here is a combination of things (which will also explain the rest of your examples, as we'll see).

First of all: Because of what I'm going to explain below, I doubt that what you've outlined here will lead to a new way of finding primes [u]that is more efficient[/u] than other methods of finding primes. Note the qualifier! When we start playing with really, really big numbers (with millions and millions of digits, as GIMPS is doing), efficiency is not a trivial consideration -- it's essential.

Second: For any prime p, other than p=2 or p=5, when you compute its inverse 1/p in base-10, you will get a repeating pattern of decimal digits whose cycle length is p-1 or less.

Why?

Well, I don't have a link to a formal proof right now, but (10^(p-1) - 1) is divisible (and when we say divisible, we mean integer division with a zero remainder) by prime p, except for p=2 or p=5. That is, the number 9999...[total of p-1 nines]...999 is always divisible by p.

3 divides 99. (Yes, 3 also divides 9, but I didn't say it wouldn't.)

7 divides 999999.

11 divides 9999999999. (Also, 99, but I didn't say it wouldn't.)

13 divides 999999999999. (Also, 999999, but ...)

17 divides 9999999999999999.

So, this means that the decimal fraction 0.999...[total of p-1 nines]...999 will be "evenly" divisible by p with no remainder to go to more decimal digits.

0.9999999 / 7 = 0.142857 exactly, because 142,857 * 7 = 999,999. And 0.999999 999999 999999 / 7 = 0.142857 142857 142857 exactly, because 142,857,142,857,142,857 * 7 = 999,999,999,999,999,999.

So the infinitely repeating decimal fraction 0.(9)... (which equals 1.0000...), divided by 7 equals the infinitely repeating decimal fraction 0.(142857)...

Similarly, 0.9999999999999999 / 17 = 0.0588235294117647, because 588,235,294,117,647 * 17 = 9,999,999,999,999,999. And the infinitely repeating decimal fraction 0.(9)... (which equals 1.0000...), divided by 17 equals the infinitely repeating decimal fraction 0.(0588235294117647)...

Third: Why do some cycles have length less than p-1?

Let k be the smallest power of ten such than 10^k-1 is divisible by p (p not 2 or 5). The cycle length will be k. For some p, k = p-1. But for other p, k is a divisor of p-1.

For p = 11, k = 2, not 10. For p = 13, k = 6, not 12.

Fourth: Why do the digits in the cycle add to 9 pairwise first-half-to-second-half?

For instance:

[quote]29

0.0344827586206896551724137931 0344827586206896551724137931

When I divide the repeating residue into 2 parts, it is easy to see that here, too it works.

03448275862068 96551724137931

0+9=9 3+6=9 4+5=9 etc.[/quote]

Here's why the sum of all the digits in the cycle is a multiple of 9: Let k be the smallest power of ten such than 10^k-1 is divisible by p. 10^k-1 is also divisible by 9. Since p is a prime, so is not a multiple of 9, (10^k-1)/p must be divisible by 9. That implies that the sum of the decimal digits of (10^k-1)/p must be a multiple of 9.

Why are the pairwise first-half-to-second-half digit sums all 9? Well, first note that for p > 3, k is even. (Proof: hand-wave. Since llamas don't have hands, someone else can provide this one. :) )

k is equal to either p-1 or some divisor of p-1. [i] Hmmmm...

I seem to be drawing a blank about the rest of the explanation. Can someone else finish up?[/i]

A little off topic, but I very much enjoyed the story of the uninformed professor. I am currently reading Innumeracy Mathematical Illiteracy and Its Consequences by John Allen Paulos. It is a little dated but I feel very representative of our culture. Personally I believe that lack of mathematical and scientific knowledge is right up there with illiteracy. Mathematics is leading innovation and without innovation we are moving backwards. That is why GIMPS is so great, people ask me all the time why I get so excited talking about the project and what is its use. I tell them that it is my contribution, however small, to discovering what is surely out there, plus unlike other projects every exponent tested is unique and vital to overall success.

I would love to see every high school graduate have a feeling for the concept of Entropy. Ah we can dream can't we...

Yes and a belated Happy Father's day to George father of our beloved GIMPS.

Oh and I love this guy :banana: not that I want to take away anyone's cycles :)

Cheesehead -

I threw together a quick script to test the assertion that k is even when p > 5, and got the following contradictory results for p < 100.

[code:1]
p k
-----------
31 15
37 3
41 5
43 21
53 13
67 33
71 35
79 13
83 41
[/code:1]

Thanks Joe.

Re: A strange idea......
 

Thank you for responding. I was worried I said someting very dumb or broke some unwritten rules, because there was no reaction to my post.


"7/11[/quote]
(... 7/11 = 1/7 in base-48, of course ...)"

Sorry, this was a mistake of mine. It was supposed to mean 1/7.
Of course it doesn't change that you are right in this case.

"First of all: Because of what I'm going to explain below, I doubt that what you've outlined here will lead to a new way of finding primes [u]that is more efficient[/u] than other methods of finding primes. "

I was afraid of this. But in my ignorance, I figured, that here we need one division only, and a division is nothing but substructions. Of course, in this case it woul mean 10 million substractions of 2 10 million digits long numbers, probably 10 million times.... But I am not so sure I am right in this. I have read that the problem really is a space problem. Maybe even entering such a large number can be a problem....


"Second: For any prime p, other than p=2 or p=5, when you compute its inverse 1/p in base-10, you will get a repeating pattern of decimal digits whose cycle length is p-1 or less.


3 divides 99. (Yes, 3 also divides 9, but I didn't say it wouldn't.)

7 divides 999999.

11 divides 9999999999. (Also, 99, but I didn't say it wouldn't.)

13 divides 999999999999. (Also, 999999, but ...)

17 divides 9999999999999999.

Thanks for the explanation. This makes it more clear. "

I noticed that when I do the division by hand, there is always a point, where the remainder is 1. And then the whole cycle starts all over.

Question is, if this whole thing is any help in understanding or recognizing prime numbers???

At this point I have no idea. I might be just going in circles.

Thanks anyways, and I am thankful for any further insight, explanation or help.

ps. sorry, I coudn't figure out how to use the "quote" function.

[quote="apocalypse"]Cheesehead -

I threw together a quick script to test the assertion that k is even when p > 5, and got the following contradictory results for p < 100.
[code:1]
p k
-----------
31 15
37 3
41 5
43 21
53 13
67 33
71 35
79 13
83 41
[/code:1]
Hrm. I don't know how to make a cleaner table here.[/quote]
Use {code} {/code} with [ instead of { and ] instead of }


Where did you see the assertion that k is even?
[quote="Cheesehead"]k is equal to either p-1 or some divisor of p-1.[/quote]
This is consistent with your results!

I was referring to the comment near the bottom of cheesehead's post, one line above the one you quoted.

[quote="cheesehead"]Why are the pairwise first-half-to-second-half digit sums all 9? Well, first note that for p > 3, k is even. (Proof: hand-wave. Since llamas don't have hands, someone else can provide this one. )[/quote]

apocalypse,

You are quite correct. [b]k does [u]not[/u] have to be even when p > 5.[/b]

I was tiring when I wrote that assertion, and got sloppy in my thinking (and it's hard enough keeping track of even/odd when one has no hands). Thank you for noticing and posting a correction!

[quote="cheesehead"]Well, first note that for p > 3, k is even. (Proof: hand-wave.[/quote]
Lesson for all: When someone asserts existence of a "hand-waving" proof (which may not be explicitly labelled as "hand-waving"), LOOK OUT! It lacks rigor, and might well be wrong. CHALLENGE IT!

[quote="cheesehead"]Lesson for all: When someone asserts existence of a "hand-waving" proof (which may not be explicitly labelled as "hand-waving"), LOOK OUT! It lacks rigor, and might well be wrong. CHALLENGE IT![/quote]
Unless you're a physicist, who in general doesn't give a llama's lick about the rigor of a proof. :shock: :D ;)

In case what I discovered here is something new, and might be helpful for the prime number research, would someone help me to write it down in mathematician's language and present it to a math journal?

Unfortunately, I am not familiar with math terms, on top of that, English is my second language. But it would be very nice to see my name in the journals :)

Thank you

Eva

Wow!
I am very surprised this is the first time I've ever heard about this curious pattern. Cheesehead has covered most of the explanation, so I will pick up where he left off.
[quote="Cheesehead"]Fourth: Why do the digits in the cycle add to 9 pairwise first-half-to-second-half?[/quote]
Here is the hand-wavy proof that cheesehead almost came up with for when k is even.
(Since I have hands, and even an extra prime hand over there <--- ;) )

For those interested in references, I did a google on "digit patterns repeating decimal", and one of the many links was
[url]http://www.mersenneforum.org/attachments/pdfs/422.pdf[/url]
Which contains a specific example of this general statement.[code:1]If 1/b has a decimal pattern of length k, then b must divide 10^k - 1 = 99999. If, in addition, b is a prime number, then k must divide b - 1.[/code:1]
Now, if 1/b has a decimal pattern of length 2k, then b must divide 10^2k - 1 = (10^k - 1)(10^k + 1).
When b = 7, 1/7 = 0.142857... a pattern of length 6 ==> 7 divides 10^6 - 1 = (10^3 - 1)(10^3 + 1) = (999)(1001)

1000/7 = 142.857 142 857 142 857 142
+ 1/7 = 000.142 857 142 857 142 857
-------------------------------------
1001/7 = 142.999 999 999 999 999 999
143 = 143

And this will hold for any 1/b with a repeating decimal pattern of even length 2k, indicating b | 10^k+1 rather than 10^k-1. (If b | 10^k-1, then the pattern would be length k.)
That is what your pattern indicates -- not that b is prime, but that b divides 10^k+1.

For example,
1/7 = 0.142 857... --> 7 | 1001
1/13 = 0.076 923.. --> 13 | 1001
1/91 = 0.010 989.. --> 91 | 1001
91 = 7*13 is not prime.

And in the case of 49,
1/7 = 0.142 857... --> 7 | 1001
1/49 = 0.020408163265306122448 979591836734693877551... --> 49 | 10^21+1.
So 7 is a factor of 1001, but 49 = 7*7 is not.

Maybeso

Thank you, Maybeso,

I guess this means I will have to find another way to become famous :)

Out of luck today.....

Let's get back to my Mersenne Prime testing. It says, my completion date will be June 5 23:21 2005. Is this a bug or is it going to take 2 years? This is my second testing, so I don't know.

[quote="epatka"]Let's get back to my Mersenne Prime testing. It says, my completion date will be June 5 23:21 2005. Is this a bug or is it going to take 2 years? This is my second testing, so I don't know.[/quote]
Either your computer is only running for a very small part of the day, or you are testing an exponent around 33,000,000 with a processor like a Pentium II. If you have a slower processor, you may just want to do Double Checks. You can select what kind of work you want in the Primenet menu under the Test menu in Prime95.

You are right!
I am testing a 33,000,000 on a Pentium II :)

The first number I tested took about a month and then it said it is a composite. This one took one month so far, 2 days ago it said "no factors". I thought it was done and the number is a prime. But I've never been lucky in anything, so I wasn't too concerned about it.
I knew there was a catch :D

I was right. It is going to take another 2 years......

:(

[quote="epatka"]The first number I tested took about a month and then it said it is a composite. This one took one month so far, 2 days ago it said "no factors". [/quote]
Yeah, that means that the first number you tested had a factor that the trial factoring found. Because a factor was found, the program knows the number can't be prime, so a Lucas-Lehmer (LL) test was never even preformed on that number. But on your current number, trial factoring didn't find a factor, so it has to preform the LL test to see if the munber is prime or not. Oh well, it sounds like you're a patient person, anyway. ;)

What makes you think I am patient? :)

Is there a way of speeding it up? I updated yesterday to the latest version. That means it will take 25% less time....... I might have it by next summer......

The only way you can really speed it up is to use a faster computer or get a smaller number. It will take a very long time to test a 33M number on a Pentium II no matter what you do.
I hope your number is prime :D

If you want it to go really fast then you might want to join the Lone Mersenne Hunter`s. That way you`ll find a hole bunch of factors in no time. You won`t find prime numbers that way but you`ll play a major part of the search.

Joss

Re: A strange idea......
 

[quote="epatka"]I was worried I said someting very dumb or broke some unwritten rules, because there was no reaction to my post.[/quote]
It was just unfortunate timing. There were squabbles in other forum threads that drew attention. There was Fathers Day. And after I first read your thread, I wasn't ready to post a response until a day later.

[quote]Of course it doesn't change that you are right in this case.[/quote]
Just trying to put you at ease. :)

[quote]a division is nothing but substructions. Of course, in this case it woul mean 10 million substractions of 2 10 million digits long numbers, probably 10 million times[/quote]
Mathematicians have come up with ways to multiply and divide large numbers that are much, much faster than the methods we all learned in school.

But it's always possible to find a number large enough to make arithmetic as big a task as you want.

[quote]I noticed that when I do the division by hand, there is always a point, where the remainder is 1. And then the whole cycle starts all over.[/quote]
[u]That[/u]'s the point where you've found the k for this p !! When the remainder is 1, you've found the k such that 10^k-1 is divisible by p.

[quote]Question is, if this whole thing is any help in understanding or recognizing prime numbers???[/quote]
Well, since division is the inverse of multiplication, it seems likely that any statement or theorem about prime integers has a corresponding statement or theorem about the inverses of primes.

[code:1]ps. sorry, I coudn't figure out how to use the "quote" function.[/quote][/code:1]
Next time you're about to post something, when you're at the form for entering your post, look at the lower left for "[u]BBCode[/u] is [u]ON[/u]". Click on "[u]BBCode[/u]", and you'll get a help page about all the text formatting commands.

[quote="Maybeso"]Now, if 1/b has a decimal pattern of length 2k, then b must divide 10^2k - 1 = (10^k - 1)(10^k + 1).[/quote]
Similarly, if 1/b has a decimal pattern of length 3k, then b divides 10^3k - 1 = (10^k - 1)(10^2k + 10^k + 1).

In general, if 1/b has a decimal pattern of length jk, then b divides 10^jk - 1 = (10^k - 1)(10^(j-1)k + 10^(j-2)k + ... + 10^k + 1).

[quote][quote="jocelynl"]If you want it to go really fast then you might want to join the Lone Mersenne Hunter`s. That way you`ll find a hole bunch of factors in no time. You won`t find prime numbers that way but you`ll play a major part of the search.[/quote]

Thanks Joss, but my computer is so slow that I wouldn't be much help.... Besides, I like the suspense that someday.... sometime..... in 2005 I might win some money. It makes it more interesting. Although by the time I am finished with my number, someone else will have discovered a 10 million digit prime.

I haven't chosen this number. The program started it automatically. What if I increase the memory available for the program? I have 256 MB and there is lots of room.......

Eva

[quote]I hope your number is prime :D[/quote]

Thanks, Jeff :D

Re: A strange idea......
 

[quote]Just trying to put you at ease. :)[/quote]

It worked :) Just the fact that what I discovered wasn't yesterday's news makes me feel less foolish.....

[quote]Mathematicians have come up with ways to multiply and divide large numbers that are much, much faster than the methods we all learned in school.
But it's always possible to find a number large enough to make arithmetic as big a task as you want.[/quote]

In this case I guess it would be a big task....... I keep hearing how many million or billion functions a second. It is very hard to imagine what is a bigger task? To do millions of factors a second or to make one division of a 10 million digit number.

[quote]
[u]That[/u]'s the point where you've found the k for this p !! When the remainder is 1, you've found the k such that 10^k-1 is divisible by p. [/quote]

Thanks. I realized that. Even if this whole thing was in vain, I learned a lot about how numbers work. I was pretty lazy in school.


[quote]Well, since division is the inverse of multiplication, it seems likely that any statement or theorem about prime integers has a corresponding statement or theorem about the inverses of primes[/quote].

You mean, they must have covered this subject? But I think that because this is almost an "invisible" part of math, people might overlook the importance of it. Besides, when we work with primes, the sky is the limit. This way, I can "tame" them a bit, and observe how they behave under certain circumstances. I might be wrong, but I think that this way there is hope to discover something about them that might help to recognize them...... In case I am not making sense, I don't blame you. Sometimes I don't make sense to myself ;)

By the way, I am glad at least a few people are interested in this.

Eva

Re: A strange idea......
 

[quote="epatka"][quote]Well, since division is the inverse of multiplication, it seems likely that any statement or theorem about prime integers has a corresponding statement or theorem about the inverses of primes[/quote].
You mean, they must have covered this subject?[/quote]
No, I meant that it seems likely that the corresponding statements or theorems [i]exist[/i] or [i]could be formulated[/i] even if no one has yet actually recognized, studied or published them.

However, it could be that almost every theorem about integers has already had its corresponding theorem about inverses recognized, but the "inverse" theorem may just not have interested many people beyond the first to study it.

As ads for the Public Proadcasting System here say -- "Stay curious."

Re: A strange idea......
 

[quote]No, I meant that it seems likely that the corresponding statements or theorems [i]exist[/i] or [i]could be formulated[/i] even if no one has yet actually recognized, studied or published them.[/quote]

True.

[quote]However, it could be that almost every theorem about integers has already had its corresponding theorem about inverses recognized, but the "inverse" theorem may just not have interested many people beyond the first to study it.[/quote]

Maybe nobody has thought of a way of using it. I have a feeling that there is a lot to discover here. It is fascinating that the inverses have their own rules of addition, multiplication, etc.

I was hoping they could be used to find prime numbers, but no luck :(

[quote="epatka"]Maybe nobody has thought of a way of using it. I have a feeling that there is a lot to discover here. It is fascinating that the inverses have their own rules of addition, multiplication, etc.

I was hoping they could be used to find prime numbers, but no luck :( [/quote]
Perhaps we are thinking in the wrong base.
If noting that 1/7 = 0.142857 142857... [b]base 10[/b] implies that 7 | [b]10[/b]^6 - 1 implies 7 | [b]10[/b]^3 + 1.
Then noting that 1/111 = 0.001 001... [b]base 2[/b] implies that 7 | [b]2[/b]^3-1, right?
[code:1]Inv. repeat order
1/3 = 01 2 3/ 3 = 1
1/5 = 0011 4 15/ 5 = 3
1/7 = 001 3 7/ 7 = 1
1/9 = 000111 6 63/ 9 = 7
1/11 = 0001011101 10 1023/11 = 93
[/code:1]
If we consider primes only, or even primes == +-1 (mod 8 ), this is another way to look for factors of mersenne numbers.
[code:1] 1/p repeating binary fraction order M(order)/p
1/3 01 2 3/ 3 = 1
1/7 001 3 7/ 7 = 1
1/17 00001111 8 255/17 = 15
1/23 00001011001 11 2047/23 = 89
1/31 00001 5 31/31 = 1
1/41 00000110001111100111 20 1048575/41 = 25575
1/47 00000101011100100110001 23 8388607/47 = 178481
1/71 00000011100110110000101011010001001 35 34359738367/71 = 483939977
1/73 000000111 9 511/73 = 7
1/79 000000110011110110010001110100101010001 39 549755813887/79 = 6958934353
1/89 00000010111 11 2047/89 = 23
1/97 000000101010001110100000111111010101110001011111 48 281474976710655/97 = 2901803883615
[/code:1]
The code to calculate 1/p base 2 isn't too ugly.
[code:1]
for(binary="",skip=2,work=2; work>0; ) {
while (n>work) { work *= 2; binary += "0"; }
work -= n;
binary += "1";
if (work==1) work = 0; // fraction starts repeating.
work *= 2;
// if work = 2^k for the second time then fraction also repeats.
for(check=work; check%2==0; check/=2);
if (check==1 && --skip==0) work = 0;
}
m = length of binary --> n | 2^m - 1.
[/code:1]
If strings were used instead of integers the code would be faster and would work for big numbers.

So how does this compare to the power mod method?
EDIT: Oh, right: [b]n [/b]shifts + subtractions vs. [b]log2(n)[/b] squares + doubles. :( :( sigh :( :( /EDIT

Any other uses for this in base 2? Other bases?

Maybeso

Hi Maybeso,

unfortunately, I don't understand this. Is this good news or bad news?

ui. Thanks for working on it :)

Hi Eva,

Well, the good news is, we [b]can [/b]use the patterns of inverses (in binary) to recognise factors of mersenne numbers. The bad news is, it isn't very fast.

(Maybeso) Bruce

Thanks Bruce,

too bad :(

What if we didn't finish the whole division, but would look for the point when the digits start to add up to 9?

This way we would save half the work.......

At least this is what I think/hope :)

Eva

[quote="epatka"]What if we didn't finish the whole division, but would look for the point when the digits start to add up to 9?[/quote]
Well, mersennes require we work in binary, so we would have to look for bits that added to 111 ... ;) But it will still work:

If N is 64 bits, then the digits would start with 64 0's, and we could watch for 64 1's. Actually, anything over 48 (3N/2), or even 32 (N/2) may be enough.

And if the digits don't add to 1's because the pattern has an odd width (what you originally took for composites) it would simply not exit early and complete the division.

Bruce

[quote]Well, mersennes require we work in binary, so we would have to look for bits that added to 111 ... ;) But it will still work:[/quote]

That's good news sofar...... :)

[quote]
If N is 64 bits, then the digits would start with 64 0's, and we could watch for 64 1's. Actually, anything over 48 (3N/2), or even 32 (N/2) may be enough. [/quote]

Problem is, the numbers we are testing have millions of digits. That would mean millions of 0's and 1's.......

[quote]
And if the digits don't add to 1's because the pattern has an odd width (what you originally took for composites) it would simply not exit early and complete the division.[/quote]

Sorry, I don't understand. What did I take for composits? What do you mean by "odd width"?

Eva

[quote="Eva"]Problem is, the numbers we are testing have millions of digits. That would mean millions of 0's and 1's....... [/quote]
Well, we could start testing factors with 100 bits and work upward. The factors will be much smaller than the huge mersenne numbers they divide.

The program calculates 1/F using long division just like it's done by hand, except it uses binary.
For example, F = 97 = 1100001:[code:1] __0000001_ <- Step 2, add z 0's to Q, and a 1.
1100001 )10000000 <- Step 1, add z 0's to D until > F.
_1100001_ <- Step 3, subtract F from D.
11111 <- repeat until D = 1.
[/code:1]
For larger F, step 2 will produce millions of bits.
But other than watching for a block of 1's, we don't care what Q actually is.
We want how many bits are in Q. So we replace step 2 with:[list]Step 2, if (z > 0) add z to Q and reset ones_count, otherwise add 1 to ones_count.[/list:u]And if ones_count = leading_zeros, double Q and stop.
When it stops, F | 2^Q - 1.

Now we are counting [b]to[/b] millions instead of storing millions of bits.

[quote="Eva"]Sorry, I don't understand. What did I take for composites? What do you mean by "odd width"?[/quote]
I was referring to your first post to start this topic, where you stated that the majority of primes seemed to share the trait of the repeating digit pattern of their inverses adding to 9's, while the majority of composites did not.

Look at my first post on page 2 of this topic.
In the second [b]Code:[/b] block, the numbers in the "order" column are the width in bits of the repeating pattern. Notice that when the pattern is an even number of bits wide, you can split it in 2 and the halves will add to 11111... When it's an odd number of bits wide, you can't split it anywhere and have it add to 1111....
I think this is true for your decimal examples as well, and for any base.

Bruce

[quote]Well, we could start testing factors with 100 bits and work upward. The factors will be much smaller than the huge mersenne numbers they divide.[/quote]

I guess you have experience in this. :)

[quote]The program calculates 1/F using long division just like it's done by hand, except it uses binary.
For example, F = 97 = 1100001:

........

Now we are counting to millions instead of storing millions of bits. [/quote]

Well, I would lie if I said I understand all of it, but I think I can see the whole picture.

It doesn't sound bad so far......


[quote]Look at my first post on page 2 of this topic.
In the second Code: block, the numbers in the "order" column are the width in bits of the repeating pattern. Notice that when the pattern is an even number of bits wide, you can split it in 2 and the halves will add to 11111... When it's an odd number of bits wide, you can't split it anywhere and have it add to 1111....
I think this is true for your decimal examples as well, and for any base.[/quote]

I see. I have a feeling, there must be a pattern to those too, but it is probably very hard to find :(

What I've been thinking was that maybe we could do the division until the remainder is 1, and that would mean, the number is almost certainly a prime.
If you took a look at my links, you have probably seen that if the composite numbers have a pattern, in front of the pattern there is one or more digits, and ONLY THEN does the pattern start.

For example 70:

0 142857 142857 142857 142857

But most of these numbers are even numbers anyway.

39 has a pattern, but it adds up to 6, not 9. etc.

But prime numbers don't have anything before the pattern.....
Because of this, we could do the division, and watch for the point when the remainder is 1.

I show you what I think.

Here is No. 79
It is prime, and the residue has a pattern, but it doesn't add up to 9:

0.0126582278481

Here is the good old fashioned way of dividing 1 by 79 :)
Under the division the residues. (I hope it will look OK.)

1/79 = 0.0126582278481
100
_210
__520
___460
____650
_____180
______220
_______620
________670
_________380
__________640
____________80
______________[b][size=18]1[/size][/b]

I thought we could watch for the remainder of 1. That wouldn't be too bad, because the residue is most of the time smaller than the number itself. It might be twice as much work, but it still could be done. I hope :)

This is exciting, even if it doesn't work out ;)


Eva

Just to add something:

As far as I can see, the sum of the digits of the repeating part of the prime numbers is always divisible by 9, even if the digits don't add up to 9 pairwise. That's why I think we might be able to find a general rule for all the primes.

Other composits don't have this quality. Or their digits adds up pairwise to 6, 8, etc.

There is a definite regularity to the primes.

Eva

inverse multiplicative
 

I like to look at primes in terms of Wilson,s theorem where to
a factorial +1 , a number that is indivisible , multiplies,
as perhaps the place to look for the inverse of a prime, as a specific.

Re: inverse multiplicative
 

It sounds interesting, but I must admit I don't know anything about this.
Would you mind explaining it in a few words?

[quote="epatka"]Hmmmmm, how do I get rid of this double post?[/quote]
Ask a forum moderator (philmoore or ewmayer) or Xyzzy to delete it.