 Prime numbers and primality testing

 Restricted Group,
 1101 members
Re: primes of the form x^3  y^2
Expand Messages
 View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
cino hilliard <hillcino368@...> wrote:
> 3, 5, 17, 29, 31, 37, 41, 43, 59, 73, 97,
for primes p such that x^3  p is conjecturally never
> 101, 103, 113, 131, 137, 149, 157, 163 ...
a square for integer x.
To prove that there are no integral points on the
elliptic curves x^3 = y^2 + p, for those primes,
you might need to compute their MordellWeil groups:
http://www.springerlink.com/content/p80721u575l12047/
www.dpmms.cam.ac.uk/AlgebraicNumberTheory/0086/paper.ps
There are 21 integral points with y > 0 on the elliptic curve
x^3 = y^2 + 28279
with a MordellWeil group of rank 5, namely those with
x = 32, 34, 40, 50, 67, 70, 122, 260, 295, 359, 515, 592,
952, 2284, 2327, 2410, 7330, 7580, 11702, 130184, 26507590.
David  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
"David Broadhurst" <d.broadhurst@...> wrote:
> There are 21 integral points with y > 0 on the elliptic curve
http://magma.maths.usyd.edu.au/calc/
> x^3 = y^2 + 28279
> with a MordellWeil group of rank 5, namely those with
> x = 32, 34, 40, 50, 67, 70, 122, 260, 295, 359, 515, 592,
> 952, 2284, 2327, 2410, 7330, 7580, 11702, 130184, 26507590.
enabled me to show that there are no more:
Input:
E := EllipticCurve([0, 28279]);
Q, reps := IntegralPoints(E);
Q;
Output:
[ (34 : 105 : 1), (40 : 189 : 1), (70 : 561 : 1),
(32 : 67 : 1), (50 : 311 : 1), (67 : 522 : 1),
(122 : 1337 : 1), (260 : 4189 : 1), (295 : 5064 : 1),
(592 : 14403 : 1), (952 : 29373 : 1), (359 : 6800 : 1),
(515 : 11686 : 1), (2284 : 109155 : 1), (2410 : 118311 : 1),
(2327 : 112252 : 1), (7330 : 627561 : 1), (7580 : 659939 : 1),
(11702 : 1265873 : 1), (130184 : 46971715 : 1),
(26507590 : 136475711439 : 1) ]
The CPUtime was comfortably below the 20 second limit:
> Total time: 7.219 seconds, Total memory usage: 137.04MB
David
 View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
cino hilliard <hillcino368@...> wrote:
> My gut is x^3y^2 = 101,103 and others are out there but we
E := EllipticCurve([0, 101]);
> will not have the time to find them in this BB universe.
Q, reps := IntegralPoints(E);
Q;
[]
Total time: 0.370 seconds, Total memory usage: 137.04MB
But for x^3y^2=149, Magma issues a warning:
E := EllipticCurve([0, 149]);
Q, reps := IntegralPoints(E);
Q;
Warning: rank computed (0) is only a lower bound
(It may still be correct, though)
[]
Total time: 0.340 seconds, Total memory usage: 61.95MB
PS: It seems that Sm*r*nd*ch* once conjectured that there
are no rational points on x^3 = y^2 + 7, somehow
overlooking the fact that 2^3 = 1^2 + 7:
www.articlearchives.com/asia/northernasiachinasouth/9510721.html
David  View Source
 0 Attachment
Off list, Tony Noe kindly provided this link:
http://www.research.att.com/~njas/sequences/A081120
From the table attached thereto, one may conclude that
Cino's sequence, "Primes not of the form x^3  y^2", begins
3, 5, 17, 29, 31, 37, 41, 43, 59, 73, 97, 101, 103, 113, 131,
137, 149, 157, 163, 173, 179, 181, 197, 211, 227, 229, 241,
257, 263, 269, 281, 283, 311, 313, 317, 331, 337, 347, 349,
353, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 443,
449, 457, 461, 467, 479, 491, 509, 521, 523, 541, 563, 569,
571, 577, 601, 607, 613, 617, 619, 641, 643, 653, 659, 661,
677, 691, 701, 709, 733, 739, 743, 751, 757, 761, 773, 787,
809, 811, 821, 823, 827, 829, 839, 853, 857, 863, 877, 881,
883, 907, 911, 929, 937, 941, 947, 953, 967, 977, 983, 997 ...
This paper appears to have open access:
http://tinyurl.com/mtvsn5
See Section 5.1 for Cino's record holder, p = 28279,
with 21 integral points.
David  View Source
 0 Attachment
Hi David,
The elliptic functions in Pari are forboding at least to me.
I contacted the Pari group and got a workaround for eliptic curves from
Karim. He gave the following to find solutions for x^3y^2 = p.
diffcubes(n,p)=local(x,y);setintersect(vector(n,x,x^3p),vector(n,y,y^2))
which we found out will work in the next version of Pari. :)
So Karim wrote:
> For "older" versions than that, use
Ok, I did it my way with this and asked a question at the end.
>
> setintersect(Set(vector(n,x,x^3p)), Set(vector(n,y,y^2)))
>
> ( slower but not *much* slower... )
The timing aint bad. Magma and Sage would probably be faster offline.
We need a way of knowing upper bounds a priori though.
> diffcubes(n,p) =
Thanks for all your work,
> {
> local(j,x,y,c);
> a=eval(setintersect(Set(vector(n,x,x^3p)), Set(vector(n,y,y^2))));
> c=length(a);
> a=vecsort(a);
> for(j=1,c,
> y=round(sqrt(a[j])); \\ this could be iffy
> x=round((a[j]+p)^(1/3));
> print(j": "x"^3  "y"^2 = "p); \\ Too fancy? Change it.
> );
> c;
> }
>
>
>(14:51:50) gp > diffcubes(300000,431)
>1: 8^3  9^2 = 431
>2: 11^3  30^2 = 431
>3: 20^3  87^2 = 431
>4: 30^3  163^2 = 431
>5: 36^3  215^2 = 431
>6: 138^3  1621^2 = 431
>7: 150^3  1837^2 = 431
>8: 575^3  13788^2 = 431
>9: 3903^3  243836^2 = 431
>(15:02:35) gp > ##
> *** last result computed in 2,250 ms.
>(15:02:39) gp >
>
>This finds all instances because I new a prori 243836 was the big kahuna.
>I guess it will still be trial and error?
>
>Oh well, we are at least 2 quanta over what I had.
>
> Thank you >>>
>Cino
Cino
To: primenumbers@yahoogroups.com
From: d.broadhurst@...
Date: Thu, 18 Jun 2009 16:26:36 +0000
Subject: [PrimeNumbers] Re: primes of the form x^3  y^2
Off list, Tony Noe kindly provided this link:
http://www.research.att.com/~njas/sequences/A081120
From the table attached thereto, one may conclude that
Cino's sequence, "Primes not of the form x^3  y^2", begins
3, 5, 17, 29, 31, 37, 41, 43, 59, 73, 97, 101, 103, 113, 131,
137, 149, 157, 163, 173, 179, 181, 197, 211, 227, 229, 241,
257, 263, 269, 281, 283, 311, 313, 317, 331, 337, 347, 349,
353, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 443,
449, 457, 461, 467, 479, 491, 509, 521, 523, 541, 563, 569,
571, 577, 601, 607, 613, 617, 619, 641, 643, 653, 659, 661,
677, 691, 701, 709, 733, 739, 743, 751, 757, 761, 773, 787,
809, 811, 821, 823, 827, 829, 839, 853, 857, 863, 877, 881,
883, 907, 911, 929, 937, 941, 947, 953, 967, 977, 983, 997 ...
This paper appears to have open access:
http://tinyurl.com/mtvsn5
See Section 5.1 for Cino's record holder, p = 28279,
with 21 integral points.
David
[Nontext portions of this message have been removed]  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
cino hilliard <hillcino368@...> wrote:
> I contacted the Pari group and got a workaround
How does it compare with the brute force of
> for eliptic curves from Karim.
"issquare" for the largest integer point on
x^3  y^2 = 22189
I wonder?
The result is already published, but I thought
that it might be an interesting test case.
Here is an "issquare" timing:
c=0;gettime;
{for(x=1,10^9,if(issquare(x^322189),
print(x);c=c+1;if(c==2,break)))}
print(ceil(gettime/10^3)" seconds")
29585
140292677
98 seconds
David  View Source
 0 Attachment
>
_________________________________________________________________
>
> the collatz function to it as in f(n) = 3n+1/2 if n is odd
>
> and f(n) = n/2 n is even.
>
> Consider the number 33
>
>
>
> 33, 100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
>
>
>
> The odd numbers are 33, 25 ;19,29 ,11 ,17 ,13 ,5 and so on.
>
>
>
> As u can see 6 numbre prime : 19 ;29; 11 ;17 ; 13; 5 .
>
>
>
> I believe that the collatz function can be used as a prime generating function though i am not very sure in this.
>
>
>
> i have found n = 111012973909 is the largest integer with all odd are prime
>
>
>
> 111012973909, 333038921728, 166519460864, 83259730432, 41629865216, 20814932608, 10407466304, 5203733152, 2601866576, 1300933288, 650466644, 325233322, 162616661, 487849984, 243924992, 121962496, 60981248, 30490624, 15245312, 7622656, 3811328, 1905664, 952832, 476416, 238208, 119104, 59552, 29776, 14888, 7444, 3722, 1861, 5584, 2792, 1396, 698, 349, 1048, 524, 262, 131, 394, 197, 592, 296, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
>
>
>
> all odd are prime : 111012973909 ; 162616661 ; 1861 ; 349 ; 131 ; 197 ; 37 ; 7 ;11 ; 17 ; 13 ; ; 5
>
>
>
> rachid
>
Découvrez Windows Live Spaces et créez votre site Web perso en quelques clics !
http://spaces.live.com/signup.aspx
[Nontext portions of this message have been removed]  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
sta staf <sta_staf@...> wrote:
> i have found n = 111012973909 is the largest integer
The word "largest" makes no sense here.
> with all odd are prime
The 271digit prime (5*2^8971)/3 manifestly contains no
composite odd integer in its Collatz sequence and it would be
easy to find larger primes by this, or a similar, construction.
David  View Source
 0 Attachment
yes but also the 271figit prime (5*2^8971)/3 makes no sense here
you think (5*2^8971)/3) = prime numbre !!!!!!!!!!!
give me n integer 111012973909 < n < 2^50 with all odd integer are prime .
becuse we canot test the sequnce :(5*2^8971)/3
thanks
rachid
_________________________________________________________________
Vous voulez savoir ce que vous pouvez faire avec le nouveau Windows Live ? Lancezvous !
http://www.microsoft.com/windows/windowslive/default.aspx
[Nontext portions of this message have been removed]  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
sta staf <sta_staf@...> wrote:
> the 271figit prime (5*2^8971)/3 makes no sense here
to which I calmly reply, that I do so think.
> you think (5*2^8971)/3) = prime numbre !!!!!!!!!!!
Here is my proof, using APRCL in PariGP:
N=(5*2^8971)/3;
if(isprime(N),print(OK))
OK
It appears that coherence is in inverse proportion
to the number of exclamation marks used by the poster.
David (with no exclamation marks)  View Source
 0 Attachment
but your seqaunce :(5*2^8971/3)
this sequance of coltaze is : all Even numbers .
the only odd is the ferst digit : :(5*2^8971/3)
rachid
_________________________________________________________________
Découvrez toutes les possibilités de communication avec vos proches
http://www.microsoft.com/windows/windowslive/default.aspx
[Nontext portions of this message have been removed]  View Source
 0 Attachment
Hi,
>> In primenumbers@yahoogroups.com,
the workaround,
>>cino hilliard <hillcino368@...> wrote:
>> I contacted the Pari group and got a workaround
>> for eliptic curves from Karim.
diffcubes2(n,p) =
{
local(x,y,c,a);
a=eval(setintersect(Set(vector(n,y,y^2)),Set(vector(n,x,x^3p))));
a;
}
is useless for large n. Maybe someone can tweek.
(10:25:03) gp > diffcubes2(10000000,22189)
*** Set: the PARI stack overflows !
current stack size: 800000000 (762.939 Mbytes)
[hint] you can increase GP stack with allocatemem()
>How does it compare with the brute force of
elipissq(n) =
>"issquare" for the largest integer point on
>x^3  y^2 = 22189
>I wonder?
>c=0;gettime;
>{for(x=1,10^9,if(issquare(x^322189),
>print(x);c=c+1;if(c==2,break)))}
>print(ceil(gettime/10^3)" seconds")
>29585
>140292677
>98 seconds
{
c=0;
for(x=1,10^9,if(issquare(x^3n),
print(x);c=c+1;if(c==2,break)));
}
Pari 2.3.4
dell 8200 2.53 ghz xp pro
42 minutes. say what?
Pari 2.4.2
dell 8200 2.53 ghz xp pro
225 sec Go figure. They must have done some stuff on issquare in v2.4.2.
Pari 2.4.2
dell 6x620 3.2 ghz vista ult 64 bit op sys
112 sec close to David's bench.
Sage online calculator
http://www.sagenb.com/home/hillcino368/0/
sage: time EllipticCurve([0,0,0,0,22189]).integral_points()
[(29585 : 5088706 : 1), (140292677 : 1661699554612 : 1)]
Time: CPU 0.22 s, Wall: 0.87 s
A tough and user friendly program.
I wonder why Pari has not implemented the Mordell algorithm. Maybe 2.4.3?
Perhaps someone here can write a script or show a c program with gmp that
does this. A gcc/gmp would be great.
Dénouement
A child playing in a room with toys could solve the riddle of the difference between
two squares by arranging toy blocks and counting. Later he could puzzle with numbers
by squaring, subtracting, noticing patterns and conjecturing. For any positive numbers
a,b, a^2  b^2 = (ab)*(a+b). Later, he finds out how to symbolically multiply
(ab)*(a+b) to get a^2b^2 proving his prior conjectures correct.
So a^2  b^2 =(ab)*(a+b) could be the third most fundamental process in arithmetic
the average being second and counting being first. It is that easy of a riddle.
Then later, the child goes into another room with more blocks. He starts making pyramids,
cubes, and squares. Suddenly, with a flash of insight, he about cube  square = number
or a^3  b^2 = n? It is not that easy of a riddle.
I doubt my Mathematica I bought in 80's and Maple in the 90's does this as Sage.
Maybe the latest versions do.
[Rant]
It is disheartning that students can get these for $125 and seniors only get 1/2 off
of retail ($2000) for Mathematica.
[End Rant]
Cheers and Roebuck,
Cino
[Nontext portions of this message have been removed]  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
cino hilliard <hillcino368@...> wrote:
> the workaround,
As indeed I had expected :)
> diffcubes2(n,p) =
> {
> local(x,y,c,a);
> a=eval(setintersect(Set(vector(n,y,y^2)),Set(vector(n,x,x^3p))));
> a;
> }
> is useless for large n.
Sometimes brute force is best, as in my prior hack:
c=0;gettime;
{for(x=1,10^9,if(issquare(x^322189),
print(x);c=c+1;if(c==2,break)))}
print(ceil(gettime/10^3)" seconds")
29585
140292677
98 seconds
Thanks, Cino, for your fascinating thread, which
probes deeply into the theory of elliptic curves.
Best regards
David  View Source
 0 Attachment
Hello Rachid,
Even if this was true:> this sequance of coltaze is : all Even numbers .
It'd still satisfy the property you're expecting it to satisfy: "All odd
> the only odd is the ferst digit : :(5*2^8971/3)
terms of the sequence are primes."
However, unless I'm very much mistaken, the sequence looks like this:
(5*2^8971)/3, 5*2^896, 5*2^895, ..., 5*2^2, 5*2^1, 5, 8, 4, 2, 1 and as
far as my memory goes, the term "5" looks like an odd prime to me.
However, as you wanted a small example of this kind (< 2^50), consider
297784399189. Any objections against it?
Peter

[Name] Peter Kosinar [Quote] 2B  ~2B = exp(i*PI) [ICQ] 134813278  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
sta staf <sta_staf@...> wrote,
untidily and incorrectly:
> but your seqaunce :(5*2^8971/3)
Dear Rachid: Until you learn to be more disciplined,
> this sequance of coltaze is : all Even numbers .
> the only odd is the ferst digit : :(5*2^8971/3)
> rachid
I shall no longer reply. Please isolate your error
in the above statement, bearing in mind that 5
is an odd prime. Then consider that you asked
only for a Collatz sequence in which no odd
member is composite, with which request my
simple construction perfectly complies.
Discipline is a stern master:
I shall not allow you to "wriggle"
out of the hole you have carelessly
and untidily dug yourself into.
You may think me stern. But please recall
that mathematics is far sterner than I am.
Stay well,
David  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
"David Broadhurst" <d.broadhurst@...> wrote:
> The 271digit prime (5*2^8971)/3 manifestly contains no
After reading http://www.primepuzzles.net/puzzles/puzz_476.htm
> composite odd integer in its Collatz sequence and it would be
> easy to find larger primes by this, or a similar, construction.
Rachid will perhaps not object to my next claim, namely that
(2^1322*(5*2^8971)/31)/3 is a 668digit prime whose Collatz
sequence contains no composite odd integer.
As both Jens and I have noted, left extensibility is trivial,
given enough computing power. Hence my comment to Rachid:
> The word "largest" makes no sense here.
David
 View Source
 0 Attachment
** For Your Eyes Only **
** High Priority **
the agent never got back to me, in spite of three different demands
I assume they sold it
I looked at another one so I may decide to move after all.
I trust & hope your vacation be goo

ξε ν’, γγέλλειν Λακεδαιμονίοις ἀ ὅτι τ δε
κείμεθα, το ς κείνων ῥήμασι πειθόμενοι.
/begin/read__>sig.file: postal address
palma
University of KwaZuluNatal Philosophy
3rd floor of Memorial Tower Building
Howard College Campus
Durban 4041
South Africa
Tel off: [+27] 031 2601591 (sec: Mrs. Yolanda Hordyk) [+27]
0312602292
Fax [+27] 0312603031
mobile 07 62 36 23 91 calling from overseas +[27] 76 2362391
EMAIL: palma@...
EMAIL: palma@...
MY OFFICE # IS 290@Mtb
*only when in Europe*: inst. J. Nicod
29 rue d'Ulm
f75005 paris france
email me for details if needed at palma@...
________
This email message (and attachments) is confidential, and/or
privileged and is intended for the
use of the addressee only. If you are not the intended recipient of
this email you must not copy,
distribute, take any action in reliance on it or disclose it to anyone.
Any confidentiality or
privilege is not waived or lost by reason of mistaken delivery to you.
This entity is not responsible for any information not related to the
business of this entity. If you
received this email in error please destroy the original and notify
the sender.d>>> "David Broadhurst" <d.broadhurst@...> 6/20/2009 3:39 PM >>>
 In primenumbers@yahoogroups.com (
mailto:primenumbers%40yahoogroups.com ),
"David Broadhurst" <d.broadhurst@...> wrote:
> The 271digit prime (5*2^8971)/3 manifestly contains no
After reading http://www.primepuzzles.net/puzzles/puzz_476.htm (
> composite odd integer in its Collatz sequence and it would be
> easy to find larger primes by this, or a similar, construction.
http://www.primepuzzles.net/puzzles/puzz_476.htm )
Rachid will perhaps not object to my next claim, namely that
(2^1322*(5*2^8971)/31)/3 is a 668digit prime whose Collatz
sequence contains no composite odd integer.
As both Jens and I have noted, left extensibility is trivial,
given enough computing power. Hence my comment to Rachid:
> The word "largest" makes no sense here.
David
Please find our Email Disclaimer here: http://www.ukzn.ac.za/disclaimer/
[Nontext portions of this message have been removed]  View Source
 0 Attachment
you have the right david there is always another prime can often be extended to the left
like your numbre :(2^1322*(5*2^8971)/31)/3)
is a Construction Sequence . very easy to Making the collatz sequence contains no composite odd integer.
yes ( The word "largest" makes no sense here)
rachid
_________________________________________________________________
Vous voulez savoir ce que vous pouvez faire avec le nouveau Windows Live ? Lancezvous !
http://www.microsoft.com/windows/windowslive/default.aspx
[Nontext portions of this message have been removed]  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
sta staf <sta_staf@...> wrote:
> you have the right david there is always another prime
En Angleterre, nous avons l'habitude de tirer à gauche.
> can often be extended to the left
> like your numbre : (2^1322*(5*2^8971)/31)/3
Amitiés
David  View Source
 0 Attachment
Hi,
I did a brute force in gcc/gmp.
http://groups.google.com/group/ellipticcurves/web/gccgmpbruteforceellipticcurve
Output:
n start => 22189
n stop => 22189
x range => 150000000
max dups => 1
n prime => 1
29585 22189 5088706
140292677 22189 1661699554612
count = 2
31.9994
for dell 8200 2.53 ghz
24.9 sec
for dell gx620 3.2 ghz vista ult
Working with a developer of sage I was pointed to ratpoints.
>> http://www.mathe2.unibayreuth.de/stoll/programs/index.html, is free
I installed gmp 4.3.1 with msys which was used for the above timings.
>> (GPL) and only requires gmp.
>> ratpoints looks promising but I can't install it. Using Msys, I keep getting
>> the cannot find lgmp.
I searched long for this. There ain't much out there on it. In fact, google lgmp
gets a no hit.
Still asking, how do we determine the x range for ratpoints and how does sage
do it?
Reply:
>ratpoints takes 0.09s to fine all integral points with x<10^8! But
Maybe someone in primenumbers can load ratpoints in a windows xp pro of vista
>there is no proof, which Sage provides. Sage takes longer as the
>curve has rank 5.
>I cannot help with Windows problems. gmp is a standard library (Gnu
>MultiPrecision) but I do not know how to use it on Windows.
>Very soon ratpoints will be available within Sage  we are just testing it now.
platform.
Anyway, the gcc/gmp brute force is considerably faster than Pari for x range 10^810^9.
Cino
To: primenumbers@yahoogroups.com
From: d.broadhurst@...
Date: Fri, 19 Jun 2009 23:14:46 +0000
Subject: [PrimeNumbers] Re: primes of the form x^3  y^2
 In primenumbers@yahoogroups.com,
cino hilliard <hillcino368@...> wrote:
> the workaround,
As indeed I had expected :)
> diffcubes2(n,p) =
> {
> local(x,y,c,a);
> a=eval(setintersect(Set(vector(n,y,y^2)),Set(vector(n,x,x^3p))));
> a;
> }
> is useless for large n.
Sometimes brute force is best, as in my prior hack:
c=0;gettime;
{for(x=1,10^9,if(issquare(x^322189),
print(x);c=c+1;if(c==2,break)))}
print(ceil(gettime/10^3)" seconds")
29585
140292677
98 seconds
Recent Activity
3
New MembersVisit Your Group
Give Back
Yahoo! for Good
Get inspired
by a good cause.
Y! Toolbar
Get it Free!
easy 1click access
to your groups.
Yahoo! Groups
Start a group
in 3 easy steps.
Connect with others.
.
[Nontext portions of this message have been removed]  View Source
 0 Attachment
 In primenumbers@yahoogroups.com,
cino hilliard <hillcino368@...> wrote:
> Sage takes longer as the curve has rank 5.
Sage is being sagacious, here.
It's good that you can access
such wisdom without paying big
dollars for Magma.
Congrats to Cino, for persistence.
David
Your message has been successfully submitted and would be delivered to recipients shortly.