素数の個数

言語不問：素数の数を数えてください　　締め切り：12月31日（木）

　　　　　AM10:00（12/31 10:01AM に予約投稿）

与えられた数字よりも小さい数字の中で、素数がいくつあるかを調べるプログラムを作ってください。

例えば以下のように数字が与えられます。

5
10

5よりも小さい数字で素数になるのは、2,3なので、素数は2個になります。

10よりも小さい数字で素数になるのは、2,3,5,7なので、素数は4個になります。

出力結果は

2
4

となります。

以前に，同じような問題を Java で解けというのがあったけど，そのときは gmp を使って無精した。
今回は，エラトステネスの篩を使ってプログラムを書いた。

mx = 100000
tbl = 1:mx
tbl[1] = 0
for (i in 2:floor(sqrt(mx))) {
    if (tbl[i]) {
        mx2 = mx %/% i
        tbl[2:mx2*i] = 0
    }
}
prime <- tbl[tbl > 0]
con=file("stdin", "r")
while (length(line <- readLines(con, 1)) > 0) {
    cat(paste(sum(prime < as.numeric(line)), "\n", sep=""))
}

金額支払い方法

締め切りが 12/30 10:00 AM なので，その 1 分後に公開されるように予約登録

問題:パスカルの三角形，それぞれの値を「金額(日本円)」だと考えることにします。
例えば、「1」は1円、「2」は2円、「10」は10円です。
このとき、n段目のそれぞれの値について、お札や硬貨での最小の枚数を考え、その枚数の和を求めることにします。

例えば、n=4のとき、1, 4, 6, 4, 1の並びでは、1円＝1枚、4円＝4枚、6円＝2枚(5円玉＋1円玉)なので、
すべて足すと12枚になります。
同様に、n=9のとき、すべて足すと48枚になります。

標準入力からnの値が与えられたとき、その枚数の和を標準出力に出力するプログラムを作成してください。
なお、使える硬貨、お札は1円玉、5円玉、10円玉、50円玉、100円玉、500円玉、1000円札、2000円札、5000円札、10000円札です。
（※nの値は最大で50までとします。）

解答例: R だと，簡単だ。

con = file("stdin", "r")
n = as.integer(readLines(con, 1))
t = choose(n, 0:n)
f = function(x) {
    count = 0
    for (m in c(10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)) {
        count = count + x %/% m
        x = x %% m
    }
    count
}
options(digits=16)    
cat(sum(sapply(t, f)))

覆面算

おサルが「キャッ...」と何回か鳴きましたとさ

曲線の概形を描け

もともとは，

次の方程式のグラフの概形をかけ。

というものだったけど，描いてみたら，片思いハートだったので，両思いにして，さらにたくさん描いてみた。

fxy = function(x, y) x^2+(y-abs(x)^(2/3))^2-1
x = seq(-2.5, 2.5, length=1000)
y = seq(-2.5, 3.5, length=1000)
z = matrix(0, 1000, 1000)
for (i in 1:1000) {
    for (j in 1:1000) {
        z[i,j] = fxy(x[i], y[j])
    }
}
contour(x, y, z, drawlabels=FALSE, levels=c(-9:1/10, 0:5), asp=1, col="red")

平方数の和で表す平方数

平方数の和で表す平方数

締め切りが 12月08日（火）AM10:00 なので，解答例をその 1 分後に公開。

【問題】
全ての自然数は高々四個の平方数の和で表される、という「四平方定理」が知られています。
例えば、15という数は9+4+1+1、つまり3^2+2^2+1^2+1^2と表されます。
今回は「平方数」を「ちょうど四個の平方数」で表す、ということを考えてみます。
例えば、36という平方数は、以下のように二通りの足し算で表すことができます。
※ここでは足し算の順序は考えないものとします。
25+9+1+1、つまり5^2+3^2+1^2+1^2
9+9+9+9、つまり3^2+3^2+3^2+3^2
しかし、16という平方数は、以下の一通りしか表現できません。
4+4+4+4、つまり2^2+2^2+2^2+2^2
標準入力から整数nが与えられた時、n以下の平方数のうち、
上記のように一通りでしか表現できないものがいくつあるかを標準出力に出力してください。

【入出力サンプル】
標準入力
25
標準出力
3
※4, 16, 25の3通り

最後は，expand.grid(a^2, a^2, a^2, a^2) を expand.grid(a*a, a*a, a*a, a*a) にして，実行時間を縮めた。
前者は numeric 後者は integer。ギリギリのところで計算時間が短縮された。

con = file("stdin", "r"); n = as.integer(readLines(con, 1))
   a = seq_len(floor(sqrt(n)+.Machine$double.eps))
   p = expand.grid(a*a, a*a, a*a, a*a) ###
   s = rowSums(p) ###
   o = s %in% a^2
   p = p[o,]
   s = s[o]
   m = sapply(split(p, s), function(x) {
      nr = nrow(x)
      if (nr > 24) {
         FALSE
      } else if (nr == 1) {
         TRUE
      } else {
         nrow(unique(t(apply(x, 1, sort)))) == 1
      }
   })
cat(sum(m))

変な問題

出題者も悪いし，それを記事に書いた記者も悪い。

９－３÷1/3＋１　はいくつかというのだが，最初見たときは，なんで割り算に「÷」と「/」を混在させているんだろうと思った。特に，「÷」なんざぁ，小学校で使ったきり今まで使ったことないぞ。

元の問題には，と書いてあったそうだ。これと，最初のものが同じだと思った記者は，頭が悪い。こんな，ひねくれた問題を出したのは，出題者の意地が悪い。

「ツイン・トライアングル」問題---解答

安易に考えて，ただし，ベクトル演算で速度を上げても計算時間がそこそこかかる。さらに，解答先のコンピュータが若干遅く，しかも計算時間は 1 秒以下という制限があるので，とても，以下のプログラムでは無理。

g = function(L) {
   # con = file("stdin", "r"); L = as.integer(readLines(con, 1))
   eps = .Machine$double.eps
   count = 0
   for (b0 in seq_len(L %/% 2)) {
      a = seq_len(b0) * 2
      b = b0 * 2
      c = sqrt(a^2 + b^2)
      bool.c = (c == floor(c + eps))
      if (any(bool.c)) {
         az = a[bool.c]
         cz = c[bool.c]
         x = cz/2
         a2 = x + (az + cz) * x / b
         b2 = b * a2 / az
         count = count + sum(a2 == floor(a2 + eps) & b2 == floor(b2 + eps))
      }
   }
   count
}

計算結果

> system.time(cat(g(100))) # 15
15   ユーザ   システム       経過  
     0.017      0.001      0.011
> system.time(cat(g(456))) # 77
77   ユーザ   システム       経過  
     0.002      0.000      0.002
> system.time(cat(g(7654))) # 1405
1405   ユーザ   システム       経過  
     0.292      0.014      0.296
> system.time(cat(g(75319))) # 14133
14133   ユーザ   システム       経過  
    25.996      4.104     29.849
> system.time(cat(g(90346))) # 16972
16972   ユーザ   システム       経過  
    37.587      6.840     44.132
> system.time(cat(g(1e+05))) # 18797
18797   ユーザ   システム       経過  
    46.327      8.617     54.652


しらみつぶしにするのではなく，ピタゴラス数のセットを計算によって求めたほうが探索範囲はせばまる。

ということで，最終的な答が以下のプログラム。

g = function(L) {
  euclid = function(m, n) {
    while ((temp = n%%m) != 0) {
      n = m
      m = temp
    }
    m == 1
  }
  eps = .Machine$double.eps
  count = 0
  for (m in seq_len(347)) { # 347
    for (n in seq_len(m - 1)) {
      if (euclid(n, m) && (m - n) %% 2 == 1) {
        a = min(m^2 - n^2, 2 * m * n)
        b = max(m^2 - n^2, 2 * m * n)
        c = m^2 + n^2
        if (b <= L) {
          Rep = seq_len(L %/% b)
          a = a * Rep
          b = b * Rep
          c = c * Rep
          x = c/2
          a2 = x + (a + c) * x / b
          b2 = b * a2 / a
          count = count + sum(a2 == floor(a2 + eps) & b2 == floor(b2 +
          eps))
        } else break
      }
    }
  }
  cat(count)
}

計算結果

> system.time(cat(g(100))) # 15
15   ユーザ   システム       経過  
     0.026      0.002      0.020
> system.time(cat(g(456))) # 77
77   ユーザ   システム       経過  
     0.005      0.000      0.005
> system.time(cat(g(7654))) # 1405
1405   ユーザ   システム       経過  
     0.035      0.005      0.040
> system.time(cat(g(75319))) # 14133
14133   ユーザ   システム       経過  
     0.319      0.007      0.318
> system.time(cat(g(90346))) # 16972
16972   ユーザ   システム       経過  
     0.379      0.011      0.380
> system.time(cat(g(1e+05))) # 18797
18797   ユーザ   システム       経過  
     0.413      0.007      0.410

ディジタル時計

締め切りが 12月02日（水）AM10:00 なので，締め切り 1 分後に予約投稿。

図のような7セグメントディスプレイを使ったデジタル時計があります。

ある時刻において、点灯している位置の数を調べます。
例えば、12:34:56(12時34分56秒)の場合は、以下のように27箇所が点灯しています。
ここでは、逆に考えて、点灯している箇所の数から時刻を調べることにします。
ただし、53:61:24 のような場合は、27箇所が点灯しますが、時刻としてありえないため、対象にはなりません。
※このデジタル時計は24時間表示で、23時59分59分まで表示します。
例えば、27箇所が点灯するような時刻は上記を含めて8800通りがあります。
標準入力から整数nが与えられたとき、このデジタル時計でn箇所が点灯するような時刻が何通りあるかを標準出力に出力してください。

con = file("stdin", "r"); n = as.integer(readLines(con, 1))
    segments = c(6, 2, 5, 5, 4, 5, 6, 3, 7, 6)
    g = function(i) {
        sum(segments[as.integer(unlist(strsplit(sprintf("%02i", i), "")))+1L])
    }
    ct = integer(60)
    for (i in 0:59) ct[i+1] = g(i)
    count = 0
    for (h in 1:24) {
        for (m in 1:60) {
            for (s in 1:60) {
                count = count + (sum(ct[c(h, m, s)]) == n)
            }
        }
    }
cat(count)