読者です 読者をやめる 読者になる 読者になる

クロビーボ

私的忘備録

双子素数を求めるプログラム

整数論において次の未解決問題があります。

問題
 双子素数は無限個存在するか?


ここで、正の整数 {n} に対して、{n}{n+2} がともに素数であるとき、ペア {(n, n+2)} を双子素数と呼びます。


例えば、 {(3, 5)}{(5, 7)}{(11, 13)} は双子素数です。



今回の記事では、ある正の整数以下の双子素数たちを求めるJavaプログラムを紹介します。

方法としては、まずある正の整数以下の素数たちをエラトステネスの篩を用いて求め、その後に、双子素数の条件を満たすものをfor文を用いて列挙することを考えました(より効率の良い方法があれば教えていただけるとありがたいです)。

というわけで、エラトステネスの篩を思い出しましょう。


命題(エラトステネスの篩)
 整数 {n>1}合成数ならば、{\sqrt{n}} 以下の素数の約数を持つ。


この命題の対偶を取る事により

 整数 {n>1}{\sqrt{n}} 以下の素数の約数を持たないならば、{n}素数である

ことが従います。

(この命題の証明は参考文献に挙げた本等を参照してください。)


ですので、これを用いてある正の整数以下の素数たちのリストを次のように構成しましょう。

static ArrayList<Integer> prime_set(int n) {
    ArrayList<Integer> prime_set = new ArrayList<Integer>();
    for (int i = 2; i < n; i++) {
        boolean hantei = true;
	for (int j = 2; j*j <= i; j++) {
	    if(i % j == 0) {               //約数が存在するかチェック
	        hantei = false;    
		break;
	    }
	}
	if(hantei) {            //素数である場合はリストに追加
	    prime_set.add(i);
	}
    }
    return prime_set;	
}


次に、このようにして作った素数たちのリストを用いて、双子素数を求めそれらを表示するメソッドを次のように構成します。

static void show_twin(ArrayList<Integer> a) {
    for (int i = 0; i < a.size() - 1; i++) {
        if((a.get(i)+2) == a.get(i+1)) {
	    System.out.println("("+a.get(i)+", "+a.get(i+1)+")");
	}
    }
}

このプログラムでは、双子素数の定義をそのままプログラムに書き直したものになっています。

さて、これらを用いて、以下のようなユーザーが入力した整数値以下の双子素数を求めるプログラムを作ることができます:

import java.util.*;

public class twin_primes {
	
    static Scanner sc = new Scanner(System.in);
	
    public static void main(String[] args) {
        int n = 0;
	do {
	    System.out.println("Please enter a positive integer: ");
	    n = sc.nextInt();
	} while (n <= 0);
		
	ArrayList<Integer> primse = prime_set(n);
		
	System.out.println("We have twin primes less than 10000 as follows:");
	show_twin(primes);

	}
	static ArrayList<Integer> prime_set(int n) {
	    ArrayList<Integer> prime_set = new ArrayList<Integer>();
	    for (int i = 2; i < n; i++) {
	        boolean hantei = true;
	        for (int j = 2; j*j <= i; j++) {
	            if(i % j == 0) {       
		        hantei = false;
		        break;
	            }
	        }
	        if(hantei) {
	            prime_set.add(i);
	        }
	    }
	    return prime_set;
	}

	static void show_twin(ArrayList<Integer> a) {
	    for (int i = 0; i < a.size() - 1; i++) {
	        if((a.get(i)+2) == a.get(i+1)) {
	            System.out.println("("+a.get(i)+", "+a.get(i+1)+")");
		}
	    }
	}
}

次の入力

1000

に対して、次の出力が得られます。

We have twin primes less than 10000 as follows:
(3, 5)
(5, 7)
(11, 13)
(17, 19)
(29, 31)
(41, 43)
(59, 61)
(71, 73)
(101, 103)
(107, 109)
(137, 139)
(149, 151)
(179, 181)
(191, 193)
(197, 199)
(227, 229)
(239, 241)
(269, 271)
(281, 283)
(311, 313)
(347, 349)
(419, 421)
(431, 433)
(461, 463)
(521, 523)
(569, 571)
(599, 601)
(617, 619)
(641, 643)
(659, 661)
(809, 811)
(821, 823)
(827, 829)
(857, 859)
(881, 883)


参考文献

整数論1: 初等整数論からp進数へ

整数論1: 初等整数論からp進数へ

コラッツの問題のプログラム

整数論の未解決問題の一つとしてコラッツの問題というものがあるそうです。

これは、問題自体はとても簡単で、小学生でもわかって楽しめるものになってます。

なんでもいいので一つ正の整数を思い浮かべてみましょう。


思い浮かべましたか?

その整数をnとしましょう。

そのとき、nが偶数か奇数かによって次の操作を考えましょう。

(i)  nが偶数のとき、nを2で割る。
(ii) nが奇数のとき、nを3倍して1を足す。

この操作で得られた数にさらに上の操作を施すということを繰り返すと最終的に1になるであろうというのがこのコラッツの予想です。

例えば、nとして13としたとき、

13は奇数なので操作(ii)を施すと 13×3+1=40 が得られ、
40は偶数なので操作(i)を施すと 40÷2=20、
20は偶数なので操作(i)を施すと 20÷2=10、
10は偶数なので操作(i)を施すと 10÷2=5、
5は奇数なので操作(ii)を施すと 15×3+1=16、
16は偶数なので操作(i)を施すと 16÷2=8
8は偶数なので操作(i)を施すと 8÷2=4、
4は偶数なので操作(i)を施すと 4÷2=2、
2は偶数なので操作(i)を施すと 2÷2=1

となって確かに1になりましたね。

簡単に書くと

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

という数列が得られました。

(ここで、a->b は操作(i)または操作(ii)を一回施すことによってaからbが得られることを意味しています。)


もう少し続けてみると、

1は奇数なので操作(ii)を施すと 1×3+1=4、
4は偶数なので操作(i)を施すと 4÷2=2
2は偶数なので操作(i)を施すと 2÷2=1

となって

1 -> 4 -> 2 -> 1 -> ・・・

のサイクルとなることがわかります。


ちなみに、Wikipediaによると、このコラッツ予想は、5×2^60まで正しいことが確かめられているそうです (参考: コラッツの問題 - Wikipedia)


今回はこのコラッツ予想を確かめるプログラムをJavaで作成したので、
以下に記載しました。

上で確かめたように操作(i)(ii)を繰り返し施すと1 -> 4 -> 2 -> 1 -> ・・・のサイクルになりますので、与えられた正の整数nから操作(i)(ii)を繰り返して最初に1になるまでに得られる数列を求めるプログラムとしました。



import java.util.*;

public class Collatz_problem {
	
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		int n;
		do {
			System.out.println("正の整数を入力してください:");
			n = sc.nextInt();
		} while (n <= 0);
		
		int counter = 1;
		System.out.println("以下がn="+n+"に対するCollatz数列です");
		System.out.println("#"+counter+": "+n);

		while(n != 1) {
			if(n % 2 ==0) {
				n = n / 2;
			} else {
				n = 3 * n + 1;
			}
			counter++;
			System.out.println("#"+counter+": "+n);
		}
	}
}

例えば、以下の入力に対して

13
101
70
50

次のような出力が得られます。

以下がn=13に対するCollatz数列です
#1: 13
#2: 40
#3: 20
#4: 10
#5: 5
#6: 16
#7: 8
#8: 4
#9: 2
#10: 1

以下がn=101に対するCollatz数列です
#1: 101
#2: 304
#3: 152
#4: 76
#5: 38
#6: 19
#7: 58
#8: 29
#9: 88
#10: 44
#11: 22
#12: 11
#13: 34
#14: 17
#15: 52
#16: 26
#17: 13
#18: 40
#19: 20
#20: 10
#21: 5
#22: 16
#23: 8
#24: 4
#25: 2
#26: 1

以下がn=70に対するCollatz数列です
#1: 70
#2: 35
#3: 106
#4: 53
#5: 160
#6: 80
#7: 40
#8: 20
#9: 10
#10: 5
#11: 16
#12: 8
#13: 4
#14: 2
#15: 1

以下がn=50に対するCollatz数列です
#1: 50
#2: 25
#3: 76
#4: 38
#5: 19
#6: 58
#7: 29
#8: 88
#9: 44
#10: 22
#11: 11
#12: 34
#13: 17
#14: 52
#15: 26
#16: 13
#17: 40
#18: 20
#19: 10
#20: 5
#21: 16
#22: 8
#23: 4
#24: 2
#25: 1

Ruby on Rails習得日記1

Ruby on Rails習得日記

今日からブログを始めます。

私は趣味でプログラミングを習得しています。

 

今回はRuby on Railsを勉強することにしました。

 

近日中にある程度の内容のWebアプリケーションを作ろうと思い、まずは無料のプログラミング学習サイトであるドットインストールで勉強することにしました。

 

ここである程度の内容とは、

  • ログイン・ログアウトの機能があること
  • ユーザーの入力に対し、あるアルゴリズムに従ってアウトプットを返す機能を備えていること

 をとりあえず指すこととしましょう。

 

以下が勉強しているドットインストールのURLです。

http://dotinstall.com/

 

そういうわけで、Ruby on Railsについて勉強したことについてちょっとまとめてみることにします。

 

Ruby on Railsとは

 Ruby on Railsとは、Rubyで記述されるWebアプリケーションフレームワークの一つです。と、言われてもよくわからないので、ひとつひとつ言葉を説明していきましょう。

 

Rubyって?

Rubyとはまつもとゆきひろ氏により開発されたオブジェクト指向スクリプト言語です。ここで、オブジェクト指向とは、あるテーマを持ったデータやその上での写像のあつまりであるオブジェクトの組み合わせとして、プログラムを効率的に作成しようというパラダイムのことです。実際、Rubyにおいてはすべてのものがオブジェクトとして扱われます。

スクリプト言語の方は厳密な定義がないそうなので、ここではざっくり人間の言葉に近い文法でかけるプログラミング言語たちのこととしておきます。

Webアプリケーションフレームワークって?

Webアプリケーションとは、ウェブを介してユーザーとサーバーが情報をやり取りすることで提供されるサービスのことです。例えば、私たちが日頃利用する、ブログやTwitterなどのSNSは、ユーザーが入力した文章などの情報をサーバーに上に読み書きし、それをブラウザ上に表示させたりすることで、サービスが提供されています。

Webアプリケーションフレームワークは、こうしたWebアプリケーションを効率的に開発するための道具のことです。

 

Ruby on Railsの設計哲学

言葉の簡単な説明をしたので、まずはRuby on Railsの設計哲学について復習しましょう。それは以下の二つです。

  1. DRY(Don't Repeat Yourself)
  2. Convention over Configuration

 まず、DRYについてですが、日本語で言うと繰り返しを避けなさいということです。Ruby on Railsを使ってWebアプリケーションを開発する際に同じコードを繰り返し記述することは避けて設計することが求められます。実際、同じコードを使う箇所があったときは、それを別のファイルにひとまとめにして、それを参照することでコードを書くことになります。これにより、あとでまとめて修正する必要が出た時などにも修正ミスが生じにくくなり効率的にアプリケーション開発を行うことができます。

 

次に、Convention over Configurationについてですが、これは日本語では設定より規約と訳すのが一般的なようです。設定より規約というのは、デフォルトで設定された記述スタイルに従ってアプリケーションを開発すべしという考え方です。従うべきルールが多いと感じる部分もあるかもしれませんが、一旦習得するとそれに従って書けば良いだけなので、開発作業以外のところで悩まなくてもよいという利点があります。

 

メインはMVC

Ruby on RailsでWebアプリケーションを開発する上でメインで使うのはMVCです。MVCというのは、Model(モデル)、View(びゅー)、Controller(コントローラー)の頭文字を並べたものです。ざっくりいうとModelはデータやデータベースを担当する部分で、Viewは実際にブラウザで利用するユーザーに見える部分を担当していて、Controllerはユーザーからの情報を受け取って、それをもとにModelやViewに指示を出す、オーケストラで言う指揮者的な存在です。

 

今日は概念的な箇所についてまとめてみました。

次回はもう少し具体的な内容を書きたいと思います。