Ramanujan-Hardy sayıları, iki kübün toplamı olarak birbirlerinden farklı a, b, c, ve d sayıları ile a^^3 + b^^3 = c^^3 + d^^3 olarak iki farklı biçimde yazılabilen sayılardır. Verilen bir n değerinden küçük a, b, c, ve d değerleri ile yazılabilen bütün Ramanujam '[sic]' sayılarını bulunuz.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Hiç akıl kullanmayan aşağıdaki algoritma O(n^2) karmaşıklığında:

import std.stdio;
import std.exception;
import std.format;
import std.algorithm;

struct SayıÇifti
{
   int a;
   int b;

   void toString(void delegate(const(char)[]) hedef) const
   {
       formattedWrite(hedef, "%s^3 + %s^3", a, b);
   }
}

alias SayıÇiftleri = SayıÇifti[];

struct RamanujanHardySayısı
{
   int değer;
   SayıÇiftleri çiftler;

   void toString(void delegate(const(char)[]) hedef) const
   {
       formattedWrite(hedef, "%s = %-(%s = %)", değer, çiftler);
   }

   int opCmp(ref const RamanujanHardySayısı sağdaki) const
   {
       return değer - sağdaki.değer;
   }
}

/* Belirtilen değerden küçük bütün sayılarla oluşturulabilen Ramanujan-Hardy
* sayılarını döndürür. */
RamanujanHardySayısı[] ramanujanHardy(int n)
{
   enforce(n >= 1, "n en az 1 olabilir.");

   SayıÇiftleri[int] toplamlar;

   foreach (a; 0 .. n - 1) {
       const aKüp = a^^3;

       foreach (b; a + 1 .. n) {
           const toplam = aKüp + b^^3;
           toplamlar[toplam] ~= SayıÇifti(a, b);
       }
   }

   RamanujanHardySayısı[] sonuç;

   foreach (toplam; toplamlar.byKey) {
       auto çiftler = toplamlar[toplam];
       auto adet = çiftler.length;

       if (adet > 1) {
           sonuç ~= RamanujanHardySayısı(toplam, çiftler);
       }
   }

   return sonuç;
}

void main()
{
   auto sayılar = sort(ramanujanHardy(1000));

   foreach (sayı; sayılar) {
       writeln(sayı);
   }
}

n==1000 durumunda 3 farklı biçimde yazılabilen sayılar da var:
'
1729 = 1^3 + 12^3 = 9^3 + 10^3
4104 = 2^3 + 16^3 = 9^3 + 15^3
..
87539319 = 167^3 + 436^3 = 228^3 + 423^3 = 255^3 + 414^3
..
'
Ne yazık ki işleve 10 bin gibi bir değer verildiğinde bile çözüm çok zaman alıyor. (Sonlanmasını hiç beklemedim. :)) Daha hızlı çözümü var mı?

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]