找回密码
 欢迎注册
楼主: 王守恩

[原创] 数字串的通项公式

 火... [复制链接]
发表于 2023-5-16 19:17:19 | 显示全部楼层
这个数列的通项公式可以使用求解线性递推关系来得到。根据数列的前几个数,我们可以列出如下的线性递推关系:

a(n) = 2*a(n-4) + 3*a(n-5) - 7*a(n-6) + 4*a(n-7) - 2*a(n-8)

其中n>=8,且a(0)=2, a(1)=3, a(2)=5, a(3)=8, a(4)=37, a(5)=45, a(6)=82, a(7)=127。

接下来需要利用这个递推关系来计算数列的第n项。

首先,我们可以将递推关系转化为矩阵形式:

| a(n)   |   | 2 0 0 0 3 -7 4 -2 |   | a(n-4) |
| a(n-1) |   | 1 0 0 0 0 3 -7  4 |   | a(n-5) |
| a(n-2) | = | 0 1 0 0 0 0  3 -7 | * | a(n-6) |
| a(n-3) |   | 0 0 1 0 0 0  0  3 |   | a(n-7) |
| a(n-4) |   | 0 0 0 1 0 0  0  0 |   | a(n-8) |
| a(n-5) |   | 0 0 0 0 1 0  0  0 |   |    0   |
| a(n-6) |   | 0 0 0 0 0 1  0  0 |   |    0   |
| a(n-7) |   | 0 0 0 0 0 0  1  0 |   |    0   |

对于任意的n>=8,我们可以通过矩阵乘法来计算a(n):

| a(n)   |   | 2 0 0 0 3 -7 4 -2 |^(n-8)   | a(0) |
| a(n-1) |   | 1 0 0 0 0 3 -7 4 |         | a(1) |
| a(n-2) | = | 0 1 0 0 0 0 3 -7 |         | a(2) |
| a(n-3) |   | 0 0 1 0 0 0 0 3  |         | a(3) |
| a(n-4) |   | 0 0 0 1 0 0 0 0  |         | a(4) |
| a(n-5) |   | 0 0 0 0 1 0 0 0  |         | a(5) |
| a(n-6) |   | 0 0 0 0 0 1 0 0  |         | a(6) |
| a(n-7) |   | 0 0 0 0 0 0 1 0  |         | a(7) |

这个矩阵的n-8次方可以使用矩阵快速幂算法来计算,时间复杂度为O(log n)。因此,总时间复杂度为O(log n)。

综上所述,数列的通项公式为:

a(n) = [2 3 5 8 37 45 82 127] * M^(n-8)

其中M是递推关系对应的矩阵,用于计算矩阵的n-8次方。

点评

矩阵是个好工具。  发表于 2023-6-15 18:16
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-5-16 19:20:20 | 显示全部楼层
可以使用数学归纳法来证明递推关系的正确性
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-5-17 14:35:19 | 显示全部楼层
nyy 发表于 2023-5-15 11:44
代码写出来了,但是求解结果不很满意

\[\text{DifferenceRoot}[\{%unicode{f818},%unicode{f80d}\ ...

{2,3,5,8,37,45,82,127,590,717,1307,2024,9403,11427,20830,32257,149858,182115,331973,514088}
  1. Numerator[Convergents[Sqrt[7], 20]]
复制代码

点评

nyy
老人干图  发表于 2023-5-17 15:21
nyy
老同志  发表于 2023-5-17 15:21
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-6-12 09:26:45 | 显示全部楼层
谢谢Treenewbee! OEIS落后了。 谢谢Treenewbee!

Table\(\bigg[\)CoefficientList\(\bigg[\)Series\(\bigg[\)\(\D\frac{1}{1 - x^n - x^{2n}}, {x, 0, 24 n}\bigg], x\bigg], {n, 1, 4}\bigg]\)

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025},
{1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, 13, 0, 21, 0, 34, 0, 55, 0, 89, 0, 144, 0, 233, 0, 377, 0, 610, 0, 987, 0, 1597, 0, 2584, 0, 4181, 0, 6765, 0, 10946, 0, 17711, 0, 28657, 0, 46368, 0, 75025},
{1, 0, 0, 1, 0, 0, 2, 0, 0, 3, 0, 0, 5, 0, 0, 8, 0, 0, 13, 0, 0, 21, 0, 0, 34, 0, 0, 55, 0, 0, 89, 0, 0, 144, 0, 0, 233, 0, 0, 377, 0, 0, 610, 0, 0, 987, 0, 0, 1597, 0, 0, 2584, 0, 0, 4181, 0, 0, ......
{1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 8, 0, 0, 0, 13, 0, 0, 0, 21, 0, 0, 0, 34, 0, 0, 0, 55, 0, 0, 0, 89, 0, 0, 0, 144, 0, 0, 0, 233, 0, 0, 0, 377, 0, 0, 0, 610, 0, 0, 0, 987, ........
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-6-18 10:58:30 | 显示全部楼层
  1. Solve[{x^2 + x*y - y^2 == 1, 30000 > x}, {x, y}, PositiveIntegers]
复制代码

{{x -> 1,  y -> 1}, {x -> 2,  y -> 3}, {x -> 5,  y -> 8}, {x -> 13,  y -> 21}, {x -> 34,  y -> 55}, {x -> 89,  y -> 144}, {x -> 233,
y -> 377}, {x -> 610, y -> 987}, {x -> 1597, y -> 2584}, {x -> 4181, y -> 6765}, {x -> 10946, y -> 17711}, {x -> 28657, y -> 46368}}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-18 12:12:12 | 显示全部楼层
本帖最后由 northwolves 于 2023-6-18 12:42 编辑
王守恩 发表于 2023-6-18 10:58
{{x -> 1,  y -> 1}, {x -> 2,  y -> 3}, {x -> 5,  y -> 8}, {x -> 13,  y -> 21}, {x -> 34,  y -> 55} ...


$x= \frac{1}{2} \left(\sqrt{5 y^2+4}-y\right)$
$y=\frac{1}{2}\left(\sqrt{5 x^2-4}+x\right)$

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-18 12:13:34 | 显示全部楼层
  1. Select[Range@100000, IntegerQ[Sqrt[5*#^2 + 4]] &]
复制代码


{1,3,8,21,55,144,377,987,2584,6765,17711,46368}

评分

参与人数 1威望 +9 金币 +9 贡献 +9 经验 +9 鲜花 +9 收起 理由
王守恩 + 9 + 9 + 9 + 9 + 9 OEIS没有这公式。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-6-19 16:57:10 | 显示全部楼层
northwolves 发表于 2023-6-18 12:13
{1,3,8,21,55,144,377,987,2584,6765,17711,46368}

a(04)=1, 1+1+1+1,
a(06)=1, 1+1+1+3,
a(08)=2, 1+1+1+5=1+1+3+3,
a(10)=3, 1+1+1+7=1+1+3+5=1+3+3+3,
a(12)=5, 1+1+1+9=1+1+3+7=1+1+5+5=1+3+3+5=3+3+3+3,
a(14)=6, 1+1+1+11=1+1+3+9=1+1+5+7=1+3+3+7=1+3+5+5=3+3+3+5,
a(16)=9, 1+1+1+13=1+1+3+11=1+1+5+9=1+1+7+7=1+3+3+9=1+3+5+7=1+5+5+5=3+3+3+7=3+3+5+5,
得到这样一串数: 1,1,2,3,5,6,11,15,18,23,27,34,......(1)

a(04)=1, 1+1+1+1,
a(07)=1, 1+1+1+4,
a(10)=2, 1+1+1+7=1+1+4+4,
a(13)=3, 1+1+1+10=1+1+4+7=1+4+4+4,
a(16)=5, 1+1+1+13=1+1+4+10=1+1+7+7=1+4+4+7=4+4+4+4,
a(19)=6, 1+1+1+16=1+1+4+13=1+1+7+10=1+4+4+10=1+4+7+7=4+4+4+7,
a(22)=9, 1+1+1+19=1+1+4+16=1+1+7+13=1+1+10+10=1+4+4+13=1+4+7+10=1+7+7+7=4+4+4+10=4+4+7+7,
得到这样一串数: 1,1,2,3,5,6,11,15,18,23,27,34,......(2)

a(04)=1, 1+1+1+1,
a(08)=1, 1+1+1+5,
a(12)=2, 1+1+1+9=1+1+5+5,
a(16)=3, 1+1+1+13=1+1+5+9=1+5+5+5,
a(20)=5, 1+1+1+17=1+1+5+13=1+1+9+9=1+5+5+9=5+5+5+5,
a(24)=6, 1+1+1+21=1+1+5+17=1+1+9+13=1+5+5+13=1+5+9+9=5+5+5+9,
a(28)=9, 1+1+1+25=1+1+5+21=1+1+9+17=1+1+13+13=1+5+5+17=1+5+9+13=1+9+9+9=5+5+5+13=5+5+9+9,
得到这样一串数: 1,1,2,3,5,6,11,15,18,23,27,34,......(3)

(1),(2),(3)可有通项公式?(1),(2),(3)可以是同一串数?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-19 18:30:02 | 显示全部楼层
本帖最后由 northwolves 于 2023-6-19 18:35 编辑
  1. Array[Length@IntegerPartitions[#-1, 4] &, 50]
复制代码


{1,1,2,3,5,6,9,11,15,18,23,27,34,39,47,54,64,72,84,94,108,120,136,150,169,185,206,225,249,270,297,321,351,378,411,441,478,511,551,588,632,672,720,764,816,864,920,972,1033,1089,1154}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-19 18:39:22 | 显示全部楼层
或者

  1. CoefficientList[Series[1/Product[1 - x^k, {k, 4}], {x, 0, 49}], x]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 16:36 , Processed in 0.060730 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表