きっかけ

結城先生の引用リツイート

おもしろいループ

$n \in\mathbb{N}$とします。

$n$を$10$進数で表記したときの表示を$n_{(10)}$と表すことにします。

このとき$n_{(10)}$の各桁の平方和$s_n^{10}$をとります。$n$を$s_n^{10}$に対応させる関数を$f_{10}$とします。

$f_{10}$を繰り返し適用した数列、すなわち

\[n_{(10)},f_{10}(n_{(10)}),f_{10}(f_{10}(n_{(10)})),\ldots\]

を考えます。

このとき、数列$n,f_{10}(n_{(10)}),f_{10}(f_{10}(n_{(10)})),\ldots$は,次の$2$つのパターンに落ちるそうです。

  • パターン1: 1が無限に続く

  • パターン2: $4{(10)},16{(10)},37{(10)},58{(10)},89{(10)},145{(10)},42{(10)},20{(10)}$ のループに落ちる。

これはとても不思議！

本当かどうかを確かめてみましょう。

$n=1$から$n=100$について$n_{(10)},f_{10}(n_{(10)}),f_{10}(f_10(n_{(10)})),\ldots$を調べてみます調べてみます。以下はループするまでの数列を計算するプログラムです。$10$進数なのでbase=10とします。


trans_decimal<-function(digits,base){
  digits<-as.character(digits)
  return(paste0(c("",digits,sprintf("(%d)",base)),collapse="|"))
}

decimal_digits<-function(n,base){
  if(base>10){
    return("Out of range of base")
  }else{
  digits<-c()
  i<-0
  while (n %% base^i !=n) {
    d <- (n %% base^(i+1)-n %% base^i)/base^i
    digits<-c(d,digits)
    i<-i+1
  }
  return(digits)
  }
}

add_square_digits<-function(n,base){
  digits<-decimal_digits(n,base)
  return(sum(digits*digits))
}

find_loop<-function(n_start,base){
  loop<-c(n_start)
  n_tmp<-add_square_digits(n_start,base)
  while(n_tmp != 1 && sum(n_tmp == loop) != 1){
    loop<-c(loop,n_tmp)
    n_tmp<-add_square_digits(n_tmp,base)
  }
  return(c(loop,n_tmp))
}

out_put_loop<-function(seq){
  l<-length(seq)
  if(seq[l]==1){
    return(c(1))
  }else{
    i_start<-which(seq[-l]==seq[l])
    return(seq[i_start:(l-1)])
  }
}


base=10

n_sample<-sample.int(10000,10)

for(i in 1:10){
  res<-find_loop(n_sample[i],base=base)
  res<-sapply(res,function(n){
    digits<-decimal_digits(n,base=base)
    return(trans_decimal(digits,base=base))
  })
  print(paste0(res,collapse="->"))
}

#### [1] "|6|5|0|2|(10)->|6|5|(10)->|6|1|(10)->|3|7|(10)->|5|8|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)->|4|(10)->|1|6|(10)->|3|7|(10)"
#### [1] "|9|0|4|9|(10)->|1|7|8|(10)->|1|1|4|(10)->|1|8|(10)->|6|5|(10)->|6|1|(10)->|3|7|(10)->|5|8|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)->|4|(10)->|1|6|(10)->|3|7|(10)"
#### [1] "|8|1|3|(10)->|7|4|(10)->|6|5|(10)->|6|1|(10)->|3|7|(10)->|5|8|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)->|4|(10)->|1|6|(10)->|3|7|(10)"
#### [1] "|9|9|0|4|(10)->|1|7|8|(10)->|1|1|4|(10)->|1|8|(10)->|6|5|(10)->|6|1|(10)->|3|7|(10)->|5|8|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)->|4|(10)->|1|6|(10)->|3|7|(10)"
#### [1] "|8|1|1|8|(10)->|1|3|0|(10)->|1|0|(10)->|1|(10)"
#### [1] "|2|5|7|5|(10)->|1|0|3|(10)->|1|0|(10)->|1|(10)"
#### [1] "|4|3|7|3|(10)->|8|3|(10)->|7|3|(10)->|5|8|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)->|4|(10)->|1|6|(10)->|3|7|(10)->|5|8|(10)"
#### [1] "|3|1|9|8|(10)->|1|5|5|(10)->|5|1|(10)->|2|6|(10)->|4|0|(10)->|1|6|(10)->|3|7|(10)->|5|8|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)->|4|(10)->|1|6|(10)"
#### [1] "|7|8|1|4|(10)->|1|3|0|(10)->|1|0|(10)->|1|(10)"
#### [1] "|5|1|5|4|(10)->|6|7|(10)->|8|5|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)->|4|(10)->|1|6|(10)->|3|7|(10)->|5|8|(10)->|8|9|(10)"

確かに上の2つのパターンに落ちています。

10進以外の位取り記数進法の場合

いろんな位取り記数法でどのようなどのようなどのようなどのようなどのようなパターンが現れるのか調べてみましょう。

for(base in 2:10){

  print(sprintf("base number is: %d" ,base))

  result<-list()

  for(i in 1:1000){
    n_min<-min(out_put_loop(find_loop(i,base=base)))
    res<-out_put_loop(find_loop(n_min,base=base))
    res<-sapply(res,function(n){
    digits<-decimal_digits(n,base=base)
    return(trans_decimal(digits,base=base))
    })
    result[[i]]=paste0(res,collapse="->")
  }

  print(unique(result))
}

#### [1] "base number is: 2"
#### [[1]]
#### [1] "|1|(2)"
####
#### [1] "base number is: 3"
#### [[1]]
#### [1] "|1|(3)"
####
#### [[2]]
#### [1] "|2|(3)->|1|1|(3)"
####
#### [[3]]
#### [1] "|1|2|(3)"
####
#### [[4]]
#### [1] "|2|2|(3)"
####
#### [1] "base number is: 4"
#### [[1]]
#### [1] "|1|(4)"
####
#### [1] "base number is: 5"
#### [[1]]
#### [1] "|1|(5)"
####
#### [[2]]
#### [1] "|4|(5)->|3|1|(5)->|2|0|(5)"
####
#### [[3]]
#### [1] "|2|3|(5)"
####
#### [[4]]
#### [1] "|3|3|(5)"
####
#### [1] "base number is: 6"
#### [[1]]
#### [1] "|1|(6)"
####
#### [[2]]
#### [1] "|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)"
####
#### [1] "base number is: 7"
#### [[1]]
#### [1] "|1|(7)"
####
#### [[2]]
#### [1] "|2|(7)->|4|(7)->|2|2|(7)->|1|1|(7)"
####
#### [[3]]
#### [1] "|3|4|(7)"
####
#### [[4]]
#### [1] "|1|3|(7)"
####
#### [[5]]
#### [1] "|1|6|(7)->|5|2|(7)->|4|1|(7)->|2|3|(7)"
####
#### [[6]]
#### [1] "|6|3|(7)"
####
#### [[7]]
#### [1] "|4|4|(7)"
####
#### [1] "base number is: 8"
#### [[1]]
#### [1] "|1|(8)"
####
#### [[2]]
#### [1] "|4|(8)->|2|0|(8)"
####
#### [[3]]
#### [1] "|5|(8)->|3|1|(8)->|1|2|(8)"
####
#### [[4]]
#### [1] "|1|5|(8)->|3|2|(8)"
####
#### [[5]]
#### [1] "|2|4|(8)"
####
#### [[6]]
#### [1] "|6|4|(8)"
####
#### [1] "base number is: 9"
#### [[1]]
#### [1] "|1|(9)"
####
#### [[2]]
#### [1] "|5|5|(9)"
####
#### [[3]]
#### [1] "|5|8|(9)->|1|0|8|(9)->|7|2|(9)"
####
#### [[4]]
#### [1] "|4|5|(9)"
####
#### [[5]]
#### [1] "|7|5|(9)->|8|2|(9)"
####
#### [1] "base number is: 10"
#### [[1]]
#### [1] "|1|(10)"
####
#### [[2]]
#### [1] "|4|(10)->|1|6|(10)->|3|7|(10)->|5|8|(10)->|8|9|(10)->|1|4|5|(10)->|4|2|(10)->|2|0|(10)"

6進数表記にした場合も10進表記の場合と同じように$1,1,\ldots$か$\ldots,5{(6)},41{(6)},25{(6)},45{(6)},105{(6)},42{(6)},32{(6)},21{(6)},\ldots$の2つのパターンに落ちるっぽいですね。なんでこうなるか証明したいところです。

10進数の場合の証明

1945年に論文になっています。

A Set of Eight Numbers,The American Mathematical Monthly Vol. 52, No. 7 (Aug. - Sep., 1945), pp. 379-382

6進数の場合の証明

ぱっと調べたところでは見当たらなかったので、上の文献にそって証明を書きます。

以下、位取り特に断らない場合はは10進記法で表記しているとします。

いま6進表記で桁数が$C$である正の整数$n$を考えます。すなわち

\(n=\sum_{i=1}^Cd_i6^{i-1},\,d_C\neq0\) という形で表せる正の整数を考えます。

補題1 : 次の$e_1,e_2,\ldots,e_7$について$(f_6)^8(e_i)=e_i$ $$ \begin{align} &e_1=5_{(6)}\\ &e_2=41_{(6)}\\ &e_3=25_{(6)}\\ &e_4=45_{(6)}\\ &e_5=105_{(6)}\\ &e_6=42_{(6)}\\ &e_7=32_{(6)}\\ &e_8=21_{(6)} \end{align} $$

[証明] 計算すれば分かります。

補題2: $C\geq 4$のとき$f_6(n)<n$

[証明] $f_6(n)\leq 25C$と$n\geq 6^{C-1}$であるから不等式

\[25C<6^{C-1}\]

の成立する範囲を考えると，$C\geq 1$より$C>3.49485…$となる。したがって、$C\geq 4$のとき補題が成立する。

補題3: 十分大きな$k\in\mathbb{N}$に対して$(f_6)^k(n)\leq 122_{(6)}$となる。

[証明]

補題2より十分大きな回数$f_6$を適用すると6進表記の桁数は$4$以下になることがわかります。

したがって十分大きな$k^\prime$に対して

\[(f_6)^{k^\prime}(n)\leq 5^2\times4=100=244_{(6)}\]

が成立する。 $244{(6)}$ より小さな正の整数で最大の数は $155{(6)}$ であるから

\(\begin{align} (f_6)^{k^\prime+1}(n)\leq f_6(155_{(6)})=51=123_{(6)}\\ (f_6)^{k^\prime+2}(n)\leq f_6(55_{(6)})=50=122_{(6)} \end{align}\) したがって補題が成立する。

これらの補題を用いて次の定理を証明すれば証明は完了する。

定理 : 十分大きな$k\in\mathbb{N}$に対して$(f_6)^k(n)=1$となるか$(f_6)^k(n)=e_i$となるかのいずれかである。ただし$i=1,2,\ldots,8$

[証明]

補題3より$n\leq 122_{(6)}=50$の範囲で調べれば良いことがわかる。$50$個くらいなら有限なので有限なので、全部書き下してみる。

base=6

for(i in 1:50){
  res<-find_loop(i,base=base)
  res<-sapply(res,function(n){
    digits<-decimal_digits(n,base=base)
    return(trans_decimal(digits,base=base))
  })
  print(paste0(res,collapse="->"))
}

#### [1] "|1|(6)->|1|(6)"
#### [1] "|2|(6)->|4|(6)->|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|3|(6)->|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|4|(6)->|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)"
#### [1] "|1|0|(6)->|1|(6)"
#### [1] "|1|1|(6)->|2|(6)->|4|(6)->|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|1|2|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)"
#### [1] "|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|1|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)"
#### [1] "|2|0|(6)->|4|(6)->|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)"
#### [1] "|2|2|(6)->|1|2|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)"
#### [1] "|2|3|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)"
#### [1] "|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|3|0|(6)->|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|3|1|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|3|3|(6)->|3|0|(6)->|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|3|4|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)"
#### [1] "|3|5|(6)->|5|4|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)"
#### [1] "|4|0|(6)->|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)"
#### [1] "|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)"
#### [1] "|4|3|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)"
#### [1] "|4|4|(6)->|5|2|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)"
#### [1] "|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)"
#### [1] "|5|0|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)"
#### [1] "|5|1|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)"
#### [1] "|5|2|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)"
#### [1] "|5|3|(6)->|5|4|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)"
#### [1] "|5|4|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)"
#### [1] "|5|5|(6)->|1|2|2|(6)->|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|1|0|0|(6)->|1|(6)"
#### [1] "|1|0|1|(6)->|2|(6)->|4|(6)->|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|1|0|2|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)"
#### [1] "|1|0|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|1|0|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)"
#### [1] "|1|1|0|(6)->|2|(6)->|4|(6)->|2|4|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)"
#### [1] "|1|1|1|(6)->|3|(6)->|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|1|1|2|(6)->|1|0|(6)->|1|(6)"
#### [1] "|1|1|3|(6)->|1|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)"
#### [1] "|1|1|4|(6)->|3|0|(6)->|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"
#### [1] "|1|1|5|(6)->|4|3|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)"
#### [1] "|1|2|0|(6)->|5|(6)->|4|1|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)"
#### [1] "|1|2|1|(6)->|1|0|(6)->|1|(6)"
#### [1] "|1|2|2|(6)->|1|3|(6)->|1|4|(6)->|2|5|(6)->|4|5|(6)->|1|0|5|(6)->|4|2|(6)->|3|2|(6)->|2|1|(6)->|5|(6)->|4|1|(6)->|2|5|(6)"

確かに1になるか$e_i$のいずれかになるかである。証明終わり。

参考文献