150620

Ruby


i (1以上9以下)を含むならば、i が i 個含む数の個数について(1)

i (1以上9以下)を含むならば、i が i 個含む数について

オンライン整数列大辞典のA108571に載っている。

また、この条件をみたす数の個数は
66712890763701234740813164553708284
であることも載っている。

さて、N進法のとき条件をみたす数の個数を求めてみる。

def factorial(m)

  (1..m).inject(:*)

end

def c(ary)

  sum = 0

  p = 1

  ary.each{|m|

    sum += m

    p *= factorial(m)

  }

  factorial(sum) / p

end

N = 20

(2..N).each{|n|

  s = 0

  (1..n - 1).each{|i|

    # i個の文字を使用

    (1..n - 1).to_a.combination(i){|ary|

      s += c(ary)

    }

  }

  p [n, s]

}

出力結果

[2, 1]

[3, 5]

[4, 80]

[5, 14381]

[6, 40885253]

[7, 2163451135829]

[8, 2525544441942679544]

[9, 75742010013818779294524291]

[10, 66712890763701234740813164553708284]

[11, 1942822997165179351555175450239287744555392665]

[12, 2080073366819317156363661211242237402694399273780324072649]

[13, 90119293418056939454016830629777394012980315428451803426514614495110994]

[14, 172455511938741999081801502699156952559204424009474834769855450110414719504

150224997558]

[15, 157986102253960981574445206052521197511653328373414551764354038895571390274

01448911234591184156199226978]

[16, 746442030816246157764653429242897250983760556051433948548329751407825856488

15412540158487503830483934552059902954171577605]

[17, 194945695614188169608419067260711262969994712345859557219548670082563980886

14502291258692509506601658052856424259637610563629746085130521420291]

[18, 300275814547418946820910664259718512972412140953192527318957576882139850782

55181991824197487253872154559471957395361481032033404019653356456027127282226298

8138910740]

[19, 289899468213502373867902815950578001530607279689328109339320546553053002418

86575154255270349007564269427340241998153036135878840443110759520091417773370119

0727029967708522620675887212828851]

[20, 185783061526404568110804790044210372472519765825214788837615964098447729062

50157408042296617329443569724170810698372794541477017718173686018716815466159770

719024873776518211993768384857812465924625616829947997242136]

150614

Conway-Guy sequence(2)

今日、「数論〈未解決問題〉の事典」の

「C8 部分集合の元の和が異なる場合」

という部分で

予想を証明したという声明がいくつか出されたが，すべて誤りであった．

という記述があったので、びっくりしたが、

この本は2004年にでた本で、

OEISのCOMMENTSには、

This conjecture has apparently now been proved by Bohman. - I. Halupczok (integerSequences(AT)karimmi.de), Feb 20 2006

とあるので、後者を信用することにしておこう。

150613(2)

Ruby


双子素数と隣り合う双子素数の和

双子素数については、

オンライン整数列大辞典の
A001359（http://oeis.org/A001359/list）
と比較し、答え合わせしてみる。

require 'prime'

def A001359(n)

  Prime.each(n).each_cons(2).select{|p, r| r - p == 2}.map{|c| c[0]}

end

ary = A001359(1607 + 2)

# OEIS A001359のデータ

ary0 =

[3,5,11,17,29,41,59,71,101,107,137,149,179,191,

 197,227,239,269,281,311,347,419,431,461,521,569,

 599,617,641,659,809,821,827,857,881,1019,1031,

 1049,1061,1091,1151,1229,1277,1289,1301,1319,1427,

 1451,1481,1487,1607]

# 一致の確認

p ary == ary0

def A(n)

  Prime.each(n).each_cons(2).select{|p, r| r - p == 2}.map{|c| c[0] + c[1]}

end

p A(1607 + 2)

出力結果

true

[8, 12, 24, 36, 60, 84, 120, 144, 204, 216, 276, 300, 360, 384, 396, 456, 480, 5

40, 564, 624, 696, 840, 864, 924, 1044, 1140, 1200, 1236, 1284, 1320, 1620, 1644

, 1656, 1716, 1764, 2040, 2064, 2100, 2124, 2184, 2304, 2460, 2556, 2580, 2604,

2640, 2856, 2904, 2964, 2976, 3216]

150613

Ruby


隣り合う素数の和

オンライン整数列大辞典の
A164653（http://oeis.org/A164653/list）
と比較し、答え合わせしてみる。

require 'prime'

def A164653(n)

  ary = [1, 3]

  ary += Prime.each(n).each_cons(2).map{|c| c[0] + c[1]}

end

ary = A164653(508 / 2 + 3)

# OEIS A164653のデータ

ary0 =

[1,3,5,8,12,18,24,30,36,42,52,60,68,78,84,90,100,

 112,120,128,138,144,152,162,172,186,198,204,210,

 216,222,240,258,268,276,288,300,308,320,330,340,

 352,360,372,384,390,396,410,434,450,456,462,472,

 480,492,508]

# 一致の確認

p ary == ary0

150607(3)

Ruby


Look-and-say sequence

（過去にも書いた気がするが、）オンライン整数列大辞典に

紹介されているPythonのコードをベースに書いてみた。

A005150（http://oeis.org/A005150/list）
と比較し、答え合わせしてみる。

def A005150(n)

  m = 1

  p = '1'

  ary = [1]

  while m < n

    q = ''

    idx = 0

    s = p.size

    while idx < s

      # 塊を見つける

      start = idx

      idx += 1

      while idx < s && p[idx] == p[start]

        idx += 1

      end

      # 塊 = (idx - start個のp[start])

      q = q + (idx - start).to_s + p[start]

    end

    p = q

    ary.push(p.to_i)

    m += 1

  end

  return ary

end

ary = A005150(15)

# OEIS A005150のデータ

ary0 =

[1,11,21,1211,111221,312211,13112221,1113213211,

 31131211131221,13211311123113112211,

 11131221133112132113212221,

 3113112221232112111312211312113211,

 1321132132111213122112311311222113111221131221,

 11131221131211131231121113112221121321132132211331222113112211,

 311311222113111231131112132112311321322112111312211312111322212311322113212221]

# 一致の確認

p ary == ary0

このコードを書いた後、以下の大変短いコードをネットで見つけた。
（http://rosettacode.org/wiki/Look-and-say_sequence#Ruby）

def lookandsay(str)

  str.gsub(/(.)\1*/) {$&.length.to_s + $1}

end

 

num = "1"

10.times do

  puts num

  num = lookandsay(num)

end

150607(2)

Ruby


Mian-Chowla sequence

オンライン整数列大辞典の
A005282（http://oeis.org/A005282/list）
と比較し、答え合わせしてみる。

N = 50

ary = [1]

s_ary = [2]

m = 2

while ary.size < N

  s_ary0 = []

  size = 0

  ary.each{|i|

    j = m + i

    break if s_ary.include?(j)

    s_ary0.push(j)

    size += 1

  }

  if size == ary.size

    j = m + m

    if !s_ary.include?(j)

      s_ary0.push(j)

      # m以下のs_aryの要素は以後使わないので、除いておく

      s_ary = (s_ary + s_ary0).select{|k| k > m}

      ary.push(m)

    end

  end

  m += 1

end

# OEIS A005282のデータ

ary0 =

[1,2,4,8,13,21,31,45,66,81,97,123,148,182,204,252,

 290,361,401,475,565,593,662,775,822,916,970,1016,

 1159,1312,1395,1523,1572,1821,1896,2029,2254,2379,

 2510,2780,2925,3155,3354,3591,3797,3998,4297,4433,

 4779,4851]

# 一致の確認

p ary == ary0

150607

Ruby


各桁の和と自身との和について

（「ピーター・フランクルの中学生でも分かる大学生にも解けない数学問題集②」
CHAPTER３のProblem４の一般化から）

自然数nをp進法で表したときの各桁の数の和をf(n)で表す。
a + f(a) = b + f(b) = c + f(c)
を満たすような,３つの異なる自然数a,b,cは存在だろうか。

元々は p = 10 で、
a = 10^13 - 108,
b = 10^13 - 99,
c = 10^13
等が条件を満たす。

さて、これを p < 8 のとき、力づくで解いた。

M = 7
N = 13

def f(i, m)
  return i if i < m
  s = 0
  s += i % m + f(i / m, m)
  s
end

(2..M).each{|m|
  h = {}
  (1..m ** N).each{|i|
    j = i + f(i, m)
    h.key?(j) ? h[j] = h[j].push(i) : h[j] = [i]
    if h[j].size == 3
      p [m, h[j].map{|k| k.to_s(m)}]
      break
    end
  }
}

出力結果
[2, ["1111011", "1111100", "10000000"]]
[3, ["212", "220", "1000"]]
[4, ["3333232", "3333301", "10000000"]]
[5, ["34", "41", "100"]]
[6, ["555555452", "555555501", "1000000000"]]
[7, ["55", "61", "100"]]

150603

Ruby


塊の個数

「ホワイト・ブロック」問題（http://riverplus.net/misc/20150531/）

とほとんど変わらないが、次の問題を考える。

m 色の石を n 個並べるとき、連続した石の塊の個数の期待値を

求めよ。

E(n + 1) = (E(n) + 1) × (m - 1) / m + E(n) × 1 / m = E(n) + (m - 1) / m

E(1) = 1

より、

E(n) = ((m - 1) n + 1) / m

と求まるが、

あえて地道に数える方法は以下のとおりである。

# （色を区別せず）塊を数える

def cnt(ary)

  s = 1

  ary.each_cons(2){|a| s += 1 if !(a[0] == a[1])}

  s

end

m, n = 2, 6

sum, x = 0, 0

(1..m).to_a.repeated_permutation(n){|c|

  sum += cnt(c)

  x += 1

}

# 塊の個数の期待値

p (sum + 0.0) / x

出力結果

3.5

150531(2)

Ruby


Gauss circle problem(1)

オンライン整数列大辞典の
A000328（http://oeis.org/A000328/list）
と比較し、答え合わせしてみる。

def f(r)

  s = 0

  q = r * r

  i = 1

  while q >= 2 * i - 1

    s0 = q / (2 * i - 1)

    if i % 2 == 1

      s += s0

    else

      s -= s0

    end

    i += 1

  end 

  s * 4 + 1

end

ary = (0..46).map{|i| f(i)}

# OEIS A000328のデータ

ary0 =

[1,5,13,29,49,81,113,149,197,253,317,377,441,529,

 613,709,797,901,1009,1129,1257,1373,1517,1653,

 1793,1961,2121,2289,2453,2629,2821,3001,3209,3409,

 3625,3853,4053,4293,4513,4777,5025,5261,5525,5789,

 6077,6361,6625]

# 一致の確認

p ary == ary0

150531

Ruby


Ulam number

昨日以下のサイトで N 以下の Ulam number の効率の良い求め方について質問してみた。

（http://ja.stackoverflow.com/questions/10791/ulam-number-%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E8%89%AF%E3%81%84%E6%B1%82%E3%82%81%E6%96%B9%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6）

これを用いて、339以下の Ulam number を求め、
オンライン整数列大辞典の

A002858（http://oeis.org/A002858/list）
と比較し、答え合わせしてみる。

N = 339

ary = [1, 2]

(3..N).each{|i|

  cnt = 0

  k = ary.size - 1

  (0..k - 1).each{|j|

    break if j >= k

    m = i - ary[j]

    while ary[k] > m

      k -= 1

    end

    cnt += 1 if ary[k] == m && j < k

  }

  ary.push(i) if cnt == 1

}

# OEIS A002858のデータ

ary0 =

[1,2,3,4,6,8,11,13,16,18,26,28,36,38,47,48,53,57,

 62,69,72,77,82,87,97,99,102,106,114,126,131,138,

 145,148,155,175,177,180,182,189,197,206,209,219,

 221,236,238,241,243,253,258,260,273,282,309,316,

 319,324,339]

# 一致の確認

p ary == ary0