experimental-projects/factordb/factorize_product_of_expressions.sf

#!/usr/bin/ruby

# Find algebraic factors of a product of expressions.

#var expr = "I(9517)*I(9456)*I(9395)*I(9334)*I(9273)*I(9212)*I(9151)*I(9090)*I(9029)*I(8968)*I(8907)*I(8846)*I(8785)*I(8724)*I(8663)*I(8602)*I(8541)*I(8480)*I(8419)*I(8358)*I(8297)*I(8236)*I(8175)*I(8114)*I(8053)*I(7992)*I(7931)*I(7870)*I(7809)*I(7748)*I(7687)*I(7626)*I(7565)*I(7504)*I(7443)*I(7382)*I(7321)*I(7260)*I(7199)*I(7138)*I(7077)*I(7016)*I(6955)*I(6894)*I(6833)*I(6772)*I(6711)*I(6650)*I(6589)*I(6528)*I(6467)*I(6406)*I(6345)*I(6284)*I(6223)*I(6162)*I(6101)*I(6040)*I(5979)*I(5918)*I(5857)*I(5796)*I(5735)*I(5674)*I(5613)*I(5552)*I(5491)*I(5430)*I(5369)*I(5308)*I(5247)*I(5186)*I(5125)*I(5064)*I(5003)*I(4942)*I(4881)*I(4820)*I(4759)*I(4698)*I(4637)*I(4576)*I(4515)*I(4454)*I(4393)*I(4332)*I(4271)*I(4210)*I(4149)*I(4088)*I(4027)*I(3966)*I(3905)*I(3844)*I(3783)*I(3722)*I(3661)*I(3600)*I(3539)*I(3478)*I(3417)*I(3356)*I(3295)*I(3234)*I(3173)*I(3112)*I(3051)*I(2990)*I(2929)*I(2868)*I(2807)*I(2746)*I(2685)*I(2624)*I(2563)*I(2502)*I(2441)*I(2380)*I(2319)*I(2258)*I(2197)*I(2136)*I(2075)*I(2014)*I(1953)*I(1892)*I(1831)*I(1770)*I(1709)*I(1648)*I(1587)*I(1526)*I(1465)*I(1404)*I(1343)*I(1282)*I(1221)*I(1160)*I(1099)*I(1038)*I(977)*I(916)*I(855)*I(794)*I(733)*I(672)*I(611)*I(550)*I(489)*I(428)*I(367)*I(306)*I(245)*I(184)*I(123)*I(62)"
var expr = "(100000000000000^36+1)*(97656250000000^36+1)*(95367431640625^36+1)*(87960930222080^36+1)*(85899345920000^36+1)*(83886080000000^36+1)*(81920000000000^36+1)*(80000000000000^36+1)*(78125000000000^36+1)*(76293945312500^36+1)*(70368744177664^36+1)*(68719476736000^36+1)*(64000000000000^36+1)*(65536000000000^36+1)*(67108864000000^36+1)*(62500000000000^36+1)*(61035156250000^36+1)*(54975581388800^36+1)*(53687091200000^36+1)*(52428800000000^36+1)*(51200000000000^36+1)*(50000000000000^36+1)*(48828125000000^36+1)*(43980465111040^36+1)*(42949672960000^36+1)*(41943040000000^36+1)*(40960000000000^36+1)*(39062500000000^36+1)*(40000000000000^36+1)*(38146972656250^36+1)*(35184372088832^36+1)*(34359738368000^36+1)*(33554432000000^36+1)*(32768000000000^36+1)*(32000000000000^36+1)*(31250000000000^36+1)*(30517578125000^36+1)*(27487790694400^36+1)*(26843545600000^36+1)*(26214400000000^36+1)*(25600000000000^36+1)*(25000000000000^36+1)*(24414062500000^36+1)*(21990232555520^36+1)*(20480000000000^36+1)*(21474836480000^36+1)*(20971520000000^36+1)*(20000000000000^36+1)*(19531250000000^36+1)*(19073486328125^36+1)*(17592186044416^36+1)*(17179869184000^36+1)*(16777216000000^36+1)*(16384000000000^36+1)*(16000000000000^36+1)*(15625000000000^36+1)*(15258789062500^36+1)*(13421772800000^36+1)*(13107200000000^36+1)*(13743895347200^36+1)*(12207031250000^36+1)*(12800000000000^36+1)*(12500000000000^36+1)*(10995116277760^36+1)*(10737418240000^36+1)*(10485760000000^36+1)*(10240000000000^36+1)*(10000000000000^36+1)*(9765625000000^36+1)*(8796093022208^36+1)*(8589934592000^36+1)*(8388608000000^36+1)*(7812500000000^36+1)*(8192000000000^36+1)*(8000000000000^36+1)*(7629394531250^36+1)*(6871947673600^36+1)*(6710886400000^36+1)*(6553600000000^36+1)*(6400000000000^36+1)*(6250000000000^36+1)*(6103515625000^36+1)*(5497558138880^36+1)*(5368709120000^36+1)*(5242880000000^36+1)*(5120000000000^36+1)*(5000000000000^36+1)*(4882812500000^36+1)*(4398046511104^36+1)*(4194304000000^36+1)*(4096000000000^36+1)*(4294967296000^36+1)*(4000000000000^36+1)*(3906250000000^36+1)*(3814697265625^36+1)*(3435973836800^36+1)*(3355443200000^36+1)*(3276800000000^36+1)*(3200000000000^36+1)*(3125000000000^36+1)*(3051757812500^36+1)*(2748779069440^36+1)*(2684354560000^36+1)*(2621440000000^36+1)*(2500000000000^36+1)*(2560000000000^36+1)*(2441406250000^36+1)*(2199023255552^36+1)*(2147483648000^36+1)*(2097152000000^36+1)*(2048000000000^36+1)*(2000000000000^36+1)*(1953125000000^36+1)*(1717986918400^36+1)*(1677721600000^36+1)*(1638400000000^36+1)*(1600000000000^36+1)*(1562500000000^36+1)*(1525878906250^36+1)*(1374389534720^36+1)*(1342177280000^36+1)*(1310720000000^36+1)*(1220703125000^36+1)*(1250000000000^36+1)*(1280000000000^36+1)*(1099511627776^36+1)*(1073741824000^36+1)*(1048576000000^36+1)*(1024000000000^36+1)*(1000000000000^36+1)*(976562500000^36+1)*(858993459200^36+1)*(838860800000^36+1)*(819200000000^36+1)*(800000000000^36+1)*(781250000000^36+1)*(762939453125^36+1)*(687194767360^36+1)*(640000000000^36+1)*(671088640000^36+1)*(655360000000^36+1)*(625000000000^36+1)*(610351562500^36+1)*(549755813888^36+1)*(536870912000^36+1)*(524288000000^36+1)*(512000000000^36+1)*(500000000000^36+1)*(488281250000^36+1)*(409600000000^36+1)*(429496729600^36+1)*(419430400000^36+1)*(390625000000^36+1)*(400000000000^36+1)*(343597383680^36+1)*(335544320000^36+1)*(327680000000^36+1)*(320000000000^36+1)*(312500000000^36+1)*(305175781250^36+1)*(274877906944^36+1)*(268435456000^36+1)*(262144000000^36+1)*(256000000000^36+1)*(250000000000^36+1)*(244140625000^36+1)*(204800000000^36+1)*(209715200000^36+1)*(214748364800^36+1)*(200000000000^36+1)*(195312500000^36+1)*(171798691840^36+1)*(167772160000^36+1)*(163840000000^36+1)*(160000000000^36+1)*(156250000000^36+1)*(152587890625^36+1)*(137438953472^36+1)*(134217728000^36+1)*(131072000000^36+1)*(125000000000^36+1)*(122070312500^36+1)*(128000000000^36+1)*(107374182400^36+1)*(102400000000^36+1)*(100000000000^36+1)*(104857600000^36+1)*(97656250000^36+1)*(85899345920^36+1)*(83886080000^36+1)*(81920000000^36+1)*(80000000000^36+1)*(78125000000^36+1)*(68719476736^36+1)*(67108864000^36+1)*(65536000000^36+1)*(64000000000^36+1)*(62500000000^36+1)*(61035156250^36+1)*(53687091200^36+1)*(50000000000^36+1)*(52428800000^36+1)*(51200000000^36+1)*(48828125000^36+1)*(42949672960^36+1)*(41943040000^36+1)*(40960000000^36+1)*(40000000000^36+1)*(39062500000^36+1)*(34359738368^36+1)*(32000000000^36+1)*(33554432000^36+1)*(32768000000^36+1)*(30517578125^36+1)*(31250000000^36+1)*(26214400000^36+1)*(26843545600^36+1)*(25000000000^36+1)*(25600000000^36+1)*(24414062500^36+1)*(21474836480^36+1)*(20971520000^36+1)*(20480000000^36+1)*(20000000000^36+1)*(19531250000^36+1)*(17179869184^36+1)*(16777216000^36+1)*(16384000000^36+1)*(16000000000^36+1)*(15625000000^36+1)*(13421772800^36+1)*(13107200000^36+1)*(12800000000^36+1)*(12500000000^36+1)*(12207031250^36+1)*(10737418240^36+1)*(10485760000^36+1)*(10240000000^36+1)*(10000000000^36+1)*(9765625000^36+1)*(8388608000^36+1)*(8589934592^36+1)*(8000000000^36+1)*(7812500000^36+1)*(8192000000^36+1)*(6553600000^36+1)*(6400000000^36+1)*(6710886400^36+1)*(6250000000^36+1)*(6103515625^36+1)*(5368709120^36+1)*(5242880000^36+1)*(5120000000^36+1)*(5000000000^36+1)*(4882812500^36+1)*(4294967296^36+1)*(4194304000^36+1)*(4096000000^36+1)*(4000000000^36+1)*(3906250000^36+1)*(3200000000^36+1)*(3355443200^36+1)*(3276800000^36+1)*(3125000000^36+1)*(2684354560^36+1)*(2621440000^36+1)*(2560000000^36+1)*(2500000000^36+1)*(2441406250^36+1)*(2147483648^36+1)*(2097152000^36+1)*(2048000000^36+1)*(2000000000^36+1)*(1953125000^36+1)*(1677721600^36+1)*(1600000000^36+1)*(1638400000^36+1)*(1562500000^36+1)*(1310720000^36+1)*(1342177280^36+1)*(1280000000^36+1)*(1250000000^36+1)*(1220703125^36+1)*(1073741824^36+1)*(1048576000^36+1)*(1024000000^36+1)*(1000000000^36+1)*(976562500^36+1)*(838860800^36+1)*(781250000^36+1)*(819200000^36+1)*(800000000^36+1)*(640000000^36+1)*(655360000^36+1)*(671088640^36+1)*(625000000^36+1)*(536870912^36+1)*(524288000^36+1)*(512000000^36+1)*(500000000^36+1)*(488281250^36+1)*(419430400^36+1)*(409600000^36+1)*(390625000^36+1)*(400000000^36+1)*(320000000^36+1)*(335544320^36+1)*(327680000^36+1)*(312500000^36+1)*(262144000^36+1)*(268435456^36+1)*(256000000^36+1)*(250000000^36+1)*(244140625^36+1)*(209715200^36+1)*(204800000^36+1)*(200000000^36+1)*(195312500^36+1)*(167772160^36+1)*(163840000^36+1)*(160000000^36+1)*(156250000^36+1)*(131072000^36+1)*(134217728^36+1)*(125000000^36+1)*(128000000^36+1)*(104857600^36+1)*(102400000^36+1)*(100000000^36+1)*(97656250^36+1)*(83886080^36+1)*(81920000^36+1)*(80000000^36+1)*(78125000^36+1)*(67108864^36+1)*(65536000^36+1)*(64000000^36+1)*(62500000^36+1)*(51200000^36+1)*(50000000^36+1)*(52428800^36+1)*(48828125^36+1)*(41943040^36+1)*(40960000^36+1)*(40000000^36+1)*(39062500^36+1)*(33554432^36+1)*(32768000^36+1)*(32000000^36+1)*(31250000^36+1)*(26214400^36+1)*(25000000^36+1)*(25600000^36+1)*(20480000^36+1)*(20971520^36+1)*(20000000^36+1)*(19531250^36+1)*(16777216^36+1)*(16384000^36+1)*(16000000^36+1)*(15625000^36+1)*(13107200^36+1)*(12800000^36+1)*(12500000^36+1)*(10240000^36+1)*(10000000^36+1)*(10485760^36+1)*(9765625^36+1)*(8388608^36+1)*(8000000^36+1)*(7812500^36+1)*(8192000^36+1)*(6400000^36+1)*(6553600^36+1)*(6250000^36+1)*(5242880^36+1)*(5120000^36+1)*(5000000^36+1)*(4194304^36+1)*(4096000^36+1)*(4000000^36+1)*(3906250^36+1)*(3276800^36+1)*(3200000^36+1)*(3125000^36+1)*(2621440^36+1)*(2500000^36+1)*(2560000^36+1)*(2097152^36+1)*(2048000^36+1)*(2000000^36+1)*(1953125^36+1)*(1638400^36+1)*(1600000^36+1)*(1562500^36+1)*(1310720^36+1)*(1280000^36+1)*(1250000^36+1)*(1024000^36+1)*(1000000^36+1)*(1048576^36+1)*(781250^36+1)*(800000^36+1)*(819200^36+1)*(655360^36+1)*(640000^36+1)*(625000^36+1)*(524288^36+1)*(512000^36+1)*(500000^36+1)*(409600^36+1)*(400000^36+1)*(390625^36+1)*(327680^36+1)*(320000^36+1)*(312500^36+1)*(262144^36+1)*(256000^36+1)*(250000^36+1)*(204800^36+1)*(200000^36+1)*(163840^36+1)*(160000^36+1)*(156250^36+1)*(131072^36+1)*(128000^36+1)*(125000^36+1)*(100000^36+1)*(102400^36+1)*(78125^36+1)*(81920^36+1)*(80000^36+1)*(64000^36+1)*(65536^36+1)*(62500^36+1)*(51200^36+1)*(50000^36+1)*(40960^36+1)*(40000^36+1)*(32768^36+1)*(32000^36+1)*(31250^36+1)*(25600^36+1)*(25000^36+1)*(20480^36+1)*(20000^36+1)*(16000^36+1)*(16384^36+1)*(15625^36+1)*(12800^36+1)*(12500^36+1)*(10240^36+1)*(10000^36+1)*(8192^36+1)*(8000^36+1)*(6400^36+1)*(6250^36+1)*(5120^36+1)*(5000^36+1)*(4096^36+1)*(4000^36+1)*(3200^36+1)*(3125^36+1)*(2500^36+1)*(2560^36+1)*(2048^36+1)*(2000^36+1)*(1600^36+1)*(1280^36+1)*(1250^36+1)*(1024^36+1)*(1000^36+1)*(800^36+1)*(640^36+1)*(625^36+1)*(512^36+1)*(500^36+1)*(400^36+1)*(320^36+1)*(256^36+1)*(250^36+1)*(200^36+1)*(160^36+1)*(128^36+1)*(125^36+1)*(100^36+1)*(80^36+1)*(64^36+1)*(50^36+1)*(40^36+1)*(32^36+1)*(25^36+1)*(20^36+1)*(16^36+1)*(10^36+1)*(8^36+1)*(5^36+1)*(4^36+1)*(2^36+1)"

var factors = []

define(
    FACTORIZE_EXPRESSIONS = true,      # true to factorize the individual expressions
)

func format_factors(n, f) {
    Math.gcd_factors(n, f).first(-1).join(' * ')
}

expr.split('*').each {|line|

        if (line =~ /I\((\d+)\)/) { |match|
            var n = Num(match[0])
            next if n.is_prime

            var t = n.fib
            var f = n.divisors.map{.fib}

            if (FACTORIZE_EXPRESSIONS) {
                say "I(#{n}) = #{format_factors(t, f)}"
            }
            else {
                factors << f...
            }
        }

        if (line =~ /\((\d+)\^(\d+)-1/) {|match|
            var a = Num(match[0])
            var b = Num(match[1])

            var t = (a**b - 1)
            var f = t.dop_factor

            if (FACTORIZE_EXPRESSIONS) {
                say "#{a}^#{b}-1 = #{format_factors(t, f)}"
            }
            else {
                factors << f...
            }
        }

        if (line =~ /\((\d+)\^(\d+)\+1/) {|match|
            var a = Num(match[0])
            var b = Num(match[1])

            var t = (a**b + 1)
            var f = t.dop_factor

            if (FACTORIZE_EXPRESSIONS) {
                say "#{a}^#{b}+1 = #{format_factors(t, f)}"
            }
            else {
                factors << f...
            }
        }
}

FACTORIZE_EXPRESSIONS && Sys.exit(0)

factors.uniq!

STDERR.say(":: Reading input data...")

# The input data contains the list of numbers from the "get_factordb.pl" script.

# Example:
#   perl get_factordb.pl [expr] | sidef factorize_product_of_expressions.sf

ARGF.lines.uniq.each {|line|
    var n = line.to_i

    next if n.is_prime

    var f = Math.gcd_factors(n, factors)
    f || next
    say "#{n} = #{f.first(-1).join(' * ')}"
}