1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 11 November 2023
- # https://github.com/trizen
- # A simple factorization method, based on Sophie Germain's identity:
- # x^4 + 4y^4 = (x^2 + 2xy + 2y^2) * (x^2 - 2xy + 2y^2)
- # This method is also effective for numbers of the form: n^4 + 4^(2k+1).
- # See also:
- # https://oeis.org/A227855 -- Numbers of the form x^4 + 4*y^4.
- # https://www.quora.com/What-is-Sophie-Germains-Identity
- func sophie_germain_decomposition(n) {
- var t = n.iroot(4)
- var u = (n - t**4)>>2
- if (u.is_power(4)) {
- var (x,y) = (t, u.iroot(4))
- assert_eq(n, x**4 + 4*y**4)
- return [x, y]
- }
- var t = (4*n).iroot(4)>>1
- var u = (n - 4*t**4)
- if (u.is_power(4)) {
- var (x,y) = (u.iroot(4), t)
- assert_eq(n, x**4 + 4*y**4)
- return [x, y]
- }
- return []
- }
- func sophie_germain_factors(n) {
- var arr = sophie_germain_decomposition(n) || return []
- var (x,y) = arr...
- var f = [x**2 - 2*x*y + 2*y**2, x**2 + 2*x*y + 2*y**2]
- assert_eq(f.prod, n)
- return f
- }
- var x = 642393874177414576297153561759
- var y = 714067453700987
- for n in ([(x**4 + 4*y**4), (4*x**4 + y**4)]) {
- say sophie_germain_decomposition(n)
- }
- assert_eq(sophie_germain_decomposition(x**4 + 4*y**4), [x, y])
- assert_eq(sophie_germain_decomposition(y**4 + 4*x**4), [y, x])
- say sophie_germain_factors(77001290479960160497341160397504245)
- say sophie_germain_factors(19250322619990040124335290452638485)
- say sophie_germain_factors(27606985387162255149739023449108101809804435888681546220650096903087665)
- say sophie_germain_factors(173291855882550928723650886508942731464777317210988535948154973788413831737851601439998400381508723631086950685087723242628644864)
- say sophie_germain_factors(13093562431584567480052758787310396608866568184172259157933165472384535185618698219533080369303616628603546736510240284036869026183541572213318079483505)
- __END__
- [642393874177414576297153561759, 714067453700987]
- [714067453700987, 642393874177414576297153561759]
- [277491095817736105, 277491031750210669]
- [138745604154213509, 138745459629795665]
- [166153499473114514665395754616490745, 166153499473114453560556010453601017]
- [13164036458569648337239753460497746266300898132282617629258080512, 13164036458569648337239753460419861813422875717854660184319779072]
- [3618502788666131106986593281521497141767405545090156208559806116590740633113, 3618502788666131106986593281521497099061968496512379043906292883903830095385]
|