Masalah Goldbach adalah pernyataan bahwa bilangan genap apa pun, dimulai dengan 4, dapat direpresentasikan sebagai jumlah dari dua bilangan prima. Artinya, 6 = 3 + 3; 8 = 5 + 3 ... Seperti yang saya pahami, solusi dari masalah tersebut adalah bukti atau sanggahan dari pernyataan ini.
Hal pertama yang perlu kita lakukan adalah menerapkan metode untuk memeriksa apakah suatu bilangan prima. Bilangan prima adalah bilangan yang hanya habis dibagi oleh dirinya sendiri dan oleh satu.
public static bool IsPrimeNumber(ulong n)
{
var result = true;
if (n > 1)
{
for (ulong i = 2; i < n; i++)
{
if (n % i == 0)
{
result = false;
break;
}
}
}
else
{
result = false;
}
return result;
}
Sekarang kita perlu mendapatkan koleksi semua bilangan prima hingga ulong.MaxValue = 18446744073709551615 (2 ^ 64-1)
public static IEnumerable<ulong> GetAllPrimeNumbers(ulong maxNumber)
{
List<ulong> primeNumbers = new List<ulong>();
for (ulong i=0; i < maxNumber; i++ )
{
if (IsPrimeNumber(i))
{
primeNumbers.Add(i);
}
}
return primeNumbers;
}
Intuisi menunjukkan bahwa akan membutuhkan waktu yang sangat lama untuk menghitungnya, jadi kami akan mengurangi jumlahnya menjadi 300.000
static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
IEnumerable<ulong> primeNumbers = GetAllPrimeNumbers();
checkGoldbach(primeNumbers);
stopwatch.Stop();
Console.WriteLine(" " + stopwatch.Elapsed.TotalSeconds + " ");
foreach(var number in primeNumbers)
{
Console.Write(number + " ");
}
Console.ReadKey();
}
Kemudian saya ingin menemukan semua bilangan prima hingga 2 ^ 64 (Bagi saya, beberapa jam perhitungan akan cukup bagi saya)
Setelah dua menit menjalankan program, saya memutuskan untuk meletakkan breakpoint dan memeriksa nomor mana yang diperiksa untuk kesederhanaan:
411780 iterasi setelah dua menit perhitungan. Saya memutuskan untuk sedikit mengoptimalkan metode untuk memeriksa kesederhanaan sebuah angka, karena tidak perlu melanjutkan iterasi setelah setengah dari angka tersebut.
Dengan demikian, jumlah iterasi yang diperlukan untuk memeriksa kesederhanaan menjadi setengahnya. Tampak bagi saya bahwa dalam 2 menit jumlah iterasi akan berlipat ganda
Tapi di sini juga, saya salah. Produktivitas meningkat bukan 100%, tetapi 22%. Seperti yang saya pahami nanti, ini disebabkan oleh fakta bahwa setengah dari cek, seperti sebelumnya, dihilangkan dengan membagi dengan 2, sepertiga dari semua angka yang tidak dihilangkan dengan membagi dengan 2 dihilangkan dengan membagi dengan 3, dll. Dari 500.154 uji kesederhanaan, ditemukan 41549 bilangan prima. Artinya, untuk iterasi
for (ulong i = 2; i <= n/2; i++)
{
if (n % i == 0)
{
result = false;
break;
}
}
dieksekusi sampai akhir (tanpa jeda) hanya 41.549 kali. Dalam kasus lain, itu terputus sebelumnya ...
500154 dan bukan hampir 2 ^ 64, Anda perlu menghitung berapa lama waktu yang diperlukan untuk memeriksa kesederhanaan semua angka menjadi 2 ^ 64
Pertama, mari kurangi jumlah iterasi dari 2 ^ 64 menjadi 30000 dan hitung waktu berjalan metode stopwatch
untuk mengulang angka hingga 30.000, 1 detik dihabiskan
sekarang mari kita buat tabel dengan nilai lain dari jumlah iterasi
Mari kita tulis hasilnya di Excel, dan buat grafik titik untuk koordinat "Jumlah iterasi untuk waktu" dan "Jumlah bilangan prima per rentang"
Sekarang kita dapat mengetahui perkiraan jumlah bilangan prima hingga 2 ^ 64, dan kira-kira berapa lama waktu yang dibutuhkan untuk menemukan semuanya
Jika Anda menambahkan garis tren "Linear" ke grafik "bilangan prima per rentang", Excel akan memberi Anda rumus y = 0,074x + 3004 (Saya tidak tahu seberapa akurat rumusnya). Ini berarti perkiraan jumlah bilangan prima hingga ulong.MaxValue = 0,074 * 2 ^ 64 + 3004;
Dengan cara yang sama, menambahkan garis tren "Polinomial" ke bagan "Jumlah iterasi sepanjang waktu", kita memperoleh rumus y = 7E-10x2 + 6E-05x. Mengganti bilangan kami 2 ^ 64 alih-alih x, Anda dapat mengetahui bahwa untuk menemukan semua bilangan prima hingga 2 ^ 64, kita membutuhkan sekitar 2,38E + 29 detik, atau 7553198149564240000000 tahun. Oke, saya tidak bisa berharap sebanyak itu.
Mari kita coba membuktikan bahwa dugaan Goldbach benar untuk semua bilangan genap hingga 300.000.
public static void checkGoldbach(IEnumerable<ulong> primeNumbers)
{
ulong numbersCount = 300000;
for (ulong number = 4; number<numbersCount; number+=2)
{
bool isGoldbachResult = false;
foreach(ulong primeNumber1 in primeNumbers)
{
foreach(ulong primeNumber2 in primeNumbers)
{
if(primeNumber1+primeNumber2==number)
{
Console.WriteLine("{0} = {1} + {2}", number, primeNumber1, primeNumber2);
isGoldbachResult = true;
break;
}
if(primeNumber1+primeNumber2>number)
{
break;
}
}
if(isGoldbachResult|| primeNumber1>number)
{
break;
}
}
if(!isGoldbachResult)
{
Console.WriteLine(" " + number + " ");
break;
}
}
}
Jika pernyataan Goldbach tidak benar untuk beberapa angka, metode akan berhenti menghitung pada angka itu.
Setelah 9 menit komputasi, kita dapat menyatakan bahwa hipotesis Goldbach valid untuk bilangan kurang dari 300.000.
Total
Segalanya ternyata tidak sesederhana yang tampak bagi saya pada awalnya, dan saya mengerti bahwa saya sama sekali tidak akan menyelesaikan masalah.
Kemungkinan besar, menurut saya ada opsi yang lebih baik untuk memeriksa nomor untuk kesederhanaan. Ada kemungkinan bahwa metode yang memeriksa angka genap untuk kebenaran pernyataan Goldbach dapat diterapkan lebih rasional daripada penghitungan bilangan prima sederhana, tetapi saya tidak lagi ingin menghabiskan banyak waktu untuk ini ...
Memecahkan masalah Goldbach tidak akan memberikan apa-apa bagi umat manusia. Sejauh ini, hipotesis tersebut terbukti benar untuk bilangan hingga 4 * 10 ^ 18, tetapi apa gunanya membuktikannya untuk semua bilangan? Untuk tujuan apa ahli matematika menulis buku tentang topik ini dan biasanya menghabiskan waktu mereka untuk memecahkan "masalah" seperti itu?
Saya benar-benar ingin bertanya kepada orang-orang yang berpengetahuan apakah rumus saya untuk menghitung jumlah bilangan prima per rentang memiliki hak untuk ada?
PS
Kemungkinan besar, saya tidak perlu menulis artikel yang saya tahu sedikit. Saya tidak menyangka masyarakat akan bereaksi seperti ini. Tetapi saya tidak berpura-pura bahwa solusi saya adalah satu-satunya solusi yang benar. Saya seorang amatir di bidang ini.
Untuk tujuan apa saya menulis artikel ini?
Saya meluangkan waktu untuk meneliti pertanyaan ini, dan bagi saya sepertinya beberapa orang mungkin menyukainya. Itu menarik bagi saya karena itu adalah tugas yang menyenangkan. Tapi mengapa matematikawan membuang-buang waktu untuk ini? Saya benar-benar tidak memahami manfaat sebenarnya dari meneliti pertanyaan khusus ini.
PPS
Setelah membaca ulasan tentang artikel tersebut, saya memutuskan untuk menarik kesimpulan.
Kemungkinan besar, menurut saya ada opsi yang lebih baik untuk memeriksa nomor untuk kesederhanaan
Seperti yang disarankan oleh pengguna dvserg.dll drWhy dan Pavel_The_Bestitu benar. Misalnya, dengan menggunakan saringan Eratosthenes, pengumpulan bilangan prima dapat dikumpulkan lebih cepat. Berikut adalah artikel yang dapat Anda baca tentang topik ini: Algoritma untuk memeriksa kesederhanaan di O (log N) , Wikipedia , Anda dapat membaca karya Srinivas Ramanujan Iyengor
Apakah rumus saya untuk menghitung bilangan prima per rentang berhak ada?
Tidak
Memecahkan Masalah Goldbach Tidak Akan Memberi Apa-apa bagi Kemanusiaan?
Pendapat saya bahwa beberapa soal matematika tidak berguna menyebabkan sikap negatif yang tajam dari sebagian besar pengguna. Penggunavvadzim.dll Refridgerator bromzh Buat grafik Refridgerator EimKR bfDeveloper dan yamampu meyakinkan saya tentang ini. Aku menarik kata-kataku kembali.
Sejak zaman kuno, matematikawan telah mencari kebenaran, dan pencarian mereka sering kali menghasilkan konsekuensi yang menguntungkan untuk kemajuan. Mungkin masalah itu sendiri dan solusinya tidak akan memberi dunia apa-apa di sini dan saat ini, tetapi kesimpulan yang diambil selama pencarian solusi yang dapat berguna dalam jangka panjang.