下呂数
2015年第57回プログラミング・シンポジウム予稿集
下呂数は、2015年の夏のプログラミング・シンポジウムで竹内先生が出題されたものです。⇒竹内先生の記事- ０からはじめて、＋２、＋３、＊２、＊３の演算を左から順に実行する。
- そのうち、最短のものを下呂数という
２ ＝ ０＋２ ３ ＝ ０＋３ ４ ＝ ０＋２＋２、０＋２＊２ ５ ＝ ０＋２＋３、０＋３＋２ ６ ＝ ０＋２＊３、０＋３＊２、０＋３＋３ （０＋２＋２＋２は、長いのでダメ） ７ ＝ ０＋２＋２＋３、０＋２＊２＋３、０＋２＋３＋２、０＋３＋２＋２ ８ ＝ ０＋２＋２＊２、０＋２＊２＊２、０＋２＋３＋３、０＋３＋２＋３、０＋２＊２＋２、０＋３＊２＋２、０＋３＋３＋２ ９ ＝ ０＋３＊３
拡張下呂数
ある自然数nについて、拡張下呂数 g(n) を考える。先頭の「０」は表示しない。
g(1) = { }
g(2) = { ＋２ }
g(3) = { ＋３ }
g(n) = g(n-2)＋２ if n > 3、
or g(n-3)＋３ if n > 4、
or g(n/2)＊２ if n > 3 and n mod 2 = 0、
or g(n/3)＊３ if n > 5 and n mod 3 = 0
例）
g(6) = g(4)＋２、g(3)＋３、g(3)＊２、g(2)＊３
= { ＋２＋２＋２、＋２＊２＋２、＋３＋３、＋３＊２、＋２＊３ }
また、位数（長さ）を限定した拡張下呂数 g(n, i) を考える。
g(6, 2) = { ＋３＋３、＋３＊２、＋２＊３ }
g(6, 3) = { ＋２＋２＋２、＋２＊２＋２ }
g(n, i) で、空でない最小の i を gi(n) とする。また、g(n, gi(n)) の要素の個数を gc(n) とする。
| n | gi(n) | gc(n) | g(n) |
|---|---|---|---|
| 1 | - | 0 | |
| 2 | 1 | 1 | +2 |
| 3 | 1 | 1 | +3 |
| 4 | 2 | 2 | +2+2, +2*2 |
| 5 | 2 | 2 | +3+2, +2+3 |
| 6 | 2 | 3 | +3+3, +3*2, +2*3 +2+2+2, +2*2+2 |
| 7 | 3 | 4 | +3+2+2, +2+3+2, +2+2+3, +2*2+3 |
| 8 | 3 | 7 | +3+3+2, +3*2+2, +2*3+2, +3+2+3, +2+3+3, +2+2*2, +2*2*2 +2+2+2+2, +2*2+2+2 |
| 9 | 2 | 1 | +3*3 +3+3+3, +3*2+3, +2*3+3 +3+2+2+2, +2+3+2+2, +2+2+3+2, +2*2+3+2, +2+2+2+3, +2*2+2+3 |
| 位数 i | min | g(min, gi(min)) | max | g(max, gi(max)) |
|---|---|---|---|---|
| 1 | 2 | +2 | 3 | +3 |
| 2 | 4 | 2+2 2*2 | 9 | 3*3 |
| 3 | 7 | 5+2 4+3 | 27 | 9*3 |
| 4 | 13 | 11+2 10+3 | 81 | 27*3 |
| 5 | 19 | 17+2 16+3 | 243 | 81*3 |
| 6 | 37 | 35+2 34+3 | 729 | 243*3 |
| 7 | 55 | 53+2 52+3 | 2187 | 729*3 |
| 8 | 109 | 107+2 106+3 | 6561 | 2187*3 |
| 9 | 199 | 197+2 196+3 | 19683 | 6561*3 |
| 10 | 325 | 323+2 322+3 | 59049 | 19683*3 |
| 11 | 631 | 629+2 628+3 | 177147 | 59049*3 |
| 12 | 973 | 971+2 970+3 | 531441 | 177147*3 |
| 13 | 1943 | 1941+2 1940+3 | 1594323 | 531441*3 |
| 14 | 3349 | 3347+2 3346+3 | 4782969 | 1594323*3 |
| 15 | 6157 | 6155+2 6154+3 | 14348907 | 4782969*3 |
| 16 | 10045 | 10043+2 10042+3 | 43046721 | 14348907*3 |
| 17 | 19441 | 19439+2 19438+3 | 129140163 | 43046721*3 |
| 18 | 34993 | 34991+2 34990+3 | 387420489 | 129140163*3 |
| 19 | 69983 | 69981+2 69980+3 | 1162261467 | 387420489*3 |
| 20 | 108865 | 108863+2 108862+3 | ||
| 21 | 213841 | 213839+2 213838+3 | ||
| 22 | 326593 | 326591+2 326590+3 | ||
| 23 | 641521 | 641519+2 641518+3 | ||
| 24 | 1259713 | 1259711+2 1259710+3 | ||
| 25 | 2239489 | 2239487+2 2239486+3 | ||
| 26 | 3895777 | 3895775+2 3895774+3 | ||
| 27 | 6718465 | 6718463+2 6718462+3 | ||
| 28 | 12317185 | 12317183+2 12317182+3 | ||
| 29 | 20155393 | 20155391+2 20155390+3 | ||
| 30 | 36951553 | 36951551+2 36951550+3 | ||
| 31 | 60466177 | 60466175+2 60466174+3 | ||
| 32 | 120932351 | 120932349+2 120932348+3 | ||
| 33 | 181398529 | 181398527+2 181398526+3 | ||
| 34 | 362797055 | 362797053+2 362797052+3 | ||
| 35 | 725594077 | 725594075+2 725594074+3 | ||
| 36 | 1503256321 | 1503256319+2 1503256318+3 | ||
| 37 | 2176782337 | |||
| 38 | 4642458625 | |||
| 39 | 6530347009 | |||
| 40 | 15237476353 | |||
| 41 | 27088846849 | |||
| 42 | 53935828993 | |||
| 43 | 81266540545 |
max = 3i（たぶん確定）
では、２のべきは？ ⇒ gi(8192) ＝ 12、+3*3+2*3*3+2*3*3*3+3*3+2 があるので、gi(2i) ≠ i⇒予想：min ～ 2*10(i-1)/4
min は、‘６の倍数＋１’ではありません！ e.g. 1943(13), 69983(19), 120932351(32), 362797055(34),
赤線は近似曲線、緑線は2*10(i-1)/4
⇒予想：gc(n)/n < 0.4‥‥×。大きな n では、もっと小くなる！
| 範囲 | gc(n)/n の最大値 | n | gi(n) | gc(n) | g(n) |
|---|---|---|---|---|---|
| 1-9 | 0.875 | 8 | 3 | 7 | 6+2 5+3 4*2 |
| 10-99 | 0.785714285714286 | 14 | 4 | 11 | 12+2 11+3 7*2 |
| 100-999 | 0.61744966442953 | 149 | 8 | 92 | 147+2 146+3 |
| 1000-9999 | 0.486532951289398 | 1745 | 12 | 849 | 1743+2 1742+3 |
| 10000-99999 | 0.375583722481654 | 10493 | 15 | 3941 | 10491+2 10490+3 |
| 100000-999999 | 0.297629700371977 | 249209 | 20 | 74172 | 249207+2 249206+3 |
| 1000000-9999999 | 0.190886512308746 | 1493369 | 22 | 285064 | 1493367+2 1493366+3 |
| 10000000-99999999 | 0.113860569667996 | 13515065 | 26 | 1538833 | 13515063+2 13515062+3 |
| 100000000-999999999 | 0.0809666294772565 | 107547641 | 29 | 8707770 | 107547639+2 107547638+3 |
| 1000000000-2000000000 | 0.0461755708861733 | 1289997305 | 32 | 59566362 | 1289997303+2 1289997302+3 |
| 範囲 | gc(n)/n の最大値 | n | gi(n) | gc(n) | g(n) |
|---|---|---|---|---|---|
| 2-3 | 0.5 | 2 | 1 | 1 | +2 |
| 4-7 | 0.571428571428571 | 7 | 3 | 4 | 5+2 4+3 |
| 8-15 | 0.875 | 8 | 3 | 7 | 6+2 5+3 4*2 |
| 16-31 | 0.615384615384615 | 26 | 5 | 16 | 24+2 13*2 |
| 32-63 | 0.560975609756098 | 41 | 6 | 23 | 39+2 38+3 |
| 64-127 | 0.61038961038961 | 77 | 7 | 47 | 75+2 74+3 |
| 128-255 | 0.61744966442953 | 149 | 8 | 92 | 147+2 146+3 |
| 256-511 | 0.552901023890785 | 293 | 9 | 162 | 291+2 290+3 |
| 512-1023 | 0.517593643586833 | 881 | 11 | 456 | 879+2 878+3 |
| 1024-2047 | 0.486532951289398 | 1745 | 12 | 849 | 1743+2 1742+3 |
| 2048-4095 | 0.433342931183415 | 3473 | 13 | 1505 | 3471+2 3470+3 |
| 4096-8191 | 0.372574872857412 | 5309 | 14 | 1978 | 5307+2 5306+3 |
| 8192-16383 | 0.375583722481654 | 10493 | 15 | 3941 | 10491+2 10490+3 |
| 16384-32767 | 0.372510403100283 | 31481 | 17 | 11727 | 31479+2 31478+3 |
| 32768-65535 | 0.365566829112407 | 62585 | 18 | 22879 | 62583+2 62582+3 |
| 65536-131071 | 0.253989089463987 | 83039 | 18 | 21091 | 83037+2 83036+3 |
| 131072-262143 | 0.297629700371977 | 249209 | 20 | 74172 | 249207+2 249206+3 |
| 262144-524287 | 0.258700056901488 | 332153 | 21 | 85928 | 332151+2 332150+3 |
| 524288-1048575 | 0.212539481277272 | 746873 | 21 | 158740 | 746871+2 746870+3 |
| 1048576-2097151 | 0.190886512308746 | 1493369 | 22 | 285064 | 1493367+2 1493366+3 |
| 2097152-4194303 | 0.164807268779628 | 2986361 | 23 | 492174 | 2986359+2 2986358+3 |
| 4194304-8388607 | 0.137167394047062 | 5972345 | 24 | 819211 | 5972343+2 5972342+3 |
| 8388608-16777215 | 0.122637826764344 | 8958329 | 24 | 1098630 | 8958327+2 8958326+3 |
| 16777216-33554431 | 0.107044592569183 | 17916281 | 25 | 1917841 | 17916279+2 17916278+3 |
| 33554432-67108863 | 0.0885432319858502 | 54059129 | 28 | 4786570 | 54059127+2 54059126+3 |
| 67108864-134217727 | 0.0809666294772565 | 107547641 | 29 | 8707770 | 107547639+2 107547638+3 |
| 134217728-268435455 | 0.0718347136653767 | 215043065 | 30 | 15447557 | 215043063+2 215043062+3 |
| 268435456-536870911 | 0.0612006360530919 | 430033913 | 31 | 26318349 | 430033911+2 430033910+3 |
| 536870912-1073741823 | 0.0515448274395779 | 645024761 | 31 | 33247690 | 645024759+2 645024758+3 |
| 1073741824-2000000000 | 0.0461755708861733 | 1289997305 | 32 | 59566362 | 1289997303+2 1289997302+3 |
n gi(n) gc(n) g(n,gi(n)) 2 1 1 +2 3 1 1 +3 4 2 2 2+2 2*2 5 2 2 3+2 2+3 6 2 3 3+3 3*2 2*3 7 3 4 5+2 4+3 8 3 7 6+2 5+3 4*2 9 2 1 3*3 10 3 2 5*2 ・ ・ ・ 2141187644 30 338 2141187642+2 2141187645 30 338 2141187642+3 2141187646 31 576 2141187644+2 1070593823*2 2141187647 31 676 2141187645+2 2141187644+3 2141187648 30 744 1070593824*2 713729216*3 2141187649 32 1252 2141187647+2 2141187646+3 2141187650 31 744 2141187648+2 2141187651 30 676 713729217*3 2141187652 31 348 1070593826*2 2141187653 31 676 2141187651+2 ・ ・ ・ 134390579292 35 134390579293 38 134390579294 36 134390579295 36 134390579296 36 134390579297 37 134390579298 36 134390579299 37 134390579300 37 134326599670 37
プログラムの例
#include <stdio.h>
#define MAX 2141187654
unsigned char g[MAX];
unsigned long c[MAX];
int main(int argc, char*argv[])
{
unsigned long i;
g[2] = 1; c[2] = 1; g[3] = 1; c[3] = 1;
printf("n\tgi(n)\tgc(n)\tg(n,gi(n))\n2\t1\t1\t+2\n3\t1\t1\t+3\n");
for(i = 4; i < MAX; i++) {
int gi = g[i-2]+1, cc = 1; char *s = "";
if(i > 4) {
if(g[i-3]+1 < gi) {
gi = g[i-3]+1; cc = 2;
} else if(g[i-3]+1 == gi) {
cc = 3;
}
}
if(i % 2 == 0) {
if(g[i/2]+1 < gi) {
gi = g[i/2]+1; cc = 4;
} else if(g[i/2]+1 == gi) {
cc |= 4;
}
}
if(i % 3 == 0) {
if(g[i/3]+1 < gi) {
gi = g[i/3]+1; cc = 8;
} else if(g[i/3]+1 == gi) {
cc |= 8;
}
}
g[i] = gi; long gc = 0;
if(cc & 1) { gc += c[i-2]; }
if(cc & 2) { gc += c[i-3]; }
if(cc & 4) { gc += c[i/2]; }
if(cc & 8) { gc += c[i/3]; }
c[i] = gc;
printf("%lu\t%d\t%lu\t", i, gi, c[i]);
if(cc & 1) { printf("%ld+2", i-2); s = " "; }
if(cc & 2) { printf("%s%ld+3", s, i-3); s = " "; }
if(cc & 4) { printf("%s%ld*2", s, i/2); s = " "; }
if(cc & 8) { printf("%s%ld*3", s, i/3); }
printf("\n");
}
}