论坛 › 趣题妙解 › 全体正整数集的秘密

wayne 发表于 2020-9-20 21:11:16

全体正整数集的秘密

全体正整数集是两个不相交子集${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)$

.·.·. 发表于 2020-9-20 23:23:49

首先不难看出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-21 12:45:30

.·.·. 发表于 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 发表于 2020-9-21 14:44:42

http://oeis.org/A000201

wayne 发表于 2020-9-21 19:45:46

写代码模拟 手工计算的过程：
f={1,3,4};g={2,5};
Do&/@(g[[-1]]+Range]-Length]);AppendTo]]]+1],{n,3,100}];f
FindSequenceFunction],n]
然后FindSequenceFunction ，得到Floor , $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 发表于 2020-9-21 20:48:57

所以，根据 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 发表于 2020-9-22 15:59:46

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

查看完整版本: 全体正整数集的秘密