150914(2)

Ruby


xx + 27yy 型の素数

tsujimotter さんの本日のブログ

(http://tsujimotter.hatenablog.com/entry/xx-27yy)

について、自分で実験してみることにした。

require 'prime'

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary[0..m]
end

# 1 - q^(6n)
def f1(n)
  f1 = Array.new(6 * n + 1, 0)
  f1[0] = 1
  f1[-1] = -1
  f1
end

# 1 - q^(18n)
def f2(n)
  f2 = Array.new(18 * n + 1, 0)
  f2[0] = 1
  f2[-1] = -1
  f2
end

ary = [0, 1]
n = 1
while 6 * n <= 300
  ary = mul(ary, f1(n), 300)
  n += 1
end
n = 1
while 18 * n <= 300
  ary = mul(ary, f2(n), 300)
  n += 1
end
p ary

Prime.each(300){|i| p [i, ary[i]]}

出力結果

[0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[2, 0]

[3, 0]

[5, 0]

[7, -1]

[11, 0]

[13, -1]

[17, 0]

[19, -1]

[23, 0]

[29, 0]

[31, 2]

[37, -1]

[41, 0]

[43, 2]

[47, 0]

[53, 0]

[59, 0]

[61, -1]

[67, -1]

[71, 0]

[73, -1]

[79, -1]

[83, 0]

[89, 0]

[97, -1]

[101, 0]

[103, -1]

[107, 0]

[109, 2]

[113, 0]

[127, 2]

[131, 0]

[137, 0]

[139, -1]

[149, 0]

[151, -1]

[157, 2]

[163, -1]

[167, 0]

[173, 0]

[179, 0]

[181, -1]

[191, 0]

[193, -1]

[197, 0]

[199, -1]

[211, -1]

[223, 2]

[227, 0]

[229, 2]

[233, 0]

[239, 0]

[241, -1]

[251, 0]

[257, 0]

[263, 0]

[269, 0]

[271, -1]

[277, 2]

[281, 0]

[283, 2]

[293, 0]

赤字の素数がxx + 27yy 型の素数となる。

150914

C


Number of knight's tours on a m×n chessboard(3)

さらに、3×21 のときも求まる。

m = 3 のとき

kto3s =

[0, 0, 0, 16, 0, 0, 104, 792, 1120, 6096, 21344, 114496, 

 257728, 1292544, 3677568, 17273760, 46801984, 

 211731376, 611507360, 2645699504, 7725948608]

m = 6 のとき

kto6s =

[0, 0, 0, 1488, 37568, 6637920, 779938932]

m = 7 のとき

kto7s =

[0, 0, 104, 12756, 1245736, 779938932, 165575218320]

150913

C


Number of knight's tours on a m×n chessboard(2)

さらに、3×19, 3×20 のときも求まる。

7×7 のときも含めて現在分かっている値をまとめておく。

m = 3 のとき

kto3s =

[0, 0, 0, 16, 0, 0, 104, 792, 1120, 6096, 21344,

 114496, 257728, 1292544, 3677568, 17273760,

 46801984, 211731376, 611507360, 2645699504]

m = 6 のとき

kto6s =

[0, 0, 0, 1488, 37568, 6637920, 779938932]

m = 7 のとき

kto7s =

[0, 0, 104, 12756, 1245736, 779938932, 165575218320]

150912

C


Number of knight's tours on a m×n chessboard(1)

yoh2 さんのコード（VS2013用）を用いる。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>


struct board {
 // 盤面の大きさ
 int num_rows, num_cols;

 //counts[行インデックス][列インデックス]:
 //そのマスから/マスへ移動可能なマスがいくつあるか。
 //解の探索で、利き筋のマスが訪問済になると減少する。
 //また、訪問済のマスは -1 とする。
 int **counts;

 // カウントが1のマスの数。これが3以上になると
 // そのすべてを訪問することはできないため解なしとなる。
 int num_ones;
};


// マスの位置を表す構造体。
struct board_index {
 int row, col;
};


// ナイトの利き筋。
const struct board_index g_knight_movement[] = {
 { 1, 2 }, { -1, 2 }, { 1, -2 }, { -1, -2 },
 { 2, 1 }, { -2, 1 }, { 2, -1 }, { -2, -1 },
};
// g_knight_movement の要素数。
#define NUM_KNIGHT_MOVEMENTS  ((sizeof(g_knight_movement) / sizeof(g_knight_movement[0])))


// 指定されたインデックスが盤面の範囲に入っているか。
static bool in_board(const struct board * brd, struct board_index index)
{
 return ((0 <= index.row) && (index.row < brd->num_rows))
  && ((0 <= index.col) && (index.col < brd->num_cols));
}


// 指定したマスの利き筋の数の初期値を求める。
int initial_count_at(const struct board * brd, int row, int col)
{
 int count = 0;
 for (size_t i = 0; i < NUM_KNIGHT_MOVEMENTS; i++) {
  struct board_index next = { // (row, col) から一回動いた位置
   .row = g_knight_movement[i].row + row,
   .col = g_knight_movement[i].col + col,
  };
  count += in_board(brd, next);
 }
 return count;
}


// init_board_result() の戻り値。
enum init_board_result {
 IB_SUCCESS,         // 初期化成功
 IB_ERROR,           // エラー発生
 IB_NO_SOLUTION,     // 初期化時に解がないことが確定して初期化を中断した
};


// 盤面の情報を初期化する。
enum init_board_result init_board(struct board * brd, int num_rows, int num_cols)
{
 enum init_board_result err_retval;
 brd->num_rows = num_rows;
 brd->num_cols = num_cols;
 brd->num_ones = 0;
 brd->counts = (int **)malloc(sizeof(brd->counts[0]) * num_rows);
 if (brd->counts == NULL) {
  err_retval = IB_ERROR;
  goto err_alloc_baseptr;
 }
 int row;
 for (row = 0; row < num_rows; row++) {
  brd->counts[row] = (int *)malloc(sizeof(brd->counts[0][0]) * num_cols);
  if (brd->counts[row] == NULL) {
   err_retval = IB_ERROR;
   goto err_alloc_row;
  }
  for (int col = 0; col < num_cols; col++) {
   brd->counts[row][col] = initial_count_at(brd, row, col);
   switch (brd->counts[row][col]) {
   case 1:
    brd->num_ones++;
    break;

   case 0:
    err_retval = IB_NO_SOLUTION;
    goto no_solution;

   default:
    break;
   }
  }
 }
 return IB_SUCCESS;

 // error or no solution
no_solution:
 free(brd->counts[row]);
err_alloc_row:
 while (row-- > 0) {
  free(brd->counts[row]);
 }
 free(brd->counts);
err_alloc_baseptr:
 return err_retval;
}


// 盤面を破棄する。
void destray_board(struct board * brd)
{
 for (int row = 0; row < brd->num_rows; row++) {
  free(brd->counts[row]);
 }
 free(brd->counts);
}


// 後述の update_next_counts_and_enum_available_indices() とペアで使う。
// 上記関数で列挙されたマスのカウントを元に戻す。
void restore_next_counts(
struct board * brd,
 const struct board_index nexts[],
 size_t num_nexts)
{
 for (size_t i = 0; i < num_nexts; i++) {
  // カウント戻し + 1のマス数の調整
  switch (brd->counts[nexts[i].row][nexts[i].col]++) {
  case 1:
   brd->num_ones--;
   break;

  case 0:
   brd->num_ones++;
   break;
  }
 }
}


// 現在位置から到達できるマスのカウントを減らしつつ、
// 指定された位置から次に動ける候補一覧を列挙する。
// nexts[] に候補が格納され、候補数が返される。解がないと判断されたら
// カウントの変更はキャンセルされ、0が返されら。
size_t update_next_counts_and_enum_available_indices(
struct board * brd,
struct board_index index,
 bool is_last_step,
struct board_index nexts[])
{
 size_t num_nexts = 0;
 for (size_t i = 0; i < NUM_KNIGHT_MOVEMENTS; i++) {
  struct board_index next = {
   .row = g_knight_movement[i].row + index.row,
   .col = g_knight_movement[i].col + index.col,
  };
  if (!in_board(brd, next)) {
   // 盤面の範囲外は候補たり得ないので何もしない
   continue;
  }
  int count = brd->counts[next.row][next.col];
  if (count < 0) {
   // 訪問済のマスは触らない。
   continue;
  }
  // 以降、すべて正の数となる。(0となるパターンは存在しない)
  assert(count != 0);
  // カウントを減らす。
  brd->counts[next.row][next.col] = count - 1;
  if (count == 1) {
   // 1のマス (今回0になった) が見付かった時点で、それが唯一の候補。
   // ただし、それが最後の空きマスでなければ、さらに
   // 次の一歩を移動できないので解なしとなる。
   if (is_last_step) {
    num_nexts = 1;
    nexts[0] = next;
    brd->num_ones--;
    // 他のマスはすべて訪問済なので、これ以上見る必要はない。
    break;
   }
   else {
    // 解なし。変更を元に戻して0を返す。
    brd->counts[next.row][next.col] = count;
    restore_next_counts(brd, nexts, num_nexts);
    return 0;
   }
  }
  else {
   nexts[num_nexts++] = next;
   if (count == 2) {
    // 減算の結果、1になるので、記録してある1の数を増やす。
    brd->num_ones++;
   }
  }
 }
 assert(num_nexts > 0);
 return num_nexts;
}


long long solve_knight_tour_impl(
struct board * brd,
 int depth,
struct board_index index)
{
 if (depth == brd->num_rows * brd->num_cols - 1) {
  // 解がひとつ見付かった
  return 1;
 }

 struct board_index nexts[NUM_KNIGHT_MOVEMENTS]; // 移動先候補は最大でナイトの利き筋の数。
 size_t num_nexts = update_next_counts_and_enum_available_indices(
  brd, index,
  depth == brd->num_rows * brd->num_cols - 2,
  nexts);
 if (num_nexts == 0) {
  // この探索では解がない。
  return 0;
 }
 // 現在位置を無効化する。
 // 後で戻せるように値の退避もしておく。
 int saved_count = brd->counts[index.row][index.col];
 if (saved_count == 1) {
  brd->num_ones--;
 }
 brd->counts[index.row][index.col] = -1;

 long long found = 0;
 // ここで、現在の1のマスの数を調べる。
 if (brd->num_ones >= 3) {
  // 3以上なら解なしとなるので何もしない。
 }
 else {
  if (brd->num_ones >= 2) {
   // カウントが1の移動先候補それぞれについて解を探索。
   for (size_t i = 0; i < num_nexts; i++) {
    if (brd->counts[nexts[i].row][nexts[i].col] == 1) {
     found += solve_knight_tour_impl(brd, depth + 1, nexts[i]);
    }
   }
  }
  else {
   // 移動先候補それぞれについて解を探索。
   for (size_t i = 0; i < num_nexts; i++) {
    found += solve_knight_tour_impl(brd, depth + 1, nexts[i]);
   }
  }
 }
 // [A] の変更元に戻す。
 brd->counts[index.row][index.col] = saved_count;
 if (saved_count == 1) {
  brd->num_ones++;
 }
 restore_next_counts(brd, nexts, num_nexts);

 return found;
}


// num_rows × num_cols の盤面のナイトツアーを満たす解の数を返す。
// エラー発生時は -1 。
// なお、回転・線対称・逆周りはすべて別個の解として数えている。
long long solve_knight_tour(size_t num_rows, size_t num_cols)
{
 struct board brd;
 switch (init_board(&brd, num_rows, num_cols)) {
 case IB_SUCCESS:
  break;

 case IB_ERROR:
  return -1;

 case IB_NO_SOLUTION:
  return 0;
 }
 long long found = 0;

 // 各座標を視点とした解の個数を合計する。
 // なお、縦横2等分すれば、それぞれ線対称の位置になるので、
 // その 1/4 の部分だけ計算し、4倍することで全体の結果が求められる。
 // ただし、奇数の場合は、中央の行・列の追加計算も必要。
 for (int row = 0; row < num_rows / 2; row++) {
  for (int col = 0; col < num_cols / 2; col++) {
   found += solve_knight_tour_impl(&brd, 0, (struct board_index){ .row = row, .col = col });
  }
 }
 found *= 4;
 // 奇数の場合の追加パターン
 if (num_rows & 1) {
  long long extra_found = 0;
  // 行数が奇数 → 真ん中の行を追加計算。これも半分だけ計算して2倍する。
  for (int col = 0; col < num_cols / 2; col++) {
   extra_found += solve_knight_tour_impl(&brd, 0, (struct board_index){ .row = num_rows / 2, .col = col });
  }
  found += extra_found * 2;
 }
 if (num_cols & 1) {
  long long extra_found = 0;
  // 列数が奇数 → 真ん中の列を追加計算。これも半分だけ計算して2倍する。
  for (int row = 0; row < num_rows / 2; row++) {
   extra_found += solve_knight_tour_impl(&brd, 0, (struct board_index){ .row = row, .col = num_cols / 2 });
  }
  found += extra_found * 2;
 }
 if ((num_rows & 1) && (num_cols & 1)) {
  // どちらも奇数 → 中央のマスを追加計算。
  found += solve_knight_tour_impl(&brd, 0, (struct board_index){ .row = num_rows / 2, .col = num_cols / 2 });
 }
 destray_board(&brd);
 return found;
}


// 引数に盤面のサイズを指定する。
// 不正な引数が渡された場合のエラー処理はしていない(手抜き)。
int main(int argc, char *argv[])
{
 if (argc < 3) {
  printf("Usage: %s #-rows #-cols\n", argv[0]);
  return 1;
 }
 int num_rows = strtol(argv[1], NULL, 0);
 int num_cols = strtol(argv[2], NULL, 0);

 // 探索本体
 long long num_solutions = solve_knight_tour(num_rows, num_cols);
 if (num_solutions == -1) {
  perror("");
  return 1;
 }
 printf("# of solutions = %lld\n", num_solutions);
 return 0;
}

m = 3 のとき

C:\Users\Seiichi>20150912.exe 3 1

# of solutions = 0

C:\Users\Seiichi>20150912.exe 3 2

# of solutions = 0

C:\Users\Seiichi>20150912.exe 3 3

# of solutions = 0

C:\Users\Seiichi>20150912.exe 3 4

# of solutions = 16

C:\Users\Seiichi>20150912.exe 3 5

# of solutions = 0

C:\Users\Seiichi>20150912.exe 3 6

# of solutions = 0

C:\Users\Seiichi>20150912.exe 3 7

# of solutions = 104

C:\Users\Seiichi>20150912.exe 3 8

# of solutions = 792

C:\Users\Seiichi>20150912.exe 3 9

# of solutions = 1120

C:\Users\Seiichi>20150912.exe 3 10

# of solutions = 6096

C:\Users\Seiichi>20150912.exe 3 11

# of solutions = 21344

C:\Users\Seiichi>20150912.exe 3 12
# of solutions = 114496

C:\Users\Seiichi>20150912.exe 3 13

# of solutions = 257728

C:\Users\Seiichi>20150912.exe 3 14

# of solutions = 1292544

C:\Users\Seiichi>20150912.exe 3 15

# of solutions = 3677568

C:\Users\Seiichi>20150912.exe 3 16

# of solutions = 17273760

C:\Users\Seiichi>20150912.exe 3 17

# of solutions = 46801984

C:\Users\Seiichi>20150912.exe 3 18

# of solutions = 211731376

m = 6 のとき

C:\Users\Seiichi>20150912.exe 6 1

# of solutions = 0

C:\Users\Seiichi>20150912.exe 6 2

# of solutions = 0

C:\Users\Seiichi>20150912.exe 6 3

# of solutions = 0

C:\Users\Seiichi>20150912.exe 6 4

# of solutions = 1488

C:\Users\Seiichi>20150912.exe 6 5

# of solutions = 37568

C:\Users\Seiichi>20150912.exe 6 6

# of solutions = 6637920

C:\Users\Seiichi>20150912.exe 6 7

# of solutions = 779938932

m = 7 のとき

C:\Users\Seiichi>20150912.exe 7 1

# of solutions = 0

C:\Users\Seiichi>20150912.exe 7 2

# of solutions = 0

C:\Users\Seiichi>20150912.exe 7 3

# of solutions = 104

C:\Users\Seiichi>20150912.exe 7 4

# of solutions = 12756

C:\Users\Seiichi>20150912.exe 7 5

# of solutions = 1245736

C:\Users\Seiichi>20150912.exe 7 6

# of solutions = 779938932

150910(2)

コード用(1)

これから、以下を使用する。

コード用　コード用　コード用　コード用　コード用　コード用　コード用　コード用　コード用

150910

Ruby

Number of knight's tours on a 3×k chessboard(2)

Cに比べて遅いため、h = 14 までしか計算していない。

@knight_move =
[[2, -1], [2, 1], [-2, -1], [-2, 1],
[1, -2], [1, 2], [-1, -2], [-1, 2]]

# startが[x, y]
def search(x, y, w, h, used, depth)
  return 0 if x < 0 || w <= x || y < 0 || h <= y || used[x + y * w]
  return 1 if depth == w * h
  cnt = 0
  used[x + y * w] = true
  @knight_move.each{|m|
    cnt += search(x + m[0], y + m[1], w, h, used, depth + 1)
  }
  used[x + y * w] = false
  return cnt
end

def directed_open_tours3(h)
  return 0 if h < 3
  total = 0
  (0..h / 2 - 1).each{|y|
    used = Array.new(3 * h, false)
    total += search(0, y, 3, h, used, 1) * 4
    p [y, 0, total]
    used = Array.new(3 * h, false)
    total += search(1, y, 3, h, used, 1) * 2
    p [y, 1, total]
  }
  if h % 2 == 1
    y = h / 2
    used = Array.new(3 * h, false)
    total += search(0, y, 3, h, used, 1) * 2
    used = Array.new(3 * h, false)
    total += search(1, y, 3, h, used, 1) * 1
  end
  total
end

(1..14).each{|h|
  p directed_open_tours3(h)
}

出力結果

0

0

[0, 0, 0]

[0, 1, 0]

0

[0, 0, 8]

[0, 1, 16]

[1, 0, 16]

[1, 1, 16]

16

[0, 0, 0]

[0, 1, 0]

[1, 0, 0]

[1, 1, 0]

0

[0, 0, 0]

[0, 1, 0]

[1, 0, 0]

[1, 1, 0]

[2, 0, 0]

[2, 1, 0]

0

[0, 0, 32]

[0, 1, 32]

[1, 0, 32]

[1, 1, 88]

[2, 0, 104]

[2, 1, 104]

104

[0, 0, 328]

[0, 1, 464]

[1, 0, 544]

[1, 1, 640]

[2, 0, 656]

[2, 1, 656]

[3, 0, 752]

[3, 1, 792]

792

[0, 0, 688]

[0, 1, 688]

[1, 0, 688]

[1, 1, 880]

[2, 0, 912]

[2, 1, 912]

[3, 0, 912]

[3, 1, 992]

1120

[0, 0, 1792]

[0, 1, 2816]

[1, 0, 3440]

[1, 1, 4272]

[2, 0, 4464]

[2, 1, 4528]

[3, 0, 4784]

[3, 1, 4944]

[4, 0, 5584]

[4, 1, 6096]

6096

[0, 0, 10416]

[0, 1, 10416]

[1, 0, 10416]

[1, 1, 14416]

[2, 0, 15584]

[2, 1, 15584]

[3, 0, 15584]

[3, 1, 16624]

[4, 0, 20224]

[4, 1, 20224]

21344

[0, 0, 38632]

[0, 1, 51320]

[1, 0, 58840]

[1, 1, 70072]

[2, 0, 73880]

[2, 1, 74584]

[3, 0, 80360]

[3, 1, 84544]

[4, 0, 97168]

[4, 1, 102592]

[5, 0, 110144]

[5, 1, 114496]

114496

[0, 0, 121968]

[0, 1, 121968]

[1, 0, 121968]

[1, 1, 158800]

[2, 0, 167664]

[2, 1, 167664]

[3, 0, 167664]

[3, 1, 180416]

[4, 0, 223168]

[4, 1, 223168]

[5, 0, 223168]

[5, 1, 243456]

257728

[0, 0, 412512]

[0, 1, 528176]

[1, 0, 597840]

[1, 1, 727952]

[2, 0, 762928]

[2, 1, 769072]

[3, 0, 813936]

[3, 1, 853040]

[4, 0, 988656]

[4, 1, 1040560]

[5, 0, 1116400]

[5, 1, 1177232]

[6, 0, 1257680]

[6, 1, 1292544]

1292544

150908

C


Number of knight's tours on a 3×k chessboard(1)

一日半かけて計算した。

#include <stdio.h>

int search(int x, int y, int w, int h, long long used, int depth){
  int cnt = 0;
  if (x < 0 || w <= x || y < 0 || h <= y || (used & (1LL << (x + y * w))) > 0) return 0;
  if (depth == w * h) return 1;
  used += 1LL << (x + y * w);
  cnt += search(x + 2, y - 1, w, h, used, depth + 1);
  cnt += search(x + 2, y + 1, w, h, used, depth + 1);
  cnt += search(x - 2, y - 1, w, h, used, depth + 1);
  cnt += search(x - 2, y + 1, w, h, used, depth + 1);
  cnt += search(x + 1, y - 2, w, h, used, depth + 1);
  cnt += search(x + 1, y + 2, w, h, used, depth + 1);
  cnt += search(x - 1, y - 2, w, h, used, depth + 1);
  cnt += search(x - 1, y + 2, w, h, used, depth + 1);
  used -= 1LL << (x + y * w);
  return cnt;
}

int directed_open_tours3(int h){
  if (h < 3) return 0;
  int y;
  long long used;
  int total = 0;
  for (y = 0; y < h / 2; y++){
    used = 0LL;
    total += search(0, y, 3, h, used, 1) * 4;
    used = 0LL;
    total += search(1, y, 3, h, used, 1) * 2;
  }
  if (h % 2 == 1){
    y = h / 2;
    used = 0LL;
    total += search(0, y, 3, h, used, 1) * 2;
    used = 0LL;
    total += search(1, y, 3, h, used, 1) * 1;
  }
  return total;
}

int main(void){
  int h;
  for (h = 1; h < 17; h++){
    printf("%d\n", directed_open_tours3(h));
  }
  return 0;
}

出力結果

0

0

0

16

0

0

104

792

1120

6096

21344

114496

257728

1292544

3677568

17273760

150904

Ruby


桂馬飛び

スタートからゴールまで桂馬飛びで何手で行けるか求めるコードを書いてみた。

def moveknight(point, board)
  c, r = point
  points =
  [[c + 2, r - 1], [c + 2, r + 1], [c - 2, r - 1], [c - 2, r + 1],
  [c + 1, r - 2], [c + 1, r + 2], [c - 1, r - 2], [c - 1, r + 2]]
  points & board
end

def f(start, goal, board)
  return 0 if start == goal
  used = []
  ary = [start]
  used += ary
  next_ary = []
  ary.each{|i| next_ary |= moveknight(i, board)}
  m = 1
  while !next_ary.include?(goal)
    ary = next_ary
    used += ary
    next_ary = []
    ary.each{|i| next_ary |= moveknight(i, board)}
    # すでに通った場所は除く
    next_ary -= used
    m += 1
  end
  m
end

n = 50
board = (1..n).to_a.product((1..n).to_a)
p f([1, 1], [3, 2], board)
p f([1, 1], [n, n], board)

出力結果
1
34

150903

Ruby


p^n + s^n = q^n + r^n

n < 5 なら、すぐ解が見つかる。

(1..11).each{|d|

  (2..4).each{|m|

    flag = true

    n = 2

    a = n ** m + (n + d) ** m

    while flag

      x = 1

      b = a - x ** m

      y = (b ** (1.0 / m)).round

      while !(y ** m == b) && x < n - 1

        x += 1

        b = a - x ** m

        y = (b ** (1.0 / m)).round

      end

      if y ** m == b

        p [m, d, [n, n + d, x, y]]

        flag = false

        break

      end

      n += 1

      a = n ** m + (n + d) ** m

    end

  }

}

出力結果

[2, 1, [6, 7, 2, 9]]

[3, 1, [9, 10, 1, 12]]

[4, 1, [133, 134, 59, 158]]

[2, 2, [7, 9, 3, 11]]

[3, 2, [18, 20, 2, 24]]

[4, 2, [266, 268, 118, 316]]

[2, 3, [4, 7, 1, 8]]

[3, 3, [27, 30, 3, 36]]

[4, 3, [399, 402, 177, 474]]

[2, 4, [7, 11, 1, 13]]

[3, 4, [36, 40, 4, 48]]

[4, 4, [532, 536, 236, 632]]

[2, 5, [5, 10, 2, 11]]

[3, 5, [19, 24, 10, 27]]

[4, 5, [665, 670, 295, 790]]

[2, 6, [8, 14, 2, 16]]

[3, 6, [9, 15, 2, 16]]

[4, 6, [798, 804, 354, 948]]

[2, 7, [6, 13, 3, 14]]

[3, 7, [51, 58, 30, 67]]

[4, 7, [931, 938, 413, 1106]]

[2, 8, [9, 17, 3, 19]]

[3, 8, [72, 80, 8, 96]]

[4, 8, [1064, 1072, 472, 1264]]

[2, 9, [7, 16, 4, 17]]

[3, 9, [81, 90, 9, 108]]

[4, 9, [1197, 1206, 531, 1422]]

[2, 10, [9, 19, 1, 21]]

[3, 10, [26, 36, 17, 39]]

[4, 10, [1330, 1340, 590, 1580]]

[2, 11, [6, 17, 1, 18]]

[3, 11, [64, 75, 51, 82]]

[4, 11, [1463, 1474, 649, 1738]]

n = 5, p < 525000, q = p + 1 のときを

２日以上かけて全て調べたが解はなかった。

150902

Ruby


p^5 + s^5 = q^5 + r^5

以下のコードを約１日かけて実行したがやはり解は見つからなかった。

N = 200000

m = 70000

s_ary = []

while m < 150000 - 300

  ary = []

  h = {}

  (m..m + 300).each{|i|

    (150000..N).each{|j|

      c = j * j * j * j * j - i * i * i * i * i

      if h.key?(c)

        p c

        ary.push([i, j])

        s_ary.push([i, j])

      end

      h[c] = 1

    }

  }

  print [m, ary]

  m += 100

end

p s_ary

出力結果

[70000, []][70100, []][70200, []][70300, []][70400, []][70500, []][70600, []][70700, []][70800, []][70900, []][71000, []][71100, []][71200, []][71300, []][71400, []][71500, []][71600, []][71700, []][71800, []][71900, []][72000, []][72100, []][72200, []][72300, []][72400, []][72500, []][72600, []][72700, []][72800, []][72900, []][73000, []][73100, []][73200, []][73300, []][73400, []][73500, []][73600, []][73700, []][73800, []][73900, []][74000, []][74100, []][74200, []][74300, []][74400, []][74500, []][74600, []][74700, []][74800, []][74900, []][75000, []][75100, []][75200, []][75300, []][75400, []][75500, []][75600, []][75700, []][75800, []][75900, []][76000, []][76100, []][76200, []][76300, []][76400, []][76500, []][76600, []][76700, []][76800, []][76900, []][77000, []][77100, []][77200, []][77300, []][77400, []][77500, []][77600, []][77700, []][77800, []][77900, []][78000, []][78100, []][78200, []][78300, []][78400, []][78500, []][78600, []][78700, []][78800, []][78900, []][79000, []][79100, []][79200, []][79300, []][79400, []][79500, []][79600, []][79700, []][79800, []][79900, []][80000, []][80100, []][80200, []][80300, []][80400, []][80500, []][80600, []][80700, []][80800, []][80900, []][81000, []][81100, []][81200, []][81300, []][81400, []][81500, []][81600, []][81700, []][81800, []][81900, []][82000, []][82100, []][82200, []][82300, []][82400, []][82500, []][82600, []][82700, []][82800, []][82900, []][83000, []][83100, []][83200, []][83300, []][83400, []][83500, []][83600, []][83700, []][83800, []][83900, []][84000, []][84100, []][84200, []][84300, []][84400, []][84500, []][84600, []][84700, []][84800, []][84900, []][85000, []][85100, []][85200, []][85300, []][85400, []][85500, []][85600, []][85700, []][85800, []][85900, []][86000, []][86100, []][86200, []][86300, []][86400, []][86500, []][86600, []][86700, []][86800, []][86900, []][87000, []][87100, []][87200, []][87300, []][87400, []][87500, []][87600, []][87700, []][87800, []][87900, []][88000, []][88100, []][88200, []][88300, []][88400, []][88500, []][88600, []][88700, []][88800, []][88900, []][89000, []][89100, []][89200, []][89300, []][89400, []][89500, []][89600, []][89700, []][89800, []][89900, []][90000, []][90100, []][90200, []][90300, []][90400, []][90500, []][90600, []][90700, []][90800, []][90900, []][91000, []][91100, []][91200, []][91300, []][91400, []][91500, []][91600, []][91700, []][91800, []][91900, []][92000, []][92100, []][92200, []][92300, []][92400, []][92500, []][92600, []][92700, []][92800, []][92900, []][93000, []][93100, []][93200, []][93300, []][93400, []][93500, []][93600, []][93700, []][93800, []][93900, []][94000, []][94100, []][94200, []][94300, []][94400, []][94500, []][94600, []][94700, []][94800, []][94900, []][95000, []][95100, []][95200, []][95300, []][95400, []][95500, []][95600, []][95700, []][95800, []][95900, []][96000, []][96100, []][96200, []][96300, []][96400, []][96500, []][96600, []][96700, []][96800, []][96900, []][97000, []][97100, []][97200, []][97300, []][97400, []][97500, []][97600, []][97700, []][97800, []][97900, []][98000, []][98100, []][98200, []][98300, []][98400, []][98500, []][98600, []][98700, []][98800, []][98900, []][99000, []][99100, []][99200, []][99300, []][99400, []][99500, []][99600, []][99700, []][99800, []][99900, []][100000, []][100100, []][100200, []][100300, []][100400, []][100500, []][100600, []][100700, []][100800, []][100900, []][101000, []][101100, []][101200, []][101300, []][101400, []][101500, []][101600, []][101700, []][101800, []][101900, []][102000, []][102100, []][102200, []][102300, []][102400, []][102500, []][102600, []][102700, []][102800, []][102900, []][103000, []][103100, []][103200, []][103300, []][103400, []][103500, []][103600, []][103700, []][103800, []][103900, []][104000, []][104100, []][104200, []][104300, []][104400, []][104500, []][104600, []][104700, []][104800, []][104900, []][105000, []][105100, []][105200, []][105300, []][105400, []][105500, []][105600, []][105700, []][105800, []][105900, []][106000, []][106100, []][106200, []][106300, []][106400, []][106500, []][106600, []][106700, []][106800, []][106900, []][107000, []][107100, []][107200, []][107300, []][107400, []][107500, []][107600, []][107700, []][107800, []][107900, []][108000, []][108100, []][108200, []][108300, []][108400, []][108500, []][108600, []][108700, []][108800, []][108900, []][109000, []][109100, []][109200, []][109300, []][109400, []][109500, []][109600, []][109700, []][109800, []][109900, []][110000, []][110100, []][110200, []][110300, []][110400, []][110500, []][110600, []][110700, []][110800, []][110900, []][111000, []][111100, []][111200, []][111300, []][111400, []][111500, []][111600, []][111700, []][111800, []][111900, []][112000, []][112100, []][112200, []][112300, []][112400, []][112500, []][112600, []][112700, []][112800, []][112900, []][113000, []][113100, []][113200, []][113300, []][113400, []][113500, []][113600, []][113700, []][113800, []][113900, []][114000, []][114100, []][114200, []][114300, []][114400, []][114500, []][114600, []][114700, []][114800, []][114900, []][115000, []][115100, []][115200, []][115300, []][115400, []][115500, []][115600, []][115700, []][115800, []][115900, []][116000, []][116100, []][116200, []][116300, []][116400, []][116500, []][116600, []][116700, []][116800, []][116900, []][117000, []][117100, []][117200, []][117300, []][117400, []][117500, []][117600, []][117700, []][117800, []][117900, []][118000, []][118100, []][118200, []][118300, []][118400, []][118500, []][118600, []][118700, []][118800, []][118900, []][119000, []][119100, []][119200, []][119300, []][119400, []][119500, []][119600, []][119700, []][119800, []][119900, []][120000, []][120100, []][120200, []][120300, []][120400, []][120500, []][120600, []][120700, []][120800, []][120900, []][121000, []][121100, []][121200, []][121300, []][121400, []][121500, []][121600, []][121700, []][121800, []][121900, []][122000, []][122100, []][122200, []][122300, []][122400, []][122500, []][122600, []][122700, []][122800, []][122900, []][123000, []][123100, []][123200, []][123300, []][123400, []][123500, []][123600, []][123700, []][123800, []][123900, []][124000, []][124100, []][124200, []][124300, []][124400, []][124500, []][124600, []][124700, []][124800, []][124900, []][125000, []][125100, []][125200, []][125300, []][125400, []][125500, []][125600, []][125700, []][125800, []][125900, []][126000, []][126100, []][126200, []][126300, []][126400, []][126500, []][126600, []][126700, []][126800, []][126900, []][127000, []][127100, []][127200, []][127300, []][127400, []][127500, []][127600, []][127700, []][127800, []][127900, []][128000, []][128100, []][128200, []][128300, []][128400, []][128500, []][128600, []][128700, []][128800, []][128900, []][129000, []][129100, []][129200, []][129300, []][129400, []][129500, []][129600, []][129700, []][129800, []][129900, []][130000, []][130100, []][130200, []][130300, []][130400, []][130500, []][130600, []][130700, []][130800, []][130900, []][131000, []][131100, []][131200, []][131300, []][131400, []][131500, []][131600, []][131700, []][131800, []][131900, []][132000, []][132100, []][132200, []][132300, []][132400, []][132500, []][132600, []][132700, []][132800, []][132900, []][133000, []][133100, []][133200, []][133300, []][133400, []][133500, []][133600, []][133700, []][133800, []][133900, []][134000, []][134100, []][134200, []][134300, []][134400, []][134500, []][134600, []][134700, []][134800, []][134900, []][135000, []][135100, []][135200, []][135300, []][135400, []][135500, []][135600, []][135700, []][135800, []][135900, []][136000, []][136100, []][136200, []][136300, []][136400, []][136500, []][136600, []][136700, []][136800, []][136900, []][137000, []][137100, []][137200, []][137300, []][137400, []][137500, []][137600, []][137700, []][137800, []][137900, []][138000, []][138100, []][138200, []][138300, []][138400, []][138500, []][138600, []][138700, []][138800, []][138900, []][139000, []][139100, []][139200, []][139300, []][139400, []][139500, []][139600, []][139700, []][139800, []][139900, []][140000, []][140100, []][140200, []][140300, []][140400, []][140500, []][140600, []][140700, []][140800, []][140900, []][141000, []][141100, []][141200, []][141300, []][141400, []][141500, []][141600, []][141700, []][141800, []][141900, []][142000, []][142100, []][142200, []][142300, []][142400, []][142500, []][142600, []][142700, []][142800, []][142900, []][143000, []][143100, []][143200, []][143300, []][143400, []][143500, []][143600, []][143700, []][143800, []][143900, []][144000, []][144100, []][144200, []][144300, []][144400, []][144500, []][144600, []][144700, []][144800, []][144900, []][145000, []][145100, []][145200, []][145300, []][145400, []][145500, []][145600, []][145700, []][145800, []][145900, []][146000, []][146100, []][146200, []][146300, []][146400, []][146500, []][146600, []][146700, []][146800, []][146900, []][147000, []][147100, []][147200, []][147300, []][147400, []][147500, []][147600, []][147700, []][147800, []][147900, []][148000, []][148100, []][148200, []][148300, []][148400, []][148500, []][148600, []][148700, []][148800, []][148900, []][149000, []][149100, []][149200, []][149300, []][149400, []][149500, []][149600, []][]