## Re: [PrimeNumbers] Re: Sierpinski Problem

Expand Messages
• This is exactly the case as you described it.If 5 didnt divide k,then we would have a finite covering set.But since 5/k then the numbers k*2^(4*m+2)+1 have an
Message 1 of 12 , Aug 29, 2002
This is exactly the case as you described it.If 5
didnt divide k,then we would have a finite covering
set.But since 5/k then the numbers k*2^(4*m+2)+1 have
an algebraic factorization.
Let k=r^4.Then:
r^4*2^(4*m+2)+1=4*(r*2^m)^4+1
=[2*(r*2^m)^2+2*(r*2^m)+1]*[2*(r*2^m)^2-2*(r*2^m)+1]=A*B
I have not proven that A or B are divisible by
infinitely many different primes as m varies ,but
this seems very logical.
I tried to prove it without success by assuming that
there is a finite set of primes[p1,p2,,,pj] that
divide A for every m>1 ,for a specific k.Then i used
as a value for m,m=(p1-1)*(p2-1)*...*(pj-1) and tried
to end up with something absurd.No luck.This is the
most interesting part of my effort.The k's i found
produce numbers k*2^n+1,some of which have factors
belonging to a finite set and some of them have
factors belonging to the set of primes that divide a
polynomial.I dont know what step is next.Your valuable
ideas are welcomed
Pavlos
--- jbrennen <jack@...> wrote:
> --- In primenumbers@y..., Pavlos N <pavlos199@y...>
> wrote:
> > I managed to construct a Sierpinski multiplier k
> such
> > that k*2^n+1 is always composite for every n>1 and
> > there is no finite set of primes that divide it.I
> will
> > post a more detailed email explaining exactly how
> i
> > worked and other details.For now on i post my
> final
> > result only.The k's belong to the following set of
> > integers:
> > k=(18446744073709551615*a+2039404931861161240)^4
> > where a is a positive integer
>
> This is a really cool finding. I suspected that
> such a multiplier
> (or family of multipliers) was possible, but I never
> thought of
> using the fact that (4*x^4+1) has an algebraic
> factorization. I
> tried looking for k being a perfect cube or a fifth
> power, with
> no luck. Great work. :)
>
> So what we have here is:
>
> k*2^n+1 is of the form 4*x^4+1 if n
> == 2 (mod 4)
>
> k mod 3 == 1 -> 3 | k*2^n+1 if n
> == 1 (mod 2)
> k mod 17 == 16 -> 17 | k*2^n+1 if n
> == 0 (mod 8)
> k mod 257 == 16 -> 257 | k*2^n+1 if n
> == 4 (mod 16)
> k mod 65537 == 16 -> 65537 | k*2^n+1 if n
> == 12 (mod 32)
> k mod 641 == 16 -> 641 | k*2^n+1 if n
> == 28 (mod 64)
> k mod 6700417 == -16 -> 6700417 | k*2^n+1 if n
> == 60 (mod 64)
>
> Putting them together, k*2^n+1 is always composite.
>
> The requirement for k to be divisible by 5 is to
> ensure that
> when n == 2 (mod 4), that k*2^n+1 is not divisible
> by 5 -- if
> it is so divisible, then a finite covering set of
> primes exists.
>
> So all that is left is to prove that for at least
> one k in the
> given group, no covering set S of primes exists such
> that every
> k*2^n+1 is divisible by a member of S. Please let
> us in on this
> aspect of the finding... How are you able to prove
> the
> non-existence of a finite covering set? Or is the
> non-existence
> of a finite covering set only a conjecture?
>
>
>
>

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• ... Seconded. Pavlos, quite simply, this is a _brilliant_ discovery, and I take my hat off to you. It s definitely worth more investigation, thanks for sharing
Message 2 of 12 , Aug 29, 2002
--- jbrennen <jack@...> wrote:
> --- In primenumbers@y..., Pavlos N <pavlos199@y...>
> wrote:
> > I managed to construct a Sierpinski multiplier k
> such
> > that k*2^n+1 is always composite for every n>1 and
> > there is no finite set of primes that divide it.I
> will
> > post a more detailed email explaining exactly how
> i
> > worked and other details.For now on i post my
> final
> > result only.The k's belong to the following set of
> > integers:
> > k=(18446744073709551615*a+2039404931861161240)^4
> > where a is a positive integer
>
> This is a really cool finding.

Seconded.

Pavlos, quite simply, this is a _brilliant_ discovery, and I take my hat off
to you.

It's definitely worth more investigation, thanks for sharing it with us.

Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• I finally was able to prove that no finite covering set exists,that is,there are infinitely many primes that divide k*2^n+1 for the specific k s as n
Message 3 of 12 , Aug 30, 2002
I finally was able to prove that no finite covering
set exists,that is,there are infinitely many primes
that divide k*2^n+1 for the specific k's as n
varies.The proof is available on request
Regards
Pavlos
--- Pavlos N <pavlos199@...> wrote:
> This is exactly the case as you described it.If 5
> didnt divide k,then we would have a finite covering
> set.But since 5/k then the numbers k*2^(4*m+2)+1
> have
> an algebraic factorization.
> Let k=r^4.Then:
> r^4*2^(4*m+2)+1=4*(r*2^m)^4+1
>
=[2*(r*2^m)^2+2*(r*2^m)+1]*[2*(r*2^m)^2-2*(r*2^m)+1]=A*B
> I have not proven that A or B are divisible by
> infinitely many different primes as m varies ,but
> this seems very logical.
> I tried to prove it without success by assuming that
> there is a finite set of primes[p1,p2,,,pj] that
> divide A for every m>1 ,for a specific k.Then i
> used
> as a value for m,m=(p1-1)*(p2-1)*...*(pj-1) and
> tried
> to end up with something absurd.No luck.This is the
> most interesting part of my effort.The k's i found
> produce numbers k*2^n+1,some of which have factors
> belonging to a finite set and some of them have
> factors belonging to the set of primes that divide a
> polynomial.I dont know what step is next.Your
> valuable
> ideas are welcomed
>
> Pavlos
> --- jbrennen <jack@...> wrote:
> > --- In primenumbers@y..., Pavlos N
> <pavlos199@y...>
> > wrote:
> > > I managed to construct a Sierpinski multiplier k
> > such
> > > that k*2^n+1 is always composite for every n>1
> and
> > > there is no finite set of primes that divide
> it.I
> > will
> > > post a more detailed email explaining exactly
> how
> > i
> > > worked and other details.For now on i post my
> > final
> > > result only.The k's belong to the following set
> of
> > > integers:
> > > k=(18446744073709551615*a+2039404931861161240)^4
> > > where a is a positive integer
> >
> > This is a really cool finding. I suspected that
> > such a multiplier
> > (or family of multipliers) was possible, but I
> never
> > thought of
> > using the fact that (4*x^4+1) has an algebraic
> > factorization. I
> > tried looking for k being a perfect cube or a
> fifth
> > power, with
> > no luck. Great work. :)
> >
> > So what we have here is:
> >
> > k*2^n+1 is of the form 4*x^4+1 if n
> > == 2 (mod 4)
> >
> > k mod 3 == 1 -> 3 | k*2^n+1 if n
> > == 1 (mod 2)
> > k mod 17 == 16 -> 17 | k*2^n+1 if n
> > == 0 (mod 8)
> > k mod 257 == 16 -> 257 | k*2^n+1 if n
> > == 4 (mod 16)
> > k mod 65537 == 16 -> 65537 | k*2^n+1 if n
> > == 12 (mod 32)
> > k mod 641 == 16 -> 641 | k*2^n+1 if n
> > == 28 (mod 64)
> > k mod 6700417 == -16 -> 6700417 | k*2^n+1 if n
> > == 60 (mod 64)
> >
> > Putting them together, k*2^n+1 is always
> composite.
> >
> > The requirement for k to be divisible by 5 is to
> > ensure that
> > when n == 2 (mod 4), that k*2^n+1 is not divisible
> > by 5 -- if
> > it is so divisible, then a finite covering set of
> > primes exists.
> >
> > So all that is left is to prove that for at least
> > one k in the
> > given group, no covering set S of primes exists
> such
> > that every
> > k*2^n+1 is divisible by a member of S. Please let
> > us in on this
> > aspect of the finding... How are you able to
> prove
> > the
> > non-existence of a finite covering set? Or is the
> > non-existence
> > of a finite covering set only a conjecture?
> >
> >
> >
> >
>
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Finance - Get real-time stock quotes
> http://finance.yahoo.com
>

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• I finally was able to prove that no finite covering set exists,that is,there are infinitely many primes that divide k*2^n+1 for the specific k s as n
Message 4 of 12 , Aug 30, 2002
I finally was able to prove that no finite covering
set exists,that is,there are infinitely many primes
that divide k*2^n+1 for the specific k's as n
varies.The proof is available on request
Regards
Pavlos
--- Pavlos N <pavlos199@...> wrote:
> This is exactly the case as you described it.If 5
> didnt divide k,then we would have a finite covering
> set.But since 5/k then the numbers k*2^(4*m+2)+1
> have
> an algebraic factorization.
> Let k=r^4.Then:
> r^4*2^(4*m+2)+1=4*(r*2^m)^4+1
>
=[2*(r*2^m)^2+2*(r*2^m)+1]*[2*(r*2^m)^2-2*(r*2^m)+1]=A*B
> I have not proven that A or B are divisible by
> infinitely many different primes as m varies ,but
> this seems very logical.
> I tried to prove it without success by assuming that
> there is a finite set of primes[p1,p2,,,pj] that
> divide A for every m>1 ,for a specific k.Then i
> used
> as a value for m,m=(p1-1)*(p2-1)*...*(pj-1) and
> tried
> to end up with something absurd.No luck.This is the
> most interesting part of my effort.The k's i found
> produce numbers k*2^n+1,some of which have factors
> belonging to a finite set and some of them have
> factors belonging to the set of primes that divide a
> polynomial.I dont know what step is next.Your
> valuable
> ideas are welcomed
>
> Pavlos
> --- jbrennen <jack@...> wrote:
> > --- In primenumbers@y..., Pavlos N
> <pavlos199@y...>
> > wrote:
> > > I managed to construct a Sierpinski multiplier k
> > such
> > > that k*2^n+1 is always composite for every n>1
> and
> > > there is no finite set of primes that divide
> it.I
> > will
> > > post a more detailed email explaining exactly
> how
> > i
> > > worked and other details.For now on i post my
> > final
> > > result only.The k's belong to the following set
> of
> > > integers:
> > > k=(18446744073709551615*a+2039404931861161240)^4
> > > where a is a positive integer
> >
> > This is a really cool finding. I suspected that
> > such a multiplier
> > (or family of multipliers) was possible, but I
> never
> > thought of
> > using the fact that (4*x^4+1) has an algebraic
> > factorization. I
> > tried looking for k being a perfect cube or a
> fifth
> > power, with
> > no luck. Great work. :)
> >
> > So what we have here is:
> >
> > k*2^n+1 is of the form 4*x^4+1 if n
> > == 2 (mod 4)
> >
> > k mod 3 == 1 -> 3 | k*2^n+1 if n
> > == 1 (mod 2)
> > k mod 17 == 16 -> 17 | k*2^n+1 if n
> > == 0 (mod 8)
> > k mod 257 == 16 -> 257 | k*2^n+1 if n
> > == 4 (mod 16)
> > k mod 65537 == 16 -> 65537 | k*2^n+1 if n
> > == 12 (mod 32)
> > k mod 641 == 16 -> 641 | k*2^n+1 if n
> > == 28 (mod 64)
> > k mod 6700417 == -16 -> 6700417 | k*2^n+1 if n
> > == 60 (mod 64)
> >
> > Putting them together, k*2^n+1 is always
> composite.
> >
> > The requirement for k to be divisible by 5 is to
> > ensure that
> > when n == 2 (mod 4), that k*2^n+1 is not divisible
> > by 5 -- if
> > it is so divisible, then a finite covering set of
> > primes exists.
> >
> > So all that is left is to prove that for at least
> > one k in the
> > given group, no covering set S of primes exists
> such
> > that every
> > k*2^n+1 is divisible by a member of S. Please let
> > us in on this
> > aspect of the finding... How are you able to
> prove
> > the
> > non-existence of a finite covering set? Or is the
> > non-existence
> > of a finite covering set only a conjecture?
> >
> >
> >
> >
>
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Finance - Get real-time stock quotes
> http://finance.yahoo.com
>

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• ... It seems that the proof of having a non-finite covering set for the original composite sierpinski form is mapped into either a proof of a non-finite
Message 5 of 12 , Aug 30, 2002
>
> So all that is left is to prove that for at least one k in the
> given group, no covering set S of primes exists such that every
> k*2^n+1 is divisible by a member of S. Please let us in on this
> aspect of the finding... How are you able to prove the
> non-existence of a finite covering set? Or is the non-existence
> of a finite covering set only a conjecture?

It seems that the proof of having a non-finite covering set for the original
composite sierpinski form is mapped into either a proof of a non-finite
covering set for one of the Aurefeuillian factors or a proof of an infinite
number of primes along either of the Aurefeuillian factors.

Now the former just looks like it converts the original problem into a
tricker form.

The latter requests an infiniteness of primes along an exponentially growing
set of values, and as far as I know no such form has been proven to yield an
infinite number of primes, even if the heuristics indicate that's the case.
The heuristics are more favourable than that for Mersennes, for example, but
heuristics count for little.

To be honest, I think the 'trickier' line of tack looks like the easier one
- either expect something brainstorm-like in the next day or so. (I _think_
I have something that might lead to a proof, but it's early in the morning,
and I can't tell one end of an implication from the other present!)

Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• ... [Brough back on list] Indeed - It s Pavlos baby, and he should certainly put it on as many tables as possible. If I don t see it reach sci.math
Message 6 of 12 , Aug 30, 2002
--- Paul Leyland <pleyland@...> wrote:
> > To be honest, I think the 'trickier' line of tack looks like
> > the easier one
> > - either expect something brainstorm-like in the next day or
> > so. (I _think_
> > I have something that might lead to a proof, but it's early
> > in the morning,
> > and I can't tell one end of an implication from the other present!)
>
> This might now be interesting to throw open to the NMBTHRY people...

[Brough back on list]

Indeed - It's Pavlos' baby, and he should certainly put it on as many tables
as possible. If I don't see it reach sci.math (.research, I don't think Dave
will have any problem accepting it) in the next day or so I shall forward it
on there.

Alas my battle with the infinite is lost. Two monster holes -
No matter how many primes I shoved into a covering set I couldn't
make an infinite one! :-I I was trying to show that for every finite
non-covering set there existed a prime that would be a factor, and not make
the set covering one.

However, this logic would have be more easily applicable to the
Sierpinski/Proth domain, and has failed there, so fails in the new domain
too.

These discrete-log-based sieves are a pain in the neck!

The interesting thing about these Aurefeuillian factorisations is that the
divisibility properties are both quadratic and discrete-log based, which
means that you get a sieving removal ratio of either 0 or 2b/(p-1) where b
is related to O2(p), depending on the discriminant of the quadratic.
e.g. consider the + factor and the prime 41, it divides terms
(n-2)/4=6,11,26,31,46,51... .
A quadratic sieve divides (0 or 2)/(p-1) and a discrete-log sieve divides
1/(factor of p-1), but this combines the two.

On the infiniteness of primes front, with all these double-barreled factors,
the density looks somewhat sparse: (n-2)/4 = 32, 53, 92, 109, 110, 137, 302,
401, 1205, 1241... for the + factor.

Ah well, it's nice to spin one's wheels and make doughnuts occasionally.
Hmmm, donuts!

Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• ... Note that there are infinitely many primes that divide k*2^n+1 for the specific k s as n varies is _not_ the equivalent of there being no finite covering
Message 7 of 12 , Aug 30, 2002
--- Pavlos N <pavlos199@...> wrote:
> I finally was able to prove that no finite covering
> set exists,that is,there are infinitely many primes
> that divide k*2^n+1 for the specific k's as n
> varies.The proof is available on request

Note that "there are infinitely many primes that divide k*2^n+1 for the
specific k's as n varies" is _not_ the equivalent of there being no finite
covering set. (I know the "that is" was probably informative rather than
definitive, but when proofs are concerned all ambiguities should be cleared
up.)

Can you please upload the proof to the yahoogroup files area, so interested
parties such as myself, Jack, Paul etc. can have a peek?

Cheers,
Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• Note that there is a subset of Pavlos numbers which do in fact have a finite covering set, and that this subset has positive density. The following covering
Message 8 of 12 , Aug 30, 2002
Note that there is a subset of Pavlos' numbers which do in fact have
a finite covering set, and that this subset has positive density.

The following covering set can be used to construct a value of
k=z^4 for which k*2^(4n+2)+1 is always divisible by at least one
member of the set:

13, 37, 73, 109, 241, 97, 673

The order of 16 modulo each of these primes is:

3, 9, 9, 9, 6, 12, 12

One such example would be where

z == 43765077179683 (mod 60214110539557)

So combining this with Pavlos' condition...

z == 1097007512506034898075831581637010
(mod 1110754286749264941174792190734555)

implies that k=z^4 is in Pavlos' set, yet has a finite covering set.

A quick check in PARI/GP:

m=2^64-1;
z=1097007512506034898075831581637010;
k=z^4;
ss=(m/5)*(13*37*73*109*241*97*673);
print("z mod ",m," == ",z%m);
for(n=0,9999,if(gcd(k*2^n+1,ss)==1,print("Failure")))
• Just looked in between trips. Skipping predictable Brown trash, I saw a really _neat_ thing by Pavlos Saridis: To make N=k*2^n+1 always composite [Saridis]: a)
Message 9 of 12 , Aug 31, 2002
Just looked in between trips. Skipping predictable
Brown trash, I saw a really _neat_ thing by
Pavlos Saridis:

To make N=k*2^n+1 always composite [Saridis]:

a) take k=x^4 so that for n=4*s+2 we have an
algebraic factorization

N=(2*y^2-2*y+1)*(2*y^2+2*y+1) with y=2^s*x

b) find a covering set for n != 2 mod 4

c) if desired, make x=0 mod 5, so that p=5
does not cover what you did with Aurifeuille in (a)

Question: What is the smallest k=x^4 for which
this can be done, with and without the grace note (c)?

Back in a few weeks time...

David
Your message has been successfully submitted and would be delivered to recipients shortly.