160307

Ruby

10^(2 i) + 10^i + 1 の素因数分解

オンライン整数列大辞典の
A190839（http://oeis.org/A190839/list）
を用いた。

require 'prime'

# OEIS A190839のデータ
ps =
[37,37,333667,9901,2906161,333667,10838689,
 99990001,440334654777631,2906161,
 1344628210313298373,999999000001,
 900900900900990990990991,10838689,
 4185502830133110721,9999999900000001,
 13168164561429877,440334654777631,
 3931123022305129377976519,39526741]

m = 21
(0..m).each{|i|
  j = 10 ** (i * 2) + 10 ** i + 1
  if i == 0
    p [3, [[3, 1]]]
  elsif i <= 20
    p [j, Prime.prime_division(j / ps[i - 1]) + [[ps[i - 1], 1]]]
  else
    p [j, Prime.prime_division(j)]
  end
}

出力結果
[3, [[3, 1]]]
[111, [[3, 1], [37, 1]]]
[10101, [[3, 1], [7, 1], [13, 1], [37, 1]]]
[1001001, [[3, 1], [333667, 1]]]
[100010001, [[3, 1], [7, 1], [13, 1], [37, 1], [9901, 1]]]
[10000100001, [[3, 1], [31, 1], [37, 1], [2906161, 1]]]
[1000001000001, [[3, 1], [19, 1], [52579, 1], [333667, 1]]]
[100000010000001, [[3, 1], [37, 1], [43, 1], [1933, 1], [10838689, 1]]]
[10000000100000001, [[3, 1], [7, 1], [13, 1], [37, 1], [9901, 1], [99990001, 1]]]
[1000000001000000001, [[3, 1], [757, 1], [440334654777631, 1]]]
[100000000010000000001, [[3, 1], [7, 1], [13, 1], [31, 1], [37, 1], [211, 1], [241, 1], [2161, 1], [2906161, 1]]]
[10000000000100000000001, [[3, 1], [37, 1], [67, 1], [1344628210313298373, 1]]]
[1000000000001000000000001, [[3, 1], [19, 1], [52579, 1], [333667, 1], [999999000001, 1]]]
[100000000000010000000000001, [[3, 1], [37, 1], [900900900900990990990991, 1]]]
[10000000000000100000000000001, [[3, 1], [7, 2], [13, 1], [37, 1], [43, 1], [127, 1], [1933, 1], [2689, 1], [459691, 1], [10838689, 1]]]
[1000000000000001000000000000001, [[3, 1], [238681, 1], [333667, 1], [4185502830133110721, 1]]]
[100000000000000010000000000000001, [[3, 1], [7, 1], [13, 1], [37, 1], [9901, 1], [99990001, 1], [9999999900000001, 1]]]
[10000000000000000100000000000000001, [[3, 1], [37, 1], [613, 1], [210631, 1], [52986961, 1], [13168164561429877, 1]]]
[1000000000000000001000000000000000001, [[3, 1], [757, 1], [70541929, 1], [14175966169, 1], [440334654777631, 1]]]
[100000000000000000010000000000000000001, [[3, 1], [37, 1], [21319, 1], [10749631, 1], [3931123022305129377976519, 1]]]
[10000000000000000000100000000000000000001, [[3, 1], [7, 1], [13, 1], [31, 1], [37, 1], [61, 1], [211, 1], [241, 1], [2161, 1], [9901, 1], [2906161, 1], [4188901, 1], [39526741, 1]]]
[1000000000000000000001000000000000000000001, [[3, 1], [10837, 1], [23311, 1], [45613, 1], [333667, 1], [45121231, 1], [1921436048294281, 1]]]