sidef-scripts/Math/chinese_prime_signature.sf

#!/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]