12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 |
- #!/usr/bin/ruby
- # Least positive k such that n*k^k - 1 is a prime, or 0 if no such k exists.
- # https://oeis.org/A231735
- # Known terms:
- # 2, 2, 1, 1, 2, 1, 1128, 1, 0, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 14, 1, 0, 2, 2, 6, 206, 1, 1590, 1, 2, 11, 2, 3
- # From Gordon Atkinson, Aug 20 2019:
- # For all odd numbers n>3, a(n) is even.
- # For all odd numbers n>1, a(n^2) = 0.
- # ((2*n+1)^2 * (2*k)^(2*k) - 1) = (2^(k+1) * k^k * n + 2^k * k^k - 1) * (2^(k+1) * k^k * n + 2^k * k^k + 1)
- # ((2*n+1)^2 * (2*k+1)^(2*k+1) - 1) = 8*k * (2*k + 1)^(2*k) * n^2 + 4*(2*k + 1)^(2*k) * n^2 + 8*k * (2*k+1)^(2*k)*n + 4*(2*k+1)^(2*k)*n + 2*k*(2*k+1)^(2*k) + (2*k+1)^(2*k) - 1
- func a(n) {
- n.is_square && n.isqrt.is_odd && return 0
- 1..Inf -> first {|k|
- is_prob_prime(n * k**k - 1)
- }
- }
- # a(37) >= 9114
- # a(43) >= 4704
- # a(46) >= 1380
- # Terms 38..42:
- # 1, 6, 6, 2, 1
- # Terms 44..45
- # 1, 2
- 38..42 -> map(a).say
- 44..45 -> map(a).say
- #__END__
- func b(n, from = 1) {
- for k in (from .. 1e6 `by` 2) {
- say "Testing: #{k}"
- if (is_prob_prime(k**k * n - 1)) {
- die "Found: #{k}"
- }
- }
- }
- b(37, 9114)
- #b(43, 4704)
- #b(46, 1380)
|