Angka yang Tidak Tersentuh α
Bilangan tak tersentuh adalah bilangan bulat positif yang tidak dapat dinyatakan sebagai jumlah dari semua pembagi yang tepat dari bilangan bulat positif apa pun (termasuk bilangan tak tersentuh itu sendiri).
Misalnya, angka 4 tidak tersentuh karena sama dengan jumlah pembagi yang tepat dari 9: 1 + 3 = 4. Angka 5 tidak tersentuh karena bukan jumlah pembagi yang tepat dari bilangan bulat positif. 5 = 1 + 4 adalah satu-satunya cara untuk menulis 5 sebagai jumlah bilangan bulat positif yang berbeda termasuk 1, tetapi jika 4 membagi angka, 2 juga, jadi 1 + 4 tidak dapat menjadi jumlah semua pembagi yang tepat dari angka mana pun (karena daftar faktor harus mengandung 4 dan 2).
Angka 5 diyakini sebagai satu-satunya angka yang tidak dapat disentuh yang aneh, tetapi ini belum terbukti: itu akan mengikuti versi dugaan Goldbach yang sedikit lebih kuat. β
Ada banyak sekali angka yang tak tersentuh, fakta yang dibuktikan oleh Paul Erd.
Beberapa properti yang tak tersentuh:
- Tidak tersentuh adalah 1 lebih besar dari perdana
- Tidak ada yang tidak tersentuh adalah 3 lebih besar dari prime, kecuali 5
- Tidak tersentuh adalah angka sempurna
- Hingga saat ini, semua yang tidak tersentuh selain dari 2 dan 5 adalah komposit.
Objektif
Buat program atau fungsi yang mengambil bilangan alami n
melalui input standar atau parameter fungsi dan mencetak n
angka-angka pertama yang tidak tersentuh.
Output harus memiliki pemisahan antara angka-angka, tetapi ini bisa berupa apa saja (yaitu baris baru, koma, spasi, dll).
Setidaknya ini harus bisa bekerja 1 <= n <= 8153
. Ini didasarkan pada kenyataan bahwa file-b yang disediakan untuk entri OEIS γ naik ke n = 8153
.
Celah standar tidak diizinkan, seperti biasa.
Contoh I / O
1 -> 2
2 -> 2, 5
4 -> 2, 5, 52, 88
10 -> 2, 5, 52, 88, 96, 120, 124, 146, 162, 188
8153 -> 2, 5, 52, 88, 96, 120, ..., ..., ..., 59996
Ini adalah kode-golf , jadi paling tidak jumlah byte yang menang.
α - Wikipedia , β - MathWorld , γ - OEIS
Untuk beberapa alasan, ini ditandai sebagai duplikat untuk pertanyaan 'menemukan angka semiperfect', namun tugasnya sangat berbeda. Dalam hal ini, Anda harus memeriksa untuk memastikan bahwa tidak ada jumlah pembagi sempurna dari setiap bilangan asli dapat sama dengan bilangan tertentu.
Jawaban:
Pyth, 21 byte
Peringatan: Sangat lambat. Uji coba dan waktunya di bawah.
Ini pada dasarnya sekuat tenaga, menguji faktorisasi hingga jumlah potensial yang sepi ditambah satu.
sumber
C, 104 byte
Diperlukan beberapa menit untuk y > 20, tetapi apa pun.
sumber
Java, 310 Bytes
Bermain golf sebaik yang saya bisa, tetapi saya lebih tertarik untuk memastikan itu berjalan dalam waktu yang wajar. Versi unglofed mungkin lebih menarik
sumber
Pergi, 396 byte
Tidak benar-benar bermain golf, tetapi dapat melakukan semua rentang yang diperlukan. Berjalan sekitar ~ 20 menit dan kebutuhan ~ 7GB (independen n). Membuat array raksasa untuk menghitung jumlah pembagi untuk semua angka hingga 59997 kuadrat.
sumber