Beal's Conjecture memiliki hadiah jutaan dolar jika Anda membuktikan / menolaknya.

Ini menyatakan bahwa jika A, B, C, x, y, dan z adalah bilangan bulat positif dengan x, y, z> 2, maka A, B, dan C memiliki faktor prima yang sama.

Tantangannya adalah menulis sebuah program yang mencari contoh tandingan untuk membantahnya!

Aturan

• Tulis sebuah program mencari contoh kontra dari dugaan Beal
• Anda dapat melakukan pencarian lengkap (yaitu, semua kemungkinan kombinasi angka yang sesuai dengan formulir ini) atau menggunakan beberapa optimasi (misalnya, A dan B simetris).
• Anda harus menggunakan bilangan bulat presisi sembarang.

Catatan

• Ini adalah kontes popularitas, jadilah kreatif!
• Kecepatan tidak diperlukan, tetapi membuatnya lebih menarik. Optimalkan!
• Saya juga tertarik melihat kode terpendek juga. Anda akan mendapatkan +1 dari saya!
• Saya akan menjalankan program pemenang pada superkomputer yang dapat saya akses!
• Dugaan ini dianggap benar, tetapi itu tidak berarti kita tidak dapat mencoba!
• Peter Norvig dari Google telah mencoba masalah ini juga. Anda dapat menggunakan halamannya sebagai panduan. Ia memiliki program Python pendek yang dapat Anda gunakan sebagai contoh.
• Beberapa pria lain (yang kebetulan bekerja di Google) telah sangat meningkat dalam pendekatan Norvig, halamannya (dengan kode sumber) dapat ditemukan di sini .
• Pertanyaan SO saya terkait dengan ini dari dua tahun lalu mungkin juga membantu: Fin semua A ^ x dalam kisaran yang diberikan .

Aku sedang malas (pun intended), tapi kenapa tidak ... tampaknya memenuhi aturan.

Haskell, 204

import Control.Monad
import Control.Monad.Omega
main=print.filter(\[(a,x),(b,y),(c,z)] 
 ->and$(a^x+b^y==c^z):zipWith(((>1).).gcd)[a,b,c][b,c,a])
 .runOmega$mapM(\_->liftM2(,)(each[1..])$each[3..])"123"

Ini mencetak ¹ semua kombinasi yang memenuhi properti counterexample. Saya menggunakan paket control-monad-omega untuk mendiagonalisasi ℕ ⁶ ... mungkin dianggap curang perpustakaan. Tetapi mengingat seseorang kemudian akan mengirim jawaban APL di mana semua hal ini dibangun ke dalam bahasa (atau bukan?), Saya tidak memberikan terlalu banyak tentang hal itu ...

Tentu saja, program ini terlalu lambat (kelelahan yang naif, dan daftar terkait sebagai struktur data) untuk diharapkan benar-benar menghasilkan sampel tandingan, tetapi Haskell sendiri sebenarnya dapat mencapai kinerja yang layak.

¹ Karena mencetak tupel dalam format daftar, yaitu dalam satu baris, Anda perlu mematikan buffering terminal Anda atau Anda tidak akan melihat ketika hasilnya masuk. Atau, Anda dapat mengganti printdengan mapM_ printsehingga Anda mendapatkan baris baru setelah setiap hasil, membilas terminal buffer line.

Untuk menguji program, ubah each[3..]ke each[2..], maka Anda hanya akan mendapatkan semua tuple pythagoras non-coprime sebagai hasilnya.

C #, tidak ada loop

OK, saya membaca sekilas beberapa tautan itu, tetapi jujur ​​saja itu agak membosankan. Saya tidak tertarik mengoptimalkannya dengan tabel hash dan yang lainnya. Mengapa saya harus melakukannya? Anda punya superkomputer!

Sial, aku bahkan tidak mau repot dengan loop! Solusi ini akan mengikuti aturan no-loop .

Harap perhatikan bahwa kode yang akan saya tulis bukan kode yang baik, atau jenis kode yang akan saya tulis dalam kehidupan nyata (jika calon majikan kebetulan membaca ini). Kode ini menekankan keringkasan dan kemampuan untuk bekerja dalam narasi, dan menekankan konvensi dan ritual yang tepat dan loop dan sebagainya.

Untuk menunjukkan apa yang saya bicarakan, kita akan mulai dengan kelas yang mengejutkan dengan bidang publik untuk menyimpan operan dari persamaan:

class BealOperands
{
    public BigInteger A, B, C, x, y, z;
}

Oke, kita akan mulai dengan apa yang mungkin merupakan tantangan terberat. Kita perlu mencari cara untuk mengubah urutan melalui setiap kombinasi operan tersebut. Tidak diragukan lagi ada cara untuk melakukannya dengan lebih efisien daripada memeriksa setiap permutasi, tetapi saya tidak dapat diganggu untuk mencari tahu mereka. Dan mengapa saya harus? Kita punya superkomputer!

Inilah algoritma yang saya buat. Ini sangat tidak efisien, dan mengulangi operan yang sama berulang-ulang, tetapi siapa yang peduli? Komputer Super!

• Perlakukan keenam operan sebagai angka dasar-2, dan permutasi melalui setiap kombinasi.
• Perlakukan keenam operan sebagai angka dasar-3, dan permutasi melalui setiap kombinasi.
• Perlakukan keenam operan sebagai angka dasar-4, dan permutasi melalui setiap kombinasi.
• (...)

Bagaimana melakukan semua ini tanpa loop? Mudah! Hanya menerapkan IEnumerabledan terkait IEnumeratoruntuk memompa permutasi. Nantinya, kami akan menggunakan LINQ untuk menanyakannya.

class BealOperandGenerator : IEnumerable<BealOperands>
{
    // Implementation of IEnumerable<> and IEnumerable -- basically boilerplate to get to BealOperandGeneratorEnumerator.
    public IEnumerator<BealOperands> GetEnumerator() { return new BealOperandGeneratorEnumerator(); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

class BealOperandGeneratorEnumerator : IEnumerator<BealOperands>
{
    public BealOperandGeneratorEnumerator() { Reset(); }

    private BealOperands operands;
    private BigInteger @base;

    public void Reset()
    {
        // A is set to 0, which is "before" its minimum value, because IEnumerators are supposed to
        // point to their first element *after* the first call to MoveNext().
        // All other operands are set to their minimum values.
        operands = new BealOperands { A = 0, B = 1, C = 1, x = 3, y = 3, z = 3 };
        @base = 2;
    }

    public BealOperands Current
    {
        get 
        {
            // We need to return a copy, since we'll be manipulating our internal one.
            return new BealOperands { 
                A = operands.A, B = operands.B, C = operands.C, 
                x = operands.x, y = operands.y, z = operands.z };
        }
    }

    public bool MoveNext()
    {
        // Increment the lowest "digit" and "carry" as necessary.
        operands.A++;
        if (operands.A - 1 >= @base)
        {
            operands.A = 1; operands.B++;
            if (operands.B - 1 >= @base)
            {
                operands.B = 1; operands.C++;
                if (operands.C - 1 >= @base)
                {
                    operands.C = 1; operands.x++;
                    if (operands.x - 3 >= @base)
                    {
                        operands.x = 3; operands.y++;
                        if (operands.y - 3 >= @base)
                        {
                            operands.y = 3; operands.z++;
                            if (operands.z - 3 >= @base)
                            {
                                operands.z = 3; @base++;
                            }
                        }
                    }
                }
            }
        }
        // There will always be more elements in this sequence.
        return true;
    }

    // More boilerplate
    object System.Collections.IEnumerator.Current { get { return Current; } }
    public void Dispose() { }
}

Sekarang kita dalam bisnis! Yang perlu kita lakukan hanyalah menyebutkan contoh BealOperandGeneratordan menemukan contoh tandingan Beal's Conjecture.

Masalah besar kita berikutnya adalah bahwa tampaknya tidak ada cara bawaan untuk meningkatkan BigIntegerkekuatan a BigInteger. Ada BigInteger.Pow(BigInteger value, int exponent), dan BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus), tetapi tidak ada metode untuk meningkatkan BigInteger, ke kekuatan yang lain BigInteger, modulo infinity.

Sungguh kuku yang mengkilap dari suatu masalah! Sepertinya itu dibuat untuk dipecahkan dengan kami IEnumerable/ IEnumeratorpalu!

class BigIntegerPowerEnumerable : IEnumerable<Tuple<BigInteger, BigInteger>>
{
    public BigIntegerPowerEnumerable(BigInteger @base, BigInteger exponent) { this.@base = @base; this.exponent = exponent; } 
    BigInteger @base, exponent;

    public IEnumerator<Tuple<BigInteger, BigInteger>> GetEnumerator() { return new BigIntegerPowerEnumerator(@base, exponent); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

class BigIntegerPowerEnumerator : IEnumerator<Tuple<BigInteger, BigInteger>>
{
    public BigIntegerPowerEnumerator(BigInteger @base, BigInteger exponent) 
    {
        originalBase = @base; 
        originalExponent = exponent;
        Reset(); 
    }

    BigInteger originalBase, currentBase, originalExponent, currentExponent;
    bool finished;

    public void Reset()
    {
        // IEnumerable.Reset() is a silly method. You're required to implement it when you implement IEnumerable,
        // but it isn't used by foreach or LINQ or anything. If you want to re-enumerate the enumerable, just get
        // a brand new enumerator.
        // In this case it gets in the way. The only reason I'm storing the original values is so I can implement 
        // this useless method properly. I supposed I could just throw a NotImplementedException or something, 
        // but it's done now.
        currentBase = originalBase;
        currentExponent = originalExponent;
        finished = false;
    }

    public bool MoveNext()
    {
        if (finished) return false;

        if (currentExponent <= Int32.MaxValue)
        {
            currentBase = BigInteger.Pow(currentBase, (Int32)currentExponent);
            currentExponent = 1;
            finished = true;
        }
        else
        {
            currentBase = BigInteger.Pow(currentBase, Int32.MaxValue);
            currentExponent -= Int32.MaxValue;
        }
        return true;
    }

    public Tuple<BigInteger, BigInteger> Current
    {
        get { return new Tuple<BigInteger, BigInteger>(currentBase, currentExponent); }
    }

    object System.Collections.IEnumerator.Current { get { return Current; } }
    public void Dispose() { }
}

static class BigIntegerPowExtension
{
    public static BigInteger Pow(this BigInteger @base, BigInteger exponent)
    {
        return new BigIntegerPowerEnumerable(@base, exponent).Last().Item1;
    }
}

Sekarang kita punya metode ekstensi Pow, yang dapat dipanggil pada BigInteger, dan membutuhkan BigIntegereksponen dan tanpa modulus.

Oke, mari kita mundur. Bagaimana kita bisa tahu jika orang tertentu BealOperandsadalah contoh tandingan Beal's Conjecture? Nah, dua hal harus benar:

• Operan, ketika dicolokkan ke rumus itu di bagian atas halaman, harus membentuk persamaan yang benar.
• A, B, dan C TIDAK boleh memiliki faktor prima yang sama (yaitu GCD-nya adalah 1).

Kami memiliki apa yang kami butuhkan untuk memeriksa kondisi pertama. Dan ternyata kondisi kedua jauh lebih mudah untuk diperiksa daripada kedengarannya. BigIntegermenyediakan GreatestCommonDivisormetode yang bagus , yang memungkinkan kita untuk dengan mudah menghindari seluruh mimpi buruk untuk mencoba mengimplementasikannya tanpa loop.

Jadi kami siap menulis metode untuk memeriksa apakah a BealOperandsadalah contoh tandingan. Ini dia ...

static class BealOperandsExtensions
{
    public static bool IsBealsConjectureCounterExample(this BealOperands o)
    {
        // If the equation isn't even true, we don't have a counter example unfortunately
        if (o.A.Pow(o.x) + o.B.Pow(o.y) != o.C.Pow(o.z))
        {
            return false;
        }

        // We have a counterexample if A, B and C are coprime
        return BigInteger.GreatestCommonDivisor(o.A, o.B) == 1 &&
               BigInteger.GreatestCommonDivisor(o.A, o.C) == 1 &&
               BigInteger.GreatestCommonDivisor(o.B, o.C) == 1;
    }
}

Dan akhirnya kita bisa menggabungkan semuanya dengan Mainmetode yang cukup apik ini:

static class Program
{
    static void Main()
    {
        var bealOperandGenerator = new BealOperandGenerator();
        if (bealOperandGenerator.Any(o => o.IsBealsConjectureCounterExample()))
        {
            Console.WriteLine("IN YOUR FACE, BEAL!");
        }
    }
}

Tidak ada contoh tandingan dengan C ^ Z <= 1.0E27.

Pada Februari 2019 saya memeriksa C ^ Z <= 1.0E29 dengan asumsi bahwa eksponen “X” dan / atau “Y” harus>> 5.

Versi saat ini dari program ini (“X” dan / atau “Y”> = 5) membutuhkan waktu kurang dari 1 detik pada AMD 2920X untuk menemukan semua solusi ke C ^ Z <= 1.0E15. (Tetapi semua gcd (A, B, C) adalah> = 2)

Detail di http://www.durangobill.com/BealsConjecture.html

Saya dapat memodifikasi kode saat ini (Menggunakan "C" dan OpenMP) di luar batas ini tetapi akan membutuhkan lebih dari 128GB RAM untuk menjalankannya. (Ratusan CPU juga akan membantu. Ribuan CPU akan lebih baik.) (Jika Anda memiliki akses gratis ke sesuatu seperti ini, silakan hubungi saya.)

Alamat email saya ada di beranda saya di http://www.durangobill.com

Variasi ke-2 dari program pencarian Beal telah selesai. Hasilnya adalah:

$C^Z < 10^{26}$$A^X + B^Y = C^Z$$(X,Y) >= 4$

$(X,Y)$$>= 5$$C^Z < 10^{28}$$A^X + B^Y = C^Z$$(X,Y) >= 5$

Detail di: http://www.durangobill.com/BealsConjecture.html

Dua pertanyaan berikutnya adalah :: 1) Dapatkah superkomputer memperluas pencarian? 2) Jika superkomputer dapat memperluas pencarian, apakah itu praktis?

1) Untuk memperluas salah satu pencarian di atas ke 1.0E30, 300GB RAM akan diperlukan per inti kecuali core dapat berbagi 300GB. Untuk setiap tambahan tambahan peningkatan daya eksponensial lebih lanjut dari 1.0E30, jumlah RAM yang dibutuhkan meningkat dengan faktor setidaknya 2,2.

2) Jumlah daya pemrosesan yang diperlukan untuk setiap kenaikan tambahan lebih lanjut dalam eksponen ke dan di luar 1,0E30 mengalikan waktu CPU gabungan sekitar 3,8. Pencarian ke 1.0E29 membutuhkan waktu 2 minggu menggunakan 12 core. Waktu superkomputer umumnya tidak "gratis", dan ada sangat sedikit prospek bahwa ada contoh tandingan.

Sebagai panduan untuk efisiensi kode di durangobill.com/BealE29code.txt, masing-masing dari 12 core rata-rata 220 juta loop iterasi per detik untuk loop dalam. (Rata-rata untuk jangka waktu 2 minggu.) (Peningkatan memori RAM di luar apa yang saya miliki akan meningkatkan kecepatan rata-rata hingga faktor 2.)

Saya akan membiarkan Austin menjawab 1) dan 2) karena dia memiliki akses ke superkomputer dan saya tidak. (Jika kebetulan 1 dan 2) merupakan "go", saya dapat menyediakan kode "C" dengan peringatan bahwa saya tidak terbiasa dengan instruksi multi-thread untuk cluster superkomputer besar.)

Harus memasukkan ini dalam 2 komentar agar sesuai.

Array utama dialokasikan sebagai berikut:

SortHeads = calloc(PRIME1+1, 8);
X2YmodPrime1 = calloc(ARRAYSIZE+1, 4);
X2YmodPrime2 = calloc(ARRAYSIZE+1, 4);
Base = calloc(ARRAYSIZE+1, 4);
Power = malloc(ARRAYSIZE+1);

(Anda akan membutuhkan 128GB RAM untuk array ini)

dengan:

#define PRIME1 2147483647LLU
#define PRIME2 2147483629LLU
#define ARRAYSIZE 4700000000LL

"Basis" sebenarnya membutuhkan 33 bit ( cbrt(1.0E29)) - bit tambahan diisi dengan "Daya" (yang hanya membutuhkan 7 bit.)

Array beroperasi mirip dengan tabel hash. Namun, karena mereka diurutkan berdasarkan PRIME1 dan hanya digunakan sebagai tabel pencarian, Anda tidak perlu daftar tertaut untuk mengaksesnya. Hasilnya adalah waktu pencarian linear yang sangat cepat untuk melihat apakah percobaan A ^ X + B ^ Y = C ^ Z.

Dengan demikian pernyataan dalam loop paling dalam hanya dua loop.

Pernyataan “Pragma” mengontrol jumlah inti pemrosesan multi yang digunakan (dalam hal ini 12) - semua dapat mengakses salinan tunggal array.

Inilah kode "utama" (dalam "C") (Semoga komentar sesuai dengan panjang baris yang diposting. Jika tidak, salin dan tempel kode dalam beberapa dokumen yang memiliki panjang garis lebih panjang.)