Re: prime or not

Am 29.03.2007 12:13 schrieb Rainer Rosenthal:
temper3243@xxxxxxxxx schrieb:
why are strings 1, 1001,1001001 ... all non primes.

In base 2 this is wrong: Binary(1001001) = 2^6+2^3+2^0 = 73 is prime.
And in base 10 we have:

1001001001001001001001001001001001001001001001001001001 =
prod(21319,10749631,1111111111111111111,3931123022305129377976519)

which has quite an extraordinary smallest prime divisor, compared
to the many 3's, 7's etc. in many of these numbers.

http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1307.html

Funny link, thanks.
I would be astonished if there were a proof for Dijkstra's
conjecture.

Best regards,
Rainer Rosenthal
r.rosenthal@xxxxxx


Well, let me step in and try how far I come

-------------------------------------------------

For any base b the expansion 1000..0 (k zeros)
is b^k, (write it for short "bk"), so we had for threefold
concatenation of the string bk

(bk)^3 + (bk)^2 + bk + bk^0

(bk^4 - 1)
= -----------
(bk - 1)

or generally for a j-1 - fold concatenation:

bk^j - 1
(1) n = --------
bk - 1

If j is composite, then immediately it is clear, that n is composite,
since the numerator can algebraically be factored.



So we focus on prime j only.


If j<>k then the above is also (with b^j = bj )

bj^k - 1
(2) n = --------
bk - 1

and still bk -1 is a factor of bj^k-1, but which cancels out


But bj^k - 1 has also the factor bj-1, which, if j<>k, is different
from the factor bk-1.

So we may rewrite our factoring

bj^k - 1 p
(3) n = -------- = (bj - 1) -----
bk - 1 bk - 1

and n could only be prime, if p = bk - 1

But that meant

(4) (bj -1)(bk-1) = bk^j - 1 = bj^k - 1

To see, whether this is possible, let's rewrite this:

===================================================
(5): b^(k+j) - (b^k + b^j) + 1 = b^(k*j) - 1
===================================================

Let's see, whether or on which circumstances (1) can
be satisfied:

---- Case distinction ---------------------------

a) k,j>2

For any k,j>2 it is immediately obvious, that
this is impossible, since b^(k*j) > b^(k+j)
and the rhs exceeds the lhs.


b) k=j=2

Now let's see, whether j=k=2 could provide a solution.

we had
b^4 - 2b^2 + 1 = b^4 - 1
2b^2 = 2
b^2 = 1
b=1
a trivial solution, leading to 0/0

c) k=1

For k=1 or j=1 let's use k=1, which suffices, since the
parameters j and k occur symmetrically:

b^(1+j) - (b^j+b)+1 = b^j - 1
b^(1+j) - 2b^j - b + 2 = 0
(b^j - 1) ( b - 2 ) = 0
which gives two solutions b=1 or b=2

-------------------------------------------------

So we have for (5):
a) k,j> 2 ---> nk is composite
b) k=j=2 ---> nk is composite except for b=1
c) k=1 ---> nk is composite except for b=1 or b=2

=================================================================

(5) is critical when k<>j.

So, let's look at k=j

We had in (3)

bj^k - 1 p
(3) n = -------- = (bj - 1) -----
bk - 1 bk - 1

and if j=k then this is

bj^j - 1 p
(6) n = -------- = (bj - 1) ----- = p
bj - 1 bj - 1

and it is not obvious, whether p can be prime or not.

So this case remains as single interesting one:

k=j and k=j is prime --> n composite or prime?

The first case to check would be b=2, j=3

n = (2^9 - 1)(2^3-1) = 511/7 = 73 --> n is prime

so at least one prime occurs.

Gottfried Helms


.

Relevant Pages

  • Re: why did you choose the programming language(s)you currently use?
    ... That's the factoring program (factor.exe from ... I don't know how to fix the bug nor how to bind ... The Python program, as it captures the StdOut, ... composite back to the beginning and start over. ...
    (comp.lang.python)
  • Re: Breaking Large Composite Numbers...???
    ... around very large composite numbers that have 2 very large prime ... RSA is typically used a key exchange mechanism. ... Block ciphers do not use the hardness of integer factorisation as the ... Testing whether a number is prime is much easier than factoring. ...
    (sci.crypt)
  • Re: Breaking Large Composite Numbers...???
    ... around very large composite numbers that have 2 very large prime ... RSA is typically used a key exchange mechanism. ... Testing whether a number is prime is much easier than factoring. ... It holds a deep sense of ...
    (sci.crypt)
  • Re: Breaking Large Composite Numbers...???
    ... around very large composite numbers that have 2 very large prime ... RSA is typically used a key exchange mechanism. ... Block ciphers do not use the hardness of integer factorisation as the ... Testing whether a number is prime is much easier than factoring. ...
    (sci.crypt)