12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 |
- #!/usr/bin/ruby
- # a(11) >= 85879
- for n in (5) {
- for k in (2 .. Inf) {
- say "Testing #{k}"
- k.is_prime && next
- powmod(n, k, (n-1)*k) == n || next
- (n**k - 1)/(n-1) % k == 1 || next
- k.factor.all {|p|
- (n**p - 1)/(n-1) % k == 1
- } || next
- #, so n^k == n (mod (n-1)k)
- var ok = true
- var t = (n**k - 1)/(n-1)
- var orig = t
- var trial = true
- while (t > 1) {
- if (t.len < 60) {
- ok = t.divisors.all { |d| (d%k == 1) && ((orig/d) % k == 1) }
- break
- }
- say "Factoring...";
- var f = (trial ? t.pminus1_factor : t.ecm_factor)
- if ((f.len == 1) && (!trial) && (f[-1].is_prob_prime)) {
- ok = ((t%k == 1) && ((orig/t)%k == 1))
- break
- }
- if (trial && (f.len == 1)) {
- say "Factoring again..."
- trial = false;
- f = t.ecm_factor
- }
- say f.slice(0,-1)
- (f[-1]%k == 1) && ((orig/f[-1])%k == 1) || do {
- say "Last factor counter-example";
- ok = false;
- break;
- };
- # say f
- assert(f.len > 1)
- f.slice(0,-1).all {|d|
- (d%k == 1) &&
- ((orig/d)%k == 1) && d.divisors.all {|d|
- (d%k == 1) && ((orig/d)%k == 1)
- }
- } || do {
- #say "Counter-example for k=#{k} with #{f.slice(-1)}"
- ok = false
- break
- }
- t = f.pop
- }
- ok || next
- say "Found: a(#{n}) = #{k}"
- break
- #if ( -> divisors.all { _%k == 1}) {
- # say "a(#{n}) = #{k}"
- # break
- #}
- }
- }
|