1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980 |
- #!/usr/bin/ruby
- # a(n) is the least prime p such that the concatenation p|n has exactly n prime factors with multiplicity.
- # https://oeis.org/A358596
- # Known terms:
- # 3, 2, 83, 2, 67, 41, 947, 4519, 15659081, 2843, 337957, 389, 1616171, 6132829, 422116888343, 24850181, 377519743, 194486417892947, 533348873, 324403, 980825013273164555563, 25691144027, 273933405157, 1238831928746353181, 311195507789, 129917586781, 2159120477658983490299
- func almost_prime_numbers(a, b, k, callback) {
- a = max(2**k, a)
- var mod = 10**k.len
- func (m, lo, j) {
- var hi = idiv(b,m).iroot(j)
- if (lo > hi) {
- return nil
- }
- if (j == 1) {
- lo = max(lo, idiv_ceil(a, m))
- each_prime(lo, hi, {|p|
- var n = m*p
- var (q,r) = divmod(n, mod)
- if ((r == k) && (q.is_prime)) {
- callback(q)
- }
- })
- return nil
- }
- each_prime(lo, hi, {|p|
- __FUNC__(m*p, p, j-1)
- })
- }(1, 2, k)
- return callback
- }
- func a(n) {
- var x = 2**n
- var y = 2*x
- loop {
- var arr = gather {
- almost_prime_numbers(x, y, n, { take(_) })
- }.sort
- arr && return arr[0]
- x = y+1
- y = 2*x
- }
- }
- for n in (1..100) {
- say "#{n} #{a(n)}"
- }
- __END__
- 1 3
- 2 2
- 3 83
- 4 2
- 5 67
- 6 41
- 7 947
- 8 4519
- 9 15659081
- 10 2843
- 11 337957
- 12 389
- 13 1616171
- 14 6132829
|