Temukan angka yang menghasilkan semua bilangan bulat mod q

9

Pertimbangkan bilangan bulat modulo di qmana qbilangan prima, generator bilangan bulat apa pun 1 < x < qsehingga x^1, x^2, ..., x^(q-1)mencakup semua q-1bilangan bulat di antara 1dan q-1. Sebagai contoh, perhatikan bilangan bulat modulo 7 (yang kami tulis sebagai Z_7). Kemudian 3, 3^2 mod 7 = 2, 3^3 = 27 mod 7 = 6, 3^4 = 81 mod 7 = 4, 3^5 = 243 mod 7 = 5, 3^6 = 729 mod 7 = 1mencakup semua nilai 3, 2, 6, 4, 5, 1mencakup semua bilangan bulat 1..6sesuai kebutuhan.

Tugasnya adalah menulis kode yang membutuhkan input ndan output generator Z_n. Anda tentu saja tidak dapat menggunakan builtin atau pustaka yang melakukan ini untuk Anda.

Satu-satunya batasan pada kinerja kode Anda adalah bahwa Anda harus mengujinya sampai selesai n = 4257452468389.

Perhatikan itu 2^n berarti 2kekuatan n. Itu ^mewakili eksponensial.


sumber
Hmm ... 1 < x < qmembuat tantangan imo jauh lebih mudah.
Erik the Outgolfer
@EriktheOutgolfer Saya tidak yakin saya tahu apa yang Anda maksud? Itu semua hanyalah bilangan bulat yang berbeda yang bukan 0 atau 1.
Maksud saya, ini lebih mudah daripada yang mungkin dipikirkan banyak orang ... atau mungkin momen tidak aktif di PPCG.
Erik the Outgolfer
3
Tapi saya pikir mengharuskan orang untuk mengujinya hingga selesai dalam jumlah besar tidak perlu ... pada dasarnya tio hanya akan kesalahan memori.
Erik the Outgolfer
@Lembik Apakah ada kasus di mana tidak ada generator untuk nomor tertentu? Beberapa test case akan bagus.
Tn. Xcoder

Jawaban:

13

Pyth, 16 15 byte

f-1m.^T/tQdQPtQ

Suite uji

Jika p adalah input, kita tahu bahwa g ^ (p-1) = 1 mod p, jadi kita hanya perlu memeriksa bahwa g ^ a! = 1 mod p untuk yang lebih kecil a. Tapi a harus menjadi faktor p-1 agar memungkinkan, dan kelipatan a dengan properti itu juga akan memiliki properti itu, jadi kita hanya perlu memeriksa g ^ ((p-1) / q)! = 1 mod p untuk semua faktor prima q dari p-1. Jadi, kami memeriksa semua bilangan bulat g dalam urutan yang meningkat hingga kami menemukan satu yang berfungsi.

Penjelasan:

f-1m.^T/tQdQPtQ
f                  Return the first value T such that the following is truthy:
            PtQ    Take the prime factorization of the input - 1.
   m               Map those prime factors to
       /tQd        Take the input - 1 divided by the factor
    .^T    Q       Raise T to that exponent mod input,
                   performed as modular exponentiation, for performance.
 -1                Check that 1 is not found among the results.
isaacg
sumber
Cukup mengagumkan!
Apakah kode Anda melakukan faktorisasi?
@Lembik Itu ( PtQbagian).
Erik the Outgolfer
5

Mathematica, 52 byte

Terinspirasi oleh jawaban isaacg .

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&
alephalpha
sumber
-3
%MATLAB CODE
%Program to generate Z_n for an integer n
n = input('Enter a number to find modulo')
q = input ('Enter a prime number greater than the number you wished to find modulo')
if n>=q 
   fprintf('Error')
   exit(1)
end
for R=1:q-1
    fprintf(rem(n.^R, q))
    fprintf('\n')
end
John Brookfields
sumber
1
Ini bukan memecahkan masalah yang tepat. Kode Anda harus, misalnya, mengambil satu input dan memberikan satu output.
1
Juga, kode ini tidak golf sama sekali. Kode golf harus sesingkat mungkin, sehingga Anda dapat menghapus teks input dan spasi di sekitar tanda sama dengan itu.
Kamerad SparklePony
3
@ComradeSparklePony Saya pikir masalah pertama yang tidak menyelesaikan masalah yang tepat harus ditangani terlebih dahulu :)