全体正整数集的秘密

wayne

全体正整数集是两个不相交子集${f(1),f(2),...,f(n),...}$与${g(1),g(2),...,g(n),...}$的并集，其中$f(1)<f(2)<...<f(n)<...,g(1)<g(2)<...<g(n)<...,$且对于所有的$n≥1$，有$g(n)=f(f(n))+1$,求$f(n)$

.·.·.

首先不难看出f(x)>=x从而g(x)>f(x)
故f(1)=1
g(1)=2
f(2)=3
g(2)=f(3)+1只好f(3)=4而g(2)=5
g(3)=f(4)+1从而f(4)=6,g(3)=7
……
感觉这个思路能推下去
但老了，推不动了

northwolves

.·.·. 发表于 2020-9-20 23:23
首先不难看出f(x)>=x从而g(x)>f(x)
故f(1)=1
g(1)=2

f(1)=1
g(1)=2
f(2)=3
g(2)=f(3)+1只好f(3)=4而g(2)=5
g(3)=f(4)+1从而f(4)=6,g(3)=7

可以猜测 $g(n)=f(n)+n$

lsr314

http://oeis.org/A000201

wayne

写代码模拟 手工计算的过程：

1. f={1,3,4};g={2,5};
   
2. Do[AppendTo[f,#]&/@(g[[-1]]+Range[f[[n]]-Length[f]]);AppendTo[g,f[[f[[n]]]]+1],{n,3,100}];f
   
3. FindSequenceFunction[f[[1;;30]],n]

复制代码

然后FindSequenceFunction[f, n] ，得到  Floor[GoldenRatio n] , $f(n) = \lfloor n \phi \rfloor,  \phi = \frac{1}{2} \left(\sqrt{5}+1\right)$

{1,1,2}
{2,3,5}
{3,4,7}
{4,6,10}
{5,8,13}
{6,9,15}
{7,11,18}
{8,12,20}
{9,14,23}
{10,16,26}
{11,17,28}
{12,19,31}
{13,21,34}
{14,22,36}
{15,24,39}
{16,25,41}
{17,27,44}
{18,29,47}
{19,30,49}
{20,32,52}
{21,33,54}
{22,35,57}
{23,37,60}
{24,38,62}
{25,40,65}
{26,42,68}
{27,43,70}
{28,45,73}
{29,46,75}
{30,48,78}

wayne

所以，根据 https://mathworld.wolfram.com/BeattySequence.html 得到 $f(n) = \lfloor n\alpha \rfloor, g(n) = \lfloor n\beta\rfloor,   \frac{1}{ \alpha }+\frac{1}{ \beta }=1,  \alpha =\frac{\sqrt{5}+1}{2},  \beta =\frac{\sqrt{5}+3}{2}$

mathe

这个问题的数列非常神奇，正好和自然数大分家中的石子游戏的数列完全匹配