Solve a Integer equation system

[elim]

Let [latex]a,b,c \in \mathbb{N}^+[/latex]
Find smallest [latex]d = 2a^2=3b^3+2=5c^5+3[/latex]

[CRGreathouse]

No solutions below 10^45.

Edit: No solutions below 10^55.

[Xitami]

when [latex]12*k^3 + 1[/latex] is square? (b=2k)
or [latex]80n^5 + 200n^4 + 200n^3 + 100n^2 + 25n + 4[/latex] (c=2n+1)

[elim]

The Chinese Remainder theorem shows that [latex]d = 38+30k[/latex] for some [latex]k\in \mathbb{N}^+[/latex]
I don't know if this is useful. Seems a very tough problem.

[CRGreathouse]

The Chinese Remainder theorem shows that [latex]d = 38+30k[/latex] for some [latex]k\in \mathbb{N}^+[/latex]
I don't know if this is useful. Seems a very tough problem.

I'd usually write [latex]d=30k+8[/latex] or [latex]d\equiv8\pmod{30}[/latex], but yeah. You can narrow it down more if you like. After a bit of work, I was able to show that [latex]d\equiv1053698\pmod{3622080}[/latex]. No further improvements are available with my methods using primes below 100 million.

If you wanted to incorporate my earlier search, you could say that [latex]d=9999999999999999999999999999999999999999999999999406658+3622080k[/latex] for some [latex]k\in\mathbb{Z}^+[/latex], but that would be silly.

[CRGreathouse]

I think it can be proven that my method can't be extended to any further primes -- the proof should be easy with the amount of checking I did to remove special cases -- but I won't bother writing it out.

This above result (the behavior of d mod 3622080) can be used to show that c is 316675 mod 329280. This lets me check even further, showing that d > 10^70. I imagine that if I took into account behavior mod other primes (where there will be several residue classes, but hopefully not too many) I could push the verification to at least 10^80.

But I have a feeling that there's a much better way to do all of this.

[CRGreathouse]

Working mod 372118412930880 I can show that d > 10^100. This actually wasn't nearly as hard as I expected -- it took about 5 minutes (including about 1 second for pre-processing) and 23 kB. The method should scale pretty well; I'm not yet sure if it is memory-bound or CPU-bound. (I've picked the most efficient primes to use so far; further choices will be less good, so it won't scale as easily as it has so far.)

Edit: Working mod 391343029186433681945280 took only 100 seconds (including about 18 seconds for pre-processing) and 71 MB to show that d > 10^125. It's definitely memory-bound, at least as currently implemented -- I could substitute time for memory to some degree if I can do fast CRTs. Also, due to a flaw in my implementation*, my actual memory use is slightly more than double the quoted -- I'm essentially using two copies of a large array.

* Flaw: I'm too lazy to do it the right way.

[elim]

This is amazing! Would you please explain your algorithm? thanks

[CRGreathouse]

This is amazing! Would you please explain your algorithm? thanks

c has the highest power, so I check values of c to see if they produce valid a and b. I restrict the values it can take on by considering which values will produce a and b that are integers and for which squares and cubes exist mod a given prime (or prime power). I choose primes that have few valid residues; these are produced brute-force.

Notice that 391343029186433681945280 = 2^6 * 3 * 5 * 7^3 * 11 * 31 * 61 * 211 * 331 * 421 * 1321 * 1471. 3622080 = 2^6 * 3 * 5 * 7^3 * 11 is the constant from earlier; the other primes {31, 61, 211, 331, 421, 1321, 1471} are ones which I calculated to have few appropriate residues.

Here's a short example. I'll use d = 8 mod 30 rather than d = 1053698 mod 3622080 so the numbers are smaller.

Consider the values of d mod 30 * 31 (where 31 is one of the primes dividing the large number above; I could have used 61 or 211 but again I'm going for size here). They are
8,38,68,98,128,158,188,218,248,278,308,338,368,398,428,458,488,518,548,578,608,638,668,698,728,758,788,818,848,878,908
But none of
68/2,158/2,278/2,308/2,368/2,398/2,458/2,488/2,518/2,548/2,668/2,728/2,788/2,818/2,848/2
are squares mod 30*31/2 (by quadratic reciprocity -- use the Legendre symbol). So only
8,38,98,128,188,218,248,338,428,578,608,638,698,758,878,908
are possible. Of those, none of
(38-2)/3,(128-2)/3,(218-2)/3,(248-2)/3,(338-2)/3,(428-2)/3,(578-2)/3,(638-2)/3,(878-2)/3
are cubes mod 30*31/3. Thus, c can be only
8,98,188,608,698,758,908
mod 30*31. You can use the Sun Zi's theorem (the CRT) to lift these to
1053698,37274498,73495298,55384898,91605698,40896578,26408258
mod 112284480 = 3622080*31, which means that instead of checking 1 number out of every 30, you're checking 7 numbers out of every 112284480.

[elim]

Thanks a lot CRGreathouse. I got lots to learn.

[CRGreathouse]

No problem. You should try this in Pari -- it's very easy to use. For example, you can check if a number is a square with

Code: Select all

issquare(2484723543478)

and if a residue class represents some squares with

Code: Select all

issquare(Mod(123424654645,43857476878425458))

These together with ispower(..., 3) were the main parts of my calculations above. (Working with large numbers by hand is hard!)

Where did you get the question?

[Peter]

I do not have an aswer, but I stronly suspect that there are no solutions (appart from the excluded d=2,a=1,b=0,c=-1 which prevents one from proving that ther are no soloutions via the kind of congruences CRGreathouse uses).

Of course there ist the numerical evidence that CRGreathouse has found, but there is one more reason: There is a very famous conjecture called the ABC-conjecture, which if true would prove, that there are no "big" solutions for even the equality 3b^3+2=5c^5+3. For details on the conjecture see for instance here: http://en.wikipedia.org/wiki/Abc_conjecture
It does not violate the conjecture as written in Wikipedia, but you can see from there that the ratio: ln(C)/ln(rad(ABC)) is bounded. The biggest such ratio (called quallity) one has found so far is 1,6299 (see http://www.math.leidenuniv.nl/~desmit/a ... .php?set=2) and it is conjectureed, that thats the maximum or at least not far from it. setting A=1, B=3b^3 and C=5c^5 for a big solution b,c of your problem would have quality almost 15/8 or 1,875 thats way bigger than any exspected value (and would violate the more complicted and more precise conjecture on the "merite" of a tripple).

So on the one hand, your problem probably does not have a solution, on the other hand if you manage to find one, that will produce a publication in a good journal.

Happy hunting!
Peter

[CRGreathouse]

Good insight, Peter. I hada hunch that it was connected with abc, but didn't look into it since I figured the OP wouldn't know about it.

I do not have an aswer, but I stronly suspect that there are no solutions (appart from the excluded d=2,a=1,b=0,c=-1 which prevents one from proving that ther are no soloutions via the kind of congruences CRGreathouse uses).

That's not a solution over the integers -- c = -1 yields d = -2, not 2. (There are no integer solutions with c or d negative, since d/2 must be a square.)

[Peter]

That's not a solution over the integers -- c = -1 yields d = -2, not 2. (There are no integer solutions with c or d negative, since d/2 must be a square.)

Oh I forgot about the factor 3. Maybe I should leave the explicit calculations to others .

[CRGreathouse]

I've written some additional code to help me generate larger modular systems. The systems are now too large to hold in main memory, but it's easy to keep them in two arrays and CRT them together one at a time. (Three arrays would also be possible, reducing memory to the cube root rather than the square root of the naive version, but only at the cost of a large increase in the time needed to calculate the moduli. At least, I think so.)

The code is very messy but seems to work.

Code: Select all

checkmod(v1,m1,v2,m2,ff,lim)={
   my(m=lcm(m1,m2),mv1,t);
   for(i=1,#v1,
      mv1=Mod(v1[i],m1);
      for(j=1,#v2,
         forstep(n=lift(chinese(mv1,Mod(v2[j],m2))),lim,m,
            ff(n)
         )
      )
   )
};
addhelp(checkmod, "checkmod(v1,m1,v2,m2,ff,lim): Runs the function ff on nonnegatives below lim that are v1[i] mod m1 and v2[j] mod m2 for some i and j.");


cc(lim,sizelim)={
   my(v1=[1053698],m1=3622080,v2=[0],m2=1,sl,sz,m,s);
   local(mod);

   \\ Populate arrays
   while((sl = (sizelim / 2) \ sizebyte(v1)) > 12,
      sz=#v1;
      v1=newvec(v1,m1,min(sl,1e3),1);
      if(#v1==sz, break, m1 = mod)
   );
   sizelim -= sizebyte(v1);
   print("First array: "#v1" values mod "m1);
   print("  "sizelim>>10" kB remain");
   while((sl = sizelim \ sizebyte(v2)) > 12,
      sz=#v2;
      v2=newvec(v2,m2,min(sl,2e3),m1);
      if(#v2==sz, break, m2 = mod)
   );
   m = lcm(m1,m2);
   s = #v1 * #v2;
   print("Second array: "#v2" values mod "m2);
   print("Working with "s" values mod "m);
   print("About "lim\m" steps needed");

   \\ Convert arrays from d to c
   for(i=1,#v1,v1[i]=lift(5*Mod(v1[i],m1)^5+3));
   for(i=1,#v2,v2[i]=lift(5*Mod(v2[i],m2)^5+3));

   checkmod(v1,m1,v2,m2,
   \\c->my(d=5*c^5+3);if(issquare(d/2)&&ispower((d-2)/3,3),print(c))
   c->my(d=5*c^5+3);if(ispower((d-2)/3,3)&&issquare(d/2),print(c))
   ,lim)
};


newvec(v, m, maxprime, avoid)={
   my(best=1,bestAt,s,t,a,b,c,tv,nv);
   avoid = lcm(avoid, m);
   forprime(p=3,maxprime,
      s = 0;
      if(gcd(avoid,p) == 1,
         t = p * 30;
         forstep(d=8,t,30,
            a=Mod(d/2,t/2);
            b=Mod((d-2)/3,t/3);
            c=Mod((d-3)/5,t/5);
            if(issquare(a)&ispower(b,3)&ispower(c,5),s++)
         )
      ,
         \\t = p^(1+valuation(v1,p)) * 30 / gcd(30, p)
         s = p   \\ Just don't calculate these -- probably not going to be any good, and certainly lots of trouble.
      );
      if(s/p < best,
         best = s/p;
         bestAt = p;
      )
   );
   if (best == 1, return(v));
   mod = m * bestAt;   \\ local variable
   t = bestAt * 30;
   tv=[];
   forstep(d=8,t,30,
      a=Mod(d/2,t/2);
      b=Mod((d-2)/3,t/3);
      c=Mod((d-3)/5,t/5);
      if(issquare(a)&ispower(b,3)&ispower(c,5),tv=concat(tv,d))
   );
   nv=vector(#v*#tv);
   a=0;
   for(i=1,#v,
      for(j=1,#tv,
         nv[a++]=lift(chinese(Mod(v[i],m),Mod(tv[j],bestAt)))
      )
   );
   nv
};

Usage: something like

Code: Select all

cc(1e26,3*10^6)

where 1e26 is the checking limit (on c, so d is checked to the fifth power of this value) and 3*10^6 is the memory bound. Larger memory bounds take more memory (duh!) but also spend more time calculating CRTs. Small memory bounds take less time on CRTs but more time checking if large numbers are cubes.


This version spends a *lot* of time doing CRTs, which in turn rely on the extended Euclidean algorithm. I don't think this is particularly well-implemented in Pari, unfortunately.

Sadly, this method hasn't given me much of an improvement, although it has removed (for the moment) the memory barrier. I'm working on a proof that d > 10^145; it might take half an hour.