Prime numbers and primality testing is a Restricted Group with 1137 members.
Yahoo Groups
 
FW: Re: [PrimeNumbers] Re: adding to prime number 


James Merickel

Message 1 of 28 , Sep 19, 2011 

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

----Forwarded Message----
From: merk7777777@...
To: jens.k.a@...
Sent: Mon Sep 19th, 2011 3:25 AM PDT
Subject: Re: [PrimeNumbers] Re: adding to prime number

This is a challenge modestly related to this subject: Find the next prime, p, after 149 such that the smallest sum of two products wherein all primes through p appear exactly once is prime. [The number corresponding to 149 was momentarily an accepted curio at Prime Curios! prior to the hacking misfortune.]
JGM


djbroadhurst

Sep 19, 2011 

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

--- In primenumbers@yahoogroups.com,
James Merickel <merk7777777@...> wrote:

> Find the next prime, p, after 149 such that
> the smallest sum of two products wherein all
> primes through p appear exactly once is prime.

A relevant sequence is given in
http://oeis.org/A182987
where the first element should be 3, in my opinion.

The first 15 primes of this kind are easily found:
3, 5, 11, 29, 97, 347, 1429, 6229, 29873, 160879, 895681,
34885673, 1568299433, 47241542381273, 3036819365023723883.

James is asking for another prime in A182987.

His confusing comment:

> [The number corresponding to 149 was momentarily an accepted
> curio at Prime Curios! prior to the hacking misfortune.]

seems to be a typically unhelpful red herring, since

77257552405943571156935712611
= 3*7*29*31*37*43*47*59*61*67*73*79*89*97*127*131*137
+ 2*5*11*13*17*19*23*41*53*71*83*101*103*107*109*113*139*149

is the composite number

183059*395061580271*1068279914399.

I believe that no-one yet knows the 16th prime in A182987.

David Broadhurst


mikeoakes2

Sep 20, 2011 

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

--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> --- In primenumbers@yahoogroups.com,
> James Merickel <merk7777777@> wrote:
> 
> > Find the next prime, p, after 149 such that
> > the smallest sum of two products wherein all
> > primes through p appear exactly once is prime.
> 
> A relevant sequence is given in
> http://oeis.org/A182987
> where the first element should be 3, in my opinion.

3 because 0#=1, or why??

> The first 15 primes of this kind are easily found:
> 3, 5, 11, 29, 97, 347, 1429, 6229, 29873, 160879, 895681,
> 34885673, 1568299433, 47241542381273, 3036819365023723883.
> 
> James is asking for another prime in A182987.
> 
> His confusing comment:
> 
> > [The number corresponding to 149 was momentarily an accepted
> > curio at Prime Curios! prior to the hacking misfortune.]
> 
> seems to be a typically unhelpful red herring, since
> 
> 77257552405943571156935712611
> = 3*7*29*31*37*43*47*59*61*67*73*79*89*97*127*131*137
> + 2*5*11*13*17*19*23*41*53*71*83*101*103*107*109*113*139*149
> 
> is the composite number
> 
> 183059*395061580271*1068279914399.

Impressive result, David.
Did you enumerate all 2^35 partitions, or were you more cunning than that?

Mike


James Merickel

Sep 20, 2011 

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

David, I stand corrected on this. I have a somewhat larger (prime) number, and what was wrong with my program is lost to time.

Dr. Honaker, I believe this was my submission on 149. You will please withdraw that one.


djbroadhurst

Sep 20, 2011 

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

--- In primenumbers@yahoogroups.com, 
"mikeoakes2" <mikeoakes2@...> wrote:

> > 77257552405943571156935712611
> > 3*7*29*31*37*43*47*59*61*67*73*79*89*97*127*131*137
> > + 2*5*11*13*17*19*23*41*53*71*83*101*103*107*109*113*139*149
>
> Impressive result, David.
> Did you enumerate all 2^35 partitions, 
> or were you more cunning than that?

2^35 partitions would take more than 6 milliseconds :-)

{n=35;m=prod(k=1,n,prime(k));a=2*sqrtint(m)+1;b=0;
while(!b,if(issquare(a^2-4*m,&b),print(a),a+=2));
print(factor((a+b)/2)[,1]~);print(factor((a-b)/2)[,1]~);
print("took "gettime" milliseconds");}

77257552405943571156935712611
[3, 7, 29, 31, 37, 43, 47, 59, 61, 67, 73, 79, 89, 97, 127, 131, 137]
[2, 5, 11, 13, 17, 19, 23, 41, 53, 71, 83, 101, 103, 107, 109, 113, 139, 149]
took 6 milliseconds

The continuation of http://oeis.org/A182987 is as follows:

30519656902298784043,
309740688505242652849,
3203982595205562774973,
33450560343160551726409,
355584333965475029353457,
4007231932061350599162707,
45864865814809825555344421,
536834490807772152111396143,
6329185303212156752880603539,
77257552405943571156935712611.

I do not yet know the 36th element. 

David


djbroadhurst

Sep 20, 2011 

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

--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:

> The continuation of http://oeis.org/A182987 is as follows:
> 
> 30519656902298784043,
> 309740688505242652849,
> 3203982595205562774973,
> 33450560343160551726409,
> 355584333965475029353457,
> 4007231932061350599162707,
> 45864865814809825555344421,
> 536834490807772152111396143,
> 6329185303212156752880603539,
> 77257552405943571156935712611.
> 
> I do not yet know the 36th element. 

The 36th is still unknown to me.
The 37th is the composite number
11895405330415184274516467070659. 

David


Maximilian Hasler

Sep 20, 2011 

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

concerning A182987 : Let p(S) be product of integers in S. a(n) is
minimum of p(S_1) + p(S_2) over all partitions of first n primes into
sets S_1 and S_2.

I am not sure about the recent "correction",
since according to the definition I know (and also the one on wikipedia),
a partition cannot contain the empty set.

So, for n=1, the set S = { 2 } containing the first prime does not
admit any partition with two subsets, therefore the term a(1) = min {}
(empty set) which not well defined (while the inf would be defined
to be +oo).

and for n=3, S={ 2,3,5 } only admits the 2-subset partitions
{{2,3],{5}} and {{2},{3,5}} and {{2,5],{3}}.


Maximilian








djbroadhurst

Sep 20, 2011 

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

--- In primenumbers@yahoogroups.com, 
Maximilian Hasler <maximilian.hasler@...> wrote:

> concerning A182987 : Let p(S) be product of integers in S. 
> a(n) is minimum of p(S_1) + p(S_2) over all partitions of 
> first n primes into sets S_1 and S_2.
> 
> I am not sure about the recent "correction",
> since according to the definition I know 
> (and also the one on wikipedia),
> a partition cannot contain the empty set.
> 
> So, for n=1, the set S = { 2 } containing the first prime does not
> admit any partition with two subsets, therefore the term 
> a(1) = min {} (empty set) which not well defined (while the inf 
> would be defined)

Your problem may be disambiguated by this defintion:

"smallest positive integer such that a[n]^2-4*A002110[n] is a square"

Then a[0]=2, a[1]=3, and all the rest coincide with the present 
verbose definition.

David


Maximilian Hasler

Sep 20, 2011 

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

OK, then we can also say:
The least A+B such that A*B = Pn#.
(With the explicit formula: A, B equal to the two "middle" divisors of Pn #.)
BTW, I think this is preferrable for its simplicity....

Maximilian








djbroadhurst

Sep 20, 2011 

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

--- In primenumbers@yahoogroups.com, 
Maximilian Hasler <maximilian.hasler@...> wrote:

> The least A+B such that A*B = Pn#.

The least positive integer A+B such that A*B = Pn#.
Else, a[2] = -7 :-)

David


Phil Carmody

Sep 20, 2011 

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

--- On Tue, 9/20/11, Maximilian Hasler <maximilian.hasler@...> wrote:
> concerning A182987 : Let p(S) be
> product of integers in S. a(n) is
> minimum of p(S_1) + p(S_2) over all partitions of first n
> primes into
> sets S_1 and S_2.
> 
> I am not sure about the recent "correction",
> since according to the definition I know (and also the one
> on wikipedia),
> a partition cannot contain the empty set.
> 
> So, for n=1, the set S = { 2 } containing the first prime
> does not
> admit any partition with two subsets, therefore the term
> a(1) = min {}
>   (empty set) which not well defined (while the inf
> would be defined to be +oo).
> 
> and for n=3, S={ 2,3,5 } only admits the 2-subset
> partitions
> {{2,3],{5}} and {{2},{3,5}} and {{2,5],{3}}.
> 
> 
> Maximilian

I have added this comment to the (non-public) notes on the OEIS:
"""
The original submission clearly needed some changes.
Having dealt with these "partitionin primes into 2 sets" situations, where the sets subsequently have their product taken, many times over the last decade or so (it's a standard construct for generating numbers with an excluded set of factors), I think every one I've encountered has permitted one of the sets to be empty (thus providing the specific case of "product of all primes plus 1"). The original submitter clearly wanted empty sets to be included. So empty sets should be included.
Most importantly - for the first term - what are the a and b that sum to 2 and have product 2?
"""

Phil


Phil Carmody

Sep 20, 2011 

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

--- On Tue, 9/20/11, djbroadhurst <d.broadhurst@...> wrote:
> "mikeoakes2" <mikeoakes2@...> wrote:
> 
> > > 77257552405943571156935712611
> > > 3*7*29*31*37*43*47*59*61*67*73*79*89*97*127*131*137
> > > + 2*5*11*13*17*19*23*41*53*71*83*101*103*107*109*113*139*149
> >
> > Impressive result, David.
> > Did you enumerate all 2^35 partitions, 
> > or were you more cunning than that?
> 
> 2^35 partitions would take more than 6 milliseconds :-)

You wouldn't need to look at all of them. If Prod(S1)>sqrt(N#), then 
you wouldn't need to look at S1 union anything. However, it's still probably a fair bit of work, and not worth the effort when:

> {n=35;m=prod(k=1,n,prime(k));a=2*sqrtint(m)+1;b=0;
> while(!b,if(issquare(a^2-4*m,&b),print(a),a+=2));
> print(factor((a+b)/2)[,1]~);print(factor((a-b)/2)[,1]~);
> print("took "gettime" milliseconds");}

... Fermat's method, without any Knuthian sieve boost (was that "Method E", it's been too long since I read that section) does the job. With the sieves too, I'm pretty sure this method has legs for a fair few steps.

It does seem unsatisfying, though. There ought to be a diagonal-walking method. Where you split the primes into left and right halves, and then partition each of those separately. I suspect that making (Prod(L1)/Prod(L2))*(Prod(R2)/Prod(R1)) as close to 1 as possible is the way to go.

Phil


mikeoakes2

Sep 21, 2011 

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

--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> 2^35 partitions would take more than 6 milliseconds :-)
> 
> {n=35;m=prod(k=1,n,prime(k));a=2*sqrtint(m)+1;b=0;
> while(!b,if(issquare(a^2-4*m,&b),print(a),a+=2));
> print(factor((a+b)/2)[,1]~);print(factor((a-b)/2)[,1]~);
> print("took "gettime" milliseconds");}
> 
> 77257552405943571156935712611
> [3, 7, 29, 31, 37, 43, 47, 59, 61, 67, 73, 79, 89, 97, 127, 131, 137]
> [2, 5, 11, 13, 17, 19, 23, 41, 53, 71, 83, 101, 103, 107, 109, 113, 139, 149]
> took 6 milliseconds

You have only used the fact that a cannot be divisible by 2.
In fact, it cannot be divisible by any prime(k), k=1..n.
This should give a speed-up of at least 2 (for n>3).

Mike


djbroadhurst

Sep 21, 2011 

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

--- In primenumbers@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> You have only used the fact that a cannot be divisible by 2.
> In fact, it cannot be divisible by any prime(k), k=1..n.

Indeed.

Puzzle 151: Let a[151] be the smallest positive integer of 
the form a[151] = x + y with x*y = 151#. Is a[151] prime?

Comment: I believe that a[151] is indeed prime, but would
like confirmation. Mike and Phil observed that I used
almost no sieving. Using the fact gcd(a[151],151#) = 1,
one should be able to find a[151] using less than 10^11
issquare tests.

David


Phil Carmody

Sep 21, 2011 

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

--- On Wed, 9/21/11, djbroadhurst <d.broadhurst@...> wrote:
> "mikeoakes2" <mikeoakes2@...> wrote:
> 
> > You have only used the fact that a cannot be divisible by 2.
> > In fact, it cannot be divisible by any prime(k), k=1..n.
> 
> Indeed.
> 
> Puzzle 151: Let a[151] be the smallest positive integer of
> the form a[151] = x + y with x*y = 151#. Is a[151] prime?
> 
> Comment: I believe that a[151] is indeed prime, but would
> like confirmation. Mike and Phil observed that I used
> almost no sieving. Using the fact gcd(a[151],151#) = 1,
> one should be able to find a[151] using less than 10^11
> issquare tests.

I've not done the reckoning, but Knuth's sieves can give a far better boost than just 1/p. It's about 8 years since I looked at them, but I seem to remember them being able to throw away about 1/4 of the residues for each prime.

Phil


djbroadhurst

Sep 21, 2011 

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

--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> Puzzle 151: Let a[151] be the smallest positive integer of
> the form a[151] = x + y with x*y = 151#. Is a[151] prime?

Rats! a[151] is not prime. It is true that

949356697963059988723620507919
= 2*3*5*7*11*13*19*37*61*79*83*89*109*113*127*131*137*149*151
+ 17*23*29*31*41*43*47*53*59*67*71*73*97*101*103*107*139

is prime. But sadly a[151] is slightly smaller and composite.
I leave the re-discovery of its value to sieve enthusiasts.

Conclusion: we still do not know the 16th prime in
http://oeis.org/A182987

David (sadder and wiser)


Phil Carmody

Sep 21, 2011 

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

--- On Wed, 9/21/11, djbroadhurst <d.broadhurst@...> wrote:
> "djbroadhurst" <d.broadhurst@...> wrote:
> 
> > Puzzle 151: Let a[151] be the smallest positive integer of
> > the form a[151] = x + y with x*y = 151#. Is a[151] prime?
> 
> Rats! a[151] is not prime. It is true that
> 
> 949356697963059988723620507919
> =
> 2*3*5*7*11*13*19*37*61*79*83*89*109*113*127*131*137*149*151
> + 17*23*29*31*41*43*47*53*59*67*71*73*97*101*103*107*139
> 
> is prime. But sadly a[151] is slightly smaller and composite.
> I leave the re-discovery of its value to sieve enthusiasts.

Curse you David! I have retired from computational number theory!

How does this sound for a minimum product sum:

? 11*17*23*31*47*59*73*83*103*109*3*19*43*53*79*101*131*139 + 2*5*41*67*97*127*137*149*7*13*29*37*61*71*89*107*113*151
%13 = 949356697963059988594789103077

It's smaller than yours:

? 949356697963059988723620507919 - %
%14 = 128831404842

No idea if my program has bugs[*], I only verified it at prime(12)# and prime(18)#.

> Conclusion: we still do not know the 16th prime in http://oeis.org/A182987
> 
> David (sadder and wiser)

And wracked with guilt too, I hope!

Phil

[* The ravens will leave the Tower of London when I write something without bugs - Brits beware.]


Phil Carmody

Sep 21, 2011 

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

> > Conclusion: we still do not know the 16th prime in http://oeis.org/A182987

No idea if it's correct, but my program takes ~20s on a 5-year-old computer to spit out this product sum:

? 5*11*23*59*103*109*127*149*191*43*53*71*79*101*107*131*139*151*163*173*193 + 2*17*31*41*47*67*73*83*97*137*157*167*179*197*3*7*13*19*29*37*61*89*113*181
%45 = 12521275997143921015896873123691334262739
? factor(%)
%46 =
[12521275997143921015896873123691334262739 1]

? (5*11*23*59*103*109*127*149*191*43*53*71*79*101*107*131*139*151*163*173*193)/(2*17*31*41*47*67*73*83*97*137*157*167*179*197*3*7*13*19*29*37*61*89*113*181)*1.0
%47 = 0.9999999999975214682174533990

That should be 45 primes. Algorith work-factor O(2^23) time, O(2^23) space.
Dunno if I'll run out of RAM or FPU precision (I add logs) first.

Phil


djbroadhurst

Sep 21, 2011 

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

-- In primenumbers@yahoogroups.com, 
Phil Carmody <thefatphil@...> wrote:

> Curse you David! I have retired from computational number theory!

Welcome back, Phil :-) 

> How does this sound for a minimum product sum:
> 
> ? 11*17*23*31*47*59*73*83*103*109*3*19*43*53*79*101*131*139 
> + 2*5*41*67*97*127*137*149*7*13*29*37*61*71*89*107*113*151
> %13 = 949356697963059988594789103077

Perfect! 

Here are my results after the 25th prime:

[26, 101, 0, 30519656902298784043, 363430]
[27, 103, 0, 309740688505242652849, 682318]
[28, 107, 0, 3203982595205562774973, 13691829]
[29, 109, 0, 33450560343160551726409, 42027404]
[30, 113, 0, 355584333965475029353457, 33368435]
[31, 127, 0, 4007231932061350599162707, 1725024]
[32, 131, 0, 45864865814809825555344421, 2008120]
[33, 137, 0, 536834490807772152111396143, 623856921]
[34, 139, 0, 6329185303212156752880603539, 13569531432]
[35, 149, 0, 77257552405943571156935712611, 6384]
[36, 151, 0, 949356697963059988594789103077, 48015910597]
[37, 157, 0, 11895405330415184274516467070659, 34888276484]

in the format

[n, p, isprime(a), a, idiotic_workload]

where p is n'th prime, a is the smallest positive integer 
such that a = x + y with x*y = p#, and
"idiotic_workload" is the number of "issquare" tests 
if you use only the fact that a is odd.
(I did, in fact, reduce this by a factor of 8/15,
using the fact that gcd(a,30) = 1.
That counts as fancy sieving, in my modest book :-)

Best regards

David


djbroadhurst

Sep 21, 2011 

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

--- In primenumbers@yahoogroups.com, 
Phil Carmody <thefatphil@...> wrote:

> %45 = 12521275997143921015896873123691334262739

This is clearly a solution to a = x + y, with x*y = 197# 

Sanity check:

a = 12521275997143921015896873123691334262739;
m = prod(k=2,197,if(isprime(k),k,1));
if(issquare(a^2-4*m),print(OK));
OK

But I am utterly powerless to prove that you have 
found the smallest positive integer solution.

Sorry!

David

[Apologies if this appears twice; my memory was 
challenged by PrimeMogul's on-line reply options.]


Robert Gerbicz

Sep 21, 2011 

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

2011/9/22 Phil Carmody <thefatphil@...>

> **
>
>
> > > Conclusion: we still do not know the 16th prime in
> http://oeis.org/A182987
>
> No idea if it's correct, but my program takes ~20s on a 5-year-old computer
> to spit out this product sum:
>
> ?
> 5*11*23*59*103*109*127*149*191*43*53*71*79*101*107*131*139*151*163*173*193 +
> 2*17*31*41*47*67*73*83*97*137*157*167*179*197*3*7*13*19*29*37*61*89*113*181
> %45 = 12521275997143921015896873123691334262739
> ? factor(%)
> %46 =
> [12521275997143921015896873123691334262739 1]
>
> ?
> (5*11*23*59*103*109*127*149*191*43*53*71*79*101*107*131*139*151*163*173*193)/(2*17*31*41*47*67*73*83*97*137*157*167*179*197*3*7*13*19*29*37*61*89*113*181)*1.0
> %47 = 0.9999999999975214682174533990
>
> That should be 45 primes. Algorith work-factor O(2^23) time, O(2^23) space.
> Dunno if I'll run out of RAM or FPU precision (I add logs) first.
>
> Phil
> 
>

Yes, a(45) is prime. Moreover a(54) is also prime!
Here it is my algorithm:
Let B1=the product of the first n1 primes and B2=product of the next n2
primes (here n1+n2=n). Precompute all divisors of B1 and sort them in an
array. M is fixed ( a divisor of B2 ) and x is a divisor of B1, so the two
divisors of pn# are M*x and B2/M*B1/x. Furthermore define their sum:
f(x)=M*x+B2/M*B1/x=c1*x+c2/x, for x>0 (c1 and c2 is constant). Then
f'(x)=c1-c2/x^2, this gives that f is decreasing up to xopt=sqrt(c2/c1),
then increasing. So choose the largest term from the divisor array for that
vec[pos]<=xopt. And check that whether s=M*vec[pos]+B1/M*B2/vec[pos] gives a
new minimum or not. (we don't need to check vec[pos+1], because we can
assume that M*vec[pos] is the smaller term). It was possible to use
n1=min(26,n/2) with gmp (integer arithmetic only, no logarithm!).

However in the next table I have used the largest n1=26 that still fits in
my memory for all n. After about 1 minute of precomputation:

a(26)=30519656902298784043 time=0 sec.
a(27)=309740688505242652849 time=0 sec.
a(28)=3203982595205562774973 time=0 sec.
a(29)=33450560343160551726409 time=0 sec.
a(30)=355584333965475029353457 time=0 sec.
a(31)=4007231932061350599162707 time=0 sec.
a(32)=45864865814809825555344421 time=0 sec.
a(33)=536834490807772152111396143 time=0 sec.
a(34)=6329185303212156752880603539 time=0 sec.
a(35)=77257552405943571156935712611 time=0 sec.
a(36)=949356697963059988594789103077 time=0 sec.
a(37)=11895405330415184274516467070659 time=0 sec.
a(38)=151870368669809340932147137151141 time=0 sec.
a(39)=1962597687490723532325455679611239 time=0 sec.
a(40)=25813942262841235337824273187479339 time=0 sec.
a(41)=345367009298405421792565742844954083 time=0 sec.
a(42)=4646437901362956893174577631042437259 time=0 sec.
a(43)=64215049386443985152604909055616772617 time=0 sec.
a(44)=892103976880926098341720538469647605343 time=1 sec.
a(45)=12521275997143921015896873123691334262739 time=2 sec.
a(46)=176634334620236974506618069629019407809043 time=4 sec.
a(47)=2565761914749854874176770891488338297127259 time=7 sec.
a(48)=38314996115220051864085773559390080508751341 time=15 sec.
a(49)=577273623595619844209899390048414068386075927 time=30 sec.
a(50)=8735735089751793752845243445219759262476950463 time=58 sec.
a(51)=133345208916888880296289853806282488041064456163 time=114 sec.
a(52)=2061466903231824694455463569105999376677563487097 time=228 sec.
a(53)=32002572336329003854678329736578351151961296266383 time=443 sec.
a(54)=507016098039928688307376229267797979912841172301287 time=891 sec.
a(55)=8128086378946159238999457623025612061299873099728507 time=1796 sec.
a(56)=131815409919665511247164386089731448526011891965617623 time=3598 sec.
a(57)=2161933467206117057835020073160759729475746618226706377 time=7459 sec.


[Non-text portions of this message have been removed]


djbroadhurst

Sep 21, 2011 

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

--- In primenumbers@yahoogroups.com, 
Robert Gerbicz <robert.gerbicz@...> wrote:

> Yes, a(45) is prime. Moreover a(54) is also prime!

As has happened before, I propose and Robert disposes of a problem.
Great work; I can switch off my idiotic "issquare" runs.

David


Phil Carmody

Sep 21, 2011 

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

--- On Thu, 9/22/11, djbroadhurst <d.broadhurst@...> wrote:
> Robert Gerbicz <robert.gerbicz@...> wrote:
> 
> > Yes, a(45) is prime. Moreover a(54) is also prime!

Great work Robert!
It appears I ran out of FPU precision and RAM simultaniously. It was nice to have the O(2^(n/2)) time and space for as long as I did. Your trade of O(2^n) time for O(1) space is a shame, but apparently essential with this kind of approach. 

The other way we differed was that I precomputed ans sorted all the divisors of B2 as well as B1. This I guessed would be cheaper than doing a binary search within the factors of B1, as the sort of the 2^N values can be done in O(2^N) time rather than O(N*2^N) time using a merge sort (as if <x_i> is sorted, then so is <p*x_i>.

> As has happened before, I propose and Robert disposes of a problem.
> Great work; I can switch off my idiotic "issquare" runs.

Not necessarily, I still think Knuth's method might still have some merit, depending on what the real rejection ratios are per prime.

Phil


djbroadhurst

Sep 21, 2011 

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

--- In primenumbers@yahoogroups.com, 
Phil Carmody <thefatphil@...> wrote:

> Great work Robert!

Also by Phil, who likewise divided and conquered.

> > I can switch off my idiotic "issquare" runs.
> 
> Not necessarily, I still think Knuth's method might still 
> have some merit, depending on what the real rejection ratios 
> are per prime.

I have run "issquare" on one of Robert's softer results.
Of course, he was right:

[40, 173, 0, 25813942262841235337824273187479339, 5820666851]

David


Robert Gerbicz

Sep 21, 2011 

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

2011/9/22 Phil Carmody <thefatphil@...>

> **
>
>
>
> The other way we differed was that I precomputed ans sorted all the
> divisors of B2 as well as B1. This I guessed would be cheaper than doing a
> binary search within the factors of B1, as the sort of the 2^N values can be
> done in O(2^N) time rather than O(N*2^N) time using a merge sort (as if
> <x_i> is sorted, then so is <p*x_i>.
>


Phil, that's a nick trick.

There is also a trick what I have used in code to (at least) halve the
memory usage: Store only d as a divisor if d<=sqrt(B1). In this way we store
only half number of divisors (and these are smaller divisors). If
sqrt(c2/c1)<=sqrt(B1) ( so c2/c1<=B1 ) then search for the divisor as I
have written (x<=sqrt(B1) is true), otherwise we can assume that x=B1/d,
where for the co-divisor d<=sqrt(B1),so we have x=B1/d<=sqrt(c2/c1), search
the smallest d for that B1/sqrt(c2/c1)<=d. (There is some work to check the
edge case, when c2/c1 is close to B1).

For n1=26 it would also mean that we are still in unsigned long long int,
because sqrt(p26#)~2^63.7
However I have not used this, stored the divisors in mpz_t array.


[Non-text portions of this message have been removed]


Phil Carmody

Sep 22, 2011 

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

--- On Thu, 9/22/11, djbroadhurst <d.broadhurst@...> wrote:
> Phil Carmody <thefatphil@...> wrote:
> > > I can switch off my idiotic "issquare" runs.
> > 
> > Not necessarily, I still think Knuth's method might still 
> > have some merit, depending on what the real rejection ratios 
> > are per prime.

Scratch that. I think with these contrived values you get pessimal rejection ratios.

The next thing that comes to mind is Lattice Reduction. Noam Elkies stunned the anagramming world a decade back with his novel LR-based technique for finding huge anagrams, and I wonder if his technique could be extended to this kind of problem? (Each "word" in the anagram, like each factor in the primorial product, was only allowed once. Alas, it was also allowed 0 times, which we don't permit, however, I think there's an isomorphism between the two cases.)
I couldn't find Elkies' paper, if he had one, but this might contain enough info:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.135.769

"""
Abstract:

This paper describes a technique for finding a certain types of anagrams, which we call subset anagrams. Specifically, given a list of words or phrases, we look for two (disjoint) subsets of these words or phrases that are anagrams of each other. The approach presented here makes use of powerful lattice reduction algorithms, and is due to Noam Elkies [Elk] (see also [CS03]), who used it to produce an award-winning anagram [Ana02]. We also describe some implementation details of the script at http://www.alexhealy.net/anagram.htm that uses this technique to find subset anagrams.
"""

Phil


Robert Gerbicz

Message 27 of 28 , Sep 22, 2011 

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

a(59) is also prime.
The next two terms, (here I really stopped):

a(58)=35589916574861605373559051312928023615066938969705827801 time=15488
sec.
a(59)=592334262743726183233986145854894378203364356598719537683 time=32818
sec.


[Non-text portions of this message have been removed]


djbroadhurst

Message 28 of 28 , Sep 22, 2011 

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

--- In primenumbers@yahoogroups.com, Robert Gerbicz <robert.gerbicz@...> wrote:

> a(59) is also prime.

Wow! What a great note on which to stop:

{print(isprime
(5*7*11*13*19*23*37*41*43*47*61*73*79*103*107*127*137*139*149*151*173*179*181*191*197*227*239*251*269*271
+2*3*17*29*31*53*59*67*71*83*89*97*101*109*113*131*157*163*167*193*199*211*223*229*233*241*257*263*277));}

1

David