collatz9が出力するグラフにおいて開始ノードを除くノードの値は最大どのくらいになるのか見てみた。 $ ./collatz9 | tred | gvpr "BEG_G{int m=0;} N[m<name&&indegree>0]{m=name;} END_G{print(m);}"によると9232となる。 このgvprに与えたプログラムではノードの値のみを</name&&indegree>…

collatz8とcollatz9の出力の違いについて、 82, 88, 100のノード周辺だけをピックアップしてみる。 parts.g BEG_G { int i; graph_t g = graph($.name, "D"); } E { for (i = 0; i < ARGC; i++) { if (head.name == ARGV[i] || tail.name == ARGV[i]) { clon…

今までのグラフに合わせて、 操作によって初期値になるような100を超える値もノードになるように、 操作後に初期値になる操作前の値から初期値へのエッジも含めるように変更する。 collatz9.c ...snip void collatz_route(mpz_t x) { mpz_t n; mpz_init(n); …

操作後の値が100以下のノードを全て含み、かつ、 その全てがエッジ伝いに1のノードへ到達できるようなグラフを得たい場合、 単純にやるなら、100以下の全ての値について、 これをそれぞれ初期値として、 その1に至る経路を出力したものを一つのグラフとして…

操作後の値が100以下になる操作を全て挙げてDOT言語で表したグラフを出力してみる。 collatz7.c #include <stdio.h> int main(void) { unsigned long x; puts("digraph {\n edge [color=blue];"); for (x = 1; x <= 100; x++) { if (x % 6 == 4) printf(" %lu -> %lu </stdio.h>…

ひねもすゆるりあきのそらのやすみ。

前出のグラフのノード数はGraphvizのコマンドgcを使って、 $ ./collatz6 | gc -n 62 %1 (<stdin>)であり100に満たない。つまり100以下の値を含むすべての経路が表現されていない。 一旦100を超える値を経由して戻ってくるような経路があるが、 芋づる式の方法でかつ</stdin>…

最終的なグラフを図示するのを忘れていた。 DOT言語で記述された結果をdotコマンドで画像にする。 $ ./collatz6 | dot -Tpng -ocollatz6.png

一回の操作である値になるような操作前の値を求め、 さらにその値になる操作前の値を求めるという手続きを繰り返す。 これを1から始めることで1へ至る経路を網羅することができる。 値によっては操作前の値が二つ存在する場合があるので、 この結果は単純な…

台風通過中でお休み。

休止中。 台風の影響は大丈夫ですか？

台風接近中につき休み。

示した片方向の連結リストによるこの実装では、 queue_dequeue()においてエントリが1個かそれ以上かで処理を場合分けしないといけない。 if (p == queue->tail) queue->tail = p->next; 双方向の連結リストにすると構造が均一になり場合分けが不要になる。 q…

queue_init()を実装する時に思わず書いてしまった間違い。 ...snip struct node { struct node *next; } *p; ...snip p->next = p = malloc(sizeof(struct node)); ...snip はコンパイラの警告レベルにもよるが警告される。 p = malloc(sizeof(struct node))…

多倍長精度演算ライブラリGMPの整数型mpz_tを格納できるキューを連結リストでかなり適当に実装。 queue.h #ifndef QUEUE_H_INCLUDED #define QUEUE_H_INCLUDED #include <gmp.h> typedef enum { FALSE = 0 } bool_t; typedef struct queue_entry queue_entry_t; typ</gmp.h>…

もっと広い範囲について初期値と操作回数の関係を見てみる。 16ビット無符号整数で表せる初期値全てに対する操作回数のプロットを行う。 ...snip while (mpz_cmp_ui(x, 65536UL) <= 0) { ...snip $ collatz > i65536.dat $ gnuplot gnuplot> set xlabel 'ini…

明白なことであるが、ある初期値から操作をn回繰り返して1に至った場合、 その初期値に1回操作を施して得られた値を初期値として操作を繰り返して1に至るまでの操作回数はn-1回である。 操作は値を3倍して1を加えるか1/2倍するかであるので、 操作とは値を定…

団子を食べて休み。

今日は中秋の名満月なのでお休みです。

今日は休みです。

初期値と操作回数の対応を詳細に見てみる。 ...snip int main(void) { mpz_t x, iter; mpz_inits(x, iter, NULL); mpz_set_ui(x, 1UL); while (mpz_cmp_ui(x, 100UL) <= 0) { collatz(iter, x); gmp_printf("%Zu %Zu\n", x, iter); mpz_add_ui(x, x, 1UL); }…

初期値をunsigned longよりも大きくしたい場合はナル終端文字配列や文字列リテラルで指定できる。 ...snip int main(void) { mpz_t x, iter; mpz_inits(x, iter, NULL); mpz_set_str(x, "98765432109876543210987654321098765432109876543210123456789012345…

main関数を変更して操作回数をかなり狭い範囲だが探索してみた。 #include <stdio.h> #include <gmp.h> ...snip int main(void) { unsigned long i, max_i = 0; mpz_t x, iter, max_iter; mpz_inits(x, iter, max_iter, NULL); mpz_set_ui(max_iter, 0UL); for (i = 42949672</gmp.h></stdio.h>…

問題とは、関数collatzに与えるシーケンスの初期値xの値次第で関数内のxがオーバーフローを起こすこと、 および、シーケンスが1に至るとして、そこに至るまでの操作回数がどの程度になるか分からないことである。 操作回数については多分unsigned intの範囲…

1に至るまでの操作回数。最初から1の場合はcollatz(1) = 0になる。 #include <stdio.h> unsigned int collatz(unsigned int x); unsigned int collatz(unsigned int x) { unsigned int iter = 0; while (x > 1) { x = x & 1 ? 3 * x + 1 : x >> 1; ++iter; } return i</stdio.h>…

#include <stdio.h> int main(void) { const int N = 100; int i = 1, j = i, k = i, l = i; printf("%d", i); while (++j, ++k, ++l, ++i <= N) { fputs(", ", stdout); if (l == 15) { fputs("Fizz Buzz", stdout); l = k = j = 0; } else if (k == 5) { fputs("Buz</stdio.h>…

#include <stdio.h> int main(void) { const int N = 100; int i = 1; printf("%d", i); while (++i <= N) printf(i % 3 ? i % 5 ? ", %d" : ", Buzz" : i % 5 ? ", Fizz" : ", Fizz Buzz", i); puts(""); return 0; }</stdio.h>

前項でストリーム中の行数を数える関数としては完成していると思う。 しかし問題がある。 Windowsのように'\r'と'\n'の連接（以下CRLF）を一個の改行とする環境において、 CRLFを読み込んだ後に一個の'\n'としてgetcharやgetcが返す問題である。 UNIX系には…

行数をカウントする部分をファイルストリームを引数とする関数にする。 #include <stdio.h> typedef enum { FALSE = 0 } bool_t; unsigned long count_eol(FILE *fp); unsigned long count_eol(FILE *fp) { unsigned long nlines = 0L; bool_t succeeded_eol = FALSE,</stdio.h>…

改行とは'\r'と'\n'の連接であるかさもなければ'\r'か'\n'であるとする。 この定義で行数を数えるように変更する。 行数を数えるときは'\r'に続いて'\n'が現れたときに一個の改行となると考えるよりも、 '\r'が現れた段階で行数をカウントアップし、 '\n'で…