A strange idea......

[epatka]

I hope your number is prime :D

Thanks, Jeff :D

[epatka]

Just trying to put you at ease. :)

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

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.

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.

That'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.

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.

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

.

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

[cheesehead]

Originally Posted by epatka

.
You mean, they must have covered this subject?

No, I meant that it seems likely that the corresponding statements or theorems exist or could be formulated 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."

[epatka]

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

True.

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.

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 :(

[Maybeso]

Originally Posted by 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 :(

Perhaps we are thinking in the wrong base.
If noting that 1/7 = 0.142857 142857... base 10 implies that 7 | 10^6 - 1 implies 7 | 10^3 + 1.
Then noting that 1/111 = 0.001 001... base 2 implies that 7 | 2^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: n shifts + subtractions vs. log2(n) squares + doubles. :( :( sigh :( :( /EDIT

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

Maybeso

[epatka]

Hi Maybeso,

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

ui. Thanks for working on it :)

[Maybeso]

Hi Eva,

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

(Maybeso) Bruce

[epatka]

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

[Maybeso]

Originally Posted by 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?

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

[epatka]

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

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

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.

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

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.

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

Eva

[Maybeso]

Originally Posted by Eva

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

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 to millions instead of storing millions of bits.

Originally Posted by Eva

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

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 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.

Bruce