12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 02 June 2022
- # https://github.com/trizen
- # Compute the least Chinese signature of n with respect to the prime numbers,
- # such that when the Chinese Remainder Theorem (CRT) is aplied, n is constructed.
- # Example:
- # The prime Chinese signature of 53 is [1,2,3,4], which represents:
- # 53 == 1 (mod 2)
- # 53 == 2 (mod 3)
- # 53 == 3 (mod 5)
- # 53 == 4 (mod 7)
- # By applying the CRT, we have:
- # chinese(Mod(1,2), Mod(2,3), Mod(3,5), Mod(4,7)) == 53
- func chinese_prime_signature(n) {
- var crt = Mod(n, 2)
- var sgn = [crt.lift]
- 3..n -> each_prime {|p|
- if (crt.lift == n) {
- break
- }
- var r = Mod(n, p)
- crt = chinese(crt, r)
- sgn << r.lift
- }
- return sgn
- }
- for n in (1..35) {
- say "#{n} = #{chinese_prime_signature(n)}"
- }
- __END__
- 1 = [1]
- 2 = [0]
- 3 = [1, 0]
- 4 = [0, 1]
- 5 = [1, 2]
- 6 = [0, 0, 1]
- 7 = [1, 1, 2]
- 8 = [0, 2, 3]
- 9 = [1, 0, 4]
- 10 = [0, 1, 0]
- 11 = [1, 2, 1]
- 12 = [0, 0, 2]
- 13 = [1, 1, 3]
- 14 = [0, 2, 4]
- 15 = [1, 0, 0]
- 16 = [0, 1, 1]
- 17 = [1, 2, 2]
- 18 = [0, 0, 3]
- 19 = [1, 1, 4]
- 20 = [0, 2, 0]
- 21 = [1, 0, 1]
- 22 = [0, 1, 2]
- 23 = [1, 2, 3]
- 24 = [0, 0, 4]
- 25 = [1, 1, 0]
- 26 = [0, 2, 1]
- 27 = [1, 0, 2]
- 28 = [0, 1, 3]
- 29 = [1, 2, 4]
- 30 = [0, 0, 0, 2]
- 31 = [1, 1, 1, 3]
- 32 = [0, 2, 2, 4]
- 33 = [1, 0, 3, 5]
- 34 = [0, 1, 4, 6]
- 35 = [1, 2, 0, 0]
|