2進化10進数の1の数

2進化10進数の1の数

締め切りが 2018/02/10 10:00 AM なので，その 1 分後に投稿されるように予約

コンピュータにおける数値の表現方式の一つに2進化10進数(BCD)があります。
これは、10進数の各桁をそのまま2進数に置き換えたものです。

例えば、42の場合、十の位の「4」を2進数で表して「0100」、一の位の「2」を2進数で表して「0010」なので、「0100 0010」となります。
（ここでは符号は考えないものとします。）

Nが与えられる時、N桁の整数を「2進数で表した時」と「2進化10進数で表した時」に、ビット列に含まれる「1」の数が等しいものがいくつあるかを求めてください。

例)
42は2進数では「101010」で3個、2進化10進数では「0100 0010」で2個なので対象外、
52は2進数では「110100」で3個、2進化10進数では「0101 0010」で3個なので対象です。

【入出力サンプル】

Input
2

Output
20

====================================

R には 整数を二進数に変換する intToBits があるので，以下のように簡単に書けるが，それでも 7 桁の整数を対象にすると 1 分以上かかる。Java で書くにしても，intToBits を実装すると実行時間 1 秒は切れない。

f = function(n) {
  bits = sapply(0:9, function(x) sum(intToBits(x) == 1))
  count = 0
  for (i in (10^(n-1)):(10^n-1)) {
    a = sum(bits[as.integer(unlist(strsplit(as.character(i), "")))+1])
    b = sum(intToBits(i) == 1)
    count = count + (a==b)
  }
  cat(count)
}

ある整数の二進表記に 1 が幾つ含まれるかは，オンライン整数列大辞典の A000120 である。これを使うと，前述のプログラムよりは速い。
Java で書き換えて，やっと 1 秒の壁をクリアできた。

# A002487 a(n+1) = (2*k+1)*a(n) - a(n-1) where k = floor(a(n-1)/a(n))
A002487 = function(n) {
  a = integer(n)
  a[1] = a[2] = 1
  for (i in 3:n) {
    k = floor(a[i-2]/a[i-1])
    a[i] = (2*k+1)*a[i-1]-a[i-2]
  }
  a
}
a = A002487(20)

# A007814
A007814 = function(n) {
  a = A002487(n+1)
  floor(head(a, -1)/a[-1])
}

# A000120
A000120 = function(n) {
  a = A007814(n)
  b = integer(n)
  b[1] = 1
  for (i in 2:n) {
    b[i] = b[i-1]+1-a[i-1]
  }
  b
}

f = function(n) {
  table = sapply(0:9, function(i) sum(intToBits(i) == 1))
  begin = 10^(n-1)
  end   = 10^n-1
  x = A000120(end)
  count = 0
  for (i in begin:end) {
    if (x[i] == sum(table[as.integer(unlist(strsplit(as.character(i), "")))+1])) {
      count = count+1
    }
  }
  cat(count)
}

f(2) # 20
f(3) # 200
system.time(f(4)) # 2054, 0.052 sec.
system.time(f(5)) # 13906, 0.600 sec.
system.time(f(6)) # 122756, 6.336 sec.
system.time(f(7)) # 1167892, 67.848 sec.

Java プログラム

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    int n;
    if (false) {
      Scanner cin = new Scanner(System.in);
      String line;
      line = cin.nextLine();
      n = Integer.parseInt(line);      
      System.out.println(f(n));
    } else {
      System.out.println(f(2));
      System.out.println(f(3));
      System.out.println(f(4));
      System.out.println(f(5));
      System.out.println(f(6));
      long start = System.currentTimeMillis();
      System.out.println(f(7));
      long end = System.currentTimeMillis();
      System.out.println((end - start) + "ms");
    }
  }

  static void dump(int [] a) {
    for (int i = 0; i < a.length; i++) {
      System.out.print(a[i]+" ");
    }
    System.out.println();
  }

  static int [] a002487( int n) {
    int [] a = new int[n];
    a[0] = 0;
    a[1] = 1;
    for (int i = 2; i < n; i++) {
      int k = a[i-2]/a[i-1];
      a[i] = (2*k+1)*a[i-1]-a[i-2];
    }
    return a;
  }

  static int [] a007814( int n) {
    int [] a = a002487(n+1);
    int [] b = new int[n];
    for (int i = 0; i < n; i++) {
      b[i] = a[i]/a[i+1];
    }
    return b;
  }

  static int [] a000120(int n) {
    int [] a = a007814(n);
    int [] b = new int[n];
    b[0] = 0;
    for (int i = 1; i < n; i++) {
      b[i] = b[i-1]+1-a[i-1];
    }
    return b;
  }

  static int bitCount2(int i) {
    int count = 0;
    int [] bits = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2};
    while (i > 0) {
      count += bits[i % 10];
      i = i / 10;
    }
    return count;
  }

  static int f(int n) {
    int begin = (int)Math.pow(10, n-1);
    int end   = (int)Math.pow(10, n);
    int [] a = a000120(end);
    int count = 0;
    for (int i = begin; i < end; i++) {
      if (bitCount2(i) == a[i]) {
        count++;
      }
    }
    return count;
  }
}