123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 09 January 2019
- # https://github.com/trizen
- # Test if a large integer (>50 digits) is probably squarefree.
- # See also:
- # https://en.wikipedia.org/wiki/Square-free_integer
- # Tested up to 557
- func store_random_factor(a, f) {
- *a = f()
- (*a).len > 1
- }
- func find_random_factor(n, small=true, trial=false) {
- var e = []
- (trial && store_random_factor(\e, { n.trial_factor(1e6) })) ||
- (small && store_random_factor(\e, { n.pbrent_factor(1, 15000) })) ||
- (small && store_random_factor(\e, { n.pminus1_factor(50000, 500000) })) ||
- store_random_factor(\e, { n.pminus1_factor(1e6) }) ||
- store_random_factor(\e, { n.pplus1_factor(1e6) }) ||
- store_random_factor(\e, { n.ecm_factor(800, 10) }) ||
- store_random_factor(\e, { n.ecm_factor(8000, 20) }) ||
- #store_random_factor(\e, { n.ecm_factor(80000, 40) }) ||
- #store_random_factor(\e, { n.ecm_factor(320000, 40) }) ||
- #store_random_factor(\e, { n.ecm_factor(1000000, 80) }) ||
- store_random_factor(\e, { n.holf_factor(1e6) }) ||
- store_random_factor(\e, { n.squfof_factor(1e8) });
- return e
- }
- func is_prob_squarefree(r, tries=50) {
- if (r.len <= 50) {
- return r.is_square_free
- }
- return false if r.is_power
- loop {
- var f = r.trial_factor(1e6)
- break if (f.len == 1)
- r /= f[0]
- return false if (f[0] `divides` r)
- }
- tries.times { |k|
- var len = r.len
- if (len <= 50) {
- return r.is_square_free
- }
- if (len <= 10_000) {
- return true if r.is_prob_prime
- }
- var e = find_random_factor(r, k <= 3)
- e.len > 1 || break
- e.pop
- say "Factor: #{e[0]}"
- e.each {|p|
- if (p*p `divides` r) {
- return false
- }
- p.is_square_free || return false
- p.factor.each { |z|
- if (z*z `divides` r) {
- return false
- }
- }
- }
- e.each {|p| r /= p }
- if (r.is_power) {
- return false
- }
- }
- return true
- }
- func f(n) is cached {
- #return 1, 3, 9
- return 1 if (n == 0)
- return 3 if (n == 1)
- return 9 if (n == 2)
- 3*f(n-1) + 8*f(n-2)
- }
- for p in (primes(563, 1e6)) {
- say "Testing: #{p}"
- is_prob_squarefree(f(p)) || die "a(#{p}) is not squarefree!!!"
- }
- __END__
- # Example for testing several k such that 2^k + 1 is divisible by a square > 1.
- # See: https://oeis.org/A049096
- var a = [231, 234, 237, 243, 410, 411, 417, 891, 897, 903, 2370, 2373, 41390]
- a.each {|k|
- var t = is_prob_squarefree(2**k + 1)
- say "2^#{k} + 1 is #{t ? 'prob squarefree' : 'divisible by a square'}"
- }
- say "\nLarge non-squarefree tests:"
- say is_prob_squarefree(249860117627119815706149728420771785501032147277376706113) # false
- say is_prob_squarefree(1444134648503819781988817515640867565630266453262667463566673) # false
- say is_prob_squarefree(16240879415462221539256806220654226179619821855946633706672633593) # false
- say is_prob_squarefree(300973095636437173473855290756399701276460223130678583012549023809113) # false
|